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 (2017-01-10) – 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 non-tree 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 non-tree 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 (non-symmetric) 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