Skip to main content
`Ctrl`+`K`

# Connectivity

Connectivity and cut algorithms

## Edge-augmentation

Algorithms for finding k-edge-augmentations

A k-edge-augmentation is a set of edges, that once added to a graph, ensures that the graph is k-edge-connected; i.e. the graph cannot be disconnected unless k or more edges are removed. Typically, the goal is to find the augmentation with minimum weight. In general, it is not guaranteed that a k-edge-augmentation exists.

### See Also

`edge_kcomponents` : algorithms for finding k-edge-connected components `connectivity` : algorithms for determining edge connectivity.

`k_edge_augmentation`(G, k[, avail, weight, ...]) | Finds set of edges to k-edge-connect G.
`is_k_edge_connected`(G, k) | Tests to see if a graph is k-edge-connected.
`is_locally_k_edge_connected`(G, s, t, k) | Tests to see if an edge in a graph is locally k-edge-connected.

## 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 disjoint paths

Flow based node and edge disjoint paths.

`edge_disjoint_paths`(G, s, t[, flow_func, ...]) | Returns the edges disjoint paths between source and target.
`node_disjoint_paths`(G, s, t[, flow_func, ...]) | Computes node disjoint paths between source and target.

## 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, cutoff]) | 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.