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