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

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