minimum_cut

minimum_cut(flowG, _s, _t, capacity='capacity', flow_func=None, **kwargs)

Compute the value and the node partition 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:

flowGNetworkX 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.

_snode

Source node for the flow.

_tnode

Sink node for the flow.

capacitystring or function (default= ‘capacity’)

If this is a string, then edge capacity will be accessed via the edge attribute with this key (that is, the capacity of the edge joining u to v will be G.edges[u, v][capacity]). If no such edge attribute exists, the capacity of the edge is assumed to be infinite.

If this is a function, the capacity of an edge is the value returned by the function. The function must accept exactly three positional arguments: the two endpoints of an edge and the dictionary of edge attributes for that edge. The function must return a number or None to indicate a hidden edge.

flow_funcfunction

A function for computing the maximum flow among a pair of nodes in a capacitated graph. The function has to accept at least three parameters: a Graph or Digraph, a source node, and a target node. And return a residual network that follows NetworkX conventions (see Notes). If flow_func is None, the default maximum flow function (preflow_push()) is used. See below for alternative algorithms. The choice of the default function may change from version to version and should not be relied on. Default value: None.

kwargsAny other keyword parameter is passed to the function that

computes the maximum flow.

Returns:

cut_valueinteger, float

Value of the minimum cut.

partitionpair of node sets

A partitioning of the nodes that defines a minimum cut.

Raises:

NetworkXUnbounded

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

See also

maximum_flow()

maximum_flow_value()

minimum_cut_value()

edmonds_karp()

preflow_push()

shortest_augmenting_path()

Notes

The function used in the flow_func parameter has to return a residual network that follows NetworkX conventions:

The residual network R from an input graph G has the same nodes as G. R is a DiGraph that contains a pair of edges (u, v) and (v, u) iff (u, v) is not a self-loop, and at least one of (u, v) and (v, u) exists in G.

For each edge (u, v) in R, R[u][v]['capacity'] is equal to the capacity of (u, v) in G if it exists in G or zero otherwise. If the capacity is infinite, R[u][v]['capacity'] will have a high arbitrary finite value that does not affect the solution of the problem. This value is stored in R.graph['inf']. For each edge (u, v) in R, R[u][v]['flow'] represents the flow function of (u, v) and satisfies R[u][v]['flow'] == -R[v][u]['flow'].

The flow value, defined as the total flow into t, the sink, is stored in R.graph['flow_value']. Reachability to t using only edges (u, v) such that R[u][v]['flow'] < R[u][v]['capacity'] induces a minimum s-t cut.

Specific algorithms may store extra data in R.

The function should supports an optional boolean parameter value_only. When True, it can optionally terminate the algorithm as soon as the maximum flow value and the minimum cut can be determined.

Examples

>>> 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)

minimum_cut computes both the value of the minimum cut and the node partition:

>>> cut_value, partition = nx.minimum_cut(G, "x", "y")
>>> reachable, non_reachable = partition

‘partition’ here is a tuple with the two sets of nodes that define the minimum cut. You can compute the cut set of edges that induce the minimum cut as follows:

>>> cutset = set()
>>> for u, nbrs in ((n, G[n]) for n in reachable):
...     cutset.update((u, v) for v in nbrs if v in non_reachable)
>>> print(sorted(cutset))
[('c', 'y'), ('x', 'b')]
>>> cut_value == sum(G.edges[u, v]["capacity"] for (u, v) in cutset)
True

You can also use alternative algorithms for computing the minimum cut by using the flow_func parameter.

>>> from networkx.algorithms.flow import shortest_augmenting_path
>>> cut_value == nx.minimum_cut(G, "x", "y", flow_func=shortest_augmenting_path)[0]
True