Connectivity and cut algorithms


Algorithms for finding k-edge-augmentations

A k-edge-augmentation is a set of edges, that once added to a graph, ensures that the graph is k-edge-connected; 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 k-edge-augmentation exists.

See Also#

edge_kcomponents : algorithms for finding k-edge-connected components connectivity : algorithms for determining edge connectivity.

k_edge_augmentation(G, k[, avail, weight, ...])

Finds set of edges to k-edge-connect G.

is_k_edge_connected(G, k)

Tests to see if a graph is k-edge-connected.

is_locally_k_edge_connected(G, s, t, k)

Tests to see if an edge in a graph is locally k-edge-connected.


Algorithms for finding k-edge-connected components and subgraphs.

A k-edge-connected component (k-edge-cc) is a maximal set of nodes in G, such that all pairs of node have an edge-connectivity of at least k.

A k-edge-connected subgraph (k-edge-subgraph) is a maximal set of nodes in G, such that the subgraph of G defined by the nodes has an edge-connectivity at least k.

k_edge_components(G, k)

Generates nodes in each maximal k-edge-connected component in G.

k_edge_subgraphs(G, k)

Generates nodes in each maximal k-edge-connected subgraph in G.


Finds all bridge-connected components G.


A simple algorithm to find all k-edge-connected components in a graph.


Moody and White algorithm for k-components

k_components(G[, flow_func])

Returns the k-component structure of a graph G.


Kanevsky all minimum node k cutsets algorithm.

all_node_cuts(G[, k, flow_func])

Returns all minimum k cutsets of an undirected graph G.

Flow-based disjoint paths#

Flow based node and edge disjoint paths.

edge_disjoint_paths(G, s, t[, flow_func, ...])

Returns the edges disjoint paths between source and target.

node_disjoint_paths(G, s, t[, flow_func, ...])

Computes node disjoint paths between source and target.

Flow-based Connectivity#

Flow based connectivity algorithms

average_node_connectivity(G[, flow_func])

Returns the average connectivity of a graph G.

all_pairs_node_connectivity(G[, nbunch, ...])

Compute node connectivity between all pairs of nodes of G.

edge_connectivity(G[, s, t, flow_func, cutoff])

Returns the edge connectivity of the graph or digraph G.

local_edge_connectivity(G, s, t[, ...])

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

local_node_connectivity(G, s, t[, ...])

Computes local node connectivity for nodes s and t.

node_connectivity(G[, s, t, flow_func])

Returns node connectivity for a graph or digraph G.

Flow-based Minimum Cuts#

Flow based cut algorithms

minimum_edge_cut(G[, s, t, flow_func])

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

minimum_node_cut(G[, s, t, flow_func])

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

minimum_st_edge_cut(G, s, t[, flow_func, ...])

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

minimum_st_node_cut(G, s, t[, flow_func, ...])

Returns a set of nodes of minimum cardinality that disconnect source from target in G.

Stoer-Wagner minimum cut#

Stoer-Wagner minimum cut algorithm.

stoer_wagner(G[, weight, heap])

Returns the weighted minimum edge cut using the Stoer-Wagner algorithm.

Utils for flow-based 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.