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
Add speedup methods proposed in [GKLP2021] for the edge connectivity
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
– aDiGraph
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)) sage: while not D.is_strongly_connected(): ....: D = DiGraph(graphs.RandomRegular(6, 50)) sage: GabowEdgeConnectivity(D).edge_connectivity() 6
- G#
- edge_connectivity()#
Return the edge connectivity of the digraph.
EXAMPLES:
sage: from sage.graphs.edge_connectivity import GabowEdgeConnectivity sage: D = digraphs.Complete(5) sage: GabowEdgeConnectivity(D).edge_connectivity() 4
- edge_disjoint_spanning_trees()#
Iterator over the edge disjoint spanning trees.
EXAMPLES:
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