Connectivity¶

Connectivity and cut algorithms

K-node-components¶

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 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])	Returns the edge connectivity of the graph or digraph G.
`local_edge_connectivity`(G, u, v[, ...])	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 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 algorithm.

stoer_wagner(G[, weight, heap]) Returns the weighted minimum edge cut using the Stoer-Wagner algorithm.

Utilities for connectivity package

`build_auxiliary_edge_connectivity`(G)	Auxiliary digraph for computing flow based edge connectivity
`build_auxiliary_node_connectivity`(G)	Creates a directed graph D from an undirected graph G to compute flow based node connectivity.