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.acyclic_orientations(G)[source]#

Return an iterator over all acyclic orientations of an undirected graph \(G\).

ALGORITHM:

The algorithm is based on [Sq1998]. It presents an efficient algorithm for listing the acyclic orientations of a graph. The algorithm is shown to require O(n) time per acyclic orientation generated, making it the most efficient known algorithm for generating acyclic orientations.

The function uses a recursive approach to generate acyclic orientations of the graph. It reorders the vertices and edges of the graph, creating a new graph with updated labels. Then, it iteratively generates acyclic orientations by considering subsets of edges and checking whether they form upsets in a corresponding poset.

INPUT:

  • G – an undirected graph.

OUTPUT:

  • An iterator over all acyclic orientations of the input graph.

Note

The function assumes that the input graph is undirected and the edges are unlabelled.

EXAMPLES:

To count number acyclic orientations for a graph:

sage: g = Graph([(0, 3), (0, 4), (3, 4), (1, 3), (1, 2), (2, 3), (2, 4)])
sage: it = g.acyclic_orientations()
sage: len(list(it))
54

>>> from sage.all import *
>>> g = Graph([(Integer(0), Integer(3)), (Integer(0), Integer(4)), (Integer(3), Integer(4)), (Integer(1), Integer(3)), (Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(2), Integer(4))])
>>> it = g.acyclic_orientations()
>>> len(list(it))
54

Test for arbitary vertex labels:

sage: g_str = Graph([('abc', 'def'), ('ghi', 'def'), ('xyz', 'abc'), ('xyz', 'uvw'), ('uvw', 'abc'), ('uvw', 'ghi')])
sage: it = g_str.acyclic_orientations()
sage: len(list(it))
42

>>> from sage.all import *
>>> g_str = Graph([('abc', 'def'), ('ghi', 'def'), ('xyz', 'abc'), ('xyz', 'uvw'), ('uvw', 'abc'), ('uvw', 'ghi')])
>>> it = g_str.acyclic_orientations()
>>> len(list(it))
42
sage.graphs.orientations.random_orientation(G)[source]#

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)

>>> from sage.all import *
>>> from sage.graphs.orientations import random_orientation
>>> G = graphs.PetersenGraph()
>>> D = random_orientation(G)
>>> D.order() == G.order(), D.size() == G.size()
(True, True)

See also

sage.graphs.orientations.strong_orientations_iterator(G)[source]#

Return 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). According to Robbins’ theorem (see the Wikipedia article Robbins_theorem), the graphs that have strong orientations are exactly the 2-edge-connected graphs (i.e., the bridgeless graphs).

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.

See also

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

>>> from sage.all import *
>>> g = graphs.CycleGraph(Integer(4))
>>> it = g.strong_orientations_iterator()
>>> len(list(it))
1

A tree cannot be strongly oriented:

sage: g = graphs.RandomTree(10)
sage: len(list(g.strong_orientations_iterator()))
0

>>> from sage.all import *
>>> g = graphs.RandomTree(Integer(10))
>>> 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

>>> from sage.all import *
>>> g = graphs.CompleteGraph(Integer(6))
>>> g.add_vertex(Integer(7))
>>> len(list(g.strong_orientations_iterator()))
0