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 gaurenteed that a k-edge-augmentation exists.
See also
edge_kcomponents
- algorithms for finding k-edge-connected components
connectivity
- algorithms for determening 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. |