# How to get an arbitrary orientation of a graph.

I want to know how to get the iterator of all orientations of a given graph G.

There is another question in the same title, unfortunately that question has irrelevant title. https://ask.sagemath.org/question/983...

edit retag close merge delete

Sort by » oldest newest most voted

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
for u,v,l in self.edge_iterator():
if (u,v,l) in orient:
else:
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.

more