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.

Todo

• Implement the tree-packing algorithms proposed in [Gabow1995] and [BHKP2008]

• Extend to digraphs with multiple edges

• Extend to weighted digraphs

class sage.graphs.edge_connectivity.GabowEdgeConnectivity

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.

Warning

Multiple edges are currently not supported. The current implementation act as if the digraph is simple and so the return results might not be correct. We therefore raise an error if the digraph has multiple edges.

INPUT:

• D – a DiGraph

EXAMPLES:

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

Sage

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

Python

>>> 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

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

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

Python

>>> 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

G

edge_connectivity()

Return the edge connectivity of the digraph.

EXAMPLES:

Sage

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

Python

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

edge_disjoint_spanning_trees()

Iterator over the edge disjoint spanning trees.

EXAMPLES:

Sage

sage: from sage.graphs.edge_connectivity import GabowEdgeConnectivity
sage: D = digraphs.Complete(5)
sage: GabowEdgeConnectivity(D).edge_disjoint_spanning_trees()
Traceback (most recent call last):
...
NotImplementedError: this method has not been implemented yet

Python

>>> from sage.all import *
>>> from sage.graphs.edge_connectivity import GabowEdgeConnectivity
>>> D = digraphs.Complete(Integer(5))
>>> GabowEdgeConnectivity(D).edge_disjoint_spanning_trees()
Traceback (most recent call last):
...
NotImplementedError: this method has not been implemented yet