This module implements functions and operations involving directed graphs. Here is what they can do
Graph basic operations:
layout_acyclic_dummy() | Computes a (dummy) ranked layout so that all edges point upward. |
layout_acyclic() | Computes a ranked layout so that all edges point upward. |
reverse() | Returns a copy of digraph with edges reversed in direction. |
reverse_edge() | Reverses an edge. |
reverse_edges() | Reverses 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() | Returns the list of the out-neighbors of a given vertex. |
neighbor_out_iterator() | Returns an iterator over the out-neighbors of a given vertex. |
neighbors_in() | Returns the list of the in-neighbors of a given vertex. |
neighbor_in_iterator() | Returns an iterator over the in-neighbors of vertex. |
outgoing_edges() | Returns a list of edges departing from vertices. |
outgoing_edge_iterator() | Return an iterator over all departing edges from vertices |
incoming_edges() | Returns a list of edges arriving at vertices. |
incoming_edge_iterator() | Return an iterator over all arriving edges from vertices |
sources() | Returns the list of all sources (vertices without incoming edges) of this digraph. |
sinks() | Returns the list of all sinks (vertices without outoing edges) of this digraph. |
to_undirected() | Returns 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() | Returns the dig6 representation of the digraph as an ASCII string. |
Paths and cycles:
all_paths_iterator() | Returns an iterator over the paths of self. The paths are |
all_simple_paths() | Returns a list of all the simple paths of self starting |
all_cycles_iterator() | Returns an iterator over all the cycles of self starting |
all_simple_cycles() | Returns a list of all simple cycles of self. |
Representation theory:
path_semigroup() | Returns the (partial) semigroup formed by the paths of the digraph. |
Connectivity:
is_strongly_connected() | Returns whether the current DiGraph is strongly connected. |
strongly_connected_components_digraph() | Returns the digraph of the strongly connected components |
strongly_connected_components_subgraphs() | Returns the strongly connected components as a list of subgraphs. |
strongly_connected_component_containing_vertex() | Returns the strongly connected component containing a given vertex |
strongly_connected_components() | Returns the list of strongly connected components. |
Acyclicity:
is_directed_acyclic() | Returns whether the digraph is acyclic or not. |
is_transitive() | Returns whether the digraph is transitive or not. |
is_aperiodic() | Returns whether the digraph is aperiodic or not. |
period() | Returns the period of the digraph. |
level_sets() | Returns the level set decomposition of the digraph. |
topological_sort_generator() | Returns a list of all topological sorts of the digraph if it is acyclic |
topological_sort() | Returns a topological sort of the digraph if it is acyclic |
Hard stuff:
feedback_edge_set() | Computes the minimum feedback edge (arc) set of a digraph |
Bases: sage.graphs.generic_graph.GenericGraph
Directed graph.
A digraph or directed graph is a set of vertices connected by oriented edges. For more information, see the Wikipedia article on digraphs.
One can very easily create a directed graph in Sage by typing:
sage: g = DiGraph()
By typing the name of the digraph, one can get some basic information about it:
sage: g
Digraph on 0 vertices
This digraph is not very interesting as it is by default the empty graph. But Sage contains several pre-defined digraph classes that can be listed this way:
You will see a list of methods which will construct named digraphs. For example:
sage: g = digraphs.ButterflyGraph(3)
sage: g.plot()
Graphics object consisting of 81 graphics primitives
You can also use the collection of pre-defined graphs, then create a digraph from them.
sage: g = DiGraph(graphs.PetersenGraph())
sage: g.plot()
Graphics object consisting of 50 graphics primitives
Calling Digraph on a graph returns the original graph in which every edge is replaced by two different edges going toward opposite directions.
In order to obtain more information about these digraph constructors, access the documentation by typing digraphs.RandomDirectedGNP?.
Once you have defined the digraph you want, you can begin to work on it by using the almost 200 functions on graphs and digraphs in the Sage library! If your digraph is named g, you can list these functions as previously this way
As usual, you can get some information about what these functions do by typing (e.g. if you want to know about the diameter() method) g.diameter?.
If you have defined a digraph g having several connected components ( i.e. g.is_connected() returns False ), you can print each one of its connected components with only two lines:
sage: for component in g.connected_components():
....: g.subgraph(component).plot()
Graphics object consisting of 50 graphics primitives
The same methods works for strongly connected components
sage: for component in g.strongly_connected_components():
....: g.subgraph(component).plot()
Graphics object consisting of 50 graphics primitives
INPUT:
data - can be any of the following (see the format keyword):
pos - 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 - (must be an explicitly named parameter, i.e., name=”complete”) gives the graph a name
loops - boolean, whether to allow loops (ignored if data is an instance of the DiGraph class)
multiedges - boolean, whether to allow multiple edges (ignored if data is an instance of the DiGraph class)
weighted - whether digraph thinks of itself as weighted or not. See self.weighted()
format - if None, DiGraph tries to guess- can be several values, including:
'adjacency_matrix' - a square Sage matrix M, with M[i,j] equal to the number of edges {i,j}
'incidence_matrix' - a Sage matrix, with one column C for each edge, where if C represents {i, j}, C[i] is -1 and C[j] is 1
'weighted_adjacency_matrix' - a square Sage matrix M, with M[i,j] equal to the weight of the single edge {i,j}. Given this format, weighted is ignored (assumed True).
NX - data must be a NetworkX DiGraph.
Note
As Sage’s default edge labels is None while NetworkX uses {}, the {} labels of a NetworkX digraph are automatically set to None when it is converted to a Sage graph. This behaviour can be overruled by setting the keyword convert_empty_dict_labels_to_None to False (it is True by default).
boundary - a list of boundary vertices, if empty, digraph is considered as a ‘graph without boundary’
implementation - what to use as a backend for the graph. Currently, the options are either ‘networkx’ or ‘c_graph’
sparse (boolean) – sparse=True is an alias for data_structure="sparse", and sparse=False is an alias for data_structure="dense".
data_structure – one of the following
Only available when implementation == 'c_graph'
immutable (boolean) – whether to create a immutable digraph. Note that immutable=True is actually a shortcut for data_structure='static_sparse'. Set to False by default, only available when implementation='c_graph'
vertex_labels - only for implementation == ‘c_graph’. 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 - 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:
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 numpy matrix or ndarray:
sage: import numpy
sage: A = numpy.array([[0,1,0],[1,0,0],[1,1,0]])
sage: DiGraph(A)
Digraph on 3 vertices
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); 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 c_graph implemented DiGraph can be constructed from a networkx implemented DiGraph:
sage: D = DiGraph({0:[1],1:[2],2:[0]}, implementation="networkx")
sage: E = DiGraph(D,implementation="c_graph")
sage: D == E
True
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
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
Note that in all cases, we copy the NetworkX structure.
sage: import networkx
sage: g = networkx.DiGraph({0:[1,2,3], 2:[4]})
sage: G = DiGraph(g, implementation='networkx')
sage: H = DiGraph(g, implementation='networkx')
sage: G._backend._nxg is H._backend._nxg
False
TESTS:
sage: DiGraph({0:[1,2,3], 2:[4]}).edges()
[(0, 1, None), (0, 2, None), (0, 3, None), (2, 4, None)]
sage: DiGraph({0:(1,2,3), 2:(4,)}).edges()
[(0, 1, None), (0, 2, None), (0, 3, None), (2, 4, None)]
sage: DiGraph({0:Set([1,2,3]), 2:Set([4])}).edges()
[(0, 1, None), (0, 2, None), (0, 3, None), (2, 4, None)]
Get rid of mutable default argument for \(boundary\) (trac ticket #14794):
sage: D = DiGraph(boundary=None)
sage: D._boundary
[]
Demonstrate that digraphs using the static backend are equal to mutable graphs but can be used as dictionary keys:
sage: import networkx
sage: g = networkx.DiGraph({0:[1,2,3], 2:[4]})
sage: G = DiGraph(g, implementation='networkx')
sage: G_imm = DiGraph(G, data_structure="static_sparse")
sage: H_imm = DiGraph(G, data_structure="static_sparse")
sage: H_imm is G_imm
False
sage: H_imm == G_imm == G
True
sage: {G_imm:1}[H_imm]
1
sage: {G_imm:1}[G]
Traceback (most recent call last):
...
TypeError: This graph is mutable, and thus not hashable. Create an
immutable copy by `g.copy(immutable=True)`
The error message states that one can also create immutable graphs by specifying the immutable optional argument (not only by data_structure='static_sparse' as above):
sage: J_imm = DiGraph(G, immutable=True)
sage: J_imm == G_imm
True
sage: type(J_imm._backend) == type(G_imm._backend)
True
Returns an iterator over all the cycles of self starting with one of the given vertices. The cycles are enumerated in increasing length order.
INPUT:
OUTPUT:
iterator
Note
See also all_simple_cycles().
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']
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]]
Returns an iterator over the paths of self. The paths are enumerated in increasing length order.
INPUT:
OUTPUT:
iterator
AUTHOR:
Alexandre Blondin Masse
EXAMPLES:
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): print next(pi)
['a', 'a']
['a', 'b']
['b', 'c']
['c', 'd']
['d', 'c']
['a', 'a', 'a']
['a', 'a', 'b']
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): print next(pi)
['a', 'a']
['a', 'b']
['a', 'a', 'a']
['a', 'a', 'b']
['a', 'b', 'c']
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: list(pi)
[['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']]
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: list(pi)
[['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']]
By default, empty paths are not enumerated, but it may be parametrized:
sage: pi = g.all_paths_iterator(simple=True, trivial=True)
sage: list(pi)
[['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=False)
sage: list(pi)
[['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']]
Returns a list of all simple cycles of self.
INPUT:
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']]
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]]
Returns 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:
OUTPUT:
list
Note
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']]
Returns the dig6 representation of the digraph as an ASCII string. Valid for single (no multiple edges) digraphs on 0 to 262143 vertices.
EXAMPLES:
sage: D = DiGraph()
sage: D.dig6_string()
'?'
sage: D.add_edge(0,1)
sage: D.dig6_string()
'AO'
Computes 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 on feedback arc sets.
INPUT:
ALGORITHM:
This problem is solved using Linear Programming, in two different ways. The first one is to solve the following formulation:
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 :
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
TESTS:
Comparing with/without constraint generation. Also double-checks ticket trac ticket #12833:
sage: for i in range(20):
... g = digraphs.RandomDirectedGNP(10,.3)
... x = g.feedback_edge_set(value_only = True)
... y = g.feedback_edge_set(value_only = True,
... constraint_generation = False)
... if x != y:
... print "Oh my, oh my !"
... break
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
Same as degree_iterator, but for in degree.
EXAMPLES:
sage: D = graphs.Grid2dGraph(2,4).to_directed()
sage: for i in D.in_degree_iterator():
... print i
3
3
2
3
2
2
2
3
sage: for i in D.in_degree_iterator(labels=True):
... print i
((0, 1), 3)
((1, 2), 3)
((0, 0), 2)
((0, 2), 3)
((1, 3), 2)
((1, 0), 2)
((0, 3), 2)
((1, 1), 3)
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]
Return an iterator over all arriving edges from vertices.
INPUT:
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)
Returns a list of edges arriving at vertices.
INPUT:
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)]
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, cf. Wikipedia article Aperiodic_graph.
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
Since digraph is directed, returns True.
EXAMPLES:
sage: DiGraph().is_directed()
True
Returns 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:
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 u, v 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()
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.edges() ])
... return h
...
sage: all( random_acyclic(100, .2).is_directed_acyclic() # long time
... for i in range(50)) # long time
True
TESTS:
What about loops?:
sage: g = digraphs.ButterflyGraph(3)
sage: g.allow_loops(True)
sage: g.is_directed_acyclic()
True
sage: g.add_edge(0,0)
sage: g.is_directed_acyclic()
False
Returns whether the current DiGraph is strongly connected.
EXAMPLE:
The circuit is obviously strongly connected
sage: g = digraphs.Circuit(5)
sage: g.is_strongly_connected()
True
But a transitive triangle is not:
sage: g = DiGraph({ 0 : [1,2], 1 : [2]})
sage: g.is_strongly_connected()
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:
EXAMPLE:
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: digraphs.DeBruijn(5,2).is_transitive()
False
sage: digraphs.DeBruijn(5,2).is_transitive(certificate = True)
('00', '10')
sage: digraphs.RandomDirectedGNP(20,.2).transitive_closure().is_transitive()
True
Computes 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 random horizontal placement of the vertices otherwise (see layout_acyclic_dummy()).
Non acyclic graphs are partially supported by graphviz, which then chooses some edges to point down.
EXAMPLES:
sage: H = DiGraph({0:[1,2],1:[3],2:[3],3:[],5:[1,6],6:[2,3]})
The actual layout computed will depend on whether dot2tex and graphviz are installed, so we don’t test it.
sage: H.layout_acyclic() {0: [..., ...], 1: [..., ...], 2: [..., ...], 3: [..., ...], 5: [..., ...], 6: [..., ...]}
Computes a (dummy) ranked layout of an acyclic graph 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()).
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,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
Returns 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 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).
Returns an iterator over the in-neighbors of vertex.
An 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
Returns an iterator over the out-neighbors of a given vertex.
An 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
Returns the list of the in-neighbors of a given vertex.
An 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]
Returns the list of the out-neighbors of a given vertex.
An 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]
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
Same as degree_iterator, but for out degree.
EXAMPLES:
sage: D = graphs.Grid2dGraph(2,4).to_directed()
sage: for i in D.out_degree_iterator():
... print i
3
3
2
3
2
2
2
3
sage: for i in D.out_degree_iterator(labels=True):
... print i
((0, 1), 3)
((1, 2), 3)
((0, 0), 2)
((0, 2), 3)
((1, 3), 2)
((1, 0), 2)
((0, 3), 2)
((1, 1), 3)
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]
Return an iterator over all departing edges from vertices.
INPUT:
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)
Returns a list of edges departing from vertices.
INPUT:
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)]
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 Multi-digraph on 3 vertices
sage: list(F)
[e_1, e_2, e_3, a, c, b, a*b, c*b]
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, cf. Wikipedia article Aperiodic_graph.
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
Returns 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
Reverses the edge from u to v.
INPUT:
and returned as output, otherwise self is modified.
multiedges – (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:
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()
[(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()
[(1, 0, 2)]
sage: D.edges()
[(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()
[(2, 1, 'A'), (2, 1, 'A'), (2, 3, None)]
sage: 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()
[(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 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()
[(0, 1, 'A'), (0, 1, 'B'), (0, 1, 'mouse'), (1, 0, 'cat')]
Finally, an exception is raised when Sage does not know how to chose 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()
[(2, 1, 'label'), ((1, 2), 'label', None)]
sage: D.reverse_edge((1,2), 'label')
sage: D.edges()
[(2, 1, 'label'), ('label', (1, 2), None)]
TESTS:
sage: D = DiGraph([(0,1,None)])
sage: D.reverse_edge(0,1,'mylabel')
Traceback (most recent call last):
...
ValueError: Input edge must exist in the digraph.
Reverses a list of edges.
INPUT:
edges – a list of edges in the DiGraph.
and returned as output, otherwise self is modified.
forced to allow parallel edges when necessary (for more information see the documentation of reverse_edge())
See also
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()
[(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()
[(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 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()
[(2, 1, 'A'), (2, 1, 'A'), (3, 2, None)]
sage: 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()
[(1, 2, 'A'), (2, 1, 'A'), (3, 2, None)]
sage: 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()
[(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')]
TESTS:
sage: D = digraphs.Circuit(6)
sage: D.reverse_edges(D.edges(),inplace=False).edges()
[(0, 5, None), (1, 0, None), (2, 1, None),
(3, 2, None), (4, 3, None), (5, 4, None)]
sage: D = digraphs.Kautz(2,3)
sage: Dr = D.reverse_edges(D.edges(),inplace=False,multiedges=True)
sage: Dr.edges() == D.reverse().edges()
True
Returns a list of sinks of the digraph.
OUTPUT:
EXAMPLES:
sage: G = DiGraph({1:{3:['a']}, 2:{3:['b']}})
sage: G.sinks()
[3]
sage: T = DiGraph({1:{}})
sage: T.sinks()
[1]
Returns a list of sources of the digraph.
OUTPUT:
EXAMPLES:
sage: G = DiGraph({1:{3:['a']}, 2:{3:['b']}})
sage: G.sources()
[1, 2]
sage: T = DiGraph({1:{}})
sage: T.sources()
[1]
Returns the strongly connected component containing a given vertex
INPUT:
EXAMPLE:
In the symmetric digraph of a graph, the strongly connected components are the connected components:
sage: g = graphs.PetersenGraph()
sage: d = DiGraph(g)
sage: d.strongly_connected_component_containing_vertex(0)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Returns the list of strongly connected components.
EXAMPLES:
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()
[[0], [1], [2], [3], [4], [5], [6]]
sage: D.add_edge([2,0])
sage: D.strongly_connected_components()
[[0, 1, 2], [3], [4], [5], [6]]
TESTS:
Checking against NetworkX, and another of Sage’s implementations:
sage: from sage.graphs.base.static_sparse_graph import strongly_connected_components
sage: import networkx
sage: for i in range(100): # long
... g = digraphs.RandomDirectedGNP(100,.05) # long
... h = g.networkx_graph() # long
... scc1 = g.strongly_connected_components() # long
... scc2 = networkx.strongly_connected_components(h) # long
... scc3 = strongly_connected_components(g) # long
... s1 = Set(map(Set,scc1)) # long
... s2 = Set(map(Set,scc2)) # long
... s3 = Set(map(Set,scc3)) # long
... if s1 != s2: # long
... print "Ooch !" # long
... if s1 != s3: # long
... print "Oooooch !" # long
Returns the digraph of the strongly connected components
INPUT:
- keep_labels – boolean (default: False)
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 from one to the other in \(G\).
EXAMPLE:
Such a digraph is always acyclic
sage: g = digraphs.RandomDirectedGNP(15,.1)
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 = g.strongly_connected_components_digraph()
sage: g.is_directed_acyclic()
True
sage: all([ Set(scc) in scc_digraph.vertices() for scc in g.strongly_connected_components()])
True
The following digraph has three strongly connected components, and the digraph of those is a chain:
sage: g = DiGraph({0:{1:"01", 2: "02", 3: 03}, 1: {2: "12"}, 2:{1: "21", 3: "23"}})
sage: scc_digraph = g.strongly_connected_components_digraph()
sage: scc_digraph.vertices()
[{0}, {3}, {1, 2}]
sage: scc_digraph.edges()
[({0}, {3}, None), ({0}, {1, 2}, None), ({1, 2}, {3}, None)]
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: scc_digraph = g.strongly_connected_components_digraph(keep_labels = True)
sage: scc_digraph.vertices()
[{0}, {3}, {1, 2}]
sage: scc_digraph.edges()
[({0}, {3}, '0-3'), ({0}, {1, 2}, '0-12'),
({1, 2}, {3}, '1-3'), ({1, 2}, {3}, '2-3'),
({1, 2}, {1, 2}, '1-2'), ({1, 2}, {1, 2}, '2-1')]
Returns the strongly connected components as a list of subgraphs.
EXAMPLE:
In the symmetric digraph of a graph, the strongly connected components are the connected components:
sage: g = graphs.PetersenGraph()
sage: d = DiGraph(g)
sage: d.strongly_connected_components_subgraphs()
[Subgraph of (Petersen graph): Digraph on 10 vertices]
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
Returns an undirected version of the graph. Every directed edge becomes an edge.
INPUT:
- implementation - string (default: ‘networkx’) the implementation goes here. Current options are only ‘networkx’ or ‘c_graph’.
- data_structure – one of "sparse", "static_sparse", or "dense". See the documentation of Graph or DiGraph.
- sparse (boolean) – 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(labels=False)
[(0, 1), (0, 2), (1, 0)]
sage: G.edges(labels=False)
[(0, 1), (0, 2)]
TESTS:
Immutable graphs yield immutable graphs (trac ticket #17005):
sage: DiGraph([[1, 2]], immutable=True).to_undirected()._backend
<class 'sage.graphs.base.static_sparse_backend.StaticSparseBackend'>
Returns a topological sort of the digraph if it is acyclic, and raises a TypeError if the digraph contains a directed cycle. 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:
See also
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: D.topological_sort(implementation = "NetworkX")
[4, 5, 6, 9, 0, 1, 2, 3, 7, 8, 10]
Using the NetworkX recursive implementation
sage: D.topological_sort(implementation = "recursive")
[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.
Note
There is a recursive version of this in NetworkX, it used to have problems in earlier versions but they have since been fixed:
sage: import networkx
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: N = D.networkx_graph()
sage: networkx.topological_sort(N)
[4, 5, 6, 9, 0, 1, 2, 3, 7, 8, 10]
sage: networkx.topological_sort_recursive(N)
[4, 5, 6, 9, 0, 3, 2, 7, 1, 8, 10]
TESTS:
A wrong value for the implementation keyword:
sage: D.topological_sort(implementation = "cloud-reading")
Traceback (most recent call last):
...
ValueError: implementation must be set to one of "default"
or "NetworkX"
Returns a list of all topological sorts of the digraph if it is acyclic, and raises a TypeError if the digraph contains a directed cycle.
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 Graph.topological_sort().
AUTHORS:
REFERENCE:
EXAMPLES:
sage: D = DiGraph({ 0:[1,2], 1:[3], 2:[3,4] })
sage: D.plot(layout='circular').show()
sage: D.topological_sort_generator()
[[0, 1, 2, 3, 4], [0, 1, 2, 4, 3], [0, 2, 1, 3, 4], [0, 2, 1, 4, 3], [0, 2, 4, 1, 3]]
sage: for sort in D.topological_sort_generator():
... for edge in D.edge_iterator():
... u,v,l = edge
... if sort.index(u) > sort.index(v):
... print "This should never happen."