Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

Connectivity

Connectivity and cut algorithms

K-edge-components

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.
bridge_components(G) Finds all bridge-connected components G.
EdgeComponentAuxGraph A simple algorithm to find all k-edge-connected components in a graph.

K-node-components

Moody and White algorithm for k-components

k_components(G[, flow_func]) Returns the k-component structure of a graph G.

K-node-cutsets

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

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

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.