minimum_node_cut

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

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

If source and target nodes are provided, this function returns the set of nodes of minimum cardinality that, if removed, would destroy all paths among source and target in G. If not, it returns a set of nodes 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 nodes that, if removed, would disconnect G. If source and target nodes are provided, the set contians the nodes that if removed, would destroy all paths between source and target.

See also

node_connectivity, edge_connectivity, minimum_edge_cut, max_flow, ford_fulkerson

Notes

This is a flow based implementation of minimum node cut. The algorithm is based in solving a number of max-flow problems (ie local st-node connectivity, see local_node_connectivity) to determine the capacity of the minimum cut on an auxiliary directed network that corresponds to the minimum node cut of G. It handles both directed and undirected graphs.

This implementation is based on algorithm 11 in [R204]. We use the Ford and Fulkerson algorithm to compute max flow (see ford_fulkerson).

References

[R204]

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

Examples

>>> # Platonic icosahedral graph has node connectivity 5 
>>> G = nx.icosahedral_graph()
>>> len(nx.minimum_node_cut(G))
5
>>> # this is the minimum over any pair of non adjacent nodes
>>> from itertools import combinations
>>> for u,v in combinations(G, 2):
...     if v not in G[u]:
...         assert(len(nx.minimum_node_cut(G,u,v)) == 5)
...