minimum_st_edge_cut

minimum_st_edge_cut(G, s, t, capacity='capacity')

Returns the edges of the cut-set of a minimum (s, t)-cut.

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

capacity: string :

Edges of the graph G are expected to have an attribute capacity that indicates how much flow the edge can support. If this attribute is not present, the edge is considered to have infinite capacity. Default value: ‘capacity’.

Returns :

cutset : set

Set of edges that, if removed from the graph, will disconnect it

Raises :

NetworkXUnbounded :

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

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)
>>> sorted(nx.minimum_edge_cut(G, 'x', 'y'))
[('c', 'y'), ('x', 'b')]
>>> nx.min_cut(G, 'x', 'y')
3.0