Returns the edge connectivity of the graph or digraph G.
The edge connectivity is equal to the minimum number of edges that must be removed to disconnect G or render it trivial. If source and target nodes are provided, this function returns the local edge connectivity: the minimum number of edges that must be removed to break all paths from source to target in G.
This is a flow based implementation. The algorithm is based in solving a number of max-flow problems (ie local st-edge connectivity, see local_edge_connectivity) to determine the capacity of the minimum cut on an auxiliary directed network that corresponds to the minimum edge cut of G. It handles both directed and undirected graphs.
| Parameters : | G : NetworkX graph
s : node
t : node
|
|---|---|
| Returns : | K : integer
|
See also
local_node_connectivity, node_connectivity, local_edge_connectivity, max_flow, ford_fulkerson
Notes
This is a flow based implementation of global edge connectivity. For undirected graphs the algorithm works by finding a ‘small’ dominating set of nodes of G (see algorithm 7 in [R198] ) and computing local max flow (see local_edge_connectivity) between an arbitrary node in the dominating set and the rest of nodes in it. This is an implementation of algorithm 6 in [R198] .
For directed graphs, the algorithm does n calls to the max flow function. This is an implementation of algorithm 8 in [R198] . We use the Ford and Fulkerson algorithm to compute max flow (see ford_fulkerson).
References
| [R198] | (1, 2, 3, 4) Abdol-Hossein Esfahanian. Connectivity Algorithms. http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf |
Examples
>>> # Platonic icosahedral graph is 5-edge-connected
>>> G = nx.icosahedral_graph()
>>> nx.edge_connectivity(G)
5