Orientations¶
This module implements several methods to compute orientations of undirected graphs subject to specific constraints (e.g., acyclic, strongly connected, etc.). It also implements some iterators over all these orientations.
This module contains the following methods
strong_orientations_iterator() 
Return an iterator over all strong orientations of a graph \(G\) 
random_orientation() 
Return a random orientation of a graph \(G\) 
Authors¶
 Kolja Knauer, Petru Valicov (20170110) – initial version
Methods¶

sage.graphs.orientations.
random_orientation
(G)¶ Return a random orientation of a graph \(G\).
An orientation of an undirected graph is a directed graph such that every edge is assigned a direction. Hence there are \(2^m\) oriented digraphs for a simple graph with \(m\) edges.
INPUT:
G
– a Graph.
EXAMPLES:
sage: from sage.graphs.orientations import random_orientation sage: G = graphs.PetersenGraph() sage: D = random_orientation(G) sage: D.order() == G.order(), D.size() == G.size() (True, True)
See also

sage.graphs.orientations.
strong_orientations_iterator
(G)¶ Returns an iterator over all strong orientations of a graph \(G\).
A strong orientation of a graph is an orientation of its edges such that the obtained digraph is strongly connected (i.e. there exist a directed path between each pair of vertices).
ALGORITHM:
It is an adaptation of the algorithm published in [CGMRV16]. It runs in \(O(mn)\) amortized time, where \(m\) is the number of edges and \(n\) is the number of vertices. The amortized time can be improved to \(O(m)\) with a more involved method. In this function, first the graph is preprocessed and a spanning tree is generated. Then every orientation of the nontree edges of the graph can be extended to at least one new strong orientation by orienting properly the edges of the spanning tree (this property is proved in [CGMRV16]). Therefore, this function generates all partial orientations of the nontree edges and then launches a helper function corresponding to the generation algorithm described in [CGMRV16]. In order to avoid trivial symmetries, the orientation of an arbitrary edge is fixed before the start of the enumeration process.
INPUT:
G
– an undirected graph.
OUTPUT:
 an iterator which will produce all strong orientations of this graph.
Note
Works only for simple graphs (no multiple edges). To avoid symmetries an orientation of an arbitrary edge is fixed.
EXAMPLES:
A cycle has one possible (nonsymmetric) strong orientation:
sage: g = graphs.CycleGraph(4) sage: it = g.strong_orientations_iterator() sage: len(list(it)) 1
A tree cannot be strongly oriented:
sage: g = graphs.RandomTree(100) sage: len(list(g.strong_orientations_iterator())) 0
Neither can be a disconnected graph:
sage: g = graphs.CompleteGraph(6) sage: g.add_vertex(7) sage: len(list(g.strong_orientations_iterator())) 0