Connectivity¶
Connectivity and cut algorithms
Edgeaugmentation¶
Algorithms for finding kedgeaugmentations
A kedgeaugmentation is a set of edges, that once added to a graph, ensures that the graph is kedgeconnected; i.e. the graph cannot be disconnected unless k or more edges are removed. Typically, the goal is to find the augmentation with minimum weight. In general, it is not guaranteed that a kedgeaugmentation exists.
See Also¶
edge_kcomponents
: algorithms for finding kedgeconnected components
connectivity
: algorithms for determening edge connectivity.

Finds set of edges to kedgeconnect G. 

Tests to see if a graph is kedgeconnected. 

Tests to see if an edge in a graph is locally kedgeconnected. 
Kedgecomponents¶
Algorithms for finding kedgeconnected components and subgraphs.
A kedgeconnected component (kedgecc) is a maximal set of nodes in G, such that all pairs of node have an edgeconnectivity of at least k.
A kedgeconnected subgraph (kedgesubgraph) is a maximal set of nodes in G, such that the subgraph of G defined by the nodes has an edgeconnectivity at least k.

Generates nodes in each maximal kedgeconnected component in G. 

Generates nodes in each maximal kedgeconnected subgraph in G. 
Finds all bridgeconnected components G. 

A simple algorithm to find all kedgeconnected components in a graph. 
Knodecomponents¶
Moody and White algorithm for kcomponents

Returns the kcomponent structure of a graph G. 
Knodecutsets¶
Kanevsky all minimum node k cutsets algorithm.

Returns all minimum k cutsets of an undirected graph G. 
Flowbased disjoint paths¶
Flow based node and edge disjoint paths.

Returns the edges disjoint paths between source and target. 

Computes node disjoint paths between source and target. 
Flowbased Connectivity¶
Flow based connectivity algorithms

Returns the average connectivity of a graph G. 

Compute node connectivity between all pairs of nodes of G. 

Returns the edge connectivity of the graph or digraph G. 

Returns local edge connectivity for nodes s and t in G. 

Computes local node connectivity for nodes s and t. 

Returns node connectivity for a graph or digraph G. 
Flowbased Minimum Cuts¶
Flow based cut algorithms

Returns a set of edges of minimum cardinality that disconnects G. 

Returns a set of nodes of minimum cardinality that disconnects G. 

Returns the edges of the cutset of a minimum (s, t)cut. 

Returns a set of nodes of minimum cardinality that disconnect source from target in G. 
StoerWagner minimum cut¶
StoerWagner minimum cut algorithm.

Returns the weighted minimum edge cut using the StoerWagner algorithm. 
Utils for flowbased connectivity¶
Utilities for connectivity package
Auxiliary digraph for computing flow based edge connectivity 

Creates a directed graph D from an undirected graph G to compute flow based node connectivity. 