minimum_st_node_cut

minimum_st_node_cut(G, s, t, aux_digraph=None, mapping=None)

Returns a set of nodes of minimum cardinality that disconnect source from target in G.

This function returns the set of nodes of minimum cardinality that, if removed, would destroy all paths among source and target in G.

Parameters :

G : NetworkX graph

s : node

Source node.

t : node

Target node.

Returns :

cutset : set

Set of nodes that, if removed, would destroy all paths between source and target in G.

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 [R205]. We use the Ford and Fulkerson algorithm to compute max flow (see ford_fulkerson).

References

[R205]

(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, 0, 6))
5