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 indegree. 
neighbors_out() 
Return the list of the outneighbors of a given vertex. 
neighbor_out_iterator() 
Return an iterator over the outneighbors of a given vertex. 
neighbors_in() 
Return the list of the inneighbors of a given vertex. 
neighbor_in_iterator() 
Return an iterator over the inneighbors 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. 
Paths and cycles:
all_paths_iterator() 
Return an iterator over the paths of self . 
all_simple_paths() 
Return a list of all the simple paths of self starting with one of the given vertices. 
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. 
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. 
immediate_dominators() 
Return the immediate dominators of all vertices reachable from \(root\). 
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 
Miscellanous:
flow_polytope() 
Compute the flow polytope of a digraph 
degree_polynomial() 
Return the generating polynomial of degrees of vertices in self . 
Methods¶

class
sage.graphs.digraph.
DiGraph
(data=None, pos=None, loops=None, format=None, weighted=None, implementation='c_graph', data_structure='sparse', vertex_labels=True, name=None, multiedges=None, convert_empty_dict_labels_to_None=None, sparse=True, immutable=False)¶ Bases:
sage.graphs.generic_graph.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 predefined digraphs, see the
digraph_generators
module.A
DiGraph
object has many methods whose list can be obtained by typingg.<tab>
(i.e. hit the ‘tab’ key) or by reading the documentation ofdigraph
,generic_graph
, andgraph
.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 theformat
argument):DiGraph()
– build a digraph on 0 verticesDiGraph(5)
– return an edgeless digraph on the 5 vertices 0,…,4DiGraph([list_of_vertices, list_of_edges])
– return a digraph with given vertices/edgesTo bypass autodetection, prefer the more explicit
DiGraph([V, E], format='vertices_and_edges')
.DiGraph(list_of_edges)
– return a digraph with a given list of edges (see documentation ofadd_edges()
).To bypass autodetection, prefer the more explicit
DiGraph(L, format='list_of_edges')
.DiGraph({1: [2,3,4], 3: [4]})
– return a digraph by associating to each vertex the list of its outneighbors.To bypass autodetection, prefer the more explicit
DiGraph(D, format='dict_of_lists')
.DiGraph({1: {2: 'a', 3: 'b'}, 3: {2: 'c'}})
– return a digraph by associating a list of outneighbors to each vertex and providing its edge label.To bypass autodetection, 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']}})
.DiGraph(a_matrix)
– return a digraph with given (weighted) adjacency matrix (see documentation ofadjacency_matrix()
).To bypass autodetection, prefer the more explicit
DiGraph(M, format='adjacency_matrix')
. To take weights into account, useformat='weighted_adjacency_matrix'
instead.DiGraph(a_nonsquare_matrix)
– return a digraph with given incidence matrix (see documentation ofincidence_matrix()
).To bypass autodetection, prefer the more explicit
DiGraph(M, format='incidence_matrix')
.DiGraph([V, f])
– return a digraph with a vertex setV
and an edge \(u,v\) whenever \(f(u, v)\) isTrue
. Example:DiGraph([ [1..10], lambda x,y: abs(x  y).is_square()])
DiGraph('FOC@?OC@_?')
– return a digraph from adig6
string (see documentation ofdig6_string()
).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 5cycle 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. Seeself.weighted()
format
– string (default:None
); if set toNone
,DiGraph
tries to guess input’s format. To avoid this possibly timeconsuming 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 fordata_structure="sparse"
, andsparse=False
is an alias fordata_structure="dense"
data_structure
– string (default:"sparse"
); one of the following (for more information, seeoverview
):"dense"
– selects thedense_graph
backend"sparse"
– selects thesparse_graph
backend"static_sparse"
– selects thestatic_sparse_backend
(this backend is faster than the sparse backend and smaller in memory, and it is immutable, so that the resulting graphs can be used as dictionary keys).
immutable
– boolean (default:False
); whether to create a immutable digraph. Note thatimmutable=True
is actually a shortcut fordata_structure='static_sparse'
.vertex_labels
– boolean (default:True
); whether to allow any object as a vertex (slower), or only the integers \(0,...,n1\), 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 byNone
, the default Sage edge label. It is set toTrue
iff a NetworkX graph is on the input.
EXAMPLES:
A dictionary of dictionaries:
sage: g = DiGraph({0: {1: 'x', 2: 'z', 3: 'a'}, 2: {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.
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
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() [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] sage: g.adjacency_matrix() [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]
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.
an adjacency matrix:
sage: M = Matrix([[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]]); 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) Digraph on 5 vertices sage: M = Matrix([[0,1,1],[1,0,1/2],[1,1/2,0]]); M [ 0 1 1] [ 1 0 1/2] [ 1 1/2 0] sage: G = DiGraph(M,sparse=True,weighted=True); G Digraph on 3 vertices sage: G.weighted() True
an incidence matrix:
sage: M = Matrix(6, [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]); 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) Digraph on 6 vertices
A
dig6
string: Sage automatically recognizes whether a string is indig6
format, which is a directed version ofgraph6
:sage: D = DiGraph('IRAaDCIIOWEOKcPWAo') sage: D Digraph on 10 vertices sage: D = DiGraph('IRAaDCIIOEOKcPWAo') Traceback (most recent call last): ... RuntimeError: the string (IRAaDCIIOEOKcPWAo) seems corrupt: for n = 10, the string is too short sage: D = DiGraph("IRAaDCI'OWEOKcPWAo") Traceback (most recent call last): ... RuntimeError: the string seems corrupt: valid characters are ?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{}~
A NetworkX XDiGraph:
sage: import networkx sage: g = networkx.MultiDiGraph({0: [1, 2, 3], 2: [4]}) sage: DiGraph(g) Digraph on 5 vertices
A NetworkX digraph:
sage: import networkx sage: g = networkx.DiGraph({0: [1, 2, 3], 2: [4]}) sage: DiGraph(g) Digraph on 5 vertices
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
If
vertex_labels
isTrue
, the names of the vertices are given by the vertex attribute'name'
, if available:sage: g = igraph.Graph([(0,1),(0,2)], directed=True, vertex_attrs={'name':['a','b','c']}) # optional  python_igraph sage: DiGraph(g).vertices() # optional  python_igraph ['a', 'b', 'c'] sage: g = igraph.Graph([(0,1),(0,2)], directed=True, vertex_attrs={'label':['a','b','c']}) # optional  python_igraph sage: DiGraph(g).vertices() # optional  python_igraph [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, edge_attrs={'name':['a','b'], 'weight':[1,3]}) # optional  python_igraph sage: DiGraph(g).edges() # 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)¶ 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. IfNone
, then all vertices of the graph can be starting points. This argument is necessary ifrooted
is set toTrue
.simple
– boolean (default:False
); if set toTrue
, then only simple cycles are considered. A cycle is simple if the only vertex occuring 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 toNone
, then all lengths are allowed.trivial
 boolean (default:False
); if set toTrue
, then the empty paths are also enumerated.
OUTPUT:
iteratorSee also
AUTHOR:
Alexandre Blondin MasseEXAMPLES:
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']
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) []
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']
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']]
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']]
One may prefer to enumerate simple cycles, i.e. cycles such that the only vertex occuring 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]]

all_paths_iterator
(starting_vertices=None, ending_vertices=None, simple=False, max_length=None, trivial=False)¶ Return an iterator over the paths of
self
.The paths are enumerated in increasing length order.
INPUT:
starting_vertices
– iterable (default:None
); vertices from which the paths must start. IfNone
, then all vertices of the graph can be starting points.ending_vertices
– iterable (default:None
); allowed ending vertices of the paths. IfNone
, then all vertices are allowed.simple
– boolean (default:False
); if set toTrue
, then only simple paths are considered. Simple paths are paths in which no two arcs share a head or share a tail, i.e. every vertex in the path is entered at most once and exited at most once.max_length
– non negative integer (default:None
); the maximum length of the enumerated paths. If set toNone
, then all lengths are allowed.trivial
 boolean (default:False
); if set toTrue
, then the empty paths are also enumerated.
OUTPUT:
iteratorAUTHOR:
Alexandre Blondin MasseEXAMPLES:
sage: g = DiGraph({'a': ['a', 'b'], 'b': ['c'], 'c': ['d'], 'd': ['c']}, loops=True) sage: pi = g.all_paths_iterator() sage: for _ in range(7): # py2 ....: print(next(pi)) # py2 ['a', 'a'] ['a', 'b'] ['b', 'c'] ['c', 'd'] ['d', 'c'] ['a', 'a', 'a'] ['a', 'a', 'b'] sage: pi = g.all_paths_iterator() sage: [len(next(pi))  1 for _ in range(7)] [1, 1, 1, 1, 1, 2, 2]
It is possible to precise the allowed starting and/or ending vertices:
sage: pi = g.all_paths_iterator(starting_vertices=['a']) sage: for _ in range(5): # py2 ....: print(next(pi)) # py2 ['a', 'a'] ['a', 'b'] ['a', 'a', 'a'] ['a', 'a', 'b'] ['a', 'b', 'c'] sage: pi = g.all_paths_iterator(starting_vertices=['a']) sage: [len(next(pi))  1 for _ in range(5)] [1, 1, 2, 2, 2] sage: pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['b']) sage: for _ in range(5): ....: print(next(pi)) ['a', 'b'] ['a', 'a', 'b'] ['a', 'a', 'a', 'b'] ['a', 'a', 'a', 'a', 'b'] ['a', 'a', 'a', 'a', 'a', 'b']
One may prefer to enumerate only simple paths (see
all_simple_paths()
):sage: pi = g.all_paths_iterator(simple=True) sage: sorted(list(pi), key=lambda x:(len(x), x)) [['a', 'a'], ['a', 'b'], ['b', 'c'], ['c', 'd'], ['d', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['c', 'd', 'c'], ['d', 'c', 'd'], ['a', 'b', 'c', 'd']] sage: pi = g.all_paths_iterator(simple=True) sage: [len(p)  1 for p in pi] [1, 1, 1, 1, 1, 2, 2, 2, 2, 3]
Or simply bound the length of the enumerated paths:
sage: pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['b', 'c'], max_length=6) sage: sorted(list(pi), key=lambda x:(len(x), x)) [['a', 'b'], ['a', 'a', 'b'], ['a', 'b', 'c'], ['a', 'a', 'a', 'b'], ['a', 'a', 'b', 'c'], ['a', 'a', 'a', 'a', 'b'], ['a', 'a', 'a', 'b', 'c'], ['a', 'b', 'c', 'd', 'c'], ['a', 'a', 'a', 'a', 'a', 'b'], ['a', 'a', 'a', 'a', 'b', 'c'], ['a', 'a', 'b', 'c', 'd', 'c'], ['a', 'a', 'a', 'a', 'a', 'a', 'b'], ['a', 'a', 'a', 'a', 'a', 'b', 'c'], ['a', 'a', 'a', 'b', 'c', 'd', 'c'], ['a', 'b', 'c', 'd', 'c', 'd', 'c']] sage: pi = g.all_paths_iterator(starting_vertices=['a'], ending_vertices=['b', 'c'], max_length=6) sage: [len(p)  1 for p in pi] [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6]
By default, empty paths are not enumerated, but it may be parametrized:
sage: pi = g.all_paths_iterator(simple=True, trivial=True) sage: sorted(list(pi), key=lambda x:(len(x), x)) [['a'], ['b'], ['c'], ['d'], ['a', 'a'], ['a', 'b'], ['b', 'c'], ['c', 'd'], ['d', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['c', 'd', 'c'], ['d', 'c', 'd'], ['a', 'b', 'c', 'd']] sage: pi = g.all_paths_iterator(simple=True, trivial=True) sage: [len(p)  1 for p in pi] [0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3] sage: pi = g.all_paths_iterator(simple=True, trivial=False) sage: sorted(list(pi), key=lambda x:(len(x), x)) [['a', 'a'], ['a', 'b'], ['b', 'c'], ['c', 'd'], ['d', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['c', 'd', 'c'], ['d', 'c', 'd'], ['a', 'b', 'c', 'd']] sage: pi = g.all_paths_iterator(simple=True, trivial=False) sage: [len(p)  1 for p in pi] [1, 1, 1, 1, 1, 2, 2, 2, 2, 3]

all_simple_cycles
(starting_vertices=None, rooted=False, max_length=None, trivial=False)¶ Return a list of all simple cycles of
self
.INPUT:
starting_vertices
– iterable (default:None
); vertices from which the cycles must start. IfNone
, then all vertices of the graph can be starting points. This argument is necessary ifrooted
is set toTrue
.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 toNone
, then all lengths are allowed.trivial
 boolean (default:False
); if set toTrue
, then the empty paths are also enumerated.
OUTPUT:
listNote
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']]
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, 8, 3], [3, 4, 3], [4, 9, 4], [5, 8, 5], [5, 7, 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, 8, 3], [3, 4, 3], [4, 9, 4], [5, 8, 5], [5, 7, 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, 9, 6, 1, 0], [0, 4, 9, 7, 5, 0], [0, 4, 3, 8, 5, 0], [0, 4, 3, 2, 1, 0], [0, 5, 8, 3, 4, 0], [0, 5, 8, 6, 1, 0], [0, 5, 7, 9, 4, 0], [0, 5, 7, 2, 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, 8, 5, 7, 2], [2, 3, 4, 9, 7, 2], [2, 7, 9, 4, 3, 2], [2, 7, 5, 8, 3, 2], [3, 8, 6, 9, 4, 3], [3, 4, 9, 6, 8, 3], [5, 8, 6, 9, 7, 5], [5, 7, 9, 6, 8, 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, 9, 6, 8, 5, 0], [0, 4, 9, 7, 2, 1, 0], [0, 4, 3, 8, 6, 1, 0], [0, 4, 3, 2, 7, 5, 0], [0, 5, 8, 3, 2, 1, 0], [0, 5, 8, 6, 9, 4, 0], [0, 5, 7, 9, 6, 1, 0], [0, 5, 7, 2, 3, 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, 8, 5, 7, 9, 4, 3], [3, 4, 9, 7, 5, 8, 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]]
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, 1, 0], [0, 2, 0], [0, 3, 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], [0, 16, 0], [0, 17, 0], [0, 18, 0], [0, 19, 0], [1, 2, 1], [1, 3, 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], [1, 16, 1], [1, 17, 1], [1, 18, 1], [1, 19, 1], [2, 3, 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], [2, 16, 2], [2, 17, 2], [2, 18, 2], [2, 19, 2], [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], [3, 16, 3], [3, 17, 3], [3, 18, 3], [3, 19, 3], [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], [4, 16, 4], [4, 17, 4], [4, 18, 4], [4, 19, 4], [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], [5, 16, 5], [5, 17, 5], [5, 18, 5], [5, 19, 5], [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], [6, 16, 6], [6, 17, 6], [6, 18, 6], [6, 19, 6], [7, 8, 7], [7, 9, 7], [7, 10, 7], [7, 11, 7], [7, 12, 7], [7, 13, 7], [7, 14, 7], [7, 15, 7], [7, 16, 7], [7, 17, 7], [7, 18, 7], [7, 19, 7], [8, 9, 8], [8, 10, 8], [8, 11, 8], [8, 12, 8], [8, 13, 8], [8, 14, 8], [8, 15, 8], [8, 16, 8], [8, 17, 8], [8, 18, 8], [8, 19, 8], [9, 10, 9], [9, 11, 9], [9, 12, 9], [9, 13, 9], [9, 14, 9], [9, 15, 9], [9, 16, 9], [9, 17, 9], [9, 18, 9], [9, 19, 9], [10, 11, 10], [10, 12, 10], [10, 13, 10], [10, 14, 10], [10, 15, 10], [10, 16, 10], [10, 17, 10], [10, 18, 10], [10, 19, 10], [11, 12, 11], [11, 13, 11], [11, 14, 11], [11, 15, 11], [11, 16, 11], [11, 17, 11], [11, 18, 11], [11, 19, 11], [12, 13, 12], [12, 14, 12], [12, 15, 12], [12, 16, 12], [12, 17, 12], [12, 18, 12], [12, 19, 12], [13, 14, 13], [13, 15, 13], [13, 16, 13], [13, 17, 13], [13, 18, 13], [13, 19, 13], [14, 15, 14], [14, 16, 14], [14, 17, 14], [14, 18, 14], [14, 19, 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, 1, 0], [0, 2, 0], [0, 3, 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], [0, 16, 0], [0, 17, 0], [0, 18, 0], [0, 19, 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]]

all_simple_paths
(starting_vertices=None, ending_vertices=None, max_length=None, trivial=False)¶ Return a list of all the simple paths of
self
starting with one of the given vertices.Simple paths are paths in which no two arcs share a head or share a tail, i.e. every vertex in the path is entered at most once and exited at most once.
INPUT:
starting_vertices
– list (default:None
); vertices from which the paths must start. IfNone
, then all vertices of the graph can be starting points.ending_vertices
– iterable (default:None
); allowed ending vertices of the paths. IfNone
, then all vertices are allowed.max_length
– non negative integer (default:None
); the maximum length of the enumerated paths. If set toNone
, then all lengths are allowed.trivial
 boolean (default:False
); if set toTrue
, then the empty paths are also enumerated.
OUTPUT:
listNote
Although the number of simple paths of a finite graph is always finite, computing all its paths 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_paths() [['a', 'a'], ['a', 'b'], ['b', 'c'], ['c', 'd'], ['d', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['c', 'd', 'c'], ['d', 'c', 'd'], ['a', 'b', 'c', 'd']]
One may compute all paths having specific starting and/or ending vertices:
sage: g.all_simple_paths(starting_vertices=['a']) [['a', 'a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'c', 'd']] sage: g.all_simple_paths(starting_vertices=['a'], ending_vertices=['c']) [['a', 'b', 'c']] sage: g.all_simple_paths(starting_vertices=['a'], ending_vertices=['b', 'c']) [['a', 'b'], ['a', 'b', 'c']]
It is also possible to bound the length of the paths:
sage: g.all_simple_paths(max_length=2) [['a', 'a'], ['a', 'b'], ['b', 'c'], ['c', 'd'], ['d', 'c'], ['a', 'b', 'c'], ['b', 'c', 'd'], ['c', 'd', 'c'], ['d', 'c', 'd']]
By default, empty paths are not enumerated, but this can be parametrized:
sage: g.all_simple_paths(starting_vertices=['a'], trivial=True) [['a'], ['a', 'a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'c', 'd']] sage: g.all_simple_paths(starting_vertices=['a'], trivial=False) [['a', 'a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'b', 'c', 'd']]

degree_polynomial
()¶ 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)
andout(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.
See also
num_verts()
for the value at \((x, y) = (1, 1)\)EXAMPLES:
sage: G = posets.PentagonPoset().hasse_diagram() sage: G.degree_polynomial() x^2 + 3*x*y + y^2 sage: G = posets.BooleanLattice(4).hasse_diagram() sage: G.degree_polynomial().factor() (x + y)^4

dig6_string
()¶ 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, n1\}\), arelabelled copy
will be encoded, if necessary.See also
graph6_string()
– a similar string format for undirected graphs
EXAMPLES:
sage: D = DiGraph({0: [1, 2], 1: [2], 2: [3], 3: [0]}) sage: D.dig6_string() 'CW`_'

feedback_edge_set
(constraint_generation=True, value_only=False, solver=None, verbose=0)¶ 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
, theSet
of edges of a minimal edge set is returned.
 When set to
constraint_generation
– boolean (default:True
); whether to use constraint generation when solving the Mixed Integer Linear Program.solver
– string (default:None
); specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
); sets the level of verbosity. Set to 0 by default, which means quiet.
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_ud_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,n1]\) 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) 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: dg = DiGraph(g) sage: feedback = dg.feedback_edge_set() sage: u,v,l = next(g.edge_iterator()) sage: (u,v) in feedback or (v,u) in feedback True

flow_polytope
(edges=None, ends=None)¶ 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 ofself
. The order of the edges is the one returned byself.edges()
. If a different order is desired, it can be specified using the optionaledges
parameter.The faces and volume of these polytopes are of interest. Examples of these polytopes are the ChanRobbinsYuen polytope and the PitmanStanley polytope [PitSta].
INPUT:
edges
– (optional, default:self.edges()
) a list or tuple of all edges ofself
(each only once). This determines which coordinate of a point in the polytope will correspond to which edge ofself
. It is also possible to specify a list which contains not all edges ofself
; 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 byself.edges()
; so, ifself.edges()
outputs an edge in the form(1, 3, None)
, then(1, 3)
will not do!ends
– (optional, default:(self.sources(), self.sinks())
) a pair \((S, T)\) of an iterable \(S\) and an iterable \(T\).
Note
Flow polytopes can also be built through the
polytopes.<tab>
object:sage: polytopes.flow_polytope(digraphs.Path(5)) A 0dimensional 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 A 1dimensional polyhedron in QQ^4 defined as the convex hull of 2 vertices sage: fl.vertices() (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: fl = G.flow_polytope(edges=G.edges(key=lambda x: x[0]  x[1])); fl A 1dimensional polyhedron in QQ^4 defined as the convex hull of 2 vertices sage: fl.vertices() (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 A 3dimensional polyhedron in QQ^6 defined as the convex hull of 4 vertices sage: fl.vertices() (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), ....: (2, 3, None), (0, 3, None)]) sage: fl A 1dimensional polyhedron in QQ^4 defined as the convex hull of 2 vertices sage: fl.vertices() (A vertex at (0, 0, 0, 1), A vertex at (1, 1, 1, 0))
Using a different choice of sources and sinks:
sage: fl = H.flow_polytope(ends=([1], [3])); fl A 1dimensional 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 3dimensional 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 2dimensional 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))
A digraph with one source and two sinks:
sage: Y = DiGraph({1: [2], 2: [3, 4]}) sage: Y.flow_polytope() The empty polyhedron in QQ^3
A digraph with one vertex and no edge:
sage: Z = DiGraph({1: []}) sage: Z.flow_polytope() A 0dimensional polyhedron in QQ^0 defined as the convex hull of 1 vertex
REFERENCES:
[PitSta] Jim Pitman, Richard Stanley, “A polytope related to empirical distributions, plane trees, parking functions, and the associahedron”, Arxiv math/9908029

immediate_dominators
(r, reverse=False)¶ Return the immediate dominators of all vertices reachable from \(r\).
A flowgraph \(G = (V, A, r)\) is a digraph where every vertex in \(V\) is reachable from a distinguished root vertex \(r\in V\). In such digraph, a vertex \(w\) dominates a vertex \(v\) if every path from \(r\) to \(v\) includes \(w\). Let \(dom(v)\) be the set of the vertices that dominate \(v\). Obviously, \(r\) and \(v\), the trivial dominators of \(v\), are in \(dom(v)\). For \(v \neq r\), the immediate dominator of \(v\), denoted by \(d(v)\), is the unique vertex \(w \neq v\) that dominates \(v\) and is dominated by all the vertices in \(dom(v)\setminus\{v\}\). The (immediate) dominator tree is a directed tree (or arborescence) rooted at \(r\) that is formed by the arcs \(\{ (d(v), v)\mid v\in V\setminus\{r\}\}\). See [Ge2005] for more details.
This method implements the algorithm proposed in [CHK2001] which performs very well in practice, although its worst case time complexity is in \(O(n^2)\).
INPUT:
r
– a vertex of the digraph, the root of the immediate dominators treereverse
– boolean (default:False
); when set toTrue
, we consider the reversed digraph in which outneighbors become the inneighbors and viceversa. This option is available only if the backend of the digraph isSparseGraphBackend
.
OUTPUT: The (immediate) dominator tree rooted at \(r\), encoded as a predecessor dictionary.
EXAMPLES:
The output encodes a tree rooted at \(r\):
sage: D = digraphs.Complete(4) * 2 sage: D.add_edges([(0, 4), (7, 3)]) sage: d = D.immediate_dominators(0) doctest:...: DeprecationWarning: immediate_dominators is now deprecated. Please use method dominator_tree instead. See https://trac.sagemath.org/25030 for details. sage: T = DiGraph([(d[u], u) for u in d if u != d[u]]) sage: Graph(T).is_tree() True sage: all(T.in_degree(u) <= 1 for u in T) True
In a strongly connected digraph, the result depends on the root:
sage: D = digraphs.Circuit(5) sage: D.immediate_dominators(0) {0: 0, 1: 0, 2: 1, 3: 2, 4: 3} sage: D.immediate_dominators(1) {0: 4, 1: 1, 2: 1, 3: 2, 4: 3}
The (immediate) dominator tree contains only reachable vertices:
sage: P = digraphs.Path(5) sage: P.immediate_dominators(0) {0: 0, 1: 0, 2: 1, 3: 2, 4: 3} sage: P.immediate_dominators(3) {3: 3, 4: 3}
Immediate dominators in the reverse digraph:
sage: D = digraphs.Complete(5)+digraphs.Complete(4) sage: D.add_edges([(0, 5), (1, 6), (7, 2)]) sage: idom = D.immediate_dominators(0, reverse=True) sage: idom {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 7, 6: 7, 7: 2, 8: 7} sage: D_reverse = D.reverse() sage: D_reverse.immediate_dominators(0) == idom True

in_degree
(vertices=None, labels=False)¶ 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

in_degree_iterator
(vertices=None, labels=False)¶ 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)]

in_degree_sequence
()¶ Return the indegree sequence.
EXAMPLES:
The indegree 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]
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]

incoming_edge_iterator
(vertices, labels=True)¶ Return an iterator over all arriving edges from vertices.
INPUT:
vertices
– a vertex or a list of verticeslabels
– 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)

incoming_edges
(vertices, labels=True)¶ Return a list of edges arriving at vertices.
INPUT:
vertices
– a vertex or a list of verticeslabels
– 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)]

is_aperiodic
()¶ 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
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
See also

is_directed
()¶ Since digraph is directed, return
True
.EXAMPLES:
sage: DiGraph().is_directed() True

is_directed_acyclic
(certificate=False)¶ Return 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)
whereordering
is a list of the vertices such thatu
appears beforev
inordering
ifu, v
is an edge.  Else, returns a pair
(False, cycle)
wherecycle
is a list of vertices representing a circuit in the graph.
 If the graph is acyclic, returns a pair
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() sage: 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
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])
Adding an edge from 7 to 4, though, makes a difference:
sage: D.add_edge(7, 4) sage: D.is_directed_acyclic() False
Indeed, it creates a circuit \(7, 4, 5\):
sage: 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)) # long time True

is_strongly_connected
(G)¶ 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
But a transitive triangle is not:
sage: g = DiGraph({0: [1, 2], 1: [2]}) sage: is_strongly_connected(g) False

is_tournament
()¶ 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.add_edge(v, u) sage: g.is_tournament() False sage: g.add_edges([(u, v), (v, u)]) sage: g.is_tournament() False

is_transitive
(g, certificate=False)¶ 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 returnsTrue
orFalse
according to the graph.  If
certificate = True
, this method either returnsTrue
answers or yield a pair of vertices \(uv\) such that there exists a \(uv\)path in \(G\) but \(uv\not\in G\).
 If
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) sage: D.is_transitive() False sage: cert = D.is_transitive(certificate=True) sage: D.has_edge(*cert) False sage: D.shortest_path(*cert) != [] True sage: digraphs.RandomDirectedGNP(20,.2).transitive_closure().is_transitive() True

layout_acyclic
(rankdir='up', **options)¶ 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
anddot2tex
if available (seelayout_graphviz()
), and using a spring layout with fixed vertical placement of the vertices otherwise (seelayout_acyclic_dummy()
andlayout_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 tolayout_ranked()
orlayout_graphviz()
EXAMPLES:
sage: H = DiGraph({0: [1, 2], 1: [3], 2: [3], 3: [], 5: [1, 6], 6: [2, 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

layout_acyclic_dummy
(heights=None, rankdir='up', **options)¶ 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 (seelayout_acyclic_dummy()
andlayout_ranked()
).INPUT:
rankdir
– string (default:'up'
); indicates which direction the edges should point toward among'up'
,'down'
,'left'
, or'right'
**options
– passed down tolayout_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.00..., 0], 1: [1.00..., 1], 2: [1.51..., 2], 3: [1.50..., 3], 5: [2.01..., 0], 6: [2.00..., 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

level_sets
()¶ 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[i1]\) (unless \(i = 0\)).
The level decomposition contains exactly the vertices not occuring 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]]
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]
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]
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)¶ Return an iterator over the inneighbors of
vertex
.An vertex \(u\) is an inneighbor 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

neighbor_out_iterator
(vertex)¶ Return an iterator over the outneighbors of a given vertex.
A vertex \(u\) is an outneighbor 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

neighbors_in
(vertex)¶ Return the list of the inneighbors of a given vertex.
A vertex \(u\) is an inneighbor 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]

neighbors_out
(vertex)¶ Return the list of the outneighbors of a given vertex.
A vertex \(u\) is an outneighbor 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]

out_degree
(vertices=None, labels=False)¶ 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

out_degree_iterator
(vertices=None, labels=False)¶ 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)]

out_degree_sequence
()¶ 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]
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]

outgoing_edge_iterator
(vertices, labels=True)¶ Return an iterator over all departing edges from vertices.
INPUT:
vertices
– a vertex or a list of verticeslabels
– 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)

outgoing_edges
(vertices, labels=True)¶ Return a list of edges departing from vertices.
INPUT:
vertices
– a vertex or a list of verticeslabels
– 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)]

path_semigroup
()¶ 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 Partial semigroup formed by the directed paths of Multidigraph on 3 vertices sage: list(F) [e_1, e_2, e_3, a, c, b, a*b, c*b]

period
()¶ 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
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
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]
ALGORITHM:
See the networkX implementation of
is_aperiodic
, that is based on breadth first search.See also

reverse
()¶ Return a copy of digraph with edges reversed in direction.
EXAMPLES:
sage: D = DiGraph({0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1]}) sage: D.reverse() Reverse of (): Digraph on 6 vertices

reverse_edge
(u, v=None, label=None, inplace=True, multiedges=None)¶ Reverse the edge from \(u\) to \(v\).
INPUT:
inplace
– boolean (default:True
); ifFalse
, a new digraph is created and returned as output, otherwiseself
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 (settingmultiedges
toTrue
orFalse
) is necessary to perform the operation. If set to
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
isTrue
(default value),self
is modified:sage: D = DiGraph([(0, 1 ,2)]) sage: D.reverse_edge(0, 1) sage: D.edges() [(1, 0, 2)]
If
inplace
isFalse
,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() [(1, 0, 2)] sage: D.edges() [(0, 1, 2)]
If
multiedges
isTrue
,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() [(2, 1, 'A'), (2, 1, 'A'), (2, 3, None)] sage: D.allows_multiple_edges() True
Even if
multiedges
isTrue
,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() [(1, 2, 'A'), (2, 1, 'A'), (3, 2, None)] sage: 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() [(1, 2, 'A'), (2, 1, 'A'), (2, 3, None)] sage: D.reverse_edge(1, 2, multiedges=False) sage: D.edges() [(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() [(1, 2, 'B'), (2, 1, 'A'), (2, 3, None)] sage: D.reverse_edge(2, 1, multiedges=False) sage: D.edges() [(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() [(1, 0, 2), (1, 2, 1)] sage: re = D.reverse_edge([1, 2], inplace=False) sage: re.edges() [(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() [(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 byedge_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() [(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.
The following syntax is supported, but note that you must use the
label
keyword:sage: D = DiGraph() sage: D.add_edge((1, 2), label='label') sage: D.edges() [(1, 2, 'label')] sage: D.reverse_edge((1, 2), label='label') sage: D.edges() [(2, 1, 'label')] sage: D.add_edge((1, 2), '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')]

reverse_edges
(edges, inplace=True, multiedges=None)¶ Reverse a list of edges.
INPUT:
edges
– a list of edges in the DiGraph.inplace
– boolean (default:True
); ifFalse
, a new digraph is created and returned as output, otherwiseself
is modified.multiedges
– boolean (default:None
); ifTrue
, input graph will be forced to allow parallel edges when necessary (for more information see the documentation ofreverse_edge()
)
See also
reverse_edge()
 Reverses a single edge.EXAMPLES:
If
inplace
isTrue
(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() [(0, 1, None), (1, 0, None), (2, 3, None), (3, 0, None), (3, 2, None), (4, 1, None), (5, 4, None)]
If
inplace
isFalse
,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() [(1, 0, 'A'), (1, 0, 'B'), (2, 1, 'C')] sage: D.edges() [(0, 1, 'A'), (1, 0, 'B'), (1, 2, 'C')] sage: D.allows_multiple_edges() False sage: re.allows_multiple_edges() True
If
multiedges
isTrue
,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() [(2, 1, 'A'), (2, 1, 'A'), (3, 2, None)] sage: D.allows_multiple_edges() True
Even if
multiedges
isTrue
,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() [(1, 2, 'A'), (2, 1, 'A'), (3, 2, None)] sage: D.allows_multiple_edges() False
If
multiedges
isFalse
,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() [(1, 2, None), (2, 1, None)] sage: D.reverse_edges([(1, 2)], multiedges=False) sage: D.edges() [(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() [(1, 0, '01'), (2, 1, 1), (3, 2, '23')]

sinks
()¶ 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]

sources
()¶ 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]

strong_articulation_points
(G)¶ 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: D.add_clique([3, 4, 5, 6]) sage: strong_articulation_points(D) [3] sage: D.strong_articulation_points() [3]
Two cliques connected by some arcs:
sage: D = digraphs.Complete(4) * 2 sage: D.add_edges([(0, 4), (7, 3)]) sage: sorted(strong_articulation_points(D)) [0, 3, 4, 7] sage: D.add_edge(1, 5) sage: sorted(strong_articulation_points(D)) [3, 7] sage: D.add_edge(6, 2) sage: strong_articulation_points(D) []

strongly_connected_component_containing_vertex
(G, v)¶ Return the strongly connected component containing a given vertex
INPUT:
G
– the input DiGraphv
– 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]
sage: g = DiGraph([(0, 1), (1, 0), (1, 2), (2, 3), (3, 2)]) sage: strongly_connected_component_containing_vertex(g, 0) [0, 1]

strongly_connected_components
(G)¶ 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 depthfirst 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.
For more information, see the Wikipedia article Tarjan’s_strongly_connected_components_algorithm.
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() [[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.add_edge([2,0]) 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']]

strongly_connected_components_digraph
(G, keep_labels=False)¶ 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 DiGraphkeep_labels
– boolean (default:False
); whenkeep_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). Whenkeep_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
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
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
By default, the labels are discarded, and the result has no loops nor multiple edges. If
keep_labels
isTrue
, 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: "012", 2: "012", 3: "03"}, 1: {2: "12", 3: "13"}, 2: {1: "21", 3: "23"}}) 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

strongly_connected_components_subgraphs
(G)¶ 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]
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]

to_directed
()¶ 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

to_undirected
(implementation='c_graph', data_structure=None, sparse=None)¶ Return an undirected version of the graph.
Every directed edge becomes an edge.
INPUT:
EXAMPLES:
sage: D = DiGraph({0: [1, 2], 1: [0]}) sage: G = D.to_undirected() sage: D.edges(labels=False) [(0, 1), (0, 2), (1, 0)] sage: G.edges(labels=False) [(0, 1), (0, 2)]

topological_sort
(implementation='default')¶ 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"
)
See also
is_directed_acyclic()
– Tests whether a directed graph is acyclic (can also join a certificate – a topological sort or a circuit in the graph).
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() sage: 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]
Using the NetworkX implementation
sage: list(D.topological_sort(implementation="NetworkX")) [4, 5, 6, 9, 0, 3, 2, 7, 1, 8, 10]
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

topological_sort_generator
()¶ 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. 373386.
EXAMPLES:
sage: D = DiGraph({0: [1, 2], 1: [3], 2: [3, 4]}) sage: D.plot(layout='circular').show() sage: list(D.topological_sort_generator()) [[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(): ....: for u, v in D.edge_iterator(labels=False): ....: if sort.index(u) > sort.index(v): ....: print("this should never happen")