minimum_edge_cut

minimum_edge_cut(G, s=None, t=None)

Returns a set of edges of minimum cardinality that disconnects G.

If source and target nodes are provided, this function returns the set of edges of minimum cardinality that, if removed, would break all paths among source and target in G. If not, it returns a set of edges of minimum cardinality that disconnects G.

Parameters :

G : NetworkX graph

s : node

Source node. Optional (default=None)

t : node

Target node. Optional (default=None)

Returns :

cutset : set

Set of edges that, if removed, would disconnect G. If source and target nodes are provided, the set contians the edges that if removed, would destroy all paths between source and target.

See also

node_connectivity, edge_connectivity, minimum_node_cut, max_flow, ford_fulkerson

Notes

This is a flow based implementation of minimum edge cut. For undirected graphs the algorithm works by finding a ‘small’ dominating set of nodes of G (see algorithm 7 in [R203]) and computing the maximum flow between an arbitrary node in the dominating set and the rest of nodes in it. This is an implementation of algorithm 6 in [R203].

For directed graphs, the algorithm does n calls to the max flow function. This is an implementation of algorithm 8 in [R203]. We use the Ford and Fulkerson algorithm to compute max flow (see ford_fulkerson).

References

[R203]

(1, 2, 3, 4) Abdol-Hossein Esfahanian. Connectivity Algorithms. http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

Examples

>>> # Platonic icosahedral graph has edge connectivity 5
>>> G = nx.icosahedral_graph()
>>> len(nx.minimum_edge_cut(G))
5
>>> # this is the minimum over any pair of nodes
>>> from itertools import combinations
>>> for u,v in combinations(G, 2):
...     assert(len(nx.minimum_edge_cut(G,u,v)) == 5)
...