![]() | 1 | initial version |
The lasiest way is hacking an existing method: you can just mimic the code of the to_directed
and add a loop iterating over subsets of (possibly labeled, possibly multiple,...) edges as follows (note that you can see the code of to_directed
by typing G.to_directed??
for some graph G
).
The only differences will be:
give the orientation
name to the function
a loop over the orientations:
for orient in subsets(self.edges()):
an if then else
test to know whether we have to add one edge or the other
return D
is replaced with yield D
to make an iterator (instead of returning the first orientation found).
So, the code you might get is:
def orientations(self, implementation='c_graph', data_structure=None,
sparse=None):
"""
Iterates over all orientations of self.
INPUT:
- ``data_structure`` -- one of ``"sparse"``, ``"static_sparse"``, or
``"dense"``. See the documentation of :class:`Graph` or
:class:`DiGraph`.
- ``sparse`` (boolean) -- ``sparse=True`` is an alias for
``data_structure="sparse"``, and ``sparse=False`` is an alias for
``data_structure="dense"``.
"""
if sparse is not None:
if data_structure is not None:
raise ValueError("The 'sparse' argument is an alias for "
"'data_structure'. Please do not define both.")
data_structure = "sparse" if sparse else "dense"
if data_structure is None:
from sage.graphs.base.dense_graph import DenseGraphBackend
from sage.graphs.base.sparse_graph import SparseGraphBackend
if isinstance(self._backend, DenseGraphBackend):
data_structure = "dense"
elif isinstance(self._backend, SparseGraphBackend):
data_structure = "sparse"
else:
data_structure = "static_sparse"
from sage.graphs.all import DiGraph
for orient in subsets(self.edges()):
D = DiGraph(name = self.name(),
pos = self._pos,
multiedges = self.allows_multiple_edges(),
loops = self.allows_loops(),
implementation = implementation,
data_structure = (data_structure if data_structure!="static_sparse"
else "sparse")) # we need a mutable copy
D.add_vertices(self.vertex_iterator())
for u,v,l in self.edge_iterator():
if (u,v,l) in orient:
D.add_edge(u,v,l)
else:
D.add_edge(v,u,l)
if hasattr(self, '_embedding'):
D._embedding = copy(self._embedding)
D._weighted = self._weighted
if data_structure == "static_sparse":
D = D.copy(data_structure=data_structure)
yield D
You can test it on a small example to see if it satisfies your need:
sage: G = graphs.CycleGraph(3)
sage: G.plot()
sage: for i in orientations(G):
....: i.plot()
It should also work for multiedges graphs, you can decide which implementation/data structure you want for the oriented graphs, the sparsity, etc.
![]() | 2 | No.2 Revision |
The lasiest way is hacking an existing method: you can just mimic the code of the to_directed
and add a loop iterating over subsets of (possibly labeled, possibly multiple,...) edges as follows (note that you can see the code of to_directed
by typing G.to_directed??
for some graph G
).
The only differences will be:
give the orientation
name to the function
a loop over the orientations:
for orient in subsets(self.edges()):
an if then else
test to know whether we have to add one edge or the other
return D
is replaced with yield D
to make an iterator (instead of returning the first orientation found).
So, the code you might get is:
def orientations(self, implementation='c_graph', data_structure=None,
sparse=None):
"""
Iterates over all orientations of self.
INPUT:
- ``data_structure`` -- one of ``"sparse"``, ``"static_sparse"``, or
``"dense"``. See the documentation of :class:`Graph` or
:class:`DiGraph`.
- ``sparse`` (boolean) -- ``sparse=True`` is an alias for
``data_structure="sparse"``, and ``sparse=False`` is an alias for
``data_structure="dense"``.
"""
if sparse is not None:
if data_structure is not None:
raise ValueError("The 'sparse' argument is an alias for "
"'data_structure'. Please do not define both.")
data_structure = "sparse" if sparse else "dense"
if data_structure is None:
from sage.graphs.base.dense_graph import DenseGraphBackend
from sage.graphs.base.sparse_graph import SparseGraphBackend
if isinstance(self._backend, DenseGraphBackend):
data_structure = "dense"
elif isinstance(self._backend, SparseGraphBackend):
data_structure = "sparse"
else:
data_structure = "static_sparse"
from sage.graphs.all import DiGraph
for orient in subsets(self.edges()):
D = DiGraph(name = self.name(),
pos = self._pos,
multiedges = self.allows_multiple_edges(),
loops = self.allows_loops(),
implementation = implementation,
data_structure = (data_structure if data_structure!="static_sparse"
else "sparse")) # we need a mutable copy
D.add_vertices(self.vertex_iterator())
for u,v,l in self.edge_iterator():
if (u,v,l) in orient:
D.add_edge(u,v,l)
else:
D.add_edge(v,u,l)
if hasattr(self, '_embedding'):
D._embedding = copy(self._embedding)
D._weighted = self._weighted
if data_structure == "static_sparse":
D = D.copy(data_structure=data_structure)
yield D
You can test it on a small example to see if it satisfies your need:
sage: G = graphs.CycleGraph(3)
sage: G.plot()
sage: for i in orientations(G):
....: i.plot()
It should also work for multiedges graphs, you can decide which implementation/data structure you want for the oriented graphs, the sparsity, to keep the embedding, etc.
EDIT see also trac ticket 21415.