networkx.min_cut

min_cut(G, s, t)

Compute the value of a minimum (s, t)-cut.

Use the max-flow min-cut theorem, i.e., the capacity of a minimum capacity cut is equal to the flow value of a maximum flow.

Parameters:

G : NetworkX graph

Edges of the graph are expected to have an attribute called ‘capacity’. If this attribute is not present, the edge is considered to have infinite capacity.

s : node

Source node for the flow.

t : node

Sink node for the flow.

Returns:

cutValue : integer, float

Value of the minimum cut.

Raises:

NetworkXError :

If the graph has a path of infinite capacity, all cuts have infinite capacity and the function raises a NetworkXError.

Examples

>>> import networkx as nx
>>> G = nx.DiGraph()
>>> G.add_edge('x','a', capacity = 3.0)
>>> G.add_edge('x','b', capacity = 1.0)
>>> G.add_edge('a','c', capacity = 3.0)
>>> G.add_edge('b','c', capacity = 5.0)
>>> G.add_edge('b','d', capacity = 4.0)
>>> G.add_edge('d','e', capacity = 2.0)
>>> G.add_edge('c','y', capacity = 2.0)
>>> G.add_edge('e','y', capacity = 3.0)
>>> nx.min_cut(G, 'x', 'y')
3.0