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