Connectivity related functions#
This module implements the connectivity based functions for graphs and digraphs. The methods in this module are also available as part of GenericGraph, DiGraph or Graph classes as aliases, and these methods can be accessed through this module or as class methods. Here is what the module can do:
For both directed and undirected graphs:
Check whether the (di)graph is connected. 

Return the list of connected components 

Return the number of connected components. 

Return a list of connected components as graph objects. 

Return a list of the vertices connected to vertex. 

Return the sizes of the connected components as a list. 

Return the blocks and cut vertices of the graph. 

Return the blocksandcuts tree of the graph. 

Return True if the input edge is a cutedge or a bridge. 

Check whether the input vertex is a cutvertex. 

Return the edge connectivity of the graph. 

Return the vertex connectivity of the graph. 
For DiGraph:
Check whether the current 

Return the digraph of the strongly connected components 

Return the strongly connected components as a list of subgraphs. 

Return the strongly connected component containing a given vertex. 

Return the strong articulation points of this digraph. 
For undirected graphs:
Returns an iterator over the bridges (or cut edges) of given undirected graph. 

Return the connected subgraphs separated by the input vertex cut. 

Check whether the graph is triconnected. 

Return a SPQRtree representing the triconnected components of the graph. 

Return the graph represented by the SPQRtree \(T\). 
Methods#
 class sage.graphs.connectivity.TriconnectivitySPQR#
Bases:
object
Decompose a graph into triconnected components and build SPQRtree.
This class implements the algorithm proposed by Hopcroft and Tarjan in [Hopcroft1973], and later corrected by Gutwenger and Mutzel in [Gut2001], for finding the triconnected components of a biconnected graph. It then organizes these components into a SPQRtree. See the:wikipedia:\(SPQR_tree\).
A SPQRtree is a tree data structure used to represent the triconnected components of a biconnected (multi)graph and the 2vertex cuts separating them. A node of a SPQRtree, and the graph associated with it, can be one of the following four types:
"S"
– the associated graph is a cycle with at least three vertices."S"
stands forseries
and is also called apolygon
."P"
– the associated graph is a dipole graph, a multigraph with two vertices and three or more edges."P"
stands forparallel
and the node is called abond
."Q"
– the associated graph has a single real edge. This trivial case is necessary to handle the graph that has only one edge."R"
– the associated graph is a 3vertexconnected graph that is not a cycle or dipole."R"
stands forrigid
.
The edges of the tree indicate the 2vertex cuts of the graph.
INPUT:
G
– graph; ifG
is aDiGraph
, the computation is done on the underlyingGraph
(i.e., ignoring edge orientation)check
– boolean (default:True
); indicates whetherG
needs to be tested for biconnectivity
EXAMPLES:
Example from the Wikipedia article SPQR_tree:
sage: from sage.graphs.connectivity import TriconnectivitySPQR sage: from sage.graphs.connectivity import spqr_tree_to_graph sage: G = Graph([(1, 2), (1, 4), (1, 8), (1, 12), (3, 4), (2, 3), ....: (2, 13), (3, 13), (4, 5), (4, 7), (5, 6), (5, 8), (5, 7), (6, 7), ....: (8, 11), (8, 9), (8, 12), (9, 10), (9, 11), (9, 12), (10, 12)]) sage: tric = TriconnectivitySPQR(G) sage: T = tric.get_spqr_tree() sage: G.is_isomorphic(spqr_tree_to_graph(T)) True
An example from [Hopcroft1973]:
sage: G = Graph([(1, 2), (1, 4), (1, 8), (1, 12), (1, 13), (2, 3), ....: (2, 13), (3, 4), (3, 13), (4, 5), (4, 7), (5, 6), (5, 7), (5, 8), ....: (6, 7), (8, 9), (8, 11), (8, 12), (9, 10), (9, 11), (9, 12), ....: (10, 11), (10, 12)]) sage: tric = TriconnectivitySPQR(G) sage: T = tric.get_spqr_tree() sage: G.is_isomorphic(spqr_tree_to_graph(T)) True sage: tric.print_triconnected_components() Triconnected: [(8, 9, None), (9, 12, None), (9, 11, None), (8, 11, None), (10, 11, None), (9, 10, None), (10, 12, None), (8, 12, 'newVEdge0')] Bond: [(8, 12, None), (8, 12, 'newVEdge0'), (8, 12, 'newVEdge1')] Polygon: [(6, 7, None), (5, 6, None), (7, 5, 'newVEdge2')] Bond: [(7, 5, 'newVEdge2'), (5, 7, 'newVEdge3'), (5, 7, None)] Polygon: [(5, 7, 'newVEdge3'), (4, 7, None), (5, 4, 'newVEdge4')] Bond: [(5, 4, 'newVEdge4'), (4, 5, 'newVEdge5'), (4, 5, None)] Polygon: [(4, 5, 'newVEdge5'), (5, 8, None), (1, 4, 'newVEdge9'), (1, 8, 'newVEdge10')] Triconnected: [(1, 2, None), (2, 13, None), (1, 13, None), (3, 13, None), (2, 3, None), (1, 3, 'newVEdge7')] Polygon: [(1, 3, 'newVEdge7'), (3, 4, None), (1, 4, 'newVEdge8')] Bond: [(1, 4, None), (1, 4, 'newVEdge8'), (1, 4, 'newVEdge9')] Bond: [(1, 8, None), (1, 8, 'newVEdge10'), (1, 8, 'newVEdge11')] Polygon: [(8, 12, 'newVEdge1'), (1, 8, 'newVEdge11'), (1, 12, None)]
An example from [Gut2001]:
sage: G = Graph([(1, 2), (1, 4), (2, 3), (2, 5), (3, 4), (3, 5), (4, 5), ....: (4, 6), (5, 7), (5, 8), (5, 14), (6, 8), (7, 14), (8, 9), (8, 10), ....: (8, 11), (8, 12), (9, 10), (10, 13), (10, 14), (10, 15), (10, 16), ....: (11, 12), (11, 13), (12, 13), (14, 15), (14, 16), (15, 16)]) sage: T = TriconnectivitySPQR(G).get_spqr_tree() sage: G.is_isomorphic(spqr_tree_to_graph(T)) True
An example with multiedges and accessing the triconnected components:
sage: G = Graph([(1, 2), (1, 5), (1, 5), (2, 3), (2, 3), (3, 4), (4, 5)], multiedges=True) sage: tric = TriconnectivitySPQR(G) sage: T = tric.get_spqr_tree() sage: G.is_isomorphic(spqr_tree_to_graph(T)) True sage: tric.print_triconnected_components() Bond: [(1, 5, None), (1, 5, None), (1, 5, 'newVEdge0')] Bond: [(2, 3, None), (2, 3, None), (2, 3, 'newVEdge1')] Polygon: [(4, 5, None), (1, 5, 'newVEdge0'), (3, 4, None), (2, 3, 'newVEdge1'), (1, 2, None)]
An example of a triconnected graph:
sage: G = Graph([('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]) sage: T = TriconnectivitySPQR(G).get_spqr_tree() sage: print(T.vertices(sort=True)) [('R', Multigraph on 4 vertices)] sage: G.is_isomorphic(spqr_tree_to_graph(T)) True
An example of a directed graph with multiedges:
sage: G = DiGraph([(1, 2), (2, 3), (3, 4), (4, 5), (1, 5), (5, 1)]) sage: tric = TriconnectivitySPQR(G) sage: tric.print_triconnected_components() Bond: [(1, 5, None), (5, 1, None), (1, 5, 'newVEdge0')] Polygon: [(4, 5, None), (1, 5, 'newVEdge0'), (3, 4, None), (2, 3, None), (1, 2, None)]
Edge labels are preserved by the construction:
sage: G = Graph([(0, 1, '01'), (0, 4, '04'), (1, 2, '12'), (1, 5, '15'), ....: (2, 3, '23'), (2, 6, '26'), (3, 7, '37'), (4, 5, '45'), ....: (5, 6, '56'), (6, 7, 67)]) sage: T = TriconnectivitySPQR(G).get_spqr_tree() sage: H = spqr_tree_to_graph(T) sage: all(G.has_edge(e) for e in H.edge_iterator()) True sage: all(H.has_edge(e) for e in G.edge_iterator()) True
 get_spqr_tree()#
Return an SPQRtree representing the triconnected components of the graph.
An SPQRtree is a tree data structure used to represent the triconnected components of a biconnected (multi)graph and the 2vertex cuts separating them. A node of a SPQRtree, and the graph associated with it, can be one of the following four types:
"S"
– the associated graph is a cycle with at least three vertices."S"
stands forseries
."P"
– the associated graph is a dipole graph, a multigraph with two vertices and three or more edges."P"
stands forparallel
."Q"
– the associated graph has a single real edge. This trivial case is necessary to handle the graph that has only one edge."R"
– the associated graph is a 3connected graph that is not a cycle or dipole."R"
stands forrigid
.
The edges of the tree indicate the 2vertex cuts of the graph.
OUTPUT:
SPQRtree
a tree whose vertices are labeled with the block’s type and the subgraph of threeblocks in the decomposition.EXAMPLES:
sage: from sage.graphs.connectivity import TriconnectivitySPQR sage: G = Graph(2) sage: for i in range(3): ....: G.add_clique([0, 1, G.add_vertex(), G.add_vertex()]) sage: tric = TriconnectivitySPQR(G) sage: Tree = tric.get_spqr_tree() sage: K4 = graphs.CompleteGraph(4) sage: all(u[1].is_isomorphic(K4) for u in Tree if u[0] == 'R') True sage: from sage.graphs.connectivity import spqr_tree_to_graph sage: G.is_isomorphic(spqr_tree_to_graph(Tree)) True sage: G = Graph(2) sage: for i in range(3): ....: G.add_path([0, G.add_vertex(), G.add_vertex(), 1]) sage: tric = TriconnectivitySPQR(G) sage: Tree = tric.get_spqr_tree() sage: C4 = graphs.CycleGraph(4) sage: all(u[1].is_isomorphic(C4) for u in Tree if u[0] == 'S') True sage: G.is_isomorphic(spqr_tree_to_graph(Tree)) True sage: G.allow_multiple_edges(True) sage: G.add_edges(G.edge_iterator()) sage: tric = TriconnectivitySPQR(G) sage: Tree = tric.get_spqr_tree() sage: all(u[1].is_isomorphic(C4) for u in Tree if u[0] == 'S') True sage: G.is_isomorphic(spqr_tree_to_graph(Tree)) True sage: G = graphs.CycleGraph(6) sage: tric = TriconnectivitySPQR(G) sage: Tree = tric.get_spqr_tree() sage: Tree.order() 1 sage: G.is_isomorphic(spqr_tree_to_graph(Tree)) True sage: G.add_edge(0, 3) sage: tric = TriconnectivitySPQR(G) sage: Tree = tric.get_spqr_tree() sage: Tree.order() 3 sage: G.is_isomorphic(spqr_tree_to_graph(Tree)) True sage: G = Graph([(0, 1)], multiedges=True) sage: tric = TriconnectivitySPQR(G) sage: Tree = tric.get_spqr_tree() sage: Tree.vertices(sort=True) [('Q', Multigraph on 2 vertices)] sage: G.add_edge(0, 1) sage: Tree = TriconnectivitySPQR(G).get_spqr_tree() sage: Tree.vertices(sort=True) [('P', Multigraph on 2 vertices)]
 get_triconnected_components()#
Return the triconnected components as a list of tuples.
Each component is represented as a tuple of the type of the component and the list of edges of the component.
EXAMPLES:
sage: from sage.graphs.connectivity import TriconnectivitySPQR sage: G = Graph(2) sage: for i in range(3): ....: G.add_path([0, G.add_vertex(), G.add_vertex(), 1]) sage: tric = TriconnectivitySPQR(G) sage: tric.get_triconnected_components() [('Polygon', [(4, 5, None), (0, 4, None), (1, 5, None), (1, 0, 'newVEdge1')]), ('Polygon', [(6, 7, None), (0, 6, None), (1, 7, None), (1, 0, 'newVEdge3')]), ('Bond', [(1, 0, 'newVEdge1'), (1, 0, 'newVEdge3'), (1, 0, 'newVEdge4')]), ('Polygon', [(1, 3, None), (1, 0, 'newVEdge4'), (2, 3, None), (0, 2, None)])]
 print_triconnected_components()#
Print the type and list of edges of each component.
EXAMPLES:
An example from [Hopcroft1973]:
sage: from sage.graphs.connectivity import TriconnectivitySPQR sage: from sage.graphs.connectivity import spqr_tree_to_graph sage: G = Graph([(1, 2), (1, 4), (1, 8), (1, 12), (1, 13), (2, 3), ....: (2, 13), (3, 4), (3, 13), (4, 5), (4, 7), (5, 6), (5, 7), (5, 8), ....: (6, 7), (8, 9), (8, 11), (8, 12), (9, 10), (9, 11), (9, 12), ....: (10, 11), (10, 12)]) sage: tric = TriconnectivitySPQR(G) sage: T = tric.get_spqr_tree() sage: G.is_isomorphic(spqr_tree_to_graph(T)) True sage: tric.print_triconnected_components() Triconnected: [(8, 9, None), (9, 12, None), (9, 11, None), (8, 11, None), (10, 11, None), (9, 10, None), (10, 12, None), (8, 12, 'newVEdge0')] Bond: [(8, 12, None), (8, 12, 'newVEdge0'), (8, 12, 'newVEdge1')] Polygon: [(6, 7, None), (5, 6, None), (7, 5, 'newVEdge2')] Bond: [(7, 5, 'newVEdge2'), (5, 7, 'newVEdge3'), (5, 7, None)] Polygon: [(5, 7, 'newVEdge3'), (4, 7, None), (5, 4, 'newVEdge4')] Bond: [(5, 4, 'newVEdge4'), (4, 5, 'newVEdge5'), (4, 5, None)] Polygon: [(4, 5, 'newVEdge5'), (5, 8, None), (1, 4, 'newVEdge9'), (1, 8, 'newVEdge10')] Triconnected: [(1, 2, None), (2, 13, None), (1, 13, None), (3, 13, None), (2, 3, None), (1, 3, 'newVEdge7')] Polygon: [(1, 3, 'newVEdge7'), (3, 4, None), (1, 4, 'newVEdge8')] Bond: [(1, 4, None), (1, 4, 'newVEdge8'), (1, 4, 'newVEdge9')] Bond: [(1, 8, None), (1, 8, 'newVEdge10'), (1, 8, 'newVEdge11')] Polygon: [(8, 12, 'newVEdge1'), (1, 8, 'newVEdge11'), (1, 12, None)]
 sage.graphs.connectivity.blocks_and_cut_vertices(G, algorithm='Tarjan_Boost', sort=False, key=None)#
Return the blocks and cut vertices of the graph.
In the case of a digraph, this computation is done on the underlying graph.
A cut vertex is one whose deletion increases the number of connected components. A block is a maximal induced subgraph which itself has no cut vertices. Two distinct blocks cannot overlap in more than a single cut vertex.
INPUT:
algorithm
– string (default:"Tarjan_Boost"
); the algorithm to use among:"Tarjan_Boost"
(default) – Tarjan’s algorithm (Boost implementation)"Tarjan_Sage"
– Tarjan’s algorithm (Sage implementation)
sort
– boolean (default:False
); whether to sort vertices inside the components and the list of cut vertices currently only available for ``”Tarjan_Sage”``key
– a function (default:None
); a function that takes a vertex as its one argument and returns a value that can be used for comparisons in the sorting algorithm (we must havesort=True
)
OUTPUT:
(B, C)
, whereB
is a list of blocks  each is a list of vertices and the blocks are the corresponding induced subgraphs  andC
is a list of cut vertices.ALGORITHM:
We implement the algorithm proposed by Tarjan in [Tarjan72]. The original version is recursive. We emulate the recursion using a stack.
See also
EXAMPLES:
We construct a trivial example of a graph with one cut vertex:
sage: from sage.graphs.connectivity import blocks_and_cut_vertices sage: rings = graphs.CycleGraph(10) sage: rings.merge_vertices([0, 5]) sage: blocks_and_cut_vertices(rings) ([[0, 1, 4, 2, 3], [0, 6, 9, 7, 8]], [0]) sage: rings.blocks_and_cut_vertices() ([[0, 1, 4, 2, 3], [0, 6, 9, 7, 8]], [0]) sage: B, C = blocks_and_cut_vertices(rings, algorithm="Tarjan_Sage", sort=True) sage: B, C ([[0, 1, 2, 3, 4], [0, 6, 7, 8, 9]], [0]) sage: B2, C2 = blocks_and_cut_vertices(rings, algorithm="Tarjan_Sage", sort=False) sage: Set(map(Set, B)) == Set(map(Set, B2)) and set(C) == set(C2) True
The Petersen graph is biconnected, hence has no cut vertices:
sage: blocks_and_cut_vertices(graphs.PetersenGraph()) ([[0, 1, 4, 5, 2, 6, 3, 7, 8, 9]], [])
Decomposing paths to pairs:
sage: g = graphs.PathGraph(4) + graphs.PathGraph(5) sage: blocks_and_cut_vertices(g) ([[2, 3], [1, 2], [0, 1], [7, 8], [6, 7], [5, 6], [4, 5]], [1, 2, 5, 6, 7])
A disconnected graph:
sage: g = Graph({1: {2: 28, 3: 10}, 2: {1: 10, 3: 16}, 4: {}, 5: {6: 3, 7: 10, 8: 4}}) sage: blocks_and_cut_vertices(g) ([[1, 2, 3], [5, 6], [5, 7], [5, 8], [4]], [5])
A directed graph with Boost’s algorithm (github issue #25994):
sage: rings = graphs.CycleGraph(10) sage: rings.merge_vertices([0, 5]) sage: rings = rings.to_directed() sage: blocks_and_cut_vertices(rings, algorithm="Tarjan_Boost") ([[0, 1, 4, 2, 3], [0, 6, 9, 7, 8]], [0])
 sage.graphs.connectivity.blocks_and_cuts_tree(G)#
Return the blocksandcuts tree of
self
.This new graph has two different kinds of vertices, some representing the blocks (type B) and some other the cut vertices of the graph (type C).
There is an edge between a vertex \(u\) of type B and a vertex \(v\) of type C if the cutvertex corresponding to \(v\) is in the block corresponding to \(u\).
The resulting graph is a tree, with the additional characteristic property that the distance between two leaves is even. When
self
is not connected, the resulting graph is a forest.When
self
is biconnected, the tree is reduced to a single node of type \(B\).We referred to [HarPri] and [Gallai] for blocks and cuts tree.
EXAMPLES:
sage: from sage.graphs.connectivity import blocks_and_cuts_tree sage: T = blocks_and_cuts_tree(graphs.KrackhardtKiteGraph()); T Graph on 5 vertices sage: T.is_isomorphic(graphs.PathGraph(5)) True sage: from sage.graphs.connectivity import blocks_and_cuts_tree sage: T = graphs.KrackhardtKiteGraph().blocks_and_cuts_tree(); T Graph on 5 vertices
The distance between two leaves is even:
sage: T = blocks_and_cuts_tree(graphs.RandomTree(40)) sage: T.is_tree() True sage: leaves = [v for v in T if T.degree(v) == 1] sage: all(T.distance(u,v) % 2 == 0 for u in leaves for v in leaves) True
The tree of a biconnected graph has a single vertex, of type \(B\):
sage: T = blocks_and_cuts_tree(graphs.PetersenGraph()) sage: T.vertices(sort=True) [('B', (0, 1, 4, 5, 2, 6, 3, 7, 8, 9))]
 sage.graphs.connectivity.bridges(G, labels=True)#
Return an iterator over the bridges (or cut edges).
A bridge is an edge whose deletion disconnects the undirected graph. A disconnected graph has no bridge.
INPUT:
labels
– boolean (default:True
); ifFalse
, each bridge is a tuple \((u, v)\) of vertices
EXAMPLES:
sage: from sage.graphs.connectivity import bridges sage: from sage.graphs.connectivity import is_connected sage: g = 2 * graphs.PetersenGraph() sage: g.add_edge(1, 10) sage: is_connected(g) True sage: list(bridges(g)) [(1, 10, None)] sage: list(g.bridges()) [(1, 10, None)]
Every edge of a tree is a bridge:
sage: g = graphs.RandomTree(100) sage: sum(1 for _ in g.bridges()) == 99 True
 sage.graphs.connectivity.cleave(G, cut_vertices=None, virtual_edges=True, solver=None, verbose=0, integrality_tolerance=0.001)#
Return the connected subgraphs separated by the input vertex cut.
Given a connected (multi)graph \(G\) and a vertex cut \(X\), this method computes the list of subgraphs of \(G\) induced by each connected component \(c\) of \(G\setminus X\) plus \(X\), i.e., \(G[c\cup X]\).
INPUT:
G
– a Graph.cut_vertices
– iterable container of vertices (default:None
); a set of vertices representing a vertex cut ofG
. If no vertex cut is given, the method will compute one via a call tovertex_connectivity()
.virtual_edges
– boolean (default:True
); whether to add virtual edges to the sides of the cut or not. A virtual edge is an edge between a pair of vertices of the cut that are not connected by an edge inG
.solver
– string (default:None
); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set toNone
, the default one is used. For more information on MILP 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.integrality_tolerance
– float; parameter for use with MILP solvers over an inexact base ring; seeMixedIntegerLinearProgram.get_values()
.
OUTPUT: A triple \((S, C, f)\), where
\(S\) is a list of the graphs that are sides of the vertex cut.
\(C\) is the graph of the cocycles. For each pair of vertices of the cut, if there exists an edge between them, \(C\) has one copy of each edge connecting them in
G
per sides of the cut plus one extra copy. Furthermore, whenvirtual_edges == True
, if a pair of vertices of the cut is not connected by an edge inG
, then it has one virtual edge between them per sides of the cut.\(f\) is the complement of the subgraph of
G
induced by the vertex cut. Hence, its vertex set is the vertex cut, and its edge set is the set of virtual edges (i.e., edges between pairs of vertices of the cut that are not connected by an edge inG
). Whenvirtual_edges == False
, the edge set is empty.
EXAMPLES:
If there is an edge between cut vertices:
sage: from sage.graphs.connectivity import cleave sage: G = Graph(2) sage: for _ in range(3): ....: G.add_clique([0, 1, G.add_vertex(), G.add_vertex()]) sage: S1,C1,f1 = cleave(G, cut_vertices=[0, 1]) sage: [g.order() for g in S1] [4, 4, 4] sage: C1.order(), C1.size() (2, 4) sage: f1.vertices(sort=True), f1.edges(sort=True) ([0, 1], [])
If
virtual_edges == False
and there is an edge between cut vertices:sage: G.subgraph([0, 1]).complement() == Graph([[0, 1], []]) True sage: S2,C2,f2 = cleave(G, cut_vertices=[0, 1], virtual_edges=False) sage: (S1 == S2, C1 == C2, f1 == f2) (True, True, True)
If cut vertices doesn’t have edge between them:
sage: G.delete_edge(0, 1) sage: S1,C1,f1 = cleave(G, cut_vertices=[0, 1]) sage: [g.order() for g in S1] [4, 4, 4] sage: C1.order(), C1.size() (2, 3) sage: f1.vertices(sort=True), f1.edges(sort=True) ([0, 1], [(0, 1, None)])
If
virtual_edges == False
and the cut vertices are not connected by an edge:sage: G.subgraph([0, 1]).complement() == Graph([[0, 1], []]) False sage: S2,C2,f2 = cleave(G, cut_vertices=[0, 1], virtual_edges=False) sage: [g.order() for g in S2] [4, 4, 4] sage: C2.order(), C2.size() (2, 0) sage: f2.vertices(sort=True), f2.edges(sort=True) ([0, 1], []) sage: (S1 == S2, C1 == C2, f1 == f2) (False, False, False)
If \(G\) is a biconnected multigraph:
sage: G = graphs.CompleteBipartiteGraph(2, 3) sage: G.add_edge(2, 3) sage: G.allow_multiple_edges(True) sage: G.add_edges(G.edge_iterator()) sage: G.add_edges([(0, 1), (0, 1), (0, 1)]) sage: S,C,f = cleave(G, cut_vertices=[0, 1]) sage: for g in S: ....: print(g.edges(sort=True, labels=0)) [(0, 1), (0, 1), (0, 1), (0, 2), (0, 2), (0, 3), (0, 3), (1, 2), (1, 2), (1, 3), (1, 3), (2, 3), (2, 3)] [(0, 1), (0, 1), (0, 1), (0, 4), (0, 4), (1, 4), (1, 4)]
 sage.graphs.connectivity.connected_component_containing_vertex(G, vertex, sort=None, key=None)#
Return a list of the vertices connected to vertex.
INPUT:
G
– the input graphv
– the vertex to search forsort
– boolean (default:None
); ifTrue
, vertices inside the component are sorted according to the default orderingAs of github issue #35889, this argument must be explicitly specified (unless a
key
is given); otherwise a warning is printed andsort=True
is used. The default will eventually be changed toFalse
.key
– a function (default:None
); a function that takes a vertex as its one argument and returns a value that can be used for comparisons in the sorting algorithm (we must havesort=True
)
EXAMPLES:
sage: from sage.graphs.connectivity import connected_component_containing_vertex sage: G = Graph({0: [1, 3], 1: [2], 2: [3], 4: [5, 6], 5: [6]}) sage: connected_component_containing_vertex(G, 0, sort=True) [0, 1, 2, 3] sage: G.connected_component_containing_vertex(0, sort=True) [0, 1, 2, 3] sage: D = DiGraph({0: [1, 3], 1: [2], 2: [3], 4: [5, 6], 5: [6]}) sage: connected_component_containing_vertex(D, 0, sort=True) [0, 1, 2, 3] sage: connected_component_containing_vertex(D, 0, sort=True, key=lambda x: x) [3, 2, 1, 0]
 sage.graphs.connectivity.connected_components(G, sort=None, key=None)#
Return the list of connected components.
This returns a list of lists of vertices, each list representing a connected component. The list is ordered from largest to smallest component.
INPUT:
G
– the input graphsort
– boolean (default:None
); ifTrue
, vertices inside each component are sorted according to the default orderingAs of github issue #35889, this argument must be explicitly specified (unless a
key
is given); otherwise a warning is printed andsort=True
is used. The default will eventually be changed toFalse
.key
– a function (default:None
); a function that takes a vertex as its one argument and returns a value that can be used for comparisons in the sorting algorithm (we must havesort=True
)
EXAMPLES:
sage: from sage.graphs.connectivity import connected_components sage: G = Graph({0: [1, 3], 1: [2], 2: [3], 4: [5, 6], 5: [6]}) sage: connected_components(G, sort=True) [[0, 1, 2, 3], [4, 5, 6]] sage: G.connected_components(sort=True) [[0, 1, 2, 3], [4, 5, 6]] sage: D = DiGraph({0: [1, 3], 1: [2], 2: [3], 4: [5, 6], 5: [6]}) sage: connected_components(D, sort=True) [[0, 1, 2, 3], [4, 5, 6]] sage: connected_components(D, sort=True, key=lambda x: x) [[3, 2, 1, 0], [6, 5, 4]]
 sage.graphs.connectivity.connected_components_number(G)#
Return the number of connected components.
INPUT:
G
– the input graph
EXAMPLES:
sage: from sage.graphs.connectivity import connected_components_number sage: G = Graph({0: [1, 3], 1: [2], 2: [3], 4: [5, 6], 5: [6]}) sage: connected_components_number(G) 2 sage: G.connected_components_number() 2 sage: D = DiGraph({0: [1, 3], 1: [2], 2: [3], 4: [5, 6], 5: [6]}) sage: connected_components_number(D) 2
 sage.graphs.connectivity.connected_components_sizes(G)#
Return the sizes of the connected components as a list.
The list is sorted from largest to lower values.
EXAMPLES:
sage: from sage.graphs.connectivity import connected_components_sizes sage: for x in graphs(3): ....: print(connected_components_sizes(x)) [1, 1, 1] [2, 1] [3] [3] sage: for x in graphs(3): ....: print(x.connected_components_sizes()) [1, 1, 1] [2, 1] [3] [3]
 sage.graphs.connectivity.connected_components_subgraphs(G)#
Return a list of connected components as graph objects.
EXAMPLES:
sage: from sage.graphs.connectivity import connected_components_subgraphs sage: G = Graph({0: [1, 3], 1: [2], 2: [3], 4: [5, 6], 5: [6]}) sage: L = connected_components_subgraphs(G) sage: graphs_list.show_graphs(L) # needs sage.plot sage: D = DiGraph({0: [1, 3], 1: [2], 2: [3], 4: [5, 6], 5: [6]}) sage: L = connected_components_subgraphs(D) sage: graphs_list.show_graphs(L) # needs sage.plot sage: L = D.connected_components_subgraphs() sage: graphs_list.show_graphs(L) # needs sage.plot
 sage.graphs.connectivity.edge_connectivity(G, value_only=True, implementation=None, use_edge_labels=False, vertices=False, solver=None, verbose=0, integrality_tolerance=0.001)#
Return the edge connectivity of the graph.
For more information, see the Wikipedia article Connectivity_(graph_theory).
Note
When the graph is a directed graph, this method actually computes the strong connectivity, (i.e. a directed graph is strongly \(k\)connected if there are \(k\) disjoint paths between any two vertices \(u, v\)). If you do not want to consider strong connectivity, the best is probably to convert your
DiGraph
object to aGraph
object, and compute the connectivity of this other graph.INPUT:
G
– the input Sage (Di)Graphvalue_only
– boolean (default:True
)When set to
True
(default), only the value is returned.When set to
False
, both the value and a minimum vertex cut are returned.
implementation
– string (default:None
); selects an implementation:None
(default) – selects the best implementation available"boost"
– use the Boost graph library (which is much more efficient). It is not available whenedge_labels=True
, and it is unreliable for directed graphs (see github issue #18753).
 
"Sage"
– use Sage’s implementation based on integer linear programming
use_edge_labels
– boolean (default:False
)When set to
True
, computes a weighted minimum cut where each edge has a weight defined by its label. (If an edge has no label, \(1\) is assumed.). Impliesboost
=False
.When set to
False
, each edge has weight \(1\).
vertices
– boolean (default:False
)When set to
True
, also returns the two sets of vertices that are disconnected by the cut. Impliesvalue_only=False
.
solver
– string (default:None
); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set toNone
, the default one is used. For more information on MILP 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.integrality_tolerance
– float; parameter for use with MILP solvers over an inexact base ring; seeMixedIntegerLinearProgram.get_values()
.
EXAMPLES:
A basic application on the PappusGraph:
sage: from sage.graphs.connectivity import edge_connectivity sage: g = graphs.PappusGraph() sage: edge_connectivity(g) 3 sage: g.edge_connectivity() 3
The edge connectivity of a complete graph is its minimum degree, and one of the two parts of the bipartition is reduced to only one vertex. The graph of the cut edges is isomorphic to a Star graph:
sage: g = graphs.CompleteGraph(5) sage: [ value, edges, [ setA, setB ]] = edge_connectivity(g,vertices=True) sage: value 4 sage: len(setA) == 1 or len(setB) == 1 True sage: cut = Graph() sage: cut.add_edges(edges) sage: cut.is_isomorphic(graphs.StarGraph(4)) True
Even if obviously in any graph we know that the edge connectivity is less than the minimum degree of the graph:
sage: g = graphs.RandomGNP(10,.3) sage: min(g.degree()) >= edge_connectivity(g) True
If we build a tree then assign to its edges a random value, the minimum cut will be the edge with minimum value:
sage: tree = graphs.RandomTree(10) sage: for u,v in tree.edge_iterator(labels=None): ....: tree.set_edge_label(u, v, random()) sage: minimum = min(tree.edge_labels()) sage: [_, [(_, _, l)]] = edge_connectivity(tree, value_only=False, # needs sage.numerical.mip ....: use_edge_labels=True) sage: l == minimum # needs sage.numerical.mip True
When
value_only=True
andimplementation="sage"
, this function is optimized for small connectivity values and does not need to build a linear program.It is the case for graphs which are not connected
sage: g = 2 * graphs.PetersenGraph() sage: edge_connectivity(g, implementation="sage") 0.0
For directed graphs, the strong connectivity is tested through the dedicated function:
sage: g = digraphs.ButterflyGraph(3) sage: edge_connectivity(g, implementation="sage") 0.0
We check that the result with Boost is the same as the result without Boost:
sage: g = graphs.RandomGNP(15, .3) sage: (edge_connectivity(g, implementation="boost") # needs sage.numerical.mip ....: == edge_connectivity(g, implementation="sage")) True
Boost interface also works with directed graphs:
sage: edge_connectivity(digraphs.Circuit(10), implementation="boost", ....: vertices=True) [1, [(0, 1)], [{0}, {1, 2, 3, 4, 5, 6, 7, 8, 9}]]
However, the Boost algorithm is not reliable if the input is directed (see github issue #18753):
sage: g = digraphs.Path(3) sage: edge_connectivity(g) 0.0 sage: edge_connectivity(g, implementation="boost") 1 sage: g.add_edge(1, 0) sage: edge_connectivity(g) 0.0 sage: edge_connectivity(g, implementation="boost") 0
 sage.graphs.connectivity.is_connected(G)#
Check whether the (di)graph is connected.
Note that in a graph, path connected is equivalent to connected.
INPUT:
G
– the input graph
See also
EXAMPLES:
sage: from sage.graphs.connectivity import is_connected sage: G = Graph({0: [1, 2], 1: [2], 3: [4, 5], 4: [5]}) sage: is_connected(G) False sage: G.is_connected() False sage: G.add_edge(0,3) sage: is_connected(G) True sage: D = DiGraph({0: [1, 2], 1: [2], 3: [4, 5], 4: [5]}) sage: is_connected(D) False sage: D.add_edge(0, 3) sage: is_connected(D) True sage: D = DiGraph({1: [0], 2: [0]}) sage: is_connected(D) True
 sage.graphs.connectivity.is_cut_edge(G, u, v=None, label=None)#
Returns True if the input edge is a cutedge or a bridge.
A cut edge (or bridge) is an edge that when removed increases the number of connected components. This function works with simple graphs as well as graphs with loops and multiedges. In a digraph, a cut edge is an edge that when removed increases the number of (weakly) connected components.
INPUT: The following forms are accepted
is_cut_edge(G, 1, 2 )
is_cut_edge(G, (1, 2) )
is_cut_edge(G, 1, 2, ‘label’ )
is_cut_edge(G, (1, 2, ‘label’) )
OUTPUT:
Returns True if (u,v) is a cut edge, False otherwise
EXAMPLES:
sage: from sage.graphs.connectivity import is_cut_edge sage: G = graphs.CompleteGraph(4) sage: is_cut_edge(G,0,2) False sage: G.is_cut_edge(0,2) False sage: G = graphs.CompleteGraph(4) sage: G.add_edge((0,5,'silly')) sage: is_cut_edge(G,(0,5,'silly')) True sage: G = Graph([[0,1],[0,2],[3,4],[4,5],[3,5]]) sage: is_cut_edge(G,(0,1)) True sage: G = Graph([[0,1],[0,2],[1,1]], loops = True) sage: is_cut_edge(G,(1,1)) False sage: G = digraphs.Circuit(5) sage: is_cut_edge(G,(0,1)) False sage: G = graphs.CompleteGraph(6) sage: is_cut_edge(G,(0,7)) Traceback (most recent call last): ... ValueError: edge not in graph
 sage.graphs.connectivity.is_cut_vertex(G, u, weak=False)#
Check whether the input vertex is a cutvertex.
A vertex is a cutvertex if its removal from the (di)graph increases the number of (strongly) connected components. Isolated vertices or leafs are not cutvertices. This function works with simple graphs as well as graphs with loops and multiple edges.
INPUT:
G
– a Sage (Di)Graphu
– a vertexweak
– boolean (default:False
); whether the connectivity of directed graphs is to be taken in the weak sense, that is ignoring edges orientations
OUTPUT:
Return
True
ifu
is a cutvertex, andFalse
otherwise.EXAMPLES:
Giving a LollipopGraph(4,2), that is a complete graph with 4 vertices with a pending edge:
sage: from sage.graphs.connectivity import is_cut_vertex sage: G = graphs.LollipopGraph(4, 2) sage: is_cut_vertex(G, 0) False sage: is_cut_vertex(G, 3) True sage: G.is_cut_vertex(3) True
Comparing the weak and strong connectivity of a digraph:
sage: from sage.graphs.connectivity import is_strongly_connected sage: D = digraphs.Circuit(6) sage: is_strongly_connected(D) True sage: is_cut_vertex(D, 2) True sage: is_cut_vertex(D, 2, weak=True) False
Giving a vertex that is not in the graph:
sage: G = graphs.CompleteGraph(4) sage: is_cut_vertex(G, 7) Traceback (most recent call last): ... ValueError: vertex (7) is not a vertex of the graph
 sage.graphs.connectivity.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
 sage.graphs.connectivity.is_triconnected(G)#
Check whether the graph is triconnected.
A triconnected graph is a connected graph on 3 or more vertices that is not broken into disconnected pieces by deleting any pair of vertices.
EXAMPLES:
The Petersen graph is triconnected:
sage: G = graphs.PetersenGraph() sage: G.is_triconnected() True
But a 2D grid is not:
sage: G = graphs.Grid2dGraph(3, 3) sage: G.is_triconnected() False
By convention, a cycle of order 3 is triconnected:
sage: G = graphs.CycleGraph(3) sage: G.is_triconnected() True
But cycles of order 4 and more are not:
sage: [graphs.CycleGraph(i).is_triconnected() for i in range(4, 8)] [False, False, False, False]
Comparing different methods on random graphs that are not always triconnected:
sage: G = graphs.RandomBarabasiAlbert(50, 3) # needs networkx sage: G.is_triconnected() == G.vertex_connectivity(k=3) # needs networkx True
 sage.graphs.connectivity.spqr_tree(G, algorithm='Hopcroft_Tarjan', solver=None, verbose=0, integrality_tolerance=0.001)#
Return an SPQRtree representing the triconnected components of the graph.
An SPQRtree is a tree data structure used to represent the triconnected components of a biconnected (multi)graph and the 2vertex cuts separating them. A node of a SPQRtree, and the graph associated with it, can be one of the following four types:
"S"
– the associated graph is a cycle with at least three vertices."S"
stands forseries
."P"
– the associated graph is a dipole graph, a multigraph with two vertices and three or more edges."P"
stands forparallel
."Q"
– the associated graph has a single real edge. This trivial case is necessary to handle the graph that has only one edge."R"
– the associated graph is a 3connected graph that is not a cycle or dipole."R"
stands forrigid
.
This method decomposes a biconnected graph into cycles, cocycles, and 3connected blocks summed over cocycles, and arranges them as a SPQRtree. More precisely, it splits the graph at each of its 2vertex cuts, giving a unique decomposition into 3connected blocks, cycles and cocycles. The cocycles are dipole graphs with one edge per real edge between the included vertices and one additional (virtual) edge per connected component resulting from deletion of the vertices in the cut. See the Wikipedia article SPQR_tree.
INPUT:
G
– the input graphalgorithm
– string (default:"Hopcroft_Tarjan"
); the algorithm to use among:"Hopcroft_Tarjan"
(default) – use the algorithm proposed by Hopcroft and Tarjan in [Hopcroft1973] and later corrected by Gutwenger and Mutzel in [Gut2001]. SeeTriconnectivitySPQR
."cleave"
– using methodcleave()
solver
– string (default:None
); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set toNone
, the default one is used. For more information on MILP 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.integrality_tolerance
– float; parameter for use with MILP solvers over an inexact base ring; seeMixedIntegerLinearProgram.get_values()
.
OUTPUT:
SPQRtree
a tree whose vertices are labeled with the block’s type and the subgraph of threeblocks in the decomposition.EXAMPLES:
sage: from sage.graphs.connectivity import spqr_tree sage: G = Graph(2) sage: for i in range(3): ....: G.add_clique([0, 1, G.add_vertex(), G.add_vertex()]) sage: Tree = spqr_tree(G) sage: Tree.order() 4 sage: K4 = graphs.CompleteGraph(4) sage: all(u[1].is_isomorphic(K4) for u in Tree if u[0] == 'R') True sage: from sage.graphs.connectivity import spqr_tree_to_graph sage: G.is_isomorphic(spqr_tree_to_graph(Tree)) True sage: G = Graph(2) sage: for i in range(3): ....: G.add_path([0, G.add_vertex(), G.add_vertex(), 1]) sage: Tree = spqr_tree(G) sage: Tree.order() 4 sage: C4 = graphs.CycleGraph(4) sage: all(u[1].is_isomorphic(C4) for u in Tree if u[0] == 'S') True sage: G.is_isomorphic(spqr_tree_to_graph(Tree)) True sage: G.allow_multiple_edges(True) sage: G.add_edges(G.edge_iterator()) sage: Tree = spqr_tree(G) sage: Tree.order() 13 sage: all(u[1].is_isomorphic(C4) for u in Tree if u[0] == 'S') True sage: G.is_isomorphic(spqr_tree_to_graph(Tree)) True sage: G = graphs.CycleGraph(6) sage: Tree = spqr_tree(G) sage: Tree.order() 1 sage: G.is_isomorphic(spqr_tree_to_graph(Tree)) True sage: G.add_edge(0, 3) sage: Tree = spqr_tree(G) sage: Tree.order() 3 sage: G.is_isomorphic(spqr_tree_to_graph(Tree)) True sage: G = Graph('LlCG{O@?GBoMw?') sage: T = spqr_tree(G, algorithm="Hopcroft_Tarjan") sage: G.is_isomorphic(spqr_tree_to_graph(T)) True sage: T2 = spqr_tree(G, algorithm='cleave') # needs sage.numerical.mip sage: G.is_isomorphic(spqr_tree_to_graph(T2)) # needs sage.numerical.mip True sage: G = Graph([(0, 1)], multiedges=True) sage: T = spqr_tree(G, algorithm='cleave') # needs sage.numerical.mip sage: T.vertices(sort=True) # needs sage.numerical.mip [('Q', Multigraph on 2 vertices)] sage: G.is_isomorphic(spqr_tree_to_graph(T)) # needs sage.numerical.mip True sage: T = spqr_tree(G, algorithm='Hopcroft_Tarjan') sage: T.vertices(sort=True) [('Q', Multigraph on 2 vertices)] sage: G.add_edge(0, 1) sage: spqr_tree(G, algorithm='cleave').vertices(sort=True) # needs sage.numerical.mip [('P', Multigraph on 2 vertices)] sage: from collections import Counter sage: G = graphs.PetersenGraph() sage: T = G.spqr_tree(algorithm="Hopcroft_Tarjan") sage: Counter(u[0] for u in T) Counter({'R': 1}) sage: T = G.spqr_tree(algorithm="cleave") # needs sage.numerical.mip sage: Counter(u[0] for u in T) # needs sage.numerical.mip Counter({'R': 1}) sage: for u,v in list(G.edges(labels=False, sort=False)): ....: G.add_path([u, G.add_vertex(), G.add_vertex(), v]) sage: T = G.spqr_tree(algorithm="Hopcroft_Tarjan") sage: sorted(Counter(u[0] for u in T).items()) [('P', 15), ('R', 1), ('S', 15)] sage: T = G.spqr_tree(algorithm="cleave") # needs sage.numerical.mip sage: sorted(Counter(u[0] for u in T).items()) # needs sage.numerical.mip [('P', 15), ('R', 1), ('S', 15)] sage: for u,v in list(G.edges(labels=False, sort=False)): ....: G.add_path([u, G.add_vertex(), G.add_vertex(), v]) sage: T = G.spqr_tree(algorithm="Hopcroft_Tarjan") sage: sorted(Counter(u[0] for u in T).items()) [('P', 60), ('R', 1), ('S', 75)] sage: T = G.spqr_tree(algorithm="cleave") # long time # needs sage.numerical.mip sage: sorted(Counter(u[0] for u in T).items()) # long time # needs sage.numerical.mip [('P', 60), ('R', 1), ('S', 75)]
 sage.graphs.connectivity.spqr_tree_to_graph(T)#
Return the graph represented by the SPQRtree \(T\).
The main purpose of this method is to test
spqr_tree()
.INPUT:
T
– a SPQR tree as returned byspqr_tree()
.
OUTPUT: a (multi) graph
EXAMPLES:
Wikipedia article SPQR_tree reference paper example:
sage: from sage.graphs.connectivity import spqr_tree sage: from sage.graphs.connectivity import spqr_tree_to_graph sage: G = Graph([(1, 2), (1, 4), (1, 8), (1, 12), (3, 4), (2, 3), ....: (2, 13), (3, 13), (4, 5), (4, 7), (5, 6), (5, 8), (5, 7), (6, 7), ....: (8, 11), (8, 9), (8, 12), (9, 10), (9, 11), (9, 12), (10, 12)]) sage: T = spqr_tree(G) sage: H = spqr_tree_to_graph(T) sage: H.is_isomorphic(G) True
A small multigraph
sage: G = Graph([(0, 2), (0, 2), (1, 3), (2, 3)], multiedges=True) sage: for i in range(3): ....: G.add_clique([0, 1, G.add_vertex(), G.add_vertex()]) sage: for i in range(3): ....: G.add_clique([2, 3, G.add_vertex(), G.add_vertex()]) sage: T = spqr_tree(G) sage: H = spqr_tree_to_graph(T) sage: H.is_isomorphic(G) True
 sage.graphs.connectivity.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) []
 sage.graphs.connectivity.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]
 sage.graphs.connectivity.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
 sage.graphs.connectivity.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]
 sage.graphs.connectivity.vertex_connectivity(G, value_only=True, sets=False, k=None, solver=None, verbose=0, integrality_tolerance=0.001)#
Return the vertex connectivity of the graph.
For more information, see the Wikipedia article Connectivity_(graph_theory) and the Wikipedia article Kvertexconnected_graph.
Note
When the graph is directed, this method actually computes the strong connectivity, (i.e. a directed graph is strongly \(k\)connected if there are \(k\) vertex disjoint paths between any two vertices \(u, v\)). If you do not want to consider strong connectivity, the best is probably to convert your
DiGraph
object to aGraph
object, and compute the connectivity of this other graph.By convention, a complete graph on \(n\) vertices is \(n1\) connected. In this case, no certificate can be given as there is no pair of vertices split by a cut of order \(k1\). For this reason, the certificates returned in this situation are empty.
INPUT:
G
– the input Sage (Di)Graphvalue_only
– boolean (default:True
)When set to
True
(default), only the value is returned.When set to
False
, both the value and a minimum vertex cut are returned.
sets
– boolean (default:False
); whether to also return the twosets of vertices that are disconnected by the cut (implies
value_only=False
)
k
– integer (default:None
); when specified, check if the vertex connectivity of the (di)graph is larger or equal to \(k\). The method thus outputs a boolean only.solver
– string (default:None
); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set toNone
, the default one is used. For more information on MILP 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.integrality_tolerance
– float; parameter for use with MILP solvers over an inexact base ring; seeMixedIntegerLinearProgram.get_values()
.
EXAMPLES:
A basic application on a
PappusGraph
:sage: from sage.graphs.connectivity import vertex_connectivity sage: g = graphs.PappusGraph() sage: vertex_connectivity(g) # needs sage.numerical.mip 3 sage: g.vertex_connectivity() # needs sage.numerical.mip 3
In a grid, the vertex connectivity is equal to the minimum degree, in which case one of the two sets is of cardinality \(1\):
sage: g = graphs.GridGraph([ 3,3 ]) sage: [value, cut, [ setA, setB ]] = vertex_connectivity(g, sets=True) # needs sage.numerical.mip sage: len(setA) == 1 or len(setB) == 1 # needs sage.numerical.mip True
A vertex cut in a tree is any internal vertex:
sage: tree = graphs.RandomTree(15) sage: val, [cut_vertex] = vertex_connectivity(tree, value_only=False) # needs sage.numerical.mip sage: tree.degree(cut_vertex) > 1 # needs sage.numerical.mip True
When
value_only = True
, this function is optimized for small connectivity values and does not need to build a linear program.It is the case for connected graphs which are not connected:
sage: g = 2 * graphs.PetersenGraph() sage: vertex_connectivity(g) # needs sage.numerical.mip 0
Or if they are just 1connected:
sage: g = graphs.PathGraph(10) sage: vertex_connectivity(g) # needs sage.numerical.mip 1
For directed graphs, the strong connectivity is tested through the dedicated function:
sage: g = digraphs.ButterflyGraph(3) sage: vertex_connectivity(g) # needs sage.numerical.mip 0
A complete graph on \(10\) vertices is \(9\)connected:
sage: g = graphs.CompleteGraph(10) sage: vertex_connectivity(g) # needs sage.numerical.mip 9
A complete digraph on \(10\) vertices is \(9\)connected:
sage: g = DiGraph(graphs.CompleteGraph(10)) sage: vertex_connectivity(g) # needs sage.numerical.mip 9
When parameter
k
is set, we only check for the existence of a vertex cut of order at leastk
:sage: g = graphs.PappusGraph() sage: vertex_connectivity(g, k=3) # needs sage.numerical.mip True sage: vertex_connectivity(g, k=4) # needs sage.numerical.mip False