# Directed graphs#

This module implements functions and operations involving directed graphs. Here is what they can do

Graph basic operations:

 layout_acyclic_dummy() Compute a (dummy) ranked layout so that all edges point upward. layout_acyclic() Compute a ranked layout so that all edges point upward. reverse() Return a copy of digraph with edges reversed in direction. reverse_edge() Reverse an edge. reverse_edges() Reverse a list of edges. out_degree_sequence() Return the outdegree sequence. out_degree_iterator() Same as degree_iterator, but for out degree. out_degree() Same as degree, but for out degree. in_degree_sequence() Return the indegree sequence of this digraph. in_degree_iterator() Same as degree_iterator, but for in degree. in_degree() Same as degree, but for in-degree. neighbors_out() Return the list of the out-neighbors of a given vertex. neighbor_out_iterator() Return an iterator over the out-neighbors of a given vertex. neighbors_in() Return the list of the in-neighbors of a given vertex. neighbor_in_iterator() Return an iterator over the in-neighbors of vertex. outgoing_edges() Return a list of edges departing from vertices. outgoing_edge_iterator() Return an iterator over all departing edges from vertices incoming_edges() Return a list of edges arriving at vertices. incoming_edge_iterator() Return an iterator over all arriving edges from vertices sources() Return the list of all sources (vertices without incoming edges) of this digraph. sinks() Return the list of all sinks (vertices without outgoing edges) of this digraph. to_undirected() Return an undirected version of the graph. to_directed() Since the graph is already directed, simply returns a copy of itself. is_directed() Since digraph is directed, returns True. dig6_string() Return the dig6 representation of the digraph as an ASCII string.

Distances:

 eccentricity() Return the eccentricity of vertex (or vertices) v. radius() Return the radius of the DiGraph. diameter() Return the diameter of the DiGraph. center() Return the set of vertices in the center of the DiGraph. periphery() Return the set of vertices in the periphery of the DiGraph.

Paths and cycles:

 all_cycles_iterator() Return an iterator over all the cycles of self starting with one of the given vertices. all_simple_cycles() Return a list of all simple cycles of self.

Representation theory:

 path_semigroup() Return the (partial) semigroup formed by the paths of the digraph. auslander_reiten_quiver() Return the Auslander-Reiten quiver of self.

Connectivity:

 is_strongly_connected() Check whether the current DiGraph is strongly connected. strongly_connected_components_digraph() Return the digraph of the strongly connected components strongly_connected_components_subgraphs() Return the strongly connected components as a list of subgraphs. strongly_connected_component_containing_vertex() Return the strongly connected component containing a given vertex strongly_connected_components() Return the list of strongly connected components. strong_articulation_points() Return the strong articulation points of this digraph.

Acyclicity:

 is_directed_acyclic() Check whether the digraph is acyclic or not. is_transitive() Check whether the digraph is transitive or not. is_aperiodic() Check whether the digraph is aperiodic or not. is_tournament() Check whether the digraph is a tournament. period() Return the period of the digraph. level_sets() Return the level set decomposition of the digraph. topological_sort_generator() Return a list of all topological sorts of the digraph if it is acyclic topological_sort() Return a topological sort of the digraph if it is acyclic

Hard stuff:

 feedback_edge_set() Compute the minimum feedback edge (arc) set of a digraph

Miscellaneous:

 flow_polytope() Compute the flow polytope of a digraph degree_polynomial() Return the generating polynomial of degrees of vertices in self. out_branchings() Return an iterator over the out branchings rooted at given vertex in self. in_branchings() Return an iterator over the in branchings rooted at given vertex in self.

## Methods#

class sage.graphs.digraph.DiGraph(data=None, pos=None, loops=None, format=None, weighted=None, data_structure='sparse', vertex_labels=True, name=None, multiedges=None, convert_empty_dict_labels_to_None=None, sparse=True, immutable=False, hash_labels=None)[source]#

Bases: GenericGraph

Directed graph.

A digraph or directed graph is a set of vertices connected by oriented edges. See also the Wikipedia article Directed_graph. For a collection of pre-defined digraphs, see the digraph_generators module.

A DiGraph object has many methods whose list can be obtained by typing g.<tab> (i.e. hit the Tab key) or by reading the documentation of digraph, generic_graph, and graph.

INPUT:

By default, a DiGraph object is simple (i.e. no loops nor multiple edges) and unweighted. This can be easily tuned with the appropriate flags (see below).

• data – can be any of the following (see the format argument):

1. DiGraph() – build a digraph on 0 vertices

2. DiGraph(5) – return an edgeless digraph on the 5 vertices 0,…,4

3. DiGraph([list_of_vertices, list_of_edges]) – return a digraph with given vertices/edges

To bypass auto-detection, prefer the more explicit DiGraph([V, E], format='vertices_and_edges').

4. DiGraph(list_of_edges) – return a digraph with a given list of edges (see documentation of add_edges()).

To bypass auto-detection, prefer the more explicit DiGraph(L, format='list_of_edges').

5. DiGraph({1: [2,3,4], 3: [4]}) – return a digraph by associating to each vertex the list of its out-neighbors.

To bypass auto-detection, prefer the more explicit DiGraph(D, format='dict_of_lists').

6. DiGraph({1: {2: 'a', 3: 'b'}, 3: {2: 'c'}}) – return a digraph by associating a list of out-neighbors to each vertex and providing its edge label.

To bypass auto-detection, prefer the more explicit DiGraph(D, format='dict_of_dicts').

For digraphs with multiple edges, you can provide a list of labels instead, e.g.: DiGraph({1: {2: ['a1', 'a2'], 3:['b']}, 3:{2:['c']}}).

7. DiGraph(a_matrix) – return a digraph with given (weighted) adjacency matrix (see documentation of adjacency_matrix()).

To bypass auto-detection, prefer the more explicit DiGraph(M, format='adjacency_matrix'). To take weights into account, use format='weighted_adjacency_matrix' instead.

8. DiGraph(a_nonsquare_matrix) – return a digraph with given incidence matrix (see documentation of incidence_matrix()).

To bypass auto-detection, prefer the more explicit DiGraph(M, format='incidence_matrix').

9. DiGraph([V, f]) – return a digraph with a vertex set V and an edge $$u,v$$ whenever $$f(u, v)$$ is True. Example: DiGraph([ [1..10], lambda x,y: abs(x - y).is_square()])

10. DiGraph('FOC@?OC@_?') – return a digraph from a dig6 string (see documentation of dig6_string()).

11. DiGraph(another_digraph) – return a digraph from a Sage (di)graph, pygraphviz digraph, NetworkX digraph, or igraph digraph.

• pos – dict (default: None); a positioning dictionary. For example, the spring layout from NetworkX for the 5-cycle is:

{0: [-0.91679746, 0.88169588],
1: [ 0.47294849, 1.125     ],
2: [ 1.125     ,-0.12867615],
3: [ 0.12743933,-1.125     ],
4: [-1.125     ,-0.50118505]}

• name – string (default: None); gives the graph a name (e.g., name=”complete”)

• loops – boolean (default: None); whether to allow loops (ignored if data is an instance of the DiGraph class)

• multiedges – boolean (default: None); whether to allow multiple edges (ignored if data is an instance of the DiGraph class)

• weighted – boolean (default: None); whether digraph thinks of itself as weighted or not. See self.weighted()

• format – string (default: None); if set to None, DiGraph tries to guess input’s format. To avoid this possibly time-consuming step, one of the following values can be specified (see description above): "int", "dig6", "rule", "list_of_edges", "dict_of_lists", "dict_of_dicts", "adjacency_matrix", "weighted_adjacency_matrix", "incidence_matrix", "NX", "igraph".

• sparse – boolean (default: True); sparse=True is an alias for data_structure="sparse", and sparse=False is an alias for data_structure="dense"

• data_structure – string (default: "sparse"); one of the following (for more information, see overview):

• immutable – boolean (default: False); whether to create a immutable digraph. Note that immutable=True is actually a shortcut for data_structure='static_sparse'.

• hash_labels – boolean (default: None); whether to include edge labels during hashing. This parameter defaults to True if the digraph is weighted. This parameter is ignored if the digraph is mutable. Beware that trying to hash unhashable labels will raise an error.

• vertex_labels – boolean (default: True); whether to allow any object as a vertex (slower), or only the integers $$0,...,n-1$$, where $$n$$ is the number of vertices.

• convert_empty_dict_labels_to_None – boolean (default: None); this arguments sets the default edge labels used by NetworkX (empty dictionaries) to be replaced by None, the default Sage edge label. It is set to True iff a NetworkX graph is on the input.

EXAMPLES:

1. A dictionary of dictionaries:

sage: g = DiGraph({0: {1: 'x', 2: 'z', 3: 'a'}, 2: {5: 'out'}}); g
Digraph on 5 vertices

>>> from sage.all import *
>>> g = DiGraph({Integer(0): {Integer(1): 'x', Integer(2): 'z', Integer(3): 'a'}, Integer(2): {Integer(5): 'out'}}); g
Digraph on 5 vertices


The labels (‘x’, ‘z’, ‘a’, ‘out’) are labels for edges. For example, ‘out’ is the label for the edge from 2 to 5. Labels can be used as weights, if all the labels share some common parent.

2. A dictionary of lists (or iterables):

sage: g = DiGraph({0: [1, 2, 3], 2: [4]}); g
Digraph on 5 vertices
sage: g = DiGraph({0: (1, 2, 3), 2: (4,)}); g
Digraph on 5 vertices

>>> from sage.all import *
>>> g = DiGraph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(2): [Integer(4)]}); g
Digraph on 5 vertices
>>> g = DiGraph({Integer(0): (Integer(1), Integer(2), Integer(3)), Integer(2): (Integer(4),)}); g
Digraph on 5 vertices

3. A list of vertices and a function describing adjacencies. Note that the list of vertices and the function must be enclosed in a list (i.e., [list of vertices, function]).

We construct a graph on the integers 1 through 12 such that there is a directed edge from $$i$$ to $$j$$ if and only if $$i$$ divides $$j$$:

sage: g = DiGraph([[1..12], lambda i,j: i != j and i.divides(j)])
sage: g.vertices(sort=True)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
[0 1 1 1 1 1 1 1 1 1 1 1]
[0 0 0 1 0 1 0 1 0 1 0 1]
[0 0 0 0 0 1 0 0 1 0 0 1]
[0 0 0 0 0 0 0 1 0 0 0 1]
[0 0 0 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0]

>>> from sage.all import *
>>> g = DiGraph([(ellipsis_range(Integer(1),Ellipsis,Integer(12))), lambda i,j: i != j and i.divides(j)])
>>> g.vertices(sort=True)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
[0 1 1 1 1 1 1 1 1 1 1 1]
[0 0 0 1 0 1 0 1 0 1 0 1]
[0 0 0 0 0 1 0 0 1 0 0 1]
[0 0 0 0 0 0 0 1 0 0 0 1]
[0 0 0 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0]

4. A Sage matrix: Note: If format is not specified, then Sage assumes a square matrix is an adjacency matrix, and a nonsquare matrix is an incidence matrix.

sage: M = Matrix([[0, 1, 1, 1, 0], [0, 0, 0, 0, 0],                         # needs sage.modules
....:             [0, 0, 0, 0, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]); M
[0 1 1 1 0]
[0 0 0 0 0]
[0 0 0 0 1]
[0 0 0 0 0]
[0 0 0 0 0]
sage: DiGraph(M)                                                            # needs sage.modules
Digraph on 5 vertices

sage: M = Matrix([[0,1,-1], [-1,0,-1/2], [1,1/2,0]]); M                     # needs sage.modules
[   0    1   -1]
[  -1    0 -1/2]
[   1  1/2    0]
sage: G = DiGraph(M, sparse=True, weighted=True); G                         # needs sage.modules
Digraph on 3 vertices
sage: G.weighted()                                                          # needs sage.modules
True

>>> from sage.all import *
>>> M = Matrix([[Integer(0), Integer(1), Integer(1), Integer(1), Integer(0)], [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)],                         # needs sage.modules
...             [Integer(0), Integer(0), Integer(0), Integer(0), Integer(1)], [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)], [Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)]]); M
[0 1 1 1 0]
[0 0 0 0 0]
[0 0 0 0 1]
[0 0 0 0 0]
[0 0 0 0 0]
>>> DiGraph(M)                                                            # needs sage.modules
Digraph on 5 vertices

>>> M = Matrix([[Integer(0),Integer(1),-Integer(1)], [-Integer(1),Integer(0),-Integer(1)/Integer(2)], [Integer(1),Integer(1)/Integer(2),Integer(0)]]); M                     # needs sage.modules
[   0    1   -1]
[  -1    0 -1/2]
[   1  1/2    0]
>>> G = DiGraph(M, sparse=True, weighted=True); G                         # needs sage.modules
Digraph on 3 vertices
>>> G.weighted()                                                          # needs sage.modules
True

• an incidence matrix:

sage: M = Matrix(6, [-1,0,0,0,1, 1,-1,0,0,0, 0,1,-1,0,0,                    # needs sage.modules
....:                0,0,1,-1,0, 0,0,0,1,-1, 0,0,0,0,0]); M
[-1  0  0  0  1]
[ 1 -1  0  0  0]
[ 0  1 -1  0  0]
[ 0  0  1 -1  0]
[ 0  0  0  1 -1]
[ 0  0  0  0  0]
sage: DiGraph(M)                                                            # needs sage.modules
Digraph on 6 vertices

>>> from sage.all import *
>>> M = Matrix(Integer(6), [-Integer(1),Integer(0),Integer(0),Integer(0),Integer(1), Integer(1),-Integer(1),Integer(0),Integer(0),Integer(0), Integer(0),Integer(1),-Integer(1),Integer(0),Integer(0),                    # needs sage.modules
...                Integer(0),Integer(0),Integer(1),-Integer(1),Integer(0), Integer(0),Integer(0),Integer(0),Integer(1),-Integer(1), Integer(0),Integer(0),Integer(0),Integer(0),Integer(0)]); M
[-1  0  0  0  1]
[ 1 -1  0  0  0]
[ 0  1 -1  0  0]
[ 0  0  1 -1  0]
[ 0  0  0  1 -1]
[ 0  0  0  0  0]
>>> DiGraph(M)                                                            # needs sage.modules
Digraph on 6 vertices

5. A dig6 string: Sage automatically recognizes whether a string is in dig6 format, which is a directed version of graph6:

sage: D = DiGraph('IRAaDCIIOWEOKcPWAo')
sage: D
Digraph on 10 vertices

Traceback (most recent call last):
...
RuntimeError: the string (IRAaDCIIOEOKcPWAo) seems corrupt: for n = 10, the string is too short

Traceback (most recent call last):
...
RuntimeError: the string seems corrupt: valid characters are
?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_abcdefghijklmnopqrstuvwxyz{|}~

>>> from sage.all import *
>>> D
Digraph on 10 vertices

Traceback (most recent call last):
...
RuntimeError: the string (IRAaDCIIOEOKcPWAo) seems corrupt: for n = 10, the string is too short

Traceback (most recent call last):
...
RuntimeError: the string seems corrupt: valid characters are
?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_abcdefghijklmnopqrstuvwxyz{|}~

6. A NetworkX MultiDiGraph:

sage: import networkx                                                       # needs networkx
sage: g = networkx.MultiDiGraph({0: [1, 2, 3], 2: [4]})                     # needs networkx
sage: DiGraph(g)                                                            # needs networkx
Multi-digraph on 5 vertices

>>> from sage.all import *
>>> import networkx                                                       # needs networkx
>>> g = networkx.MultiDiGraph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(2): [Integer(4)]})                     # needs networkx
>>> DiGraph(g)                                                            # needs networkx
Multi-digraph on 5 vertices

7. A NetworkX digraph:

sage: import networkx                                                       # needs networkx
sage: g = networkx.DiGraph({0: [1, 2, 3], 2: [4]})                          # needs networkx
sage: DiGraph(g)                                                            # needs networkx
Digraph on 5 vertices

>>> from sage.all import *
>>> import networkx                                                       # needs networkx
>>> g = networkx.DiGraph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(2): [Integer(4)]})                          # needs networkx
>>> DiGraph(g)                                                            # needs networkx
Digraph on 5 vertices

8. An igraph directed Graph (see also igraph_graph()):

sage: import igraph                                   # optional - python_igraph
sage: g = igraph.Graph([(0,1),(0,2)], directed=True)  # optional - python_igraph
sage: DiGraph(g)                                      # optional - python_igraph
Digraph on 3 vertices

>>> from sage.all import *
>>> import igraph                                   # optional - python_igraph
>>> g = igraph.Graph([(Integer(0),Integer(1)),(Integer(0),Integer(2))], directed=True)  # optional - python_igraph
>>> DiGraph(g)                                      # optional - python_igraph
Digraph on 3 vertices


If vertex_labels is True, the names of the vertices are given by the vertex attribute 'name', if available:

sage: # optional - python_igraph
sage: g = igraph.Graph([(0,1),(0,2)], directed=True, vertex_attrs={'name':['a','b','c']})
sage: DiGraph(g).vertices(sort=True)
['a', 'b', 'c']
sage: g = igraph.Graph([(0,1),(0,2)], directed=True, vertex_attrs={'label':['a','b','c']})
sage: DiGraph(g).vertices(sort=True)
[0, 1, 2]

>>> from sage.all import *
>>> # optional - python_igraph
>>> g = igraph.Graph([(Integer(0),Integer(1)),(Integer(0),Integer(2))], directed=True, vertex_attrs={'name':['a','b','c']})
>>> DiGraph(g).vertices(sort=True)
['a', 'b', 'c']
>>> g = igraph.Graph([(Integer(0),Integer(1)),(Integer(0),Integer(2))], directed=True, vertex_attrs={'label':['a','b','c']})
>>> DiGraph(g).vertices(sort=True)
[0, 1, 2]


If the igraph Graph has edge attributes, they are used as edge labels:

sage: g = igraph.Graph([(0, 1), (0, 2)], directed=True,                  # optional - python_igraph
....:                  edge_attrs={'name':['a', 'b'], 'weight':[1, 3]})
sage: DiGraph(g).edges(sort=True)                                        # optional - python_igraph
[(0, 1, {'name': 'a', 'weight': 1}), (0, 2, {'name': 'b', 'weight': 3})]

>>> from sage.all import *
>>> g = igraph.Graph([(Integer(0), Integer(1)), (Integer(0), Integer(2))], directed=True,                  # optional - python_igraph
...                  edge_attrs={'name':['a', 'b'], 'weight':[Integer(1), Integer(3)]})
>>> DiGraph(g).edges(sort=True)                                        # optional - python_igraph
[(0, 1, {'name': 'a', 'weight': 1}), (0, 2, {'name': 'b', 'weight': 3})]

all_cycles_iterator(starting_vertices=None, simple=False, rooted=False, max_length=None, trivial=False)[source]#

Return an iterator over all the cycles of self starting with one of the given vertices.

The cycles are enumerated in increasing length order.

INPUT:

• starting_vertices – iterable (default: None); vertices from which the cycles must start. If None, then all vertices of the graph can be starting points. This argument is necessary if rooted is set to True.

• simple – boolean (default: False); if set to True, then only simple cycles are considered. A cycle is simple if the only vertex occurring twice in it is the starting and ending one.

• rooted – boolean (default: False); if set to False, then cycles differing only by their starting vertex are considered the same (e.g. ['a', 'b', 'c', 'a'] and ['b', 'c', 'a', 'b']). Otherwise, all cycles are enumerated.

• max_length – non negative integer (default: None); the maximum length of the enumerated paths. If set to None, then all lengths are allowed.

• trivial – boolean (default: False); if set to True, then the empty paths are also enumerated.

OUTPUT:

iterator

AUTHOR:

Alexandre Blondin Masse

EXAMPLES:

sage: g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
sage: it = g.all_cycles_iterator()
sage: for _ in range(7): print(next(it))
['a', 'a']
['a', 'a', 'a']
['c', 'd', 'c']
['a', 'a', 'a', 'a']
['a', 'a', 'a', 'a', 'a']
['c', 'd', 'c', 'd', 'c']
['a', 'a', 'a', 'a', 'a', 'a']

>>> from sage.all import *
>>> g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
>>> it = g.all_cycles_iterator()
>>> for _ in range(Integer(7)): print(next(it))
['a', 'a']
['a', 'a', 'a']
['c', 'd', 'c']
['a', 'a', 'a', 'a']
['a', 'a', 'a', 'a', 'a']
['c', 'd', 'c', 'd', 'c']
['a', 'a', 'a', 'a', 'a', 'a']


There are no cycles in the empty graph and in acyclic graphs:

sage: g = DiGraph()
sage: it = g.all_cycles_iterator()
sage: list(it)
[]
sage: g = DiGraph({0:[1]})
sage: it = g.all_cycles_iterator()
sage: list(it)
[]

>>> from sage.all import *
>>> g = DiGraph()
>>> it = g.all_cycles_iterator()
>>> list(it)
[]
>>> g = DiGraph({Integer(0):[Integer(1)]})
>>> it = g.all_cycles_iterator()
>>> list(it)
[]


It is possible to restrict the starting vertices of the cycles:

sage: g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
sage: it = g.all_cycles_iterator(starting_vertices=['b', 'c'])
sage: for _ in range(3): print(next(it))
['c', 'd', 'c']
['c', 'd', 'c', 'd', 'c']
['c', 'd', 'c', 'd', 'c', 'd', 'c']

>>> from sage.all import *
>>> g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
>>> it = g.all_cycles_iterator(starting_vertices=['b', 'c'])
>>> for _ in range(Integer(3)): print(next(it))
['c', 'd', 'c']
['c', 'd', 'c', 'd', 'c']
['c', 'd', 'c', 'd', 'c', 'd', 'c']


Also, one can bound the length of the cycles:

sage: it = g.all_cycles_iterator(max_length=3)
sage: list(it)
[['a', 'a'], ['a', 'a', 'a'], ['c', 'd', 'c'],
['a', 'a', 'a', 'a']]

>>> from sage.all import *
>>> it = g.all_cycles_iterator(max_length=Integer(3))
>>> list(it)
[['a', 'a'], ['a', 'a', 'a'], ['c', 'd', 'c'],
['a', 'a', 'a', 'a']]


By default, cycles differing only by their starting point are not all enumerated, but this may be parametrized:

sage: it = g.all_cycles_iterator(max_length=3, rooted=False)
sage: list(it)
[['a', 'a'], ['a', 'a', 'a'], ['c', 'd', 'c'],
['a', 'a', 'a', 'a']]
sage: it = g.all_cycles_iterator(max_length=3, rooted=True)
sage: list(it)
[['a', 'a'], ['a', 'a', 'a'], ['c', 'd', 'c'], ['d', 'c', 'd'],
['a', 'a', 'a', 'a']]

>>> from sage.all import *
>>> it = g.all_cycles_iterator(max_length=Integer(3), rooted=False)
>>> list(it)
[['a', 'a'], ['a', 'a', 'a'], ['c', 'd', 'c'],
['a', 'a', 'a', 'a']]
>>> it = g.all_cycles_iterator(max_length=Integer(3), rooted=True)
>>> list(it)
[['a', 'a'], ['a', 'a', 'a'], ['c', 'd', 'c'], ['d', 'c', 'd'],
['a', 'a', 'a', 'a']]


One may prefer to enumerate simple cycles, i.e. cycles such that the only vertex occurring twice in it is the starting and ending one (see also all_simple_cycles()):

sage: it = g.all_cycles_iterator(simple=True)
sage: list(it)
[['a', 'a'], ['c', 'd', 'c']]
sage: g = digraphs.Circuit(4)
sage: list(g.all_cycles_iterator(simple=True))
[[0, 1, 2, 3, 0]]

>>> from sage.all import *
>>> it = g.all_cycles_iterator(simple=True)
>>> list(it)
[['a', 'a'], ['c', 'd', 'c']]
>>> g = digraphs.Circuit(Integer(4))
>>> list(g.all_cycles_iterator(simple=True))
[[0, 1, 2, 3, 0]]

all_simple_cycles(starting_vertices=None, rooted=False, max_length=None, trivial=False)[source]#

Return a list of all simple cycles of self.

INPUT:

• starting_vertices – iterable (default: None); vertices from which the cycles must start. If None, then all vertices of the graph can be starting points. This argument is necessary if rooted is set to True.

• rooted – boolean (default: False); if set to False, then cycles differing only by their starting vertex are considered the same (e.g. ['a', 'b', 'c', 'a'] and ['b', 'c', 'a', 'b']). Otherwise, all cycles are enumerated.

• max_length – non negative integer (default: None); the maximum length of the enumerated paths. If set to None, then all lengths are allowed.

• trivial – boolean (default: False); if set to True, then the empty paths are also enumerated.

OUTPUT:

list

Note

Although the number of simple cycles of a finite graph is always finite, computing all its cycles may take a very long time.

EXAMPLES:

sage: g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
sage: g.all_simple_cycles()
[['a', 'a'], ['c', 'd', 'c']]

>>> from sage.all import *
>>> g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True)
>>> g.all_simple_cycles()
[['a', 'a'], ['c', 'd', 'c']]


The directed version of the Petersen graph:

sage: g = graphs.PetersenGraph().to_directed()
sage: g.all_simple_cycles(max_length=4)
[[0, 1, 0], [0, 4, 0], [0, 5, 0], [1, 2, 1], [1, 6, 1], [2, 3, 2],
[2, 7, 2], [3, 4, 3], [3, 8, 3], [4, 9, 4], [5, 7, 5], [5, 8, 5],
[6, 8, 6], [6, 9, 6], [7, 9, 7]]
sage: g.all_simple_cycles(max_length=6)
[[0, 1, 0], [0, 4, 0], [0, 5, 0], [1, 2, 1], [1, 6, 1], [2, 3, 2],
[2, 7, 2], [3, 4, 3], [3, 8, 3], [4, 9, 4], [5, 7, 5], [5, 8, 5],
[6, 8, 6], [6, 9, 6], [7, 9, 7], [0, 1, 2, 3, 4, 0],
[0, 1, 2, 7, 5, 0], [0, 1, 6, 8, 5, 0], [0, 1, 6, 9, 4, 0],
[0, 4, 3, 2, 1, 0], [0, 4, 3, 8, 5, 0], [0, 4, 9, 6, 1, 0],
[0, 4, 9, 7, 5, 0], [0, 5, 7, 2, 1, 0], [0, 5, 7, 9, 4, 0],
[0, 5, 8, 3, 4, 0], [0, 5, 8, 6, 1, 0], [1, 2, 3, 8, 6, 1],
[1, 2, 7, 9, 6, 1], [1, 6, 8, 3, 2, 1], [1, 6, 9, 7, 2, 1],
[2, 3, 4, 9, 7, 2], [2, 3, 8, 5, 7, 2], [2, 7, 5, 8, 3, 2],
[2, 7, 9, 4, 3, 2], [3, 4, 9, 6, 8, 3], [3, 8, 6, 9, 4, 3],
[5, 7, 9, 6, 8, 5], [5, 8, 6, 9, 7, 5], [0, 1, 2, 3, 8, 5, 0],
[0, 1, 2, 7, 9, 4, 0], [0, 1, 6, 8, 3, 4, 0],
[0, 1, 6, 9, 7, 5, 0], [0, 4, 3, 2, 7, 5, 0],
[0, 4, 3, 8, 6, 1, 0], [0, 4, 9, 6, 8, 5, 0],
[0, 4, 9, 7, 2, 1, 0], [0, 5, 7, 2, 3, 4, 0],
[0, 5, 7, 9, 6, 1, 0], [0, 5, 8, 3, 2, 1, 0],
[0, 5, 8, 6, 9, 4, 0], [1, 2, 3, 4, 9, 6, 1],
[1, 2, 7, 5, 8, 6, 1], [1, 6, 8, 5, 7, 2, 1],
[1, 6, 9, 4, 3, 2, 1], [2, 3, 8, 6, 9, 7, 2],
[2, 7, 9, 6, 8, 3, 2], [3, 4, 9, 7, 5, 8, 3],
[3, 8, 5, 7, 9, 4, 3]]

>>> from sage.all import *
>>> g = graphs.PetersenGraph().to_directed()
>>> g.all_simple_cycles(max_length=Integer(4))
[[0, 1, 0], [0, 4, 0], [0, 5, 0], [1, 2, 1], [1, 6, 1], [2, 3, 2],
[2, 7, 2], [3, 4, 3], [3, 8, 3], [4, 9, 4], [5, 7, 5], [5, 8, 5],
[6, 8, 6], [6, 9, 6], [7, 9, 7]]
>>> g.all_simple_cycles(max_length=Integer(6))
[[0, 1, 0], [0, 4, 0], [0, 5, 0], [1, 2, 1], [1, 6, 1], [2, 3, 2],
[2, 7, 2], [3, 4, 3], [3, 8, 3], [4, 9, 4], [5, 7, 5], [5, 8, 5],
[6, 8, 6], [6, 9, 6], [7, 9, 7], [0, 1, 2, 3, 4, 0],
[0, 1, 2, 7, 5, 0], [0, 1, 6, 8, 5, 0], [0, 1, 6, 9, 4, 0],
[0, 4, 3, 2, 1, 0], [0, 4, 3, 8, 5, 0], [0, 4, 9, 6, 1, 0],
[0, 4, 9, 7, 5, 0], [0, 5, 7, 2, 1, 0], [0, 5, 7, 9, 4, 0],
[0, 5, 8, 3, 4, 0], [0, 5, 8, 6, 1, 0], [1, 2, 3, 8, 6, 1],
[1, 2, 7, 9, 6, 1], [1, 6, 8, 3, 2, 1], [1, 6, 9, 7, 2, 1],
[2, 3, 4, 9, 7, 2], [2, 3, 8, 5, 7, 2], [2, 7, 5, 8, 3, 2],
[2, 7, 9, 4, 3, 2], [3, 4, 9, 6, 8, 3], [3, 8, 6, 9, 4, 3],
[5, 7, 9, 6, 8, 5], [5, 8, 6, 9, 7, 5], [0, 1, 2, 3, 8, 5, 0],
[0, 1, 2, 7, 9, 4, 0], [0, 1, 6, 8, 3, 4, 0],
[0, 1, 6, 9, 7, 5, 0], [0, 4, 3, 2, 7, 5, 0],
[0, 4, 3, 8, 6, 1, 0], [0, 4, 9, 6, 8, 5, 0],
[0, 4, 9, 7, 2, 1, 0], [0, 5, 7, 2, 3, 4, 0],
[0, 5, 7, 9, 6, 1, 0], [0, 5, 8, 3, 2, 1, 0],
[0, 5, 8, 6, 9, 4, 0], [1, 2, 3, 4, 9, 6, 1],
[1, 2, 7, 5, 8, 6, 1], [1, 6, 8, 5, 7, 2, 1],
[1, 6, 9, 4, 3, 2, 1], [2, 3, 8, 6, 9, 7, 2],
[2, 7, 9, 6, 8, 3, 2], [3, 4, 9, 7, 5, 8, 3],
[3, 8, 5, 7, 9, 4, 3]]


The complete graph (without loops) on $$4$$ vertices:

sage: g = graphs.CompleteGraph(4).to_directed()
sage: g.all_simple_cycles()
[[0, 1, 0], [0, 2, 0], [0, 3, 0], [1, 2, 1], [1, 3, 1], [2, 3, 2],
[0, 1, 2, 0], [0, 1, 3, 0], [0, 2, 1, 0], [0, 2, 3, 0],
[0, 3, 1, 0], [0, 3, 2, 0], [1, 2, 3, 1], [1, 3, 2, 1],
[0, 1, 2, 3, 0], [0, 1, 3, 2, 0], [0, 2, 1, 3, 0],
[0, 2, 3, 1, 0], [0, 3, 1, 2, 0], [0, 3, 2, 1, 0]]

>>> from sage.all import *
>>> g = graphs.CompleteGraph(Integer(4)).to_directed()
>>> g.all_simple_cycles()
[[0, 1, 0], [0, 2, 0], [0, 3, 0], [1, 2, 1], [1, 3, 1], [2, 3, 2],
[0, 1, 2, 0], [0, 1, 3, 0], [0, 2, 1, 0], [0, 2, 3, 0],
[0, 3, 1, 0], [0, 3, 2, 0], [1, 2, 3, 1], [1, 3, 2, 1],
[0, 1, 2, 3, 0], [0, 1, 3, 2, 0], [0, 2, 1, 3, 0],
[0, 2, 3, 1, 0], [0, 3, 1, 2, 0], [0, 3, 2, 1, 0]]


If the graph contains a large number of cycles, one can bound the length of the cycles, or simply restrict the possible starting vertices of the cycles:

sage: g = graphs.CompleteGraph(20).to_directed()
sage: g.all_simple_cycles(max_length=2)
[[0, 16, 0], [0, 1, 0], [0, 17, 0], [0, 2, 0], [0, 18, 0],
[0, 3, 0], [0, 19, 0], [0, 4, 0], [0, 5, 0], [0, 6, 0], [0, 7, 0],
[0, 8, 0], [0, 9, 0], [0, 10, 0], [0, 11, 0], [0, 12, 0],
[0, 13, 0], [0, 14, 0], [0, 15, 0], [1, 16, 1], [1, 17, 1],
[1, 2, 1], [1, 18, 1], [1, 3, 1], [1, 19, 1], [1, 4, 1], [1, 5, 1],
[1, 6, 1], [1, 7, 1], [1, 8, 1], [1, 9, 1], [1, 10, 1], [1, 11, 1],
[1, 12, 1], [1, 13, 1], [1, 14, 1], [1, 15, 1], [2, 16, 2],
[2, 17, 2], [2, 18, 2], [2, 3, 2], [2, 19, 2], [2, 4, 2],
[2, 5, 2], [2, 6, 2], [2, 7, 2], [2, 8, 2], [2, 9, 2], [2, 10, 2],
[2, 11, 2], [2, 12, 2], [2, 13, 2], [2, 14, 2], [2, 15, 2],
[3, 16, 3], [3, 17, 3], [3, 18, 3], [3, 19, 3], [3, 4, 3],
[3, 5, 3], [3, 6, 3], [3, 7, 3], [3, 8, 3], [3, 9, 3], [3, 10, 3],
[3, 11, 3], [3, 12, 3], [3, 13, 3], [3, 14, 3], [3, 15, 3],
[4, 16, 4], [4, 17, 4], [4, 18, 4], [4, 19, 4], [4, 5, 4],
[4, 6, 4], [4, 7, 4], [4, 8, 4], [4, 9, 4], [4, 10, 4], [4, 11, 4],
[4, 12, 4], [4, 13, 4], [4, 14, 4], [4, 15, 4], [5, 16, 5],
[5, 17, 5], [5, 18, 5], [5, 19, 5], [5, 6, 5], [5, 7, 5],
[5, 8, 5], [5, 9, 5], [5, 10, 5], [5, 11, 5], [5, 12, 5],
[5, 13, 5], [5, 14, 5], [5, 15, 5], [6, 16, 6], [6, 17, 6],
[6, 18, 6], [6, 19, 6], [6, 7, 6], [6, 8, 6], [6, 9, 6],
[6, 10, 6], [6, 11, 6], [6, 12, 6], [6, 13, 6], [6, 14, 6],
[6, 15, 6], [7, 16, 7], [7, 17, 7], [7, 18, 7], [7, 19, 7],
[7, 8, 7], [7, 9, 7], [7, 10, 7], [7, 11, 7], [7, 12, 7],
[7, 13, 7], [7, 14, 7], [7, 15, 7], [8, 16, 8], [8, 17, 8],
[8, 18, 8], [8, 19, 8], [8, 9, 8], [8, 10, 8], [8, 11, 8],
[8, 12, 8], [8, 13, 8], [8, 14, 8], [8, 15, 8], [9, 16, 9],
[9, 17, 9], [9, 18, 9], [9, 19, 9], [9, 10, 9], [9, 11, 9],
[9, 12, 9], [9, 13, 9], [9, 14, 9], [9, 15, 9], [10, 16, 10],
[10, 17, 10], [10, 18, 10], [10, 19, 10], [10, 11, 10],
[10, 12, 10], [10, 13, 10], [10, 14, 10], [10, 15, 10],
[11, 16, 11], [11, 17, 11], [11, 18, 11], [11, 19, 11],
[11, 12, 11], [11, 13, 11], [11, 14, 11], [11, 15, 11],
[12, 16, 12], [12, 17, 12], [12, 18, 12], [12, 19, 12],
[12, 13, 12], [12, 14, 12], [12, 15, 12], [13, 16, 13],
[13, 17, 13], [13, 18, 13], [13, 19, 13], [13, 14, 13],
[13, 15, 13], [14, 16, 14], [14, 17, 14], [14, 18, 14],
[14, 19, 14], [14, 15, 14], [15, 16, 15], [15, 17, 15],
[15, 18, 15], [15, 19, 15], [16, 17, 16], [16, 18, 16],
[16, 19, 16], [17, 18, 17], [17, 19, 17], [18, 19, 18]]

sage: g = graphs.CompleteGraph(20).to_directed()
sage: g.all_simple_cycles(max_length=2, starting_vertices=[0])
[[0, 16, 0], [0, 1, 0], [0, 17, 0], [0, 2, 0], [0, 18, 0],
[0, 3, 0], [0, 19, 0], [0, 4, 0], [0, 5, 0], [0, 6, 0],
[0, 7, 0], [0, 8, 0], [0, 9, 0], [0, 10, 0], [0, 11, 0],
[0, 12, 0], [0, 13, 0], [0, 14, 0], [0, 15, 0]]

>>> from sage.all import *
>>> g = graphs.CompleteGraph(Integer(20)).to_directed()
>>> g.all_simple_cycles(max_length=Integer(2))
[[0, 16, 0], [0, 1, 0], [0, 17, 0], [0, 2, 0], [0, 18, 0],
[0, 3, 0], [0, 19, 0], [0, 4, 0], [0, 5, 0], [0, 6, 0], [0, 7, 0],
[0, 8, 0], [0, 9, 0], [0, 10, 0], [0, 11, 0], [0, 12, 0],
[0, 13, 0], [0, 14, 0], [0, 15, 0], [1, 16, 1], [1, 17, 1],
[1, 2, 1], [1, 18, 1], [1, 3, 1], [1, 19, 1], [1, 4, 1], [1, 5, 1],
[1, 6, 1], [1, 7, 1], [1, 8, 1], [1, 9, 1], [1, 10, 1], [1, 11, 1],
[1, 12, 1], [1, 13, 1], [1, 14, 1], [1, 15, 1], [2, 16, 2],
[2, 17, 2], [2, 18, 2], [2, 3, 2], [2, 19, 2], [2, 4, 2],
[2, 5, 2], [2, 6, 2], [2, 7, 2], [2, 8, 2], [2, 9, 2], [2, 10, 2],
[2, 11, 2], [2, 12, 2], [2, 13, 2], [2, 14, 2], [2, 15, 2],
[3, 16, 3], [3, 17, 3], [3, 18, 3], [3, 19, 3], [3, 4, 3],
[3, 5, 3], [3, 6, 3], [3, 7, 3], [3, 8, 3], [3, 9, 3], [3, 10, 3],
[3, 11, 3], [3, 12, 3], [3, 13, 3], [3, 14, 3], [3, 15, 3],
[4, 16, 4], [4, 17, 4], [4, 18, 4], [4, 19, 4], [4, 5, 4],
[4, 6, 4], [4, 7, 4], [4, 8, 4], [4, 9, 4], [4, 10, 4], [4, 11, 4],
[4, 12, 4], [4, 13, 4], [4, 14, 4], [4, 15, 4], [5, 16, 5],
[5, 17, 5], [5, 18, 5], [5, 19, 5], [5, 6, 5], [5, 7, 5],
[5, 8, 5], [5, 9, 5], [5, 10, 5], [5, 11, 5], [5, 12, 5],
[5, 13, 5], [5, 14, 5], [5, 15, 5], [6, 16, 6], [6, 17, 6],
[6, 18, 6], [6, 19, 6], [6, 7, 6], [6, 8, 6], [6, 9, 6],
[6, 10, 6], [6, 11, 6], [6, 12, 6], [6, 13, 6], [6, 14, 6],
[6, 15, 6], [7, 16, 7], [7, 17, 7], [7, 18, 7], [7, 19, 7],
[7, 8, 7], [7, 9, 7], [7, 10, 7], [7, 11, 7], [7, 12, 7],
[7, 13, 7], [7, 14, 7], [7, 15, 7], [8, 16, 8], [8, 17, 8],
[8, 18, 8], [8, 19, 8], [8, 9, 8], [8, 10, 8], [8, 11, 8],
[8, 12, 8], [8, 13, 8], [8, 14, 8], [8, 15, 8], [9, 16, 9],
[9, 17, 9], [9, 18, 9], [9, 19, 9], [9, 10, 9], [9, 11, 9],
[9, 12, 9], [9, 13, 9], [9, 14, 9], [9, 15, 9], [10, 16, 10],
[10, 17, 10], [10, 18, 10], [10, 19, 10], [10, 11, 10],
[10, 12, 10], [10, 13, 10], [10, 14, 10], [10, 15, 10],
[11, 16, 11], [11, 17, 11], [11, 18, 11], [11, 19, 11],
[11, 12, 11], [11, 13, 11], [11, 14, 11], [11, 15, 11],
[12, 16, 12], [12, 17, 12], [12, 18, 12], [12, 19, 12],
[12, 13, 12], [12, 14, 12], [12, 15, 12], [13, 16, 13],
[13, 17, 13], [13, 18, 13], [13, 19, 13], [13, 14, 13],
[13, 15, 13], [14, 16, 14], [14, 17, 14], [14, 18, 14],
[14, 19, 14], [14, 15, 14], [15, 16, 15], [15, 17, 15],
[15, 18, 15], [15, 19, 15], [16, 17, 16], [16, 18, 16],
[16, 19, 16], [17, 18, 17], [17, 19, 17], [18, 19, 18]]

>>> g = graphs.CompleteGraph(Integer(20)).to_directed()
>>> g.all_simple_cycles(max_length=Integer(2), starting_vertices=[Integer(0)])
[[0, 16, 0], [0, 1, 0], [0, 17, 0], [0, 2, 0], [0, 18, 0],
[0, 3, 0], [0, 19, 0], [0, 4, 0], [0, 5, 0], [0, 6, 0],
[0, 7, 0], [0, 8, 0], [0, 9, 0], [0, 10, 0], [0, 11, 0],
[0, 12, 0], [0, 13, 0], [0, 14, 0], [0, 15, 0]]


One may prefer to distinguish equivalent cycles having distinct starting vertices (compare the following examples):

sage: g = graphs.CompleteGraph(4).to_directed()
sage: g.all_simple_cycles(max_length=2, rooted=False)
[[0, 1, 0], [0, 2, 0], [0, 3, 0], [1, 2, 1], [1, 3, 1], [2, 3, 2]]
sage: g.all_simple_cycles(max_length=2, rooted=True)
[[0, 1, 0], [0, 2, 0], [0, 3, 0], [1, 0, 1], [1, 2, 1], [1, 3, 1],
[2, 0, 2], [2, 1, 2], [2, 3, 2], [3, 0, 3], [3, 1, 3], [3, 2, 3]]

>>> from sage.all import *
>>> g = graphs.CompleteGraph(Integer(4)).to_directed()
>>> g.all_simple_cycles(max_length=Integer(2), rooted=False)
[[0, 1, 0], [0, 2, 0], [0, 3, 0], [1, 2, 1], [1, 3, 1], [2, 3, 2]]
>>> g.all_simple_cycles(max_length=Integer(2), rooted=True)
[[0, 1, 0], [0, 2, 0], [0, 3, 0], [1, 0, 1], [1, 2, 1], [1, 3, 1],
[2, 0, 2], [2, 1, 2], [2, 3, 2], [3, 0, 3], [3, 1, 3], [3, 2, 3]]

auslander_reiten_quiver()[source]#

Return the Auslander-Reiten quiver of self.

EXAMPLES:

sage: D = DiGraph([[1,2,'a'], [1,2,'b']], multiedges=True)
sage: D.auslander_reiten_quiver()
Auslander-Reiten quiver of Multi-digraph on 2 vertices

>>> from sage.all import *
>>> D = DiGraph([[Integer(1),Integer(2),'a'], [Integer(1),Integer(2),'b']], multiedges=True)
>>> D.auslander_reiten_quiver()
Auslander-Reiten quiver of Multi-digraph on 2 vertices

center(by_weight=False, algorithm=None, weight_function=None, check_weight=True)[source]#

Return the set of vertices in the center of the DiGraph.

The center is the set of vertices whose eccentricity is equal to the radius of the DiGraph, i.e., achieving the minimum eccentricity.

For more information and examples on how to use input variables, see shortest_paths() and eccentricity()

INPUT:

• by_weight – boolean (default: False); if True, edge weights are taken into account; if False, all edges have weight 1

• algorithm – string (default: None); see method eccentricity() for the list of available algorithms

• weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l as a weight, if l is not None, else 1 as a weight.

• check_weight – boolean (default: True); if True, we check that the weight_function outputs a number for each edge

EXAMPLES:

Every vertex is a center in a Circuit-DiGraph:

sage: G = digraphs.Circuit(9)
sage: G.center()
[0, 1, 2, 3, 4, 5, 6, 7, 8]

>>> from sage.all import *
>>> G = digraphs.Circuit(Integer(9))
>>> G.center()
[0, 1, 2, 3, 4, 5, 6, 7, 8]


Center can be the whole graph:

sage: G.subgraph(G.center()) == G
True

>>> from sage.all import *
>>> G.subgraph(G.center()) == G
True


Some other graphs:

sage: G = digraphs.Path(5)
sage: G.center()
[0]
sage: G = DiGraph([(0,1,2), (1,2,3), (2,0,2)])
sage: G.center(by_weight=True)
[2]

>>> from sage.all import *
>>> G = digraphs.Path(Integer(5))
>>> G.center()
[0]
>>> G = DiGraph([(Integer(0),Integer(1),Integer(2)), (Integer(1),Integer(2),Integer(3)), (Integer(2),Integer(0),Integer(2))])
>>> G.center(by_weight=True)
[2]

degree_polynomial()[source]#

Return the generating polynomial of degrees of vertices in self.

This is the sum

$\sum_{v \in G} x^{\operatorname{in}(v)} y^{\operatorname{out}(v)},$

where in(v) and out(v) are the number of incoming and outgoing edges at vertex $$v$$ in the digraph $$G$$.

Because this polynomial is multiplicative for Cartesian product of digraphs, it is useful to help see if the digraph can be isomorphic to a Cartesian product.

num_verts() for the value at $$(x, y) = (1, 1)$$

EXAMPLES:

sage: G = posets.PentagonPoset().hasse_diagram()                            # needs sage.modules
sage: G.degree_polynomial()                                                 # needs sage.modules
x^2 + 3*x*y + y^2

sage: G = posets.BooleanLattice(4).hasse_diagram()
sage: G.degree_polynomial().factor()                                        # needs sage.libs.pari
(x + y)^4

>>> from sage.all import *
>>> G = posets.PentagonPoset().hasse_diagram()                            # needs sage.modules
>>> G.degree_polynomial()                                                 # needs sage.modules
x^2 + 3*x*y + y^2

>>> G = posets.BooleanLattice(Integer(4)).hasse_diagram()
>>> G.degree_polynomial().factor()                                        # needs sage.libs.pari
(x + y)^4

diameter(by_weight=False, algorithm=None, weight_function=None, check_weight=True)[source]#

Return the diameter of the DiGraph.

The diameter is defined to be the maximum distance between two vertices. It is infinite if the DiGraph is not strongly connected.

For more information and examples on how to use input variables, see shortest_paths() and eccentricity()

INPUT:

• by_weight – boolean (default: False); if True, edge weights are taken into account; if False, all edges have weight 1

• algorithm – string (default: None); one of the following algorithms:

• 'BFS': the computation is done through a BFS centered on each vertex successively. Works only if by_weight==False. It computes all the eccentricities and return the maximum value.

• 'Floyd-Warshall-Cython': a Cython implementation of the Floyd-Warshall algorithm. Works only if by_weight==False. It computes all the eccentricities and return the maximum value.

• 'Floyd-Warshall-Python': a Python implementation of the Floyd-Warshall algorithm. Works also with weighted graphs, even with negative weights (but no negative cycle is allowed). It computes all the eccentricities and return the maximum value.

• 'Dijkstra_NetworkX': the Dijkstra algorithm, implemented in NetworkX. It works with weighted graphs, but no negative weight is allowed. It computes all the eccentricities and return the maximum value.

• 'DiFUB', '2Dsweep': these algorithms are implemented in sage.graphs.distances_all_pairs.diameter() and sage.graphs.base.boost_graph.diameter(). '2Dsweep' returns lower bound on the diameter, while 'DiFUB' returns the exact computed diameter. They also work with negative weight, if there is no negative cycle. See the functions documentation for more information.

• 'standard' : the standard algorithm is implemented in sage.graphs.distances_all_pairs.diameter(). It works only if by_weight==False. See the function documentation for more information. It computes all the eccentricities and return the maximum value.

• 'Dijkstra_Boost': the Dijkstra algorithm, implemented in Boost (works only with positive weights). It computes all the eccentricities and return the maximum value.

• 'Johnson_Boost': the Johnson algorithm, implemented in Boost (works also with negative weights, if there is no negative cycle). It computes all the eccentricities and return the maximum value.

• None (default): Sage chooses the best algorithm: 'DiFUB'.

• weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l, if l is not None, else 1 as weight.

• check_weight – boolean (default: True); if True, we check that the weight_function outputs a number for each edge

EXAMPLES:

sage: # needs sage.combinat
sage: G = digraphs.DeBruijn(5,4)
sage: G.diameter()
4
sage: G = digraphs.GeneralizedDeBruijn(9, 3)
sage: G.diameter()
2

>>> from sage.all import *
>>> # needs sage.combinat
>>> G = digraphs.DeBruijn(Integer(5),Integer(4))
>>> G.diameter()
4
>>> G = digraphs.GeneralizedDeBruijn(Integer(9), Integer(3))
>>> G.diameter()
2

dig6_string()[source]#

Return the dig6 representation of the digraph as an ASCII string.

This is only valid for single (no multiple edges) digraphs on at most $$2^{18} - 1 = 262143$$ vertices.

Note

As the dig6 format only handles graphs with vertex set $$\{0, \ldots, n-1\}$$, a relabelled copy will be encoded, if necessary.

EXAMPLES:

sage: D = DiGraph({0: [1, 2], 1: [2], 2: [3], 3: [0]})
sage: D.dig6_string()
'CW_'

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1), Integer(2)], Integer(1): [Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(0)]})
>>> D.dig6_string()
'CW_'

eccentricity(v=None, by_weight=False, algorithm=None, weight_function=None, check_weight=True, dist_dict=None, with_labels=False)[source]#

Return the eccentricity of vertex (or vertices) v.

The eccentricity of a vertex is the maximum distance to any other vertex.

For more information and examples on how to use input variables, see shortest_path_all_pairs(), shortest_path_lengths() and shortest_paths()

INPUT:

• v – either a single vertex or a list of vertices. If it is not specified, then it is taken to be all vertices.

• by_weight – boolean (default: False); if True, edge weights are taken into account; if False, all edges have weight 1

• algorithm – string (default: None); one of the following algorithms:

• 'BFS' – the computation is done through a BFS centered on each vertex successively. Works only if by_weight==False.

• 'Floyd-Warshall-Cython' – a Cython implementation of the Floyd-Warshall algorithm. Works only if by_weight==False and v is None or v should contain all vertices of self.

• 'Floyd-Warshall-Python' – a Python implementation of the Floyd-Warshall algorithm. Works also with weighted graphs, even with negative weights (but no negative cycle is allowed). However, v must be None or v should contain all vertices of self.

• 'Dijkstra_NetworkX' – the Dijkstra algorithm, implemented in NetworkX. It works with weighted graphs, but no negative weight is allowed.

• 'Dijkstra_Boost' – the Dijkstra algorithm, implemented in Boost (works only with positive weights).

• 'Johnson_Boost' – the Johnson algorithm, implemented in Boost (works also with negative weights, if there is no negative cycle). Works only if v is None or v should contain all vertices of self.

• 'From_Dictionary' – uses the (already computed) distances, that are provided by input variable dist_dict.

• None (default): Sage chooses the best algorithm: 'From_Dictionary' if dist_dict is not None, 'BFS' for unweighted graphs, 'Dijkstra_Boost' if all weights are positive, 'Johnson_Boost' otherwise.

• weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l, if l is not None, else 1 as a weight.

• check_weight – boolean (default: True); if True, we check that the weight_function outputs a number for each edge

• dist_dict – a dictionary (default: None); a dict of dicts of distances (used only if algorithm=='From_Dictionary')

• with_labels – boolean (default: False); whether to return a list or a dictionary keyed by vertices.

EXAMPLES:

sage: G = graphs.KrackhardtKiteGraph().to_directed()
sage: G.eccentricity()
[4, 4, 4, 4, 4, 3, 3, 2, 3, 4]
sage: G.vertices(sort=True)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: G.eccentricity(7)
2
sage: G.eccentricity([7,8,9])
[2, 3, 4]
sage: G.eccentricity([7,8,9], with_labels=True) == {8: 3, 9: 4, 7: 2}
True
sage: G = DiGraph(3)
sage: G.eccentricity(with_labels=True)
{0: +Infinity, 1: +Infinity, 2: +Infinity}
sage: G = DiGraph({0:[]})
sage: G.eccentricity(with_labels=True)
{0: 0}
sage: G = DiGraph([(0,1,2), (1,2,3), (2,0,2)])
sage: G.eccentricity(algorithm='BFS')
[2, 2, 2]
sage: G.eccentricity(algorithm='Floyd-Warshall-Cython')
[2, 2, 2]
sage: G.eccentricity(by_weight=True, algorithm='Dijkstra_NetworkX')         # needs networkx
[5, 5, 4]
sage: G.eccentricity(by_weight=True, algorithm='Dijkstra_Boost')
[5, 5, 4]
sage: G.eccentricity(by_weight=True, algorithm='Johnson_Boost')
[5, 5, 4]
sage: G.eccentricity(by_weight=True, algorithm='Floyd-Warshall-Python')
[5, 5, 4]
sage: G.eccentricity(dist_dict=G.shortest_path_all_pairs(by_weight=True)[0])
[5, 5, 4]

>>> from sage.all import *
>>> G = graphs.KrackhardtKiteGraph().to_directed()
>>> G.eccentricity()
[4, 4, 4, 4, 4, 3, 3, 2, 3, 4]
>>> G.vertices(sort=True)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> G.eccentricity(Integer(7))
2
>>> G.eccentricity([Integer(7),Integer(8),Integer(9)])
[2, 3, 4]
>>> G.eccentricity([Integer(7),Integer(8),Integer(9)], with_labels=True) == {Integer(8): Integer(3), Integer(9): Integer(4), Integer(7): Integer(2)}
True
>>> G = DiGraph(Integer(3))
>>> G.eccentricity(with_labels=True)
{0: +Infinity, 1: +Infinity, 2: +Infinity}
>>> G = DiGraph({Integer(0):[]})
>>> G.eccentricity(with_labels=True)
{0: 0}
>>> G = DiGraph([(Integer(0),Integer(1),Integer(2)), (Integer(1),Integer(2),Integer(3)), (Integer(2),Integer(0),Integer(2))])
>>> G.eccentricity(algorithm='BFS')
[2, 2, 2]
>>> G.eccentricity(algorithm='Floyd-Warshall-Cython')
[2, 2, 2]
>>> G.eccentricity(by_weight=True, algorithm='Dijkstra_NetworkX')         # needs networkx
[5, 5, 4]
>>> G.eccentricity(by_weight=True, algorithm='Dijkstra_Boost')
[5, 5, 4]
>>> G.eccentricity(by_weight=True, algorithm='Johnson_Boost')
[5, 5, 4]
>>> G.eccentricity(by_weight=True, algorithm='Floyd-Warshall-Python')
[5, 5, 4]
>>> G.eccentricity(dist_dict=G.shortest_path_all_pairs(by_weight=True)[Integer(0)])
[5, 5, 4]

feedback_edge_set(constraint_generation, value_only=True, solver=False, verbose=None, integrality_tolerance=0)[source]#

Compute the minimum feedback edge set of a digraph (also called feedback arc set).

The minimum feedback edge set of a digraph is a set of edges that intersect all the circuits of the digraph. Equivalently, a minimum feedback arc set of a DiGraph is a set $$S$$ of arcs such that the digraph $$G - S$$ is acyclic. For more information, see the Wikipedia article Feedback_arc_set.

INPUT:

• value_only – boolean (default: False)

• When set to True, only the minimum cardinal of a minimum edge set is returned.

• When set to False, the Set of edges of a minimal edge set is returned.

• constraint_generation – boolean (default: True); whether to use constraint generation when solving the Mixed Integer Linear Program.

• solver – string (default: None); specify 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().

ALGORITHM:

This problem is solved using Linear Programming, in two different ways. The first one is to solve the following formulation:

$\begin{split}\mbox{Minimize : }&\sum_{(u,v)\in G} b_{(u,v)}\\ \mbox{Such that : }&\\ &\forall (u,v)\in G, d_u-d_v+ n \cdot b_{(u,v)}\geq 0\\ &\forall u\in G, 0\leq d_u\leq |G|\\\end{split}$

An explanation:

An acyclic digraph can be seen as a poset, and every poset has a linear extension. This means that in any acyclic digraph the vertices can be ordered with a total order $$<$$ in such a way that if $$(u,v) \in G$$, then $$u < v$$.

Thus, this linear program is built in order to assign to each vertex $$v$$ a number $$d_v \in [0,\dots,n-1]$$ such that if there exists an edge $$(u, v) \in G$$ such that $$d_v < d_u$$, then the edge $$(u,v)$$ is removed.

The number of edges removed is then minimized, which is the objective.

(Constraint Generation)

If the parameter constraint_generation is enabled, a more efficient formulation is used :

$\begin{split}\mbox{Minimize : }&\sum_{(u,v)\in G} b_{(u,v)}\\ \mbox{Such that : }&\\ &\forall C\text{ circuits }\subseteq G, \sum_{uv\in C}b_{(u,v)}\geq 1\\\end{split}$

As the number of circuits contained in a graph is exponential, this LP is solved through constraint generation. This means that the solver is sequentially asked to solved the problem, knowing only a portion of the circuits contained in $$G$$, each time adding to the list of its constraints the circuit which its last answer had left intact.

EXAMPLES:

If the digraph is created from a graph, and hence is symmetric (if $$uv$$ is an edge, then $$vu$$ is an edge too), then obviously the cardinality of its feedback arc set is the number of edges in the first graph:

sage: cycle = graphs.CycleGraph(5)
sage: dcycle = DiGraph(cycle)
sage: cycle.size()
5
sage: dcycle.feedback_edge_set(value_only=True)                             # needs sage.numerical.mip
5

>>> from sage.all import *
>>> cycle = graphs.CycleGraph(Integer(5))
>>> dcycle = DiGraph(cycle)
>>> cycle.size()
5
>>> dcycle.feedback_edge_set(value_only=True)                             # needs sage.numerical.mip
5


And in this situation, for any edge $$uv$$ of the first graph, $$uv$$ of $$vu$$ is in the returned feedback arc set:

sage: g = graphs.RandomGNP(5,.3)
sage: while not g.num_edges():
....:     g = graphs.RandomGNP(5,.3)
sage: dg = DiGraph(g)
sage: feedback = dg.feedback_edge_set()                                      # needs sage.numerical.mip
sage: u,v,l = next(g.edge_iterator())
sage: (u,v) in feedback or (v,u) in feedback                                 # needs sage.numerical.mip
True

>>> from sage.all import *
>>> g = graphs.RandomGNP(Integer(5),RealNumber('.3'))
>>> while not g.num_edges():
...     g = graphs.RandomGNP(Integer(5),RealNumber('.3'))
>>> dg = DiGraph(g)
>>> feedback = dg.feedback_edge_set()                                      # needs sage.numerical.mip
>>> u,v,l = next(g.edge_iterator())
>>> (u,v) in feedback or (v,u) in feedback                                 # needs sage.numerical.mip
True

flow_polytope(edges=None, ends=None, backend=None)[source]#

Return the flow polytope of a digraph.

The flow polytope of a directed graph is the polytope consisting of all nonnegative flows on the graph with a given set $$S$$ of sources and a given set $$T$$ of sinks.

A flow on a directed graph $$G$$ with a given set $$S$$ of sources and a given set $$T$$ of sinks means an assignment of a nonnegative real to each edge of $$G$$ such that the flow is conserved in each vertex outside of $$S$$ and $$T$$, and there is a unit of flow entering each vertex in $$S$$ and a unit of flow leaving each vertex in $$T$$. These flows clearly form a polytope in the space of all assignments of reals to the edges of $$G$$.

The polytope is empty unless the sets $$S$$ and $$T$$ are equinumerous.

By default, $$S$$ is taken to be the set of all sources (i.e., vertices of indegree $$0$$) of $$G$$, and $$T$$ is taken to be the set of all sinks (i.e., vertices of outdegree $$0$$) of $$G$$. If a different choice of $$S$$ and $$T$$ is desired, it can be specified using the optional ends parameter.

The polytope is returned as a polytope in $$\RR^m$$, where $$m$$ is the number of edges of the digraph self. The $$k$$-th coordinate of a point in the polytope is the real assigned to the $$k$$-th edge of self. The order of the edges is the one returned by self.edges(sort=True). If a different order is desired, it can be specified using the optional edges parameter.

The faces and volume of these polytopes are of interest. Examples of these polytopes are the Chan-Robbins-Yuen polytope and the Pitman-Stanley polytope [PS2002].

INPUT:

• edges – list (default: None); a list of edges of self. If not specified, the list of all edges of self is used with the default ordering of self.edges(sort=True). This determines which coordinate of a point in the polytope will correspond to which edge of self. It is also possible to specify a list which contains not all edges of self; this results in a polytope corresponding to the flows which are $$0$$ on all remaining edges. Notice that the edges entered here must be in the precisely same format as outputted by self.edges(); so, if self.edges() outputs an edge in the form (1, 3, None), then (1, 3) will not do!

• ends – (default: (self.sources(), self.sinks())) a pair $$(S, T)$$ of an iterable $$S$$ and an iterable $$T$$.

• backend – string or None (default); the backend to use; see sage.geometry.polyhedron.constructor.Polyhedron()

Note

Flow polytopes can also be built through the polytopes.<tab> object:

sage: polytopes.flow_polytope(digraphs.Path(5))                         # needs sage.geometry.polyhedron
A 0-dimensional polyhedron in QQ^4 defined as the convex hull of 1 vertex

>>> from sage.all import *
>>> polytopes.flow_polytope(digraphs.Path(Integer(5)))                         # needs sage.geometry.polyhedron
A 0-dimensional polyhedron in QQ^4 defined as the convex hull of 1 vertex


EXAMPLES:

A commutative square:

sage: G = DiGraph({1: [2, 3], 2: [4], 3: [4]})
sage: fl = G.flow_polytope(); fl                                            # needs sage.geometry.polyhedron
A 1-dimensional polyhedron in QQ^4 defined as the convex hull
of 2 vertices
sage: fl.vertices()                                                         # needs sage.geometry.polyhedron
(A vertex at (0, 1, 0, 1), A vertex at (1, 0, 1, 0))

>>> from sage.all import *
>>> G = DiGraph({Integer(1): [Integer(2), Integer(3)], Integer(2): [Integer(4)], Integer(3): [Integer(4)]})
>>> fl = G.flow_polytope(); fl                                            # needs sage.geometry.polyhedron
A 1-dimensional polyhedron in QQ^4 defined as the convex hull
of 2 vertices
>>> fl.vertices()                                                         # needs sage.geometry.polyhedron
(A vertex at (0, 1, 0, 1), A vertex at (1, 0, 1, 0))


Using a different order for the edges of the graph:

sage: ordered_edges = G.edges(sort=True, key=lambda x: x[0] - x[1])
sage: fl = G.flow_polytope(edges=ordered_edges); fl                         # needs sage.geometry.polyhedron
A 1-dimensional polyhedron in QQ^4 defined as the convex hull of 2 vertices
sage: fl.vertices()                                                         # needs sage.geometry.polyhedron
(A vertex at (0, 1, 1, 0), A vertex at (1, 0, 0, 1))

>>> from sage.all import *
>>> ordered_edges = G.edges(sort=True, key=lambda x: x[Integer(0)] - x[Integer(1)])
>>> fl = G.flow_polytope(edges=ordered_edges); fl                         # needs sage.geometry.polyhedron
A 1-dimensional polyhedron in QQ^4 defined as the convex hull of 2 vertices
>>> fl.vertices()                                                         # needs sage.geometry.polyhedron
(A vertex at (0, 1, 1, 0), A vertex at (1, 0, 0, 1))


A tournament on 4 vertices:

sage: H = digraphs.TransitiveTournament(4)
sage: fl = H.flow_polytope(); fl                                            # needs sage.geometry.polyhedron
A 3-dimensional polyhedron in QQ^6 defined as the convex hull
of 4 vertices
sage: fl.vertices()                                                         # needs sage.geometry.polyhedron
(A vertex at (0, 0, 1, 0, 0, 0),
A vertex at (0, 1, 0, 0, 0, 1),
A vertex at (1, 0, 0, 0, 1, 0),
A vertex at (1, 0, 0, 1, 0, 1))

>>> from sage.all import *
>>> H = digraphs.TransitiveTournament(Integer(4))
>>> fl = H.flow_polytope(); fl                                            # needs sage.geometry.polyhedron
A 3-dimensional polyhedron in QQ^6 defined as the convex hull
of 4 vertices
>>> fl.vertices()                                                         # needs sage.geometry.polyhedron
(A vertex at (0, 0, 1, 0, 0, 0),
A vertex at (0, 1, 0, 0, 0, 1),
A vertex at (1, 0, 0, 0, 1, 0),
A vertex at (1, 0, 0, 1, 0, 1))


Restricting to a subset of the edges:

sage: fl = H.flow_polytope(edges=[(0, 1, None), (1, 2, None),               # needs sage.geometry.polyhedron
....:                             (2, 3, None), (0, 3, None)]); fl
A 1-dimensional polyhedron in QQ^4 defined as the convex hull
of 2 vertices
sage: fl.vertices()                                                         # needs sage.geometry.polyhedron
(A vertex at (0, 0, 0, 1), A vertex at (1, 1, 1, 0))

>>> from sage.all import *
>>> fl = H.flow_polytope(edges=[(Integer(0), Integer(1), None), (Integer(1), Integer(2), None),               # needs sage.geometry.polyhedron
...                             (Integer(2), Integer(3), None), (Integer(0), Integer(3), None)]); fl
A 1-dimensional polyhedron in QQ^4 defined as the convex hull
of 2 vertices
>>> fl.vertices()                                                         # needs sage.geometry.polyhedron
(A vertex at (0, 0, 0, 1), A vertex at (1, 1, 1, 0))


Using a different choice of sources and sinks:

sage: # needs sage.geometry.polyhedron
sage: fl = H.flow_polytope(ends=([1], [3])); fl
A 1-dimensional polyhedron in QQ^6 defined as the convex hull
of 2 vertices
sage: fl.vertices()
(A vertex at (0, 0, 0, 1, 0, 1), A vertex at (0, 0, 0, 0, 1, 0))
sage: fl = H.flow_polytope(ends=([0, 1], [3])); fl
The empty polyhedron in QQ^6
sage: fl = H.flow_polytope(ends=([3], [0])); fl
The empty polyhedron in QQ^6
sage: fl = H.flow_polytope(ends=([0, 1], [2, 3])); fl
A 3-dimensional polyhedron in QQ^6 defined as the convex hull
of 5 vertices
sage: fl.vertices()
(A vertex at (0, 0, 1, 1, 0, 0),
A vertex at (0, 1, 0, 0, 1, 0),
A vertex at (1, 0, 0, 2, 0, 1),
A vertex at (1, 0, 0, 1, 1, 0),
A vertex at (0, 1, 0, 1, 0, 1))
sage: fl = H.flow_polytope(edges=[(0, 1, None), (1, 2, None),
....:                             (2, 3, None), (0, 2, None),
....:                             (1, 3, None)],
....:                      ends=([0, 1], [2, 3])); fl
A 2-dimensional polyhedron in QQ^5 defined as the convex hull
of 4 vertices
sage: fl.vertices()
(A vertex at (0, 0, 0, 1, 1),
A vertex at (1, 2, 1, 0, 0),
A vertex at (1, 1, 0, 0, 1),
A vertex at (0, 1, 1, 1, 0))

>>> from sage.all import *
>>> # needs sage.geometry.polyhedron
>>> fl = H.flow_polytope(ends=([Integer(1)], [Integer(3)])); fl
A 1-dimensional polyhedron in QQ^6 defined as the convex hull
of 2 vertices
>>> fl.vertices()
(A vertex at (0, 0, 0, 1, 0, 1), A vertex at (0, 0, 0, 0, 1, 0))
>>> fl = H.flow_polytope(ends=([Integer(0), Integer(1)], [Integer(3)])); fl
The empty polyhedron in QQ^6
>>> fl = H.flow_polytope(ends=([Integer(3)], [Integer(0)])); fl
The empty polyhedron in QQ^6
>>> fl = H.flow_polytope(ends=([Integer(0), Integer(1)], [Integer(2), Integer(3)])); fl
A 3-dimensional polyhedron in QQ^6 defined as the convex hull
of 5 vertices
>>> fl.vertices()
(A vertex at (0, 0, 1, 1, 0, 0),
A vertex at (0, 1, 0, 0, 1, 0),
A vertex at (1, 0, 0, 2, 0, 1),
A vertex at (1, 0, 0, 1, 1, 0),
A vertex at (0, 1, 0, 1, 0, 1))
>>> fl = H.flow_polytope(edges=[(Integer(0), Integer(1), None), (Integer(1), Integer(2), None),
...                             (Integer(2), Integer(3), None), (Integer(0), Integer(2), None),
...                             (Integer(1), Integer(3), None)],
...                      ends=([Integer(0), Integer(1)], [Integer(2), Integer(3)])); fl
A 2-dimensional polyhedron in QQ^5 defined as the convex hull
of 4 vertices
>>> fl.vertices()
(A vertex at (0, 0, 0, 1, 1),
A vertex at (1, 2, 1, 0, 0),
A vertex at (1, 1, 0, 0, 1),
A vertex at (0, 1, 1, 1, 0))


A digraph with one source and two sinks:

sage: Y = DiGraph({1: [2], 2: [3, 4]})
sage: Y.flow_polytope()                                                     # needs sage.geometry.polyhedron
The empty polyhedron in QQ^3

>>> from sage.all import *
>>> Y = DiGraph({Integer(1): [Integer(2)], Integer(2): [Integer(3), Integer(4)]})
>>> Y.flow_polytope()                                                     # needs sage.geometry.polyhedron
The empty polyhedron in QQ^3


A digraph with one vertex and no edge:

sage: Z = DiGraph({1: []})
sage: Z.flow_polytope()                                                     # needs sage.geometry.polyhedron
A 0-dimensional polyhedron in QQ^0 defined as the convex hull
of 1 vertex

>>> from sage.all import *
>>> Z = DiGraph({Integer(1): []})
>>> Z.flow_polytope()                                                     # needs sage.geometry.polyhedron
A 0-dimensional polyhedron in QQ^0 defined as the convex hull
of 1 vertex


A digraph with multiple edges (Issue #28837):

sage: G = DiGraph([(0, 1), (0,1)], multiedges=True); G
Multi-digraph on 2 vertices
sage: P = G.flow_polytope(); P                                              # needs sage.geometry.polyhedron
A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices
sage: P.vertices()                                                          # needs sage.geometry.polyhedron
(A vertex at (1, 0), A vertex at (0, 1))
sage: P.lines()                                                             # needs sage.geometry.polyhedron
()

>>> from sage.all import *
>>> G = DiGraph([(Integer(0), Integer(1)), (Integer(0),Integer(1))], multiedges=True); G
Multi-digraph on 2 vertices
>>> P = G.flow_polytope(); P                                              # needs sage.geometry.polyhedron
A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices
>>> P.vertices()                                                          # needs sage.geometry.polyhedron
(A vertex at (1, 0), A vertex at (0, 1))
>>> P.lines()                                                             # needs sage.geometry.polyhedron
()

in_branchings(source, spanning=True)[source]#

Return an iterator over the in branchings rooted at given vertex in self.

An in-branching is a directed tree rooted at source whose arcs are directed to source from leaves. An in-branching is spanning if it contains all vertices of the digraph.

If no spanning in branching rooted at source exist, raises ValueError or return non spanning in branching rooted at source, depending on the value of spanning.

INPUT:

• source – vertex used as the source for all in branchings.

• spanning – boolean (default: True); if False return maximum in branching to source. Otherwise, return spanning in branching if exists.

OUTPUT:

An iterator over the in branchings rooted in the given source.

ALGORITHM:

Recursively computes all in branchings.

At each step:

1. clean the graph (see below)

2. pick an edge e incoming to source

3. find all in branchings that do not contain e by first removing it

4. find all in branchings that do contain e by first merging the end vertices of e

Cleaning the graph implies to remove loops and replace multiedges by a single one with an appropriate label since these lead to similar steps of computation.

EXAMPLES:

A bidirectional 4-cycle:

sage: G = DiGraph({1:[2,3], 2:[1,4], 3:[1,4], 4:[2,3]}, format='dict_of_lists')
sage: list(G.in_branchings(1))
[Digraph on 4 vertices,
Digraph on 4 vertices,
Digraph on 4 vertices,
Digraph on 4 vertices]

>>> from sage.all import *
>>> G = DiGraph({Integer(1):[Integer(2),Integer(3)], Integer(2):[Integer(1),Integer(4)], Integer(3):[Integer(1),Integer(4)], Integer(4):[Integer(2),Integer(3)]}, format='dict_of_lists')
>>> list(G.in_branchings(Integer(1)))
[Digraph on 4 vertices,
Digraph on 4 vertices,
Digraph on 4 vertices,
Digraph on 4 vertices]


With the Petersen graph turned into a symmetric directed graph:

sage: G = graphs.PetersenGraph().to_directed()
sage: len(list(G.in_branchings(0)))
2000

>>> from sage.all import *
>>> G = graphs.PetersenGraph().to_directed()
>>> len(list(G.in_branchings(Integer(0))))
2000


With a non connected DiGraph and spanning = True:

sage: G = graphs.PetersenGraph().to_directed() + graphs.PetersenGraph().to_directed()
sage: G.in_branchings(0)
Traceback (most recent call last):
...
ValueError: no spanning in branching to vertex (0) exist

>>> from sage.all import *
>>> G = graphs.PetersenGraph().to_directed() + graphs.PetersenGraph().to_directed()
>>> G.in_branchings(Integer(0))
Traceback (most recent call last):
...
ValueError: no spanning in branching to vertex (0) exist


With a non connected DiGraph and spanning = False:

sage: g=DiGraph([(1,0), (1,0), (2,1), (3,4)],multiedges=True)
sage: list(g.in_branchings(0,spanning=False))
[Digraph on 3 vertices, Digraph on 3 vertices]

>>> from sage.all import *
>>> g=DiGraph([(Integer(1),Integer(0)), (Integer(1),Integer(0)), (Integer(2),Integer(1)), (Integer(3),Integer(4))],multiedges=True)
>>> list(g.in_branchings(Integer(0),spanning=False))
[Digraph on 3 vertices, Digraph on 3 vertices]


With multiedges:

sage: G = DiGraph({0:[1,1,1], 1:[2,2]}, format='dict_of_lists', multiedges=True)
sage: len(list(G.in_branchings(2)))
6

>>> from sage.all import *
>>> G = DiGraph({Integer(0):[Integer(1),Integer(1),Integer(1)], Integer(1):[Integer(2),Integer(2)]}, format='dict_of_lists', multiedges=True)
>>> len(list(G.in_branchings(Integer(2))))
6


With a DiGraph already being a spanning in branching:

sage: G = DiGraph({0:[], 1:[0], 2:[0], 3:[1], 4:[1], 5:[2]}, format='dict_of_lists')
sage: next(G.in_branchings(0)) == G
True

>>> from sage.all import *
>>> G = DiGraph({Integer(0):[], Integer(1):[Integer(0)], Integer(2):[Integer(0)], Integer(3):[Integer(1)], Integer(4):[Integer(1)], Integer(5):[Integer(2)]}, format='dict_of_lists')
>>> next(G.in_branchings(Integer(0))) == G
True

in_degree(vertices=None, labels=False)[source]#

Same as degree, but for in degree.

EXAMPLES:

sage: D = DiGraph({0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1]})
sage: D.in_degree(vertices=[0, 1, 2], labels=True)
{0: 2, 1: 2, 2: 2}
sage: D.in_degree()
[2, 2, 2, 2, 1, 1]
sage: G = graphs.PetersenGraph().to_directed()
sage: G.in_degree(0)
3

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1),Integer(2),Integer(3)], Integer(1): [Integer(0),Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(4)], Integer(4): [Integer(0),Integer(5)], Integer(5): [Integer(1)]})
>>> D.in_degree(vertices=[Integer(0), Integer(1), Integer(2)], labels=True)
{0: 2, 1: 2, 2: 2}
>>> D.in_degree()
[2, 2, 2, 2, 1, 1]
>>> G = graphs.PetersenGraph().to_directed()
>>> G.in_degree(Integer(0))
3

in_degree_iterator(vertices=None, labels=False)[source]#

Same as degree_iterator, but for in degree.

EXAMPLES:

sage: D = graphs.Grid2dGraph(2,4).to_directed()
sage: sorted(D.in_degree_iterator())
[2, 2, 2, 2, 3, 3, 3, 3]
sage: sorted(D.in_degree_iterator(labels=True))
[((0, 0), 2),
((0, 1), 3),
((0, 2), 3),
((0, 3), 2),
((1, 0), 2),
((1, 1), 3),
((1, 2), 3),
((1, 3), 2)]

>>> from sage.all import *
>>> D = graphs.Grid2dGraph(Integer(2),Integer(4)).to_directed()
>>> sorted(D.in_degree_iterator())
[2, 2, 2, 2, 3, 3, 3, 3]
>>> sorted(D.in_degree_iterator(labels=True))
[((0, 0), 2),
((0, 1), 3),
((0, 2), 3),
((0, 3), 2),
((1, 0), 2),
((1, 1), 3),
((1, 2), 3),
((1, 3), 2)]

in_degree_sequence()[source]#

Return the in-degree sequence.

EXAMPLES:

The in-degree sequences of two digraphs:

sage: g = DiGraph({1: [2, 5, 6], 2: [3, 6], 3: [4, 6], 4: [6], 5: [4, 6]})
sage: g.in_degree_sequence()
[5, 2, 1, 1, 1, 0]

>>> from sage.all import *
>>> g = DiGraph({Integer(1): [Integer(2), Integer(5), Integer(6)], Integer(2): [Integer(3), Integer(6)], Integer(3): [Integer(4), Integer(6)], Integer(4): [Integer(6)], Integer(5): [Integer(4), Integer(6)]})
>>> g.in_degree_sequence()
[5, 2, 1, 1, 1, 0]

sage: V = [2, 3, 5, 7, 8, 9, 10, 11]
sage: E = [[], [8, 10], [11], [8, 11], [9], [], [], [2, 9, 10]]
sage: g = DiGraph(dict(zip(V, E)))
sage: g.in_degree_sequence()
[2, 2, 2, 2, 1, 0, 0, 0]

>>> from sage.all import *
>>> V = [Integer(2), Integer(3), Integer(5), Integer(7), Integer(8), Integer(9), Integer(10), Integer(11)]
>>> E = [[], [Integer(8), Integer(10)], [Integer(11)], [Integer(8), Integer(11)], [Integer(9)], [], [], [Integer(2), Integer(9), Integer(10)]]
>>> g = DiGraph(dict(zip(V, E)))
>>> g.in_degree_sequence()
[2, 2, 2, 2, 1, 0, 0, 0]

incoming_edge_iterator(vertices, labels=True)[source]#

Return an iterator over all arriving edges from vertices.

INPUT:

• vertices – a vertex or a list of vertices

• labels – boolean (default: True); whether to return edges as pairs of vertices, or as triples containing the labels

EXAMPLES:

sage: D = DiGraph({0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1]})
sage: for a in D.incoming_edge_iterator([0]):
....:     print(a)
(1, 0, None)
(4, 0, None)

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1),Integer(2),Integer(3)], Integer(1): [Integer(0),Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(4)], Integer(4): [Integer(0),Integer(5)], Integer(5): [Integer(1)]})
>>> for a in D.incoming_edge_iterator([Integer(0)]):
...     print(a)
(1, 0, None)
(4, 0, None)

incoming_edges(vertices, labels=True)[source]#

Return a list of edges arriving at vertices.

INPUT:

• vertices – a vertex or a list of vertices

• labels – boolean (default: True); whether to return edges as pairs of vertices, or as triples containing the labels.

EXAMPLES:

sage: D = DiGraph({0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1]})
sage: D.incoming_edges([0])
[(1, 0, None), (4, 0, None)]

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1),Integer(2),Integer(3)], Integer(1): [Integer(0),Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(4)], Integer(4): [Integer(0),Integer(5)], Integer(5): [Integer(1)]})
>>> D.incoming_edges([Integer(0)])
[(1, 0, None), (4, 0, None)]

is_aperiodic()[source]#

Return whether the current DiGraph is aperiodic.

A directed graph is aperiodic if there is no integer $$k > 1$$ that divides the length of every cycle in the graph. See the Wikipedia article Aperiodic_graph for more information.

EXAMPLES:

The following graph has period 2, so it is not aperiodic:

sage: g = DiGraph({0: [1], 1: [0]})
sage: g.is_aperiodic()
False

>>> from sage.all import *
>>> g = DiGraph({Integer(0): [Integer(1)], Integer(1): [Integer(0)]})
>>> g.is_aperiodic()
False


The following graph has a cycle of length 2 and a cycle of length 3, so it is aperiodic:

sage: g = DiGraph({0: [1, 4], 1: [2], 2: [0], 4: [0]})
sage: g.is_aperiodic()
True

>>> from sage.all import *
>>> g = DiGraph({Integer(0): [Integer(1), Integer(4)], Integer(1): [Integer(2)], Integer(2): [Integer(0)], Integer(4): [Integer(0)]})
>>> g.is_aperiodic()
True

is_directed()[source]#

Since digraph is directed, return True.

EXAMPLES:

sage: DiGraph().is_directed()
True

>>> from sage.all import *
>>> DiGraph().is_directed()
True

is_directed_acyclic(certificate=False)[source]#

Check whether the digraph is acyclic or not.

A directed graph is acyclic if for any vertex $$v$$, there is no directed path that starts and ends at $$v$$. Every directed acyclic graph (DAG) corresponds to a partial ordering of its vertices, however multiple dags may lead to the same partial ordering.

INPUT:

• certificate – boolean (default: False); whether to return a certificate

OUTPUT:

• When certificate=False, returns a boolean value.

• When certificate=True:

• If the graph is acyclic, returns a pair (True, ordering) where ordering is a list of the vertices such that $$u$$ appears before $$v$$ in ordering if $$uv$$ is an edge.

• Else, returns a pair (False, cycle) where cycle is a list of vertices representing a circuit in the graph.

EXAMPLES:

At first, the following graph is acyclic:

sage: D = DiGraph({0:[1, 2, 3], 4:[2, 5], 1:[8], 2:[7], 3:[7], 5:[6,7], 7:[8], 6:[9], 8:[10], 9:[10]})
sage: D.plot(layout='circular').show()                                      # needs sage.plot
sage: D.is_directed_acyclic()
True

>>> from sage.all import *
>>> D = DiGraph({Integer(0):[Integer(1), Integer(2), Integer(3)], Integer(4):[Integer(2), Integer(5)], Integer(1):[Integer(8)], Integer(2):[Integer(7)], Integer(3):[Integer(7)], Integer(5):[Integer(6),Integer(7)], Integer(7):[Integer(8)], Integer(6):[Integer(9)], Integer(8):[Integer(10)], Integer(9):[Integer(10)]})
>>> D.plot(layout='circular').show()                                      # needs sage.plot
>>> D.is_directed_acyclic()
True


Adding an edge from $$9$$ to $$7$$ does not change it:

sage: D.add_edge(9, 7)
sage: D.is_directed_acyclic()
True

>>> from sage.all import *
>>> D.is_directed_acyclic()
True


We can obtain as a proof an ordering of the vertices such that $$u$$ appears before $$v$$ if $$uv$$ is an edge of the graph:

sage: D.is_directed_acyclic(certificate=True)
(True, [4, 5, 6, 9, 0, 1, 2, 3, 7, 8, 10])

>>> from sage.all import *
>>> D.is_directed_acyclic(certificate=True)
(True, [4, 5, 6, 9, 0, 1, 2, 3, 7, 8, 10])


Adding an edge from 7 to 4, though, makes a difference:

sage: D.add_edge(7, 4)
sage: D.is_directed_acyclic()
False

>>> from sage.all import *
>>> D.is_directed_acyclic()
False


Indeed, it creates a circuit $$7, 4, 5$$:

sage: D.is_directed_acyclic(certificate=True)
(False, [7, 4, 5])

>>> from sage.all import *
>>> D.is_directed_acyclic(certificate=True)
(False, [7, 4, 5])


Checking acyclic graphs are indeed acyclic

sage: def random_acyclic(n, p):
....:  g = graphs.RandomGNP(n, p)
....:  h = DiGraph()
....:  h.add_edges(((u, v) if u < v else (v, u)) for u, v in g.edge_iterator(labels=False))
....:  return h
...
sage: all(random_acyclic(100, .2).is_directed_acyclic()    # long time
....:      for i in range(50))
True

>>> from sage.all import *
>>> def random_acyclic(n, p):
...  g = graphs.RandomGNP(n, p)
...  h = DiGraph()
...  h.add_edges(((u, v) if u < v else (v, u)) for u, v in g.edge_iterator(labels=False))
...  return h
...
>>> all(random_acyclic(Integer(100), RealNumber('.2')).is_directed_acyclic()    # long time
...      for i in range(Integer(50)))
True

is_strongly_connected(G)[source]#

Check whether the current DiGraph is strongly connected.

EXAMPLES:

The circuit is obviously strongly connected:

sage: from sage.graphs.connectivity import is_strongly_connected
sage: g = digraphs.Circuit(5)
sage: is_strongly_connected(g)
True
sage: g.is_strongly_connected()
True

>>> from sage.all import *
>>> from sage.graphs.connectivity import is_strongly_connected
>>> g = digraphs.Circuit(Integer(5))
>>> is_strongly_connected(g)
True
>>> g.is_strongly_connected()
True


But a transitive triangle is not:

sage: g = DiGraph({0: [1, 2], 1: [2]})
sage: is_strongly_connected(g)
False

>>> from sage.all import *
>>> g = DiGraph({Integer(0): [Integer(1), Integer(2)], Integer(1): [Integer(2)]})
>>> is_strongly_connected(g)
False

is_tournament()[source]#

Check whether the digraph is a tournament.

A tournament is a digraph in which each pair of distinct vertices is connected by a single arc.

EXAMPLES:

sage: g = digraphs.RandomTournament(6)
sage: g.is_tournament()
True
sage: u,v = next(g.edge_iterator(labels=False))
sage: g.is_tournament()
False
sage: g.is_tournament()
False

>>> from sage.all import *
>>> g = digraphs.RandomTournament(Integer(6))
>>> g.is_tournament()
True
>>> u,v = next(g.edge_iterator(labels=False))
>>> g.is_tournament()
False
>>> g.is_tournament()
False

is_transitive(g, certificate=False)[source]#

Tests whether the digraph is transitive.

A digraph is transitive if for any pair of vertices $$u,v\in G$$ linked by a $$uv$$-path the edge $$uv$$ belongs to $$G$$.

INPUT:

• certificate – whether to return a certificate for negative answers.

• If certificate = False (default), this method returns True or False according to the graph.

• If certificate = True, this method either returns True answers or yield a pair of vertices $$uv$$ such that there exists a $$uv$$-path in $$G$$ but $$uv\not\in G$$.

EXAMPLES:

sage: digraphs.Circuit(4).is_transitive()
False
sage: digraphs.Circuit(4).is_transitive(certificate=True)
(0, 2)
sage: digraphs.RandomDirectedGNP(30,.2).is_transitive()
False
sage: D = digraphs.DeBruijn(5, 2)                                               # needs sage.combinat
sage: D.is_transitive()                                                         # needs sage.combinat
False
sage: cert = D.is_transitive(certificate=True)                                  # needs sage.combinat
sage: D.has_edge(*cert)                                                         # needs sage.combinat
False
sage: bool(D.shortest_path(*cert))                                              # needs sage.combinat
True
sage: digraphs.RandomDirectedGNP(20,.2).transitive_closure().is_transitive()    # needs networkx
True

>>> from sage.all import *
>>> digraphs.Circuit(Integer(4)).is_transitive()
False
>>> digraphs.Circuit(Integer(4)).is_transitive(certificate=True)
(0, 2)
>>> digraphs.RandomDirectedGNP(Integer(30),RealNumber('.2')).is_transitive()
False
>>> D = digraphs.DeBruijn(Integer(5), Integer(2))                                               # needs sage.combinat
>>> D.is_transitive()                                                         # needs sage.combinat
False
>>> cert = D.is_transitive(certificate=True)                                  # needs sage.combinat
>>> D.has_edge(*cert)                                                         # needs sage.combinat
False
>>> bool(D.shortest_path(*cert))                                              # needs sage.combinat
True
>>> digraphs.RandomDirectedGNP(Integer(20),RealNumber('.2')).transitive_closure().is_transitive()    # needs networkx
True

layout_acyclic(rankdir='up', **options)[source]#

Return a ranked layout so that all edges point upward.

To this end, the heights of the vertices are set according to the level set decomposition of the graph (see level_sets()).

This is achieved by calling graphviz and dot2tex if available (see layout_graphviz()), and using a spring layout with fixed vertical placement of the vertices otherwise (see layout_acyclic_dummy() and layout_ranked()).

Non acyclic graphs are partially supported by graphviz, which then chooses some edges to point down.

INPUT:

• rankdir – string (default: 'up'); indicates which direction the edges should point toward among 'up', 'down', 'left', or 'right'

• **options – passed down to layout_ranked() or layout_graphviz()

EXAMPLES:

sage: H = DiGraph({0: [1, 2], 1: [3], 2: [3], 3: [], 5: [1, 6], 6: [2, 3]})

>>> from sage.all import *
>>> H = DiGraph({Integer(0): [Integer(1), Integer(2)], Integer(1): [Integer(3)], Integer(2): [Integer(3)], Integer(3): [], Integer(5): [Integer(1), Integer(6)], Integer(6): [Integer(2), Integer(3)]})


The actual layout computed depends on whether dot2tex and graphviz are installed, so we don’t test its relative values:

sage: H.layout_acyclic()
{0: [..., ...], 1: [..., ...], 2: [..., ...], 3: [..., ...], 5: [..., ...], 6: [..., ...]}

sage: H = DiGraph({0: [1]})
sage: pos = H.layout_acyclic(rankdir='up')
sage: pos[1][1] > pos[0][1] + .5
True
sage: pos = H.layout_acyclic(rankdir='down')
sage: pos[1][1] < pos[0][1] - .5
True
sage: pos = H.layout_acyclic(rankdir='right')
sage: pos[1][0] > pos[0][0] + .5
True
sage: pos = H.layout_acyclic(rankdir='left')
sage: pos[1][0] < pos[0][0] - .5
True

>>> from sage.all import *
>>> H.layout_acyclic()
{0: [..., ...], 1: [..., ...], 2: [..., ...], 3: [..., ...], 5: [..., ...], 6: [..., ...]}

>>> H = DiGraph({Integer(0): [Integer(1)]})
>>> pos = H.layout_acyclic(rankdir='up')
>>> pos[Integer(1)][Integer(1)] > pos[Integer(0)][Integer(1)] + RealNumber('.5')
True
>>> pos = H.layout_acyclic(rankdir='down')
>>> pos[Integer(1)][Integer(1)] < pos[Integer(0)][Integer(1)] - RealNumber('.5')
True
>>> pos = H.layout_acyclic(rankdir='right')
>>> pos[Integer(1)][Integer(0)] > pos[Integer(0)][Integer(0)] + RealNumber('.5')
True
>>> pos = H.layout_acyclic(rankdir='left')
>>> pos[Integer(1)][Integer(0)] < pos[Integer(0)][Integer(0)] - RealNumber('.5')
True

layout_acyclic_dummy(heights=None, rankdir='up', **options)[source]#

Return a ranked layout so that all edges point upward.

To this end, the heights of the vertices are set according to the level set decomposition of the graph (see level_sets()). This is achieved by a spring layout with fixed vertical placement of the vertices otherwise (see layout_acyclic_dummy() and layout_ranked()).

INPUT:

• rankdir – string (default: 'up'); indicates which direction the edges should point toward among 'up', 'down', 'left', or 'right'

• **options – passed down to layout_ranked()

EXAMPLES:

sage: H = DiGraph({0: [1, 2], 1: [3], 2: [3], 3: [], 5: [1, 6], 6: [2, 3]})
sage: H.layout_acyclic_dummy()
{0: [1.0..., 0], 1: [1.0..., 1], 2: [1.5..., 2], 3: [1.5..., 3], 5: [2.0..., 0], 6: [2.0..., 1]}

sage: H = DiGraph({0: [1]})
sage: H.layout_acyclic_dummy(rankdir='up')
{0: [0.5..., 0], 1: [0.5..., 1]}
sage: H.layout_acyclic_dummy(rankdir='down')
{0: [0.5..., 1], 1: [0.5..., 0]}
sage: H.layout_acyclic_dummy(rankdir='left')
{0: [1, 0.5...], 1: [0, 0.5...]}
sage: H.layout_acyclic_dummy(rankdir='right')
{0: [0, 0.5...], 1: [1, 0.5...]}
sage: H = DiGraph({0: [1, 2], 1: [3], 2: [3], 3: [1], 5: [1, 6], 6: [2, 3]})
sage: H.layout_acyclic_dummy()
Traceback (most recent call last):
...
ValueError: self should be an acyclic graph

>>> from sage.all import *
>>> H = DiGraph({Integer(0): [Integer(1), Integer(2)], Integer(1): [Integer(3)], Integer(2): [Integer(3)], Integer(3): [], Integer(5): [Integer(1), Integer(6)], Integer(6): [Integer(2), Integer(3)]})
>>> H.layout_acyclic_dummy()
{0: [1.0..., 0], 1: [1.0..., 1], 2: [1.5..., 2], 3: [1.5..., 3], 5: [2.0..., 0], 6: [2.0..., 1]}

>>> H = DiGraph({Integer(0): [Integer(1)]})
>>> H.layout_acyclic_dummy(rankdir='up')
{0: [0.5..., 0], 1: [0.5..., 1]}
>>> H.layout_acyclic_dummy(rankdir='down')
{0: [0.5..., 1], 1: [0.5..., 0]}
>>> H.layout_acyclic_dummy(rankdir='left')
{0: [1, 0.5...], 1: [0, 0.5...]}
>>> H.layout_acyclic_dummy(rankdir='right')
{0: [0, 0.5...], 1: [1, 0.5...]}
>>> H = DiGraph({Integer(0): [Integer(1), Integer(2)], Integer(1): [Integer(3)], Integer(2): [Integer(3)], Integer(3): [Integer(1)], Integer(5): [Integer(1), Integer(6)], Integer(6): [Integer(2), Integer(3)]})
>>> H.layout_acyclic_dummy()
Traceback (most recent call last):
...
ValueError: self should be an acyclic graph

level_sets()[source]#

Return the level set decomposition of the digraph.

OUTPUT:

• a list of non empty lists of vertices of this graph

The level set decomposition of the digraph is a list $$l$$ such that the level $$l[i]$$ contains all the vertices having all their predecessors in the levels $$l[j]$$ for $$j < i$$, and at least one in level $$l[i-1]$$ (unless $$i = 0$$).

The level decomposition contains exactly the vertices not occurring in any cycle of the graph. In particular, the graph is acyclic if and only if the decomposition forms a set partition of its vertices, and we recover the usual level set decomposition of the corresponding poset.

EXAMPLES:

sage: H = DiGraph({0: [1, 2], 1: [3], 2: [3], 3: [], 5: [1, 6], 6: [2, 3]})
sage: H.level_sets()
[[0, 5], [1, 6], [2], [3]]

sage: H = DiGraph({0: [1, 2], 1: [3], 2: [3], 3: [1], 5: [1, 6], 6: [2, 3]})
sage: H.level_sets()
[[0, 5], [6], [2]]

>>> from sage.all import *
>>> H = DiGraph({Integer(0): [Integer(1), Integer(2)], Integer(1): [Integer(3)], Integer(2): [Integer(3)], Integer(3): [], Integer(5): [Integer(1), Integer(6)], Integer(6): [Integer(2), Integer(3)]})
>>> H.level_sets()
[[0, 5], [1, 6], [2], [3]]

>>> H = DiGraph({Integer(0): [Integer(1), Integer(2)], Integer(1): [Integer(3)], Integer(2): [Integer(3)], Integer(3): [Integer(1)], Integer(5): [Integer(1), Integer(6)], Integer(6): [Integer(2), Integer(3)]})
>>> H.level_sets()
[[0, 5], [6], [2]]


This routine is mostly used for Hasse diagrams of posets:

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: H = HasseDiagram({0: [1, 2], 1: [3], 2: [3], 3: []})
sage: [len(x) for x in H.level_sets()]
[1, 2, 1]

>>> from sage.all import *
>>> from sage.combinat.posets.hasse_diagram import HasseDiagram
>>> H = HasseDiagram({Integer(0): [Integer(1), Integer(2)], Integer(1): [Integer(3)], Integer(2): [Integer(3)], Integer(3): []})
>>> [len(x) for x in H.level_sets()]
[1, 2, 1]

sage: from sage.combinat.posets.hasse_diagram import HasseDiagram
sage: H = HasseDiagram({0: [1, 2], 1: [3], 2: [4], 3: [4]})
sage: [len(x) for x in H.level_sets()]
[1, 2, 1, 1]

>>> from sage.all import *
>>> from sage.combinat.posets.hasse_diagram import HasseDiagram
>>> H = HasseDiagram({Integer(0): [Integer(1), Integer(2)], Integer(1): [Integer(3)], Integer(2): [Integer(4)], Integer(3): [Integer(4)]})
>>> [len(x) for x in H.level_sets()]
[1, 2, 1, 1]


Complexity: $$O(n+m)$$ in time and $$O(n)$$ in memory (besides the storage of the graph itself), where $$n$$ and $$m$$ are respectively the number of vertices and edges (assuming that appending to a list is constant time, which it is not quite).

neighbor_in_iterator(vertex)[source]#

Return an iterator over the in-neighbors of vertex.

A vertex $$u$$ is an in-neighbor of a vertex $$v$$ if $$uv$$ in an edge.

EXAMPLES:

sage: D = DiGraph({0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1]})
sage: for a in D.neighbor_in_iterator(0):
....:     print(a)
1
4

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1),Integer(2),Integer(3)], Integer(1): [Integer(0),Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(4)], Integer(4): [Integer(0),Integer(5)], Integer(5): [Integer(1)]})
>>> for a in D.neighbor_in_iterator(Integer(0)):
...     print(a)
1
4

neighbor_out_iterator(vertex)[source]#

Return an iterator over the out-neighbors of a given vertex.

A vertex $$u$$ is an out-neighbor of a vertex $$v$$ if $$vu$$ in an edge.

EXAMPLES:

sage: D = DiGraph({0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1]})
sage: for a in D.neighbor_out_iterator(0):
....:     print(a)
1
2
3

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1),Integer(2),Integer(3)], Integer(1): [Integer(0),Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(4)], Integer(4): [Integer(0),Integer(5)], Integer(5): [Integer(1)]})
>>> for a in D.neighbor_out_iterator(Integer(0)):
...     print(a)
1
2
3

neighbors_in(vertex)[source]#

Return the list of the in-neighbors of a given vertex.

A vertex $$u$$ is an in-neighbor of a vertex $$v$$ if $$uv$$ in an edge.

EXAMPLES:

sage: D = DiGraph({0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1]})
sage: D.neighbors_in(0)
[1, 4]

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1),Integer(2),Integer(3)], Integer(1): [Integer(0),Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(4)], Integer(4): [Integer(0),Integer(5)], Integer(5): [Integer(1)]})
>>> D.neighbors_in(Integer(0))
[1, 4]

neighbors_out(vertex)[source]#

Return the list of the out-neighbors of a given vertex.

A vertex $$u$$ is an out-neighbor of a vertex $$v$$ if $$vu$$ in an edge.

EXAMPLES:

sage: D = DiGraph({0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1]})
sage: D.neighbors_out(0)
[1, 2, 3]

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1),Integer(2),Integer(3)], Integer(1): [Integer(0),Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(4)], Integer(4): [Integer(0),Integer(5)], Integer(5): [Integer(1)]})
>>> D.neighbors_out(Integer(0))
[1, 2, 3]

out_branchings(source, spanning=True)[source]#

Return an iterator over the out branchings rooted at given vertex in self.

An out-branching is a directed tree rooted at source whose arcs are directed from source to leaves. An out-branching is spanning if it contains all vertices of the digraph.

If no spanning out branching rooted at source exist, raises ValueError or return non spanning out branching rooted at source, depending on the value of spanning.

INPUT:

• source – vertex used as the source for all out branchings.

• spanning – boolean (default: True); if False return maximum out branching from source. Otherwise, return spanning out branching if exists.

OUTPUT:

An iterator over the out branchings rooted in the given source.

ALGORITHM:

Recursively computes all out branchings.

At each step:

1. clean the graph (see below)

2. pick an edge e out of source

3. find all out branchings that do not contain e by first removing it

4. find all out branchings that do contain e by first merging the end vertices of e

Cleaning the graph implies to remove loops and replace multiedges by a single one with an appropriate label since these lead to similar steps of computation.

EXAMPLES:

A bidirectional 4-cycle:

sage: G = DiGraph({1:[2,3], 2:[1,4], 3:[1,4], 4:[2,3]}, format='dict_of_lists')
sage: list(G.out_branchings(1))
[Digraph on 4 vertices,
Digraph on 4 vertices,
Digraph on 4 vertices,
Digraph on 4 vertices]

>>> from sage.all import *
>>> G = DiGraph({Integer(1):[Integer(2),Integer(3)], Integer(2):[Integer(1),Integer(4)], Integer(3):[Integer(1),Integer(4)], Integer(4):[Integer(2),Integer(3)]}, format='dict_of_lists')
>>> list(G.out_branchings(Integer(1)))
[Digraph on 4 vertices,
Digraph on 4 vertices,
Digraph on 4 vertices,
Digraph on 4 vertices]


With the Petersen graph turned into a symmetric directed graph:

sage: G = graphs.PetersenGraph().to_directed()
sage: len(list(G.out_branchings(0)))
2000

>>> from sage.all import *
>>> G = graphs.PetersenGraph().to_directed()
>>> len(list(G.out_branchings(Integer(0))))
2000


With a non connected DiGraph and spanning = True:

sage: G = graphs.PetersenGraph().to_directed() + graphs.PetersenGraph().to_directed()
sage: G.out_branchings(0, spanning=True)
Traceback (most recent call last):
...
ValueError: no spanning out branching from vertex (0) exist

>>> from sage.all import *
>>> G = graphs.PetersenGraph().to_directed() + graphs.PetersenGraph().to_directed()
>>> G.out_branchings(Integer(0), spanning=True)
Traceback (most recent call last):
...
ValueError: no spanning out branching from vertex (0) exist


With a non connected DiGraph and spanning = False:

sage: g=DiGraph([(0,1), (0,1), (1,2), (3,4)],multiedges=True)
sage: list(g.out_branchings(0, spanning=False))
[Digraph on 3 vertices, Digraph on 3 vertices]

>>> from sage.all import *
>>> g=DiGraph([(Integer(0),Integer(1)), (Integer(0),Integer(1)), (Integer(1),Integer(2)), (Integer(3),Integer(4))],multiedges=True)
>>> list(g.out_branchings(Integer(0), spanning=False))
[Digraph on 3 vertices, Digraph on 3 vertices]


With multiedges:

sage: G = DiGraph({0:[1,1,1], 1:[2,2]}, format='dict_of_lists', multiedges=True)
sage: len(list(G.out_branchings(0)))
6

>>> from sage.all import *
>>> G = DiGraph({Integer(0):[Integer(1),Integer(1),Integer(1)], Integer(1):[Integer(2),Integer(2)]}, format='dict_of_lists', multiedges=True)
>>> len(list(G.out_branchings(Integer(0))))
6


With a DiGraph already being a spanning out branching:

sage: G = DiGraph({0:[1,2], 1:[3,4], 2:[5], 3:[], 4:[], 5:[]}, format='dict_of_lists')
sage: next(G.out_branchings(0)) == G
True

>>> from sage.all import *
>>> G = DiGraph({Integer(0):[Integer(1),Integer(2)], Integer(1):[Integer(3),Integer(4)], Integer(2):[Integer(5)], Integer(3):[], Integer(4):[], Integer(5):[]}, format='dict_of_lists')
>>> next(G.out_branchings(Integer(0))) == G
True

out_degree(vertices=None, labels=False)[source]#

Same as degree, but for out degree.

EXAMPLES:

sage: D = DiGraph({0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1]})
sage: D.out_degree(vertices=[0, 1 ,2], labels=True)
{0: 3, 1: 2, 2: 1}
sage: D.out_degree()
[3, 2, 1, 1, 2, 1]
sage: D.out_degree(2)
1

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1),Integer(2),Integer(3)], Integer(1): [Integer(0),Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(4)], Integer(4): [Integer(0),Integer(5)], Integer(5): [Integer(1)]})
>>> D.out_degree(vertices=[Integer(0), Integer(1) ,Integer(2)], labels=True)
{0: 3, 1: 2, 2: 1}
>>> D.out_degree()
[3, 2, 1, 1, 2, 1]
>>> D.out_degree(Integer(2))
1

out_degree_iterator(vertices=None, labels=False)[source]#

Same as degree_iterator, but for out degree.

EXAMPLES:

sage: D = graphs.Grid2dGraph(2,4).to_directed()
sage: sorted(D.out_degree_iterator())
[2, 2, 2, 2, 3, 3, 3, 3]
sage: sorted(D.out_degree_iterator(labels=True))
[((0, 0), 2),
((0, 1), 3),
((0, 2), 3),
((0, 3), 2),
((1, 0), 2),
((1, 1), 3),
((1, 2), 3),
((1, 3), 2)]

>>> from sage.all import *
>>> D = graphs.Grid2dGraph(Integer(2),Integer(4)).to_directed()
>>> sorted(D.out_degree_iterator())
[2, 2, 2, 2, 3, 3, 3, 3]
>>> sorted(D.out_degree_iterator(labels=True))
[((0, 0), 2),
((0, 1), 3),
((0, 2), 3),
((0, 3), 2),
((1, 0), 2),
((1, 1), 3),
((1, 2), 3),
((1, 3), 2)]

out_degree_sequence()[source]#

Return the outdegree sequence of this digraph.

EXAMPLES:

The outdegree sequences of two digraphs:

sage: g = DiGraph({1: [2, 5, 6], 2: [3, 6], 3: [4, 6], 4: [6], 5: [4, 6]})
sage: g.out_degree_sequence()
[3, 2, 2, 2, 1, 0]

>>> from sage.all import *
>>> g = DiGraph({Integer(1): [Integer(2), Integer(5), Integer(6)], Integer(2): [Integer(3), Integer(6)], Integer(3): [Integer(4), Integer(6)], Integer(4): [Integer(6)], Integer(5): [Integer(4), Integer(6)]})
>>> g.out_degree_sequence()
[3, 2, 2, 2, 1, 0]

sage: V = [2, 3, 5, 7, 8, 9, 10, 11]
sage: E = [[], [8, 10], [11], [8, 11], [9], [], [], [2, 9, 10]]
sage: g = DiGraph(dict(zip(V, E)))
sage: g.out_degree_sequence()
[3, 2, 2, 1, 1, 0, 0, 0]

>>> from sage.all import *
>>> V = [Integer(2), Integer(3), Integer(5), Integer(7), Integer(8), Integer(9), Integer(10), Integer(11)]
>>> E = [[], [Integer(8), Integer(10)], [Integer(11)], [Integer(8), Integer(11)], [Integer(9)], [], [], [Integer(2), Integer(9), Integer(10)]]
>>> g = DiGraph(dict(zip(V, E)))
>>> g.out_degree_sequence()
[3, 2, 2, 1, 1, 0, 0, 0]

outgoing_edge_iterator(vertices, labels=True)[source]#

Return an iterator over all departing edges from vertices.

INPUT:

• vertices – a vertex or a list of vertices

• labels – boolean (default: True); whether to return edges as pairs of vertices, or as triples containing the labels.

EXAMPLES:

sage: D = DiGraph({0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1]})
sage: for a in D.outgoing_edge_iterator([0]):
....:     print(a)
(0, 1, None)
(0, 2, None)
(0, 3, None)

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1),Integer(2),Integer(3)], Integer(1): [Integer(0),Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(4)], Integer(4): [Integer(0),Integer(5)], Integer(5): [Integer(1)]})
>>> for a in D.outgoing_edge_iterator([Integer(0)]):
...     print(a)
(0, 1, None)
(0, 2, None)
(0, 3, None)

outgoing_edges(vertices, labels=True)[source]#

Return a list of edges departing from vertices.

INPUT:

• vertices – a vertex or a list of vertices

• labels – boolean (default: True); whether to return edges as pairs of vertices, or as triples containing the labels.

EXAMPLES:

sage: D = DiGraph({0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1]})
sage: D.outgoing_edges([0])
[(0, 1, None), (0, 2, None), (0, 3, None)]

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1),Integer(2),Integer(3)], Integer(1): [Integer(0),Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(4)], Integer(4): [Integer(0),Integer(5)], Integer(5): [Integer(1)]})
>>> D.outgoing_edges([Integer(0)])
[(0, 1, None), (0, 2, None), (0, 3, None)]

path_semigroup()[source]#

The partial semigroup formed by the paths of this quiver.

EXAMPLES:

sage: Q = DiGraph({1: {2: ['a', 'c']}, 2: {3: ['b']}})
sage: F = Q.path_semigroup(); F                                             # needs sage.libs.flint
Partial semigroup formed by the directed paths of Multi-digraph on 3 vertices
sage: list(F)                                                               # needs sage.libs.flint
[e_1, e_2, e_3, a, c, b, a*b, c*b]

>>> from sage.all import *
>>> Q = DiGraph({Integer(1): {Integer(2): ['a', 'c']}, Integer(2): {Integer(3): ['b']}})
>>> F = Q.path_semigroup(); F                                             # needs sage.libs.flint
Partial semigroup formed by the directed paths of Multi-digraph on 3 vertices
>>> list(F)                                                               # needs sage.libs.flint
[e_1, e_2, e_3, a, c, b, a*b, c*b]

period()[source]#

Return the period of the current DiGraph.

The period of a directed graph is the largest integer that divides the length of every cycle in the graph. See the Wikipedia article Aperiodic_graph for more information.

EXAMPLES:

The following graph has period 2:

sage: g = DiGraph({0: [1], 1: [0]})
sage: g.period()
2

>>> from sage.all import *
>>> g = DiGraph({Integer(0): [Integer(1)], Integer(1): [Integer(0)]})
>>> g.period()
2


The following graph has a cycle of length 2 and a cycle of length 3, so it has period 1:

sage: g = DiGraph({0: [1, 4], 1: [2], 2: [0], 4: [0]})
sage: g.period()
1

>>> from sage.all import *
>>> g = DiGraph({Integer(0): [Integer(1), Integer(4)], Integer(1): [Integer(2)], Integer(2): [Integer(0)], Integer(4): [Integer(0)]})
>>> g.period()
1


Here is an example of computing the period of a digraph which is not strongly connected. By definition, it is the gcd() of the periods of its strongly connected components:

sage: g = DiGraph({-1: [-2], -2: [-3], -3: [-1],
....:     1: [2], 2: [1]})
sage: g.period()
1
sage: sorted([s.period() for s
....:         in g.strongly_connected_components_subgraphs()])
[2, 3]

>>> from sage.all import *
>>> g = DiGraph({-Integer(1): [-Integer(2)], -Integer(2): [-Integer(3)], -Integer(3): [-Integer(1)],
...     Integer(1): [Integer(2)], Integer(2): [Integer(1)]})
>>> g.period()
1
>>> sorted([s.period() for s
...         in g.strongly_connected_components_subgraphs()])
[2, 3]


ALGORITHM:

See the networkX implementation of is_aperiodic, that is based on breadth first search.

periphery(by_weight=False, algorithm=None, weight_function=None, check_weight=True)[source]#

Return the set of vertices in the periphery of the DiGraph.

The periphery is the set of vertices whose eccentricity is equal to the diameter of the DiGraph, i.e., achieving the maximum eccentricity.

For more information and examples on how to use input variables, see shortest_paths() and eccentricity()

INPUT:

• by_weight – boolean (default: False); if True, edge weights are taken into account; if False, all edges have weight 1

• algorithm – string (default: None); see method eccentricity() for the list of available algorithms

• weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l as a weight, if l is not None, else 1 as a weight.

• check_weight – boolean (default: True); if True, we check that the weight_function outputs a number for each edge

EXAMPLES:

sage: G = graphs.DiamondGraph().to_directed()
sage: G.periphery()
[0, 3]
sage: P = digraphs.Path(5)
sage: P.periphery()
[1, 2, 3, 4]
sage: G = digraphs.Complete(5)
sage: G.subgraph(G.periphery()) == G
True

>>> from sage.all import *
>>> G = graphs.DiamondGraph().to_directed()
>>> G.periphery()
[0, 3]
>>> P = digraphs.Path(Integer(5))
>>> P.periphery()
[1, 2, 3, 4]
>>> G = digraphs.Complete(Integer(5))
>>> G.subgraph(G.periphery()) == G
True


Return the radius of the DiGraph.

The radius is defined to be the minimum eccentricity of any vertex, where the eccentricity is the maximum distance to any other vertex. For more information and examples on how to use input variables, see shortest_paths() and eccentricity()

INPUT:

• by_weight – boolean (default: False); if True, edge weights are taken into account; if False, all edges have weight 1

• algorithm – string (default: None); see method eccentricity() for the list of available algorithms

• weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l, if l is not None, else 1 as a weight.

• check_weight – boolean (default: True); if True, we check that the weight_function outputs a number for each edge

EXAMPLES:

The more symmetric a DiGraph is, the smaller (diameter - radius) is:

sage: G = graphs.BarbellGraph(9, 3).to_directed()
3
sage: G.diameter()
6

>>> from sage.all import *
>>> G = graphs.BarbellGraph(Integer(9), Integer(3)).to_directed()
3
>>> G.diameter()
6

sage: G = digraphs.Circuit(9)
8
sage: G.diameter()
8

>>> from sage.all import *
>>> G = digraphs.Circuit(Integer(9))
8
>>> G.diameter()
8

reverse(immutable=None)[source]#

Return a copy of digraph with edges reversed in direction.

INPUT:

• immutable – boolean (default: None); whether to return an immutable digraph or not. By default (None), the returned digraph has the same setting than self. That is, if self is immutable, the returned digraph also is.

EXAMPLES:

sage: adj = {0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1]}
sage: R = D.reverse(); R
Reverse of (): Digraph on 6 vertices
sage: H = R.reverse()
True

>>> from sage.all import *
>>> adj = {Integer(0): [Integer(1),Integer(2),Integer(3)], Integer(1): [Integer(0),Integer(2)], Integer(2): [Integer(3)], Integer(3): [Integer(4)], Integer(4): [Integer(0),Integer(5)], Integer(5): [Integer(1)]}
>>> R = D.reverse(); R
Reverse of (): Digraph on 6 vertices
>>> H = R.reverse()
True

reverse_edge(u, v=None, label=None, inplace=True, multiedges=None)[source]#

Reverse the edge from $$u$$ to $$v$$.

INPUT:

• inplace – boolean (default: True); if False, a new digraph is created and returned as output, otherwise self is modified.

• multiedges – boolean (default: None); how to decide what should be done in case of doubt (for instance when edge $$(1,2)$$ is to be reversed in a graph while $$(2,1)$$ already exists):

• If set to True, input graph will be forced to allow parallel edges if necessary and edge $$(1,2)$$ will appear twice in the graph.

• If set to False, only one edge $$(1,2)$$ will remain in the graph after $$(2,1)$$ is reversed. Besides, the label of edge $$(1,2)$$ will be overwritten with the label of edge $$(2,1)$$.

The default behaviour (multiedges = None) will raise an exception each time a subjective decision (setting multiedges to True or False) is necessary to perform the operation.

The following forms are all accepted:

• D.reverse_edge( 1, 2 )

• D.reverse_edge( (1, 2) )

• D.reverse_edge( [1, 2] )

• D.reverse_edge( 1, 2, ‘label’ )

• D.reverse_edge( ( 1, 2, ‘label’) )

• D.reverse_edge( [1, 2, ‘label’] )

• D.reverse_edge( ( 1, 2), label=’label’ )

EXAMPLES:

If inplace is True (default value), self is modified:

sage: D = DiGraph([(0, 1 ,2)])
sage: D.reverse_edge(0, 1)
sage: D.edges(sort=True)
[(1, 0, 2)]

>>> from sage.all import *
>>> D = DiGraph([(Integer(0), Integer(1) ,Integer(2))])
>>> D.reverse_edge(Integer(0), Integer(1))
>>> D.edges(sort=True)
[(1, 0, 2)]


If inplace is False, self is not modified and a new digraph is returned:

sage: D = DiGraph([(0, 1, 2)])
sage: re = D.reverse_edge(0, 1, inplace=False)
sage: re.edges(sort=True)
[(1, 0, 2)]
sage: D.edges(sort=True)
[(0, 1, 2)]

>>> from sage.all import *
>>> D = DiGraph([(Integer(0), Integer(1), Integer(2))])
>>> re = D.reverse_edge(Integer(0), Integer(1), inplace=False)
>>> re.edges(sort=True)
[(1, 0, 2)]
>>> D.edges(sort=True)
[(0, 1, 2)]


If multiedges is True, self will be forced to allow parallel edges when and only when it is necessary:

sage: D = DiGraph([(1, 2, 'A'), (2, 1, 'A'), (2, 3, None)])
sage: D.reverse_edge(1, 2, multiedges=True)
sage: D.edges(sort=True)
[(2, 1, 'A'), (2, 1, 'A'), (2, 3, None)]
sage: D.allows_multiple_edges()
True

>>> from sage.all import *
>>> D = DiGraph([(Integer(1), Integer(2), 'A'), (Integer(2), Integer(1), 'A'), (Integer(2), Integer(3), None)])
>>> D.reverse_edge(Integer(1), Integer(2), multiedges=True)
>>> D.edges(sort=True)
[(2, 1, 'A'), (2, 1, 'A'), (2, 3, None)]
>>> D.allows_multiple_edges()
True


Even if multiedges is True, self will not be forced to allow parallel edges when it is not necessary:

sage: D = DiGraph( [(1, 2, 'A'), (2, 1, 'A'), (2, 3, None)] )
sage: D.reverse_edge(2, 3, multiedges=True)
sage: D.edges(sort=True)
[(1, 2, 'A'), (2, 1, 'A'), (3, 2, None)]
sage: D.allows_multiple_edges()
False

>>> from sage.all import *
>>> D = DiGraph( [(Integer(1), Integer(2), 'A'), (Integer(2), Integer(1), 'A'), (Integer(2), Integer(3), None)] )
>>> D.reverse_edge(Integer(2), Integer(3), multiedges=True)
>>> D.edges(sort=True)
[(1, 2, 'A'), (2, 1, 'A'), (3, 2, None)]
>>> D.allows_multiple_edges()
False


If user specifies multiedges = False, self will not be forced to allow parallel edges and a parallel edge will get deleted:

sage: D = DiGraph( [(1, 2, 'A'), (2, 1, 'A'), (2, 3, None)] )
sage: D.edges(sort=True)
[(1, 2, 'A'), (2, 1, 'A'), (2, 3, None)]
sage: D.reverse_edge(1, 2, multiedges=False)
sage: D.edges(sort=True)
[(2, 1, 'A'), (2, 3, None)]

>>> from sage.all import *
>>> D = DiGraph( [(Integer(1), Integer(2), 'A'), (Integer(2), Integer(1), 'A'), (Integer(2), Integer(3), None)] )
>>> D.edges(sort=True)
[(1, 2, 'A'), (2, 1, 'A'), (2, 3, None)]
>>> D.reverse_edge(Integer(1), Integer(2), multiedges=False)
>>> D.edges(sort=True)
[(2, 1, 'A'), (2, 3, None)]


Note that in the following graph, specifying multiedges = False will result in overwriting the label of $$(1, 2)$$ with the label of $$(2, 1)$$:

sage: D = DiGraph( [(1, 2, 'B'), (2, 1, 'A'), (2, 3, None)] )
sage: D.edges(sort=True)
[(1, 2, 'B'), (2, 1, 'A'), (2, 3, None)]
sage: D.reverse_edge(2, 1, multiedges=False)
sage: D.edges(sort=True)
[(1, 2, 'A'), (2, 3, None)]

>>> from sage.all import *
>>> D = DiGraph( [(Integer(1), Integer(2), 'B'), (Integer(2), Integer(1), 'A'), (Integer(2), Integer(3), None)] )
>>> D.edges(sort=True)
[(1, 2, 'B'), (2, 1, 'A'), (2, 3, None)]
>>> D.reverse_edge(Integer(2), Integer(1), multiedges=False)
>>> D.edges(sort=True)
[(1, 2, 'A'), (2, 3, None)]


If input edge in digraph has weight/label, then the weight/label should be preserved in the output digraph. User does not need to specify the weight/label when calling function:

sage: D = DiGraph([[0, 1, 2], [1, 2, 1]], weighted=True)
sage: D.reverse_edge(0, 1)
sage: D.edges(sort=True)
[(1, 0, 2), (1, 2, 1)]
sage: re = D.reverse_edge([1, 2], inplace=False)
sage: re.edges(sort=True)
[(1, 0, 2), (2, 1, 1)]

>>> from sage.all import *
>>> D = DiGraph([[Integer(0), Integer(1), Integer(2)], [Integer(1), Integer(2), Integer(1)]], weighted=True)
>>> D.reverse_edge(Integer(0), Integer(1))
>>> D.edges(sort=True)
[(1, 0, 2), (1, 2, 1)]
>>> re = D.reverse_edge([Integer(1), Integer(2)], inplace=False)
>>> re.edges(sort=True)
[(1, 0, 2), (2, 1, 1)]


If self has multiple copies (parallel edges) of the input edge, only 1 of the parallel edges is reversed:

sage: D = DiGraph([(0, 1, '01'), (0, 1, '01'), (0, 1, 'cat'), (1, 2, '12')], weighted=True, multiedges=True)
sage: re = D.reverse_edge([0, 1, '01'], inplace=False)
sage: re.edges(sort=True)
[(0, 1, '01'), (0, 1, 'cat'), (1, 0, '01'), (1, 2, '12')]

>>> from sage.all import *
>>> D = DiGraph([(Integer(0), Integer(1), '01'), (Integer(0), Integer(1), '01'), (Integer(0), Integer(1), 'cat'), (Integer(1), Integer(2), '12')], weighted=True, multiedges=True)
>>> re = D.reverse_edge([Integer(0), Integer(1), '01'], inplace=False)
>>> re.edges(sort=True)
[(0, 1, '01'), (0, 1, 'cat'), (1, 0, '01'), (1, 2, '12')]


If self has multiple copies (parallel edges) of the input edge but with distinct labels and no input label is specified, only 1 of the parallel edges is reversed (the edge that is labeled by the first label on the list returned by edge_label()):

sage: D = DiGraph([(0, 1, 'A'), (0, 1, 'B'), (0, 1, 'mouse'), (0, 1, 'cat')], multiedges=true)
sage: D.edge_label(0, 1)
['cat', 'mouse', 'B', 'A']
sage: D.reverse_edge(0, 1)
sage: D.edges(sort=True)
[(0, 1, 'A'), (0, 1, 'B'), (0, 1, 'mouse'), (1, 0, 'cat')]

>>> from sage.all import *
>>> D = DiGraph([(Integer(0), Integer(1), 'A'), (Integer(0), Integer(1), 'B'), (Integer(0), Integer(1), 'mouse'), (Integer(0), Integer(1), 'cat')], multiedges=true)
>>> D.edge_label(Integer(0), Integer(1))
['cat', 'mouse', 'B', 'A']
>>> D.reverse_edge(Integer(0), Integer(1))
>>> D.edges(sort=True)
[(0, 1, 'A'), (0, 1, 'B'), (0, 1, 'mouse'), (1, 0, 'cat')]


Finally, an exception is raised when Sage does not know how to choose between allowing multiple edges and losing some data:

sage: D = DiGraph([(0, 1, 'A'), (1, 0, 'B')])
sage: D.reverse_edge(0, 1)
Traceback (most recent call last):
...
ValueError: reversing the given edge is about to create two parallel
edges but input digraph doesn't allow them - User needs to specify
multiedges is True or False.

>>> from sage.all import *
>>> D = DiGraph([(Integer(0), Integer(1), 'A'), (Integer(1), Integer(0), 'B')])
>>> D.reverse_edge(Integer(0), Integer(1))
Traceback (most recent call last):
...
ValueError: reversing the given edge is about to create two parallel
edges but input digraph doesn't allow them - User needs to specify
multiedges is True or False.


The following syntax is supported, but note that you must use the label keyword:

sage: D = DiGraph()
sage: D.edges(sort=True)
[(1, 2, 'label')]
sage: D.reverse_edge((1, 2), label='label')
sage: D.edges(sort=True)
[(2, 1, 'label')]
sage: D.edges(sort=False)
[((1, 2), 'label', None), (2, 1, 'label')]
sage: D.reverse_edge((1, 2), 'label')
sage: D.edges(sort=False)
[('label', (1, 2), None), (2, 1, 'label')]

>>> from sage.all import *
>>> D = DiGraph()
>>> D.edges(sort=True)
[(1, 2, 'label')]
>>> D.reverse_edge((Integer(1), Integer(2)), label='label')
>>> D.edges(sort=True)
[(2, 1, 'label')]
>>> D.edges(sort=False)
[((1, 2), 'label', None), (2, 1, 'label')]
>>> D.reverse_edge((Integer(1), Integer(2)), 'label')
>>> D.edges(sort=False)
[('label', (1, 2), None), (2, 1, 'label')]

reverse_edges(edges, inplace=True, multiedges=None)[source]#

Reverse a list of edges.

INPUT:

• edges – a list of edges in the DiGraph.

• inplace – boolean (default: True); if False, a new digraph is created and returned as output, otherwise self is modified.

• multiedges – boolean (default: None); if True, input graph will be forced to allow parallel edges when necessary (for more information see the documentation of reverse_edge())

reverse_edge() – Reverses a single edge.

EXAMPLES:

If inplace is True (default value), self is modified:

sage: D = DiGraph({ 0: [1, 1, 3], 2: [3, 3], 4: [1, 5]}, multiedges=true)
sage: D.reverse_edges([[0, 1], [0, 3]])
sage: D.reverse_edges([(2, 3), (4, 5)])
sage: D.edges(sort=True)
[(0, 1, None), (1, 0, None), (2, 3, None), (3, 0, None),
(3, 2, None), (4, 1, None), (5, 4, None)]

>>> from sage.all import *
>>> D = DiGraph({ Integer(0): [Integer(1), Integer(1), Integer(3)], Integer(2): [Integer(3), Integer(3)], Integer(4): [Integer(1), Integer(5)]}, multiedges=true)
>>> D.reverse_edges([[Integer(0), Integer(1)], [Integer(0), Integer(3)]])
>>> D.reverse_edges([(Integer(2), Integer(3)), (Integer(4), Integer(5))])
>>> D.edges(sort=True)
[(0, 1, None), (1, 0, None), (2, 3, None), (3, 0, None),
(3, 2, None), (4, 1, None), (5, 4, None)]


If inplace is False, self is not modified and a new digraph is returned:

sage: D = DiGraph([(0, 1, 'A'), (1, 0, 'B'), (1, 2, 'C')])
sage: re = D.reverse_edges([(0, 1), (1, 2)],
....:                       inplace=False,
....:                       multiedges=True)
sage: re.edges(sort=True)
[(1, 0, 'A'), (1, 0, 'B'), (2, 1, 'C')]
sage: D.edges(sort=True)
[(0, 1, 'A'), (1, 0, 'B'), (1, 2, 'C')]
sage: D.allows_multiple_edges()
False
sage: re.allows_multiple_edges()
True

>>> from sage.all import *
>>> D = DiGraph([(Integer(0), Integer(1), 'A'), (Integer(1), Integer(0), 'B'), (Integer(1), Integer(2), 'C')])
>>> re = D.reverse_edges([(Integer(0), Integer(1)), (Integer(1), Integer(2))],
...                       inplace=False,
...                       multiedges=True)
>>> re.edges(sort=True)
[(1, 0, 'A'), (1, 0, 'B'), (2, 1, 'C')]
>>> D.edges(sort=True)
[(0, 1, 'A'), (1, 0, 'B'), (1, 2, 'C')]
>>> D.allows_multiple_edges()
False
>>> re.allows_multiple_edges()
True


If multiedges is True, self will be forced to allow parallel edges when and only when it is necessary:

sage: D = DiGraph([(1, 2, 'A'), (2, 1, 'A'), (2, 3, None)])
sage: D.reverse_edges([(1, 2), (2, 3)], multiedges=True)
sage: D.edges(sort=True)
[(2, 1, 'A'), (2, 1, 'A'), (3, 2, None)]
sage: D.allows_multiple_edges()
True

>>> from sage.all import *
>>> D = DiGraph([(Integer(1), Integer(2), 'A'), (Integer(2), Integer(1), 'A'), (Integer(2), Integer(3), None)])
>>> D.reverse_edges([(Integer(1), Integer(2)), (Integer(2), Integer(3))], multiedges=True)
>>> D.edges(sort=True)
[(2, 1, 'A'), (2, 1, 'A'), (3, 2, None)]
>>> D.allows_multiple_edges()
True


Even if multiedges is True, self will not be forced to allow parallel edges when it is not necessary:

sage: D = DiGraph([(1, 2, 'A'), (2, 1, 'A'), (2, 3, None)])
sage: D.reverse_edges([(2, 3)], multiedges=True)
sage: D.edges(sort=True)
[(1, 2, 'A'), (2, 1, 'A'), (3, 2, None)]
sage: D.allows_multiple_edges()
False

>>> from sage.all import *
>>> D = DiGraph([(Integer(1), Integer(2), 'A'), (Integer(2), Integer(1), 'A'), (Integer(2), Integer(3), None)])
>>> D.reverse_edges([(Integer(2), Integer(3))], multiedges=True)
>>> D.edges(sort=True)
[(1, 2, 'A'), (2, 1, 'A'), (3, 2, None)]
>>> D.allows_multiple_edges()
False


If multiedges is False, self will not be forced to allow parallel edges and an edge will get deleted:

sage: D = DiGraph([(1, 2), (2, 1)])
sage: D.edges(sort=True)
[(1, 2, None), (2, 1, None)]
sage: D.reverse_edges([(1, 2)], multiedges=False)
sage: D.edges(sort=True)
[(2, 1, None)]

>>> from sage.all import *
>>> D = DiGraph([(Integer(1), Integer(2)), (Integer(2), Integer(1))])
>>> D.edges(sort=True)
[(1, 2, None), (2, 1, None)]
>>> D.reverse_edges([(Integer(1), Integer(2))], multiedges=False)
>>> D.edges(sort=True)
[(2, 1, None)]


If input edge in digraph has weight/label, then the weight/label should be preserved in the output digraph. User does not need to specify the weight/label when calling function:

sage: D = DiGraph([(0, 1, '01'), (1, 2, 1), (2, 3, '23')], weighted=True)
sage: D.reverse_edges([(0, 1, '01'), (1, 2), (2, 3)])
sage: D.edges(sort=True)
[(1, 0, '01'), (2, 1, 1), (3, 2, '23')]

>>> from sage.all import *
>>> D = DiGraph([(Integer(0), Integer(1), '01'), (Integer(1), Integer(2), Integer(1)), (Integer(2), Integer(3), '23')], weighted=True)
>>> D.reverse_edges([(Integer(0), Integer(1), '01'), (Integer(1), Integer(2)), (Integer(2), Integer(3))])
>>> D.edges(sort=True)
[(1, 0, '01'), (2, 1, 1), (3, 2, '23')]

sinks()[source]#

Return a list of sinks of the digraph.

OUTPUT:

• list of the vertices of the digraph that have no edges beginning at them

EXAMPLES:

sage: G = DiGraph({1: {3: ['a']}, 2: {3: ['b']}})
sage: G.sinks()
[3]
sage: T = DiGraph({1: {}})
sage: T.sinks()
[1]

>>> from sage.all import *
>>> G = DiGraph({Integer(1): {Integer(3): ['a']}, Integer(2): {Integer(3): ['b']}})
>>> G.sinks()
[3]
>>> T = DiGraph({Integer(1): {}})
>>> T.sinks()
[1]

sources()[source]#

Return a list of sources of the digraph.

OUTPUT:

• list of the vertices of the digraph that have no edges going into them

EXAMPLES:

sage: G = DiGraph({1: {3: ['a']}, 2: {3: ['b']}})
sage: G.sources()
[1, 2]
sage: T = DiGraph({1: {}})
sage: T.sources()
[1]

>>> from sage.all import *
>>> G = DiGraph({Integer(1): {Integer(3): ['a']}, Integer(2): {Integer(3): ['b']}})
>>> G.sources()
[1, 2]
>>> T = DiGraph({Integer(1): {}})
>>> T.sources()
[1]

strong_articulation_points(G)[source]#

Return the strong articulation points of this digraph.

A vertex is a strong articulation point if its deletion increases the number of strongly connected components. This method implements the algorithm described in [ILS2012]. The time complexity is dominated by the time complexity of the immediate dominators finding algorithm.

OUTPUT: The list of strong articulation points.

EXAMPLES:

Two cliques sharing a vertex:

sage: from sage.graphs.connectivity import strong_articulation_points
sage: D = digraphs.Complete(4)
sage: strong_articulation_points(D)
[3]
sage: D.strong_articulation_points()
[3]

>>> from sage.all import *
>>> from sage.graphs.connectivity import strong_articulation_points
>>> D = digraphs.Complete(Integer(4))
>>> strong_articulation_points(D)
[3]
>>> D.strong_articulation_points()
[3]


Two cliques connected by some arcs:

sage: D = digraphs.Complete(4) * 2
sage: sorted(strong_articulation_points(D))
[0, 3, 4, 7]
sage: sorted(strong_articulation_points(D))
[3, 7]
sage: strong_articulation_points(D)
[]

>>> from sage.all import *
>>> D = digraphs.Complete(Integer(4)) * Integer(2)
>>> sorted(strong_articulation_points(D))
[0, 3, 4, 7]
>>> sorted(strong_articulation_points(D))
[3, 7]
>>> strong_articulation_points(D)
[]

strongly_connected_component_containing_vertex(G, v)[source]#

Return the strongly connected component containing a given vertex

INPUT:

• G – the input DiGraph

• v – a vertex

EXAMPLES:

In the symmetric digraph of a graph, the strongly connected components are the connected components:

sage: from sage.graphs.connectivity import strongly_connected_component_containing_vertex
sage: g = graphs.PetersenGraph()
sage: d = DiGraph(g)
sage: strongly_connected_component_containing_vertex(d, 0)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: d.strongly_connected_component_containing_vertex(0)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> from sage.all import *
>>> from sage.graphs.connectivity import strongly_connected_component_containing_vertex
>>> g = graphs.PetersenGraph()
>>> d = DiGraph(g)
>>> strongly_connected_component_containing_vertex(d, Integer(0))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> d.strongly_connected_component_containing_vertex(Integer(0))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

sage: g = DiGraph([(0, 1), (1, 0), (1, 2), (2, 3), (3, 2)])
sage: strongly_connected_component_containing_vertex(g, 0)
[0, 1]

>>> from sage.all import *
>>> g = DiGraph([(Integer(0), Integer(1)), (Integer(1), Integer(0)), (Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(3), Integer(2))])
>>> strongly_connected_component_containing_vertex(g, Integer(0))
[0, 1]

strongly_connected_components(G)[source]#

Return the lists of vertices in each strongly connected components (SCCs).

This method implements the Tarjan algorithm to compute the strongly connected components of the digraph. It returns a list of lists of vertices, each list of vertices representing a strongly connected component.

The basic idea of the algorithm is this: a depth-first search (DFS) begins from an arbitrary start node (and subsequent DFSes are conducted on any nodes that have not yet been found). As usual with DFSes, the search visits every node of the graph exactly once, declining to revisit any node that has already been explored. Thus, the collection of search trees is a spanning forest of the graph. The strongly connected components correspond to the subtrees of this spanning forest that have no edge directed outside the subtree.

To recover these components, during the DFS, we keep the index of a node, that is, the position in the DFS tree, and the lowlink: as soon as the subtree rooted at $$v$$ has been fully explored, the lowlink of $$v$$ is the smallest index reachable from $$v$$ passing from descendants of $$v$$. If the subtree rooted at $$v$$ has been fully explored, and the index of $$v$$ equals the lowlink of $$v$$, that whole subtree is a new SCC.

EXAMPLES:

sage: from sage.graphs.base.static_sparse_graph import tarjan_strongly_connected_components
sage: tarjan_strongly_connected_components(digraphs.Path(3))
[[2], [1], [0]]
sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } )
sage: D.connected_components(sort=True)
[[0, 1, 2, 3], [4, 5, 6]]
sage: D = DiGraph( { 0 : [1, 3], 1 : [2], 2 : [3], 4 : [5, 6], 5 : [6] } )
sage: D.strongly_connected_components()
[[3], [2], [1], [0], [6], [5], [4]]
sage: D.strongly_connected_components()
[[3], [0, 1, 2], [6], [5], [4]]
sage: D = DiGraph([('a','b'), ('b','c'), ('c', 'd'), ('d', 'b'), ('c', 'e')])
sage: [sorted(scc) for scc in D.strongly_connected_components()]
[['e'], ['b', 'c', 'd'], ['a']]

>>> from sage.all import *
>>> from sage.graphs.base.static_sparse_graph import tarjan_strongly_connected_components
>>> tarjan_strongly_connected_components(digraphs.Path(Integer(3)))
[[2], [1], [0]]
>>> D = DiGraph( { Integer(0) : [Integer(1), Integer(3)], Integer(1) : [Integer(2)], Integer(2) : [Integer(3)], Integer(4) : [Integer(5), Integer(6)], Integer(5) : [Integer(6)] } )
>>> D.connected_components(sort=True)
[[0, 1, 2, 3], [4, 5, 6]]
>>> D = DiGraph( { Integer(0) : [Integer(1), Integer(3)], Integer(1) : [Integer(2)], Integer(2) : [Integer(3)], Integer(4) : [Integer(5), Integer(6)], Integer(5) : [Integer(6)] } )
>>> D.strongly_connected_components()
[[3], [2], [1], [0], [6], [5], [4]]
>>> D.strongly_connected_components()
[[3], [0, 1, 2], [6], [5], [4]]
>>> D = DiGraph([('a','b'), ('b','c'), ('c', 'd'), ('d', 'b'), ('c', 'e')])
>>> [sorted(scc) for scc in D.strongly_connected_components()]
[['e'], ['b', 'c', 'd'], ['a']]

strongly_connected_components_digraph(G, keep_labels=False)[source]#

Return the digraph of the strongly connected components

The digraph of the strongly connected components of a graph $$G$$ has a vertex per strongly connected component included in $$G$$. There is an edge from a component $$C_1$$ to a component $$C_2$$ if there is an edge in $$G$$ from a vertex $$u_1 \in C_1$$ to a vertex $$u_2 \in C_2$$.

INPUT:

• G – the input DiGraph

• keep_labels – boolean (default: False); when keep_labels=True, the resulting digraph has an edge from a component $$C_i$$ to a component $$C_j$$ for each edge in $$G$$ from a vertex $$u_i \in C_i$$ to a vertex $$u_j \in C_j$$. Hence the resulting digraph may have loops and multiple edges. However, edges in the result with same source, target, and label are not duplicated (see examples below). When keep_labels=False, the return digraph is simple, so without loops nor multiple edges, and edges are unlabelled.

EXAMPLES:

Such a digraph is always acyclic:

sage: from sage.graphs.connectivity import strongly_connected_components_digraph
sage: g = digraphs.RandomDirectedGNP(15, .1)
sage: scc_digraph = strongly_connected_components_digraph(g)
sage: scc_digraph.is_directed_acyclic()
True
sage: scc_digraph = g.strongly_connected_components_digraph()
sage: scc_digraph.is_directed_acyclic()
True

>>> from sage.all import *
>>> from sage.graphs.connectivity import strongly_connected_components_digraph
>>> g = digraphs.RandomDirectedGNP(Integer(15), RealNumber('.1'))
>>> scc_digraph = strongly_connected_components_digraph(g)
>>> scc_digraph.is_directed_acyclic()
True
>>> scc_digraph = g.strongly_connected_components_digraph()
>>> scc_digraph.is_directed_acyclic()
True


The vertices of the digraph of strongly connected components are exactly the strongly connected components:

sage: g = digraphs.ButterflyGraph(2)
sage: scc_digraph = strongly_connected_components_digraph(g)
sage: g.is_directed_acyclic()
True
sage: V_scc = list(scc_digraph)
sage: all(Set(scc) in V_scc for scc in g.strongly_connected_components())
True

>>> from sage.all import *
>>> g = digraphs.ButterflyGraph(Integer(2))
>>> scc_digraph = strongly_connected_components_digraph(g)
>>> g.is_directed_acyclic()
True
>>> V_scc = list(scc_digraph)
>>> all(Set(scc) in V_scc for scc in g.strongly_connected_components())
True


The following digraph has three strongly connected components, and the digraph of those is a TransitiveTournament():

sage: g = DiGraph({0: {1: "01", 2: "02", 3: "03"}, 1: {2: "12"}, 2:{1: "21", 3: "23"}})
sage: scc_digraph = strongly_connected_components_digraph(g)
sage: scc_digraph.is_isomorphic(digraphs.TransitiveTournament(3))
True

>>> from sage.all import *
>>> g = DiGraph({Integer(0): {Integer(1): "01", Integer(2): "02", Integer(3): "03"}, Integer(1): {Integer(2): "12"}, Integer(2):{Integer(1): "21", Integer(3): "23"}})
>>> scc_digraph = strongly_connected_components_digraph(g)
>>> scc_digraph.is_isomorphic(digraphs.TransitiveTournament(Integer(3)))
True


By default, the labels are discarded, and the result has no loops nor multiple edges. If keep_labels is True, then the labels are kept, and the result is a multi digraph, possibly with multiple edges and loops. However, edges in the result with same source, target, and label are not duplicated (see the edges from 0 to the strongly connected component $$\{1,2\}$$ below):

sage: g = DiGraph({0: {1: "0-12", 2: "0-12", 3: "0-3"}, 1: {2: "1-2", 3: "1-3"}, 2: {1: "2-1", 3: "2-3"}})
sage: g.order(), g.size()
(4, 7)
sage: scc_digraph = strongly_connected_components_digraph(g, keep_labels=True)
sage: (scc_digraph.order(), scc_digraph.size())
(3, 6)
sage: set(g.edge_labels()) == set(scc_digraph.edge_labels())
True

>>> from sage.all import *
>>> g = DiGraph({Integer(0): {Integer(1): "0-12", Integer(2): "0-12", Integer(3): "0-3"}, Integer(1): {Integer(2): "1-2", Integer(3): "1-3"}, Integer(2): {Integer(1): "2-1", Integer(3): "2-3"}})
>>> g.order(), g.size()
(4, 7)
>>> scc_digraph = strongly_connected_components_digraph(g, keep_labels=True)
>>> (scc_digraph.order(), scc_digraph.size())
(3, 6)
>>> set(g.edge_labels()) == set(scc_digraph.edge_labels())
True

strongly_connected_components_subgraphs(G)[source]#

Return the strongly connected components as a list of subgraphs.

EXAMPLES:

In the symmetric digraph of a graph, the strongly connected components are the connected components:

sage: from sage.graphs.connectivity import strongly_connected_components_subgraphs
sage: g = graphs.PetersenGraph()
sage: d = DiGraph(g)
sage: strongly_connected_components_subgraphs(d)
[Subgraph of (Petersen graph): Digraph on 10 vertices]
sage: d.strongly_connected_components_subgraphs()
[Subgraph of (Petersen graph): Digraph on 10 vertices]

>>> from sage.all import *
>>> from sage.graphs.connectivity import strongly_connected_components_subgraphs
>>> g = graphs.PetersenGraph()
>>> d = DiGraph(g)
>>> strongly_connected_components_subgraphs(d)
[Subgraph of (Petersen graph): Digraph on 10 vertices]
>>> d.strongly_connected_components_subgraphs()
[Subgraph of (Petersen graph): Digraph on 10 vertices]

sage: g = DiGraph([(0, 1), (1, 0), (1, 2), (2, 3), (3, 2)])
sage: strongly_connected_components_subgraphs(g)
[Subgraph of (): Digraph on 2 vertices, Subgraph of (): Digraph on 2 vertices]

>>> from sage.all import *
>>> g = DiGraph([(Integer(0), Integer(1)), (Integer(1), Integer(0)), (Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(3), Integer(2))])
>>> strongly_connected_components_subgraphs(g)
[Subgraph of (): Digraph on 2 vertices, Subgraph of (): Digraph on 2 vertices]

to_directed()[source]#

Since the graph is already directed, simply returns a copy of itself.

EXAMPLES:

sage: DiGraph({0: [1, 2, 3], 4: [5, 1]}).to_directed()
Digraph on 6 vertices

>>> from sage.all import *
>>> DiGraph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(4): [Integer(5), Integer(1)]}).to_directed()
Digraph on 6 vertices

to_undirected(data_structure=None, sparse=None)[source]#

Return an undirected version of the graph.

Every directed edge becomes an edge.

INPUT:

• data_structure – string (default: None); one of "sparse", "static_sparse", or "dense". See the documentation of Graph or DiGraph.

• sparse – boolean (default: None); sparse=True is an alias for data_structure="sparse", and sparse=False is an alias for data_structure="dense".

EXAMPLES:

sage: D = DiGraph({0: [1, 2], 1: [0]})
sage: G = D.to_undirected()
sage: D.edges(sort=True, labels=False)
[(0, 1), (0, 2), (1, 0)]
sage: G.edges(sort=True, labels=False)
[(0, 1), (0, 2)]

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1), Integer(2)], Integer(1): [Integer(0)]})
>>> G = D.to_undirected()
>>> D.edges(sort=True, labels=False)
[(0, 1), (0, 2), (1, 0)]
>>> G.edges(sort=True, labels=False)
[(0, 1), (0, 2)]

topological_sort(implementation='default')[source]#

Return a topological sort of the digraph if it is acyclic.

If the digraph contains a directed cycle, a TypeError is raised. As topological sorts are not necessarily unique, different implementations may yield different results.

A topological sort is an ordering of the vertices of the digraph such that each vertex comes before all of its successors. That is, if $$u$$ comes before $$v$$ in the sort, then there may be a directed path from $$u$$ to $$v$$, but there will be no directed path from $$v$$ to $$u$$.

INPUT:

• implementation – string (default: "default"); either use the default Cython implementation, or the default NetworkX library (implementation = "NetworkX")

EXAMPLES:

sage: D = DiGraph({0: [1, 2, 3], 4: [2, 5], 1: [8], 2: [7], 3: [7],
....:   5: [6, 7], 7: [8], 6: [9], 8: [10], 9: [10]})
sage: D.plot(layout='circular').show()                                      # needs sage.plot
sage: D.topological_sort()
[4, 5, 6, 9, 0, 1, 2, 3, 7, 8, 10]

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(4): [Integer(2), Integer(5)], Integer(1): [Integer(8)], Integer(2): [Integer(7)], Integer(3): [Integer(7)],
...   Integer(5): [Integer(6), Integer(7)], Integer(7): [Integer(8)], Integer(6): [Integer(9)], Integer(8): [Integer(10)], Integer(9): [Integer(10)]})
>>> D.plot(layout='circular').show()                                      # needs sage.plot
>>> D.topological_sort()
[4, 5, 6, 9, 0, 1, 2, 3, 7, 8, 10]

sage: D.add_edge(9, 7)
sage: D.topological_sort()
[4, 5, 6, 9, 0, 1, 2, 3, 7, 8, 10]

>>> from sage.all import *
>>> D.topological_sort()
[4, 5, 6, 9, 0, 1, 2, 3, 7, 8, 10]


Using the NetworkX implementation

sage: s = list(D.topological_sort(implementation="NetworkX")); s  # random  # needs networkx
[0, 4, 1, 3, 2, 5, 6, 9, 7, 8, 10]
sage: all(s.index(u) < s.index(v)                                           # needs networkx
....:     for u, v in D.edges(sort=False, labels=False))
True

>>> from sage.all import *
>>> s = list(D.topological_sort(implementation="NetworkX")); s  # random  # needs networkx
[0, 4, 1, 3, 2, 5, 6, 9, 7, 8, 10]
>>> all(s.index(u) < s.index(v)                                           # needs networkx
...     for u, v in D.edges(sort=False, labels=False))
True

sage: D.add_edge(7, 4)
sage: D.topological_sort()
Traceback (most recent call last):
...
TypeError: digraph is not acyclic; there is no topological sort

>>> from sage.all import *
>>> D.topological_sort()
Traceback (most recent call last):
...
TypeError: digraph is not acyclic; there is no topological sort

topological_sort_generator()[source]#

Return an iterator over all topological sorts of the digraph if it is acyclic.

If the digraph contains a directed cycle, a TypeError is raised.

A topological sort is an ordering of the vertices of the digraph such that each vertex comes before all of its successors. That is, if u comes before v in the sort, then there may be a directed path from u to v, but there will be no directed path from v to u. See also topological_sort().

AUTHORS:

• Mike Hansen - original implementation

• Robert L. Miller: wrapping, documentation

REFERENCE:

• [1] Pruesse, Gara and Ruskey, Frank. Generating Linear Extensions Fast. SIAM J. Comput., Vol. 23 (1994), no. 2, pp. 373-386.

EXAMPLES:

sage: D = DiGraph({0: [1, 2], 1: [3], 2: [3, 4]})
sage: D.plot(layout='circular').show()                                      # needs sage.plot
sage: list(D.topological_sort_generator())                                  # needs sage.modules sage.rings.finite_rings
[[0, 1, 2, 3, 4], [0, 2, 1, 3, 4], [0, 2, 1, 4, 3],
[0, 2, 4, 1, 3], [0, 1, 2, 4, 3]]

>>> from sage.all import *
>>> D = DiGraph({Integer(0): [Integer(1), Integer(2)], Integer(1): [Integer(3)], Integer(2): [Integer(3), Integer(4)]})
>>> D.plot(layout='circular').show()                                      # needs sage.plot
>>> list(D.topological_sort_generator())                                  # needs sage.modules sage.rings.finite_rings
[[0, 1, 2, 3, 4], [0, 2, 1, 3, 4], [0, 2, 1, 4, 3],
[0, 2, 4, 1, 3], [0, 1, 2, 4, 3]]

sage: for sort in D.topological_sort_generator():                           # needs sage.modules sage.rings.finite_rings
....:     for u, v in D.edge_iterator(labels=False):
....:         if sort.index(u) > sort.index(v):
....:             print("this should never happen")

>>> from sage.all import *
>>> for sort in D.topological_sort_generator():                           # needs sage.modules sage.rings.finite_rings
...     for u, v in D.edge_iterator(labels=False):
...         if sort.index(u) > sort.index(v):
...             print("this should never happen")