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

`orient()`	Return an oriented version of \(G\) according the input function \(f\).
`orientations()`	Return an iterator over orientations of \(G\).
`acyclic_orientations()`	Return an iterator over all acyclic orientations of an undirected graph \(G\).
`strong_orientation()`	Return a strongly connected orientation of the graph \(G\).
`strong_orientations_iterator()`	Return an iterator over all strong orientations of a graph \(G\)
`random_orientation()`	Return a random orientation of a graph \(G\)
`minimum_outdegree_orientation()`	Return an orientation of \(G\) with the smallest possible maximum outdegree.
`bounded_outdegree_orientation()`	Return an orientation of \(G\) such that every vertex \(v\) has out-degree less than \(b(v)\).
`eulerian_orientation(G)()`	Return a DiGraph which is an Eulerian orientation of the 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 the number of acyclic orientations for a graph:

Sage

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

Python

>>> 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

Sage Live

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

Test for arbitrary vertex labels:

Sage

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

Python

>>> 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 Live

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

Check that the method returns properly relabeled acyclic digraphs:

Sage

sage: g = Graph([(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)])
sage: orientations = set([frozenset(d.edges(labels=false)) for d in g.acyclic_orientations()])
sage: len(orientations)
18
sage: all(d.is_directed_acyclic() for d in g.acyclic_orientations())
True

Python

>>> from sage.all import *
>>> g = Graph([(Integer(0), Integer(1)), (Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(3), Integer(0)), (Integer(0), Integer(2))])
>>> orientations = set([frozenset(d.edges(labels=false)) for d in g.acyclic_orientations()])
>>> len(orientations)
18
>>> all(d.is_directed_acyclic() for d in g.acyclic_orientations())
True

Sage Live

g = Graph([(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)])
orientations = set([frozenset(d.edges(labels=false)) for d in g.acyclic_orientations()])
len(orientations)
all(d.is_directed_acyclic() for d in g.acyclic_orientations())

sage.graphs.orientations.bounded_outdegree_orientation(G, bound, solver, verbose=None, integrality_tolerance=False)[source]¶

Return an orientation of \(G\) such that every vertex \(v\) has out-degree less than \(b(v)\).

INPUT:

G – an undirected graph
bound – maximum bound on the out-degree. Can be of three different types :
- An integer \(k\). In this case, computes an orientation whose maximum out-degree is less than \(k\).
- A dictionary associating to each vertex its associated maximum out-degree.
- A function associating to each vertex its associated maximum out-degree.
solver – string (default: None); specifies a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.
integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT:

A DiGraph representing the orientation if it exists. A ValueError exception is raised otherwise.

ALGORITHM:

The problem is solved through a maximum flow :

Given a graph \(G\), we create a DiGraph \(D\) defined on \(E(G)\cup V(G)\cup \{s,t\}\). We then link \(s\) to all of \(V(G)\) (these edges having a capacity equal to the bound associated to each element of \(V(G)\)), and all the elements of \(E(G)\) to \(t\) . We then link each \(v \in V(G)\) to each of its incident edges in \(G\). A maximum integer flow of value \(|E(G)|\) corresponds to an admissible orientation of \(G\). Otherwise, none exists.

EXAMPLES:

There is always an orientation of a graph \(G\) such that a vertex \(v\) has out-degree at most \(\lceil \frac {d(v)} 2 \rceil\):

Sage

sage: g = graphs.RandomGNP(40, .4)
sage: b = lambda v: integer_ceil(g.degree(v)/2)
sage: D = g.bounded_outdegree_orientation(b)
sage: all(D.out_degree(v) <= b(v) for v in g)
True

Python

>>> from sage.all import *
>>> g = graphs.RandomGNP(Integer(40), RealNumber('.4'))
>>> b = lambda v: integer_ceil(g.degree(v)/Integer(2))
>>> D = g.bounded_outdegree_orientation(b)
>>> all(D.out_degree(v) <= b(v) for v in g)
True

Sage Live

g = graphs.RandomGNP(40, .4)
b = lambda v: integer_ceil(g.degree(v)/2)
D = g.bounded_outdegree_orientation(b)
all(D.out_degree(v) <= b(v) for v in g)

Chvatal’s graph, being 4-regular, can be oriented in such a way that its maximum out-degree is 2:

Sage

sage: g = graphs.ChvatalGraph()
sage: D = g.bounded_outdegree_orientation(2)
sage: max(D.out_degree())
2

Python

>>> from sage.all import *
>>> g = graphs.ChvatalGraph()
>>> D = g.bounded_outdegree_orientation(Integer(2))
>>> max(D.out_degree())
2

Sage Live

g = graphs.ChvatalGraph()
D = g.bounded_outdegree_orientation(2)
max(D.out_degree())

For any graph \(G\), it is possible to compute an orientation such that the maximum out-degree is at most the maximum average degree of \(G\) divided by 2. Anything less, though, is impossible.

sage: g = graphs.RandomGNP(40, .4) sage: mad = g.maximum_average_degree() # needs sage.numerical.mip

Hence this is possible

Sage

sage: d = g.bounded_outdegree_orientation(integer_ceil(mad/2))              # needs sage.numerical.mip

Python

>>> from sage.all import *
>>> d = g.bounded_outdegree_orientation(integer_ceil(mad/Integer(2)))              # needs sage.numerical.mip

Sage Live

d = g.bounded_outdegree_orientation(integer_ceil(mad/2))              # needs sage.numerical.mip

While this is not:

Sage

sage: try:                                                                  # needs sage.numerical.mip
....:     g.bounded_outdegree_orientation(integer_ceil(mad/2-1))
....:     print("Error")
....: except ValueError:
....:     pass

Python

>>> from sage.all import *
>>> try:                                                                  # needs sage.numerical.mip
...     g.bounded_outdegree_orientation(integer_ceil(mad/Integer(2)-Integer(1)))
...     print("Error")
... except ValueError:
...     pass

Sage Live

try:                                                                  # needs sage.numerical.mip
    g.bounded_outdegree_orientation(integer_ceil(mad/2-1))
    print("Error")
except ValueError:
    pass

The bounds can be specified in different ways:

Sage

sage: g = graphs.PetersenGraph()
sage: b = lambda v: integer_ceil(g.degree(v)/2)
sage: D = g.bounded_outdegree_orientation(b)
sage: b_dict = {u: b(u) for u in g}
sage: D = g.bounded_outdegree_orientation(b_dict)
sage: unique_bound = 2
sage: D = g.bounded_outdegree_orientation(unique_bound)

Python

>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> b = lambda v: integer_ceil(g.degree(v)/Integer(2))
>>> D = g.bounded_outdegree_orientation(b)
>>> b_dict = {u: b(u) for u in g}
>>> D = g.bounded_outdegree_orientation(b_dict)
>>> unique_bound = Integer(2)
>>> D = g.bounded_outdegree_orientation(unique_bound)

Sage Live

g = graphs.PetersenGraph()
b = lambda v: integer_ceil(g.degree(v)/2)
D = g.bounded_outdegree_orientation(b)
b_dict = {u: b(u) for u in g}
D = g.bounded_outdegree_orientation(b_dict)
unique_bound = 2
D = g.bounded_outdegree_orientation(unique_bound)

sage.graphs.orientations.eulerian_orientation(G)[source]¶

Return a DiGraph which is an Eulerian orientation of the graph \(G\).

An Eulerian graph being a graph such that any vertex has an even degree, an Eulerian orientation of a graph is an orientation of its edges such that each vertex \(v\) verifies \(d^+(v)=d^-(v)=d(v)/2\), where \(d^+\) and \(d^-\) respectively represent the out-degree and the in-degree of a vertex.

If the graph is not Eulerian, the orientation verifies for any vertex \(v\) that \(| d^+(v)-d^-(v) | \leq 1\).

INPUT:

G – an undirected graph

ALGORITHM:

This algorithm is a random walk through the edges of the graph, which orients the edges according to the walk. When a vertex is reached which has no non-oriented edge (this vertex must have odd degree), the walk resumes at another vertex of odd degree, if any.

This algorithm has time complexity in \(O(n+m)\) for SparseGraph and \(O(n^2)\) for DenseGraph, where \(m\) is the number of edges in the graph and \(n\) is the number of vertices in the graph.

EXAMPLES:

The CubeGraph with parameter 4, which is regular of even degree, has an Eulerian orientation such that \(d^+ = d^-\):

Sage

sage: g = graphs.CubeGraph(4)
sage: g.degree()
[4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
sage: o = g.eulerian_orientation()
sage: o.in_degree()
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
sage: o.out_degree()
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

Python

>>> from sage.all import *
>>> g = graphs.CubeGraph(Integer(4))
>>> g.degree()
[4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
>>> o = g.eulerian_orientation()
>>> o.in_degree()
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
>>> o.out_degree()
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

Sage Live

g = graphs.CubeGraph(4)
g.degree()
o = g.eulerian_orientation()
o.in_degree()
o.out_degree()

Secondly, the Petersen Graph, which is 3 regular has an orientation such that the difference between \(d^+\) and \(d^-\) is at most 1:

Sage

sage: g = graphs.PetersenGraph()
sage: o = g.eulerian_orientation()
sage: o.in_degree()
[2, 2, 2, 2, 2, 1, 1, 1, 1, 1]
sage: o.out_degree()
[1, 1, 1, 1, 1, 2, 2, 2, 2, 2]

Python

>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> o = g.eulerian_orientation()
>>> o.in_degree()
[2, 2, 2, 2, 2, 1, 1, 1, 1, 1]
>>> o.out_degree()
[1, 1, 1, 1, 1, 2, 2, 2, 2, 2]

Sage Live

g = graphs.PetersenGraph()
o = g.eulerian_orientation()
o.in_degree()
o.out_degree()

sage.graphs.orientations.minimum_outdegree_orientation(G, use_edge_labels, solver=False, verbose=None, integrality_tolerance=0)[source]¶

Return an orientation of \(G\) with the smallest possible maximum outdegree.

Given a Graph \(G\), it is polynomial to compute an orientation \(D\) of the edges of \(G\) such that the maximum out-degree in \(D\) is minimized. This problem, though, is NP-complete in the weighted case [AMOZ2006].

INPUT:

G – an undirected graph
use_edge_labels – boolean (default: False)
- When set to True, uses edge labels as weights to compute the orientation and assumes a weight of \(1\) when there is no value available for a given edge.
- When set to False (default), gives a weight of 1 to all the edges.
solver – string (default: None); specifies a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.
integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

EXAMPLES:

Given a complete bipartite graph \(K_{n,m}\), the maximum out-degree of an optimal orientation is \(\left\lceil \frac {nm} {n+m}\right\rceil\):

Sage

sage: g = graphs.CompleteBipartiteGraph(3,4)
sage: o = g.minimum_outdegree_orientation()                                     # needs sage.numerical.mip
sage: max(o.out_degree()) == integer_ceil((4*3)/(3+4))                          # needs sage.numerical.mip
True

Python

>>> from sage.all import *
>>> g = graphs.CompleteBipartiteGraph(Integer(3),Integer(4))
>>> o = g.minimum_outdegree_orientation()                                     # needs sage.numerical.mip
>>> max(o.out_degree()) == integer_ceil((Integer(4)*Integer(3))/(Integer(3)+Integer(4)))                          # needs sage.numerical.mip
True

Sage Live

g = graphs.CompleteBipartiteGraph(3,4)
o = g.minimum_outdegree_orientation()                                     # needs sage.numerical.mip
max(o.out_degree()) == integer_ceil((4*3)/(3+4))                          # needs sage.numerical.mip

Show the influence of edge labels on the solution:

Sage

sage: # needs sage.numerical.mip
sage: g = graphs.PetersenGraph()
sage: o = g.minimum_outdegree_orientation(use_edge_labels=False)
sage: max(o.out_degree())
2
sage: _ = [g.set_edge_label(u, v, 1) for u, v in g.edge_iterator(labels=False)]
sage: o = g.minimum_outdegree_orientation(use_edge_labels=True)
sage: max(o.out_degree())
2
sage: g.set_edge_label(0, 1, 100)
sage: o = g.minimum_outdegree_orientation(use_edge_labels=True)
sage: max(o.out_degree())
3

Python

>>> from sage.all import *
>>> # needs sage.numerical.mip
>>> g = graphs.PetersenGraph()
>>> o = g.minimum_outdegree_orientation(use_edge_labels=False)
>>> max(o.out_degree())
2
>>> _ = [g.set_edge_label(u, v, Integer(1)) for u, v in g.edge_iterator(labels=False)]
>>> o = g.minimum_outdegree_orientation(use_edge_labels=True)
>>> max(o.out_degree())
2
>>> g.set_edge_label(Integer(0), Integer(1), Integer(100))
>>> o = g.minimum_outdegree_orientation(use_edge_labels=True)
>>> max(o.out_degree())
3

Sage Live

# needs sage.numerical.mip
g = graphs.PetersenGraph()
o = g.minimum_outdegree_orientation(use_edge_labels=False)
max(o.out_degree())
_ = [g.set_edge_label(u, v, 1) for u, v in g.edge_iterator(labels=False)]
o = g.minimum_outdegree_orientation(use_edge_labels=True)
max(o.out_degree())
g.set_edge_label(0, 1, 100)
o = g.minimum_outdegree_orientation(use_edge_labels=True)
max(o.out_degree())

sage.graphs.orientations.orient(G, f, weighted=None, data_structure=None, sparse=None, immutable=None, hash_labels=None)[source]¶

Return an oriented version of \(G\) according the input function \(f\).

INPUT:

G – an undirected graph
f – a function that inputs an edge and outputs an orientation of this edge
weighted – boolean (default: None); weightedness for the oriented digraph. By default (None), the graph and its orientation will behave the same.
sparse – boolean (default: None); sparse=True is an alias for data_structure="sparse", and sparse=False is an alias for data_structure="dense". Only used when data_structure=None.
data_structure – string (default: None); one of 'sparse', 'static_sparse', or 'dense'. See the documentation of DiGraph.
immutable – boolean (default: None); whether to create a mutable/immutable digraph. Only used when data_structure=None.
- immutable=None (default) means that the graph and its orientation will behave the same way.
- immutable=True is a shortcut for data_structure='static_sparse'
- immutable=False means that the created digraph is mutable. When used to orient an immutable graph, the data structure used is 'sparse' unless anything else is specified.
hash_labels – boolean (default: None); whether to include edge labels during hashing of the oriented digraph. This parameter defaults to True if the graph is weighted. This parameter is ignored when parameter immutable is not True. Beware that trying to hash unhashable labels will raise an error.

OUTPUT: a DiGraph object

Note

This method behaves similarly to method copy(). That is, the returned digraph uses the same data structure by default, unless the user asks to use another data structure, and the attributes of the input graph are copied.

EXAMPLES:

Sage

sage: G = graphs.CycleGraph(4); G
Cycle graph: Graph on 4 vertices
sage: D = G.orient(lambda e:e if e[0] < e[1] else (e[1], e[0], e[2])); D
Orientation of Cycle graph: Digraph on 4 vertices
sage: sorted(D.edges(labels=False))
[(0, 1), (0, 3), (1, 2), (2, 3)]

Python

>>> from sage.all import *
>>> G = graphs.CycleGraph(Integer(4)); G
Cycle graph: Graph on 4 vertices
>>> D = G.orient(lambda e:e if e[Integer(0)] < e[Integer(1)] else (e[Integer(1)], e[Integer(0)], e[Integer(2)])); D
Orientation of Cycle graph: Digraph on 4 vertices
>>> sorted(D.edges(labels=False))
[(0, 1), (0, 3), (1, 2), (2, 3)]

Sage Live

G = graphs.CycleGraph(4); G
D = G.orient(lambda e:e if e[0] < e[1] else (e[1], e[0], e[2])); D
sorted(D.edges(labels=False))

sage.graphs.orientations.orientations(G, data_structure=None, sparse=None)[source]¶

Return an iterator over orientations of \(G\).

An orientation of an undirected graph is a directed graph such that every edge is assigned a direction. Hence there are \(2^s\) oriented digraphs for a simple graph with \(s\) edges.

INPUT:

G – an undirected graph
data_structure – one of 'sparse', 'static_sparse', or 'dense'; see the documentation of Graph or DiGraph; default is the data structure of \(G\)
sparse – boolean (default: None); sparse=True is an alias for data_structure="sparse", and sparse=False is an alias for data_structure="dense". By default (None), guess the most suitable data structure.

Warning

This always considers multiple edges of graphs as distinguishable, and hence, may have repeated digraphs.

See also

EXAMPLES:

Sage

sage: G = Graph([[1,2,3], [(1, 2, 'a'), (1, 3, 'b')]], format='vertices_and_edges')
sage: it = G.orientations()
sage: D = next(it)
sage: D.edges(sort=True)
[(1, 2, 'a'), (1, 3, 'b')]
sage: D = next(it)
sage: D.edges(sort=True)
[(1, 2, 'a'), (3, 1, 'b')]

Python

>>> from sage.all import *
>>> G = Graph([[Integer(1),Integer(2),Integer(3)], [(Integer(1), Integer(2), 'a'), (Integer(1), Integer(3), 'b')]], format='vertices_and_edges')
>>> it = G.orientations()
>>> D = next(it)
>>> D.edges(sort=True)
[(1, 2, 'a'), (1, 3, 'b')]
>>> D = next(it)
>>> D.edges(sort=True)
[(1, 2, 'a'), (3, 1, 'b')]

Sage Live

G = Graph([[1,2,3], [(1, 2, 'a'), (1, 3, 'b')]], format='vertices_and_edges')
it = G.orientations()
D = next(it)
D.edges(sort=True)
D = next(it)
D.edges(sort=True)

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

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)

Python

>>> 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)

Sage Live

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

See also

sage.graphs.orientations.strong_orientation(G)[source]¶

Return a strongly connected orientation of the graph \(G\).

An orientation of an undirected graph is a digraph obtained by giving an unique direction to each of its edges. An orientation is said to be strong if there is a directed path between each pair of vertices. See also the Wikipedia article Strongly_connected_component.

If the graph is 2-edge-connected, a strongly connected orientation can be found in linear time. If the given graph is not 2-connected, the orientation returned will ensure that each 2-connected component has a strongly connected orientation.

INPUT:

G – an undirected graph

OUTPUT: a digraph representing an orientation of the current graph

Note

This method assumes that the input the graph is connected.
The time complexity is \(O(n+m)\) for SparseGraph and \(O(n^2)\) for DenseGraph .

See also

orientations()
strong_orientations_iterator()
nauty_directg()
random_orientation()

EXAMPLES:

For a 2-regular graph, a strong orientation gives to each vertex an out-degree equal to 1:

Sage

sage: g = graphs.CycleGraph(5)
sage: g.strong_orientation().out_degree()
[1, 1, 1, 1, 1]

Python

>>> from sage.all import *
>>> g = graphs.CycleGraph(Integer(5))
>>> g.strong_orientation().out_degree()
[1, 1, 1, 1, 1]

Sage Live

g = graphs.CycleGraph(5)
g.strong_orientation().out_degree()

The Petersen Graph is 2-edge connected. It then has a strongly connected orientation:

Sage

sage: g = graphs.PetersenGraph()
sage: o = g.strong_orientation()
sage: len(o.strongly_connected_components())
1

Python

>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> o = g.strong_orientation()
>>> len(o.strongly_connected_components())
1

Sage Live

g = graphs.PetersenGraph()
o = g.strong_orientation()
len(o.strongly_connected_components())

The same goes for the CubeGraph in any dimension:

Sage

sage: all(len(graphs.CubeGraph(i).strong_orientation().strongly_connected_components()) == 1
....:     for i in range(2,6))
True

Python

>>> from sage.all import *
>>> all(len(graphs.CubeGraph(i).strong_orientation().strongly_connected_components()) == Integer(1)
...     for i in range(Integer(2),Integer(6)))
True

Sage Live

all(len(graphs.CubeGraph(i).strong_orientation().strongly_connected_components()) == 1
    for i in range(2,6))

A multigraph also has a strong orientation:

Sage

sage: g = Graph([(0, 1), (0, 2), (1, 2)] * 2, multiedges=True)
sage: g.strong_orientation()
Multi-digraph on 3 vertices

Python

>>> from sage.all import *
>>> g = Graph([(Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(1), Integer(2))] * Integer(2), multiedges=True)
>>> g.strong_orientation()
Multi-digraph on 3 vertices

Sage Live

g = Graph([(0, 1), (0, 2), (1, 2)] * 2, multiedges=True)
g.strong_orientation()

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

sage: g = graphs.CycleGraph(4)
sage: it = g.strong_orientations_iterator()
sage: len(list(it))
1

Python

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

Sage Live

g = graphs.CycleGraph(4)
it = g.strong_orientations_iterator()
len(list(it))

A tree cannot be strongly oriented:

Sage

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

Python

>>> from sage.all import *
>>> g = graphs.RandomTree(Integer(10))
>>> len(list(g.strong_orientations_iterator()))
0

Sage Live

g = graphs.RandomTree(10)
len(list(g.strong_orientations_iterator()))

Neither can be a disconnected graph:

Sage

sage: g = graphs.CompleteGraph(6)
sage: g.add_vertex(7)
sage: len(list(g.strong_orientations_iterator()))
0

Python

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

Sage Live

g = graphs.CompleteGraph(6)
g.add_vertex(7)
len(list(g.strong_orientations_iterator()))