Edge connectivity

This module implements methods for computing the edge-connectivity of graphs and digraphs. It also implements methods to extract \(k\) edge-disjoint spanning trees from a \(2k\) edge-connected graph or a \(k\) edge-connected digraph, and to pack \(k\) edge-disjoint spanning arborescences in a directed graph following the matroid approach of [Gabow1995].

Todo

  • Implement the tree-packing strengthening proposed in [BHKP2008]

  • Fix the DFS-based speed-up initialization of [GKLP2021] for digraphs with multiple edges, for which it is currently disabled

  • Extend to weighted digraphs

class sage.graphs.edge_connectivity.GabowEdgeConnectivity[source]

Bases: object

Gabow’s algorithm for finding the edge connectivity of digraphs.

This class implements the algorithm proposed in [Gabow1995] for finding the edge connectivity of a directed graph and \(k\) edge disjoint spanning trees if the digraph is \(k\) edge connected.

Digraphs with multiple edges are supported: every parallel arc counts separately, both for the edge connectivity and for the arborescence packing. Loops are tolerated and ignored.

INPUT:

EXAMPLES:

A random \(d\)-regular digraph is \(d\)-edge-connected:

sage: from sage.graphs.edge_connectivity import GabowEdgeConnectivity
sage: D = DiGraph(graphs.RandomRegular(6, 50))                                  # needs networkx
sage: while not D.is_strongly_connected():                                      # needs networkx
....:     D = DiGraph(graphs.RandomRegular(6, 50))
sage: GabowEdgeConnectivity(D).edge_connectivity()                              # needs networkx
6

>>> from sage.all import *
>>> from sage.graphs.edge_connectivity import GabowEdgeConnectivity
>>> D = DiGraph(graphs.RandomRegular(Integer(6), Integer(50)))                                  # needs networkx
>>> while not D.is_strongly_connected():                                      # needs networkx
...     D = DiGraph(graphs.RandomRegular(Integer(6), Integer(50)))
>>> GabowEdgeConnectivity(D).edge_connectivity()                              # needs networkx
6

A complete digraph with \(n\) vertices is \(n-1\)-edge-connected:

sage: from sage.graphs.edge_connectivity import GabowEdgeConnectivity
sage: D = DiGraph(digraphs.Complete(10))
sage: GabowEdgeConnectivity(D, use_rec=True).edge_connectivity()
9
[Python] 
>>> from sage.all import *
>>> from sage.graphs.edge_connectivity import GabowEdgeConnectivity
>>> D = DiGraph(digraphs.Complete(Integer(10)))
>>> GabowEdgeConnectivity(D, use_rec=True).edge_connectivity()
9

Check that we get the same result when with and without the DFS-based speed-up initialization proposed in [GKLP2021]:

sage: # needs networkx
sage: G = graphs.RandomBarabasiAlbert(100, 2)
sage: D = DiGraph(G)
sage: ec1 = GabowEdgeConnectivity(D,
....:                             dfs_preprocessing=False).edge_connectivity()
sage: ec2 = GabowEdgeConnectivity(D,
....:                             dfs_preprocessing=True).edge_connectivity()
sage: ec3 = GabowEdgeConnectivity(D, dfs_preprocessing=True,
....:                             use_rec=True).edge_connectivity()
sage: ec1 == ec2 and ec2 == ec3
True

>>> from sage.all import *
>>> # needs networkx
>>> G = graphs.RandomBarabasiAlbert(Integer(100), Integer(2))
>>> D = DiGraph(G)
>>> ec1 = GabowEdgeConnectivity(D,
...                             dfs_preprocessing=False).edge_connectivity()
>>> ec2 = GabowEdgeConnectivity(D,
...                             dfs_preprocessing=True).edge_connectivity()
>>> ec3 = GabowEdgeConnectivity(D, dfs_preprocessing=True,
...                             use_rec=True).edge_connectivity()
>>> ec1 == ec2 and ec2 == ec3
True
edge_connectivity()[source]

Return the edge connectivity of the digraph.

Digraphs with multiple edges are supported: every parallel arc counts separately in the cuts.

EXAMPLES:

sage: from sage.graphs.edge_connectivity import GabowEdgeConnectivity
sage: D = digraphs.Complete(5)
sage: GabowEdgeConnectivity(D).edge_connectivity()
4

>>> from sage.all import *
>>> from sage.graphs.edge_connectivity import GabowEdgeConnectivity
>>> D = digraphs.Complete(Integer(5))
>>> GabowEdgeConnectivity(D).edge_connectivity()
4

On a digraph with multiple edges:

sage: D = DiGraph([(0, 1), (0, 1), (1, 0)], multiedges=True)
sage: GabowEdgeConnectivity(D).edge_connectivity()
1
[Python] 
>>> from sage.all import *
>>> D = DiGraph([(Integer(0), Integer(1)), (Integer(0), Integer(1)), (Integer(1), Integer(0))], multiedges=True)
>>> GabowEdgeConnectivity(D).edge_connectivity()
1
edge_disjoint_spanning_trees(k=None, root=None, labels=False)[source]

Return k edge-disjoint spanning arborescences rooted at root.

The returned arborescences are out-arborescences (rooted spanning trees with all edges directed away from the root). Following [Gabow1995] and Edmonds’ branching theorem, the maximum number of edge-disjoint spanning out-arborescences rooted at a vertex r equals the minimum r-cut of the digraph. When the digraph is strongly connected, this is at least the edge connectivity ec of the digraph.

INPUT:

  • k – integer or None (default: None); the number of edge-disjoint spanning arborescences to return. If None, the method returns self.ec arborescences (the value computed by edge_connectivity()).

  • root – vertex of the input digraph or None (default: None); the common root of the returned arborescences. If None, defaults to the first vertex of the digraph (the same convention used by the MILP backend in edge_disjoint_spanning_trees()).

  • labels – boolean (default: False); whether the edges of the returned arborescences carry the labels of the corresponding input edges. With labels, parallel edges of a digraph with multiple edges remain distinguishable in the output: every returned edge corresponds to a distinct input edge.

OUTPUT:

A list of DiGraph, each on the same vertex set as the input. Every returned arborescence is rooted at root: the root has indegree 0, every other vertex has indegree 1, and every vertex is reachable from root. The returned arborescences are pairwise edge-disjoint.

ALGORITHM:

This uses the matroid-intersection approach of [Gabow1995], in two phases. Phase 1 builds a k-intersection whose union is a k-in-regular subgraph rooted at root (every non-root vertex has in-degree k). Phase 2 decomposes that union into k spanning out-arborescences one at a time (find_tree): it grows the set of vertices reachable from root, and whenever the next edge it needs is already used by another tree, an augmenting-path swap (search_step) frees a usable edge while keeping the other trees valid.

The extraction scheme follows the practical implementation studied in [GKMN2022]. Phase 1 runs in time \(O(km\log(n^2/m))\) [Gabow1995]. Phase 2 performs \(k\) extraction rounds, each rebuilding an intersection on the remaining edge pool before carving out one arborescence, and its swaps dominate the running time in practice: the observed total grows roughly like \(k^2 m\) (about \(n^4\) on complete digraphs, where \(k = n - 1\)).

EXAMPLES:

On a complete digraph, the algorithm returns n-1 arborescences:

sage: from sage.graphs.edge_connectivity import GabowEdgeConnectivity
sage: D = digraphs.Complete(5)
sage: trees = GabowEdgeConnectivity(D).edge_disjoint_spanning_trees(k=4)
sage: len(trees)
4
sage: all(T.num_edges() == 4 for T in trees)
True

>>> from sage.all import *
>>> from sage.graphs.edge_connectivity import GabowEdgeConnectivity
>>> D = digraphs.Complete(Integer(5))
>>> trees = GabowEdgeConnectivity(D).edge_disjoint_spanning_trees(k=Integer(4))
>>> len(trees)
4
>>> all(T.num_edges() == Integer(4) for T in trees)
True

By default (k=None) the method returns ec arborescences, where ec is the edge connectivity:

sage: from sage.graphs.edge_connectivity import GabowEdgeConnectivity
sage: D = digraphs.Complete(5)
sage: G = GabowEdgeConnectivity(D)
sage: G.edge_connectivity()
4
sage: len(G.edge_disjoint_spanning_trees())
4
[Python] 
>>> from sage.all import *
>>> from sage.graphs.edge_connectivity import GabowEdgeConnectivity
>>> D = digraphs.Complete(Integer(5))
>>> G = GabowEdgeConnectivity(D)
>>> G.edge_connectivity()
4
>>> len(G.edge_disjoint_spanning_trees())
4

The arborescences can be rooted at any vertex; the root then has indegree 0, every other vertex has indegree 1, and every vertex is reachable from the root:

sage: D = digraphs.Complete(5)
sage: trees = GabowEdgeConnectivity(D).edge_disjoint_spanning_trees(k=4, root=2)
sage: all(T.in_degree(2) == 0 for T in trees)
True
sage: all(T.in_degree(v) == 1 for T in trees for v in D if v != 2)
True
sage: all(set(T.depth_first_search(2)) == set(D) for T in trees)
True

>>> from sage.all import *
>>> D = digraphs.Complete(Integer(5))
>>> trees = GabowEdgeConnectivity(D).edge_disjoint_spanning_trees(k=Integer(4), root=Integer(2))
>>> all(T.in_degree(Integer(2)) == Integer(0) for T in trees)
True
>>> all(T.in_degree(v) == Integer(1) for T in trees for v in D if v != Integer(2))
True
>>> all(set(T.depth_first_search(Integer(2))) == set(D) for T in trees)
True

The returned arborescences are pairwise edge-disjoint:

sage: D = digraphs.Complete(5)
sage: trees = GabowEdgeConnectivity(D).edge_disjoint_spanning_trees(k=4)
sage: all_edges = sum((T.edges(labels=False, sort=False) for T in trees), [])
sage: len(all_edges) == len(set(all_edges))
True
[Python] 
>>> from sage.all import *
>>> D = digraphs.Complete(Integer(5))
>>> trees = GabowEdgeConnectivity(D).edge_disjoint_spanning_trees(k=Integer(4))
>>> all_edges = sum((T.edges(labels=False, sort=False) for T in trees), [])
>>> len(all_edges) == len(set(all_edges))
True

On a directed cycle the edge connectivity is 1, so the packing has a single arborescence: the directed path from the root:

sage: from sage.graphs.edge_connectivity import GabowEdgeConnectivity
sage: D = digraphs.Circuit(4)
sage: trees = GabowEdgeConnectivity(D).edge_disjoint_spanning_trees(root=0)
sage: len(trees)
1
sage: sorted(trees[0].edges(labels=False, sort=False))
[(0, 1), (1, 2), (2, 3)]

>>> from sage.all import *
>>> from sage.graphs.edge_connectivity import GabowEdgeConnectivity
>>> D = digraphs.Circuit(Integer(4))
>>> trees = GabowEdgeConnectivity(D).edge_disjoint_spanning_trees(root=Integer(0))
>>> len(trees)
1
>>> sorted(trees[Integer(0)].edges(labels=False, sort=False))
[(0, 1), (1, 2), (2, 3)]

On a digraph with multiple edges, labels=True shows which copy of a parallel edge each arborescence uses; every returned edge corresponds to a distinct input edge:

sage: D = DiGraph([(0, 1, 'a'), (0, 1, 'b'), (1, 0, 'c'), (1, 0, 'd')],
....:             multiedges=True)
sage: trees = GabowEdgeConnectivity(D).edge_disjoint_spanning_trees(k=2, root=0, labels=True)
sage: sorted(e[2] for T in trees for e in T.edge_iterator())
['a', 'b']
[Python] 
>>> from sage.all import *
>>> D = DiGraph([(Integer(0), Integer(1), 'a'), (Integer(0), Integer(1), 'b'), (Integer(1), Integer(0), 'c'), (Integer(1), Integer(0), 'd')],
...             multiedges=True)
>>> trees = GabowEdgeConnectivity(D).edge_disjoint_spanning_trees(k=Integer(2), root=Integer(0), labels=True)
>>> sorted(e[Integer(2)] for T in trees for e in T.edge_iterator())
['a', 'b']

Trivial case:

sage: from sage.graphs.edge_connectivity import GabowEdgeConnectivity
sage: D = digraphs.Complete(5)
sage: GabowEdgeConnectivity(D).edge_disjoint_spanning_trees(k=0)
[]

>>> from sage.all import *
>>> from sage.graphs.edge_connectivity import GabowEdgeConnectivity
>>> D = digraphs.Complete(Integer(5))
>>> GabowEdgeConnectivity(D).edge_disjoint_spanning_trees(k=Integer(0))
[]

Asking for more arborescences than the digraph can support raises EmptySetError:

sage: from sage.graphs.edge_connectivity import GabowEdgeConnectivity
sage: from sage.categories.sets_cat import EmptySetError
sage: D = digraphs.Complete(5)
sage: try:
....:     _ = GabowEdgeConnectivity(D).edge_disjoint_spanning_trees(k=5)
....: except EmptySetError:
....:     print("EmptySetError")
EmptySetError
[Python] 
>>> from sage.all import *
>>> from sage.graphs.edge_connectivity import GabowEdgeConnectivity
>>> from sage.categories.sets_cat import EmptySetError
>>> D = digraphs.Complete(Integer(5))
>>> try:
...     _ = GabowEdgeConnectivity(D).edge_disjoint_spanning_trees(k=Integer(5))
... except EmptySetError:
...     print("EmptySetError")
EmptySetError

An unknown root raises a ValueError:

sage: from sage.graphs.edge_connectivity import GabowEdgeConnectivity
sage: D = digraphs.Complete(5)
sage: GabowEdgeConnectivity(D).edge_disjoint_spanning_trees(k=2, root=99)
Traceback (most recent call last):
...
ValueError: vertex 99 is not a vertex of the graph

>>> from sage.all import *
>>> from sage.graphs.edge_connectivity import GabowEdgeConnectivity
>>> D = digraphs.Complete(Integer(5))
>>> GabowEdgeConnectivity(D).edge_disjoint_spanning_trees(k=Integer(2), root=Integer(99))
Traceback (most recent call last):
...
ValueError: vertex 99 is not a vertex of the graph