Function min_cut 

pub fn min_cut(graph: &FlowGraph, source: usize) -> MinCut

Computes the minimum s-t cut from a FlowGraph on which a max-flow algorithm has already been run.

The function does not run max-flow itself — call edmonds_karp or ford_fulkerson first, then pass the same graph here.

How it works

After max-flow saturates the network, BFS from source in the residual graph (only traversing edges with positive remaining capacity) discovers all nodes still reachable from source. These form the source side S of the cut. Every original edge crossing from S to T = V \ S is a cut edge.

Arguments

• graph — a FlowGraph after max-flow has been computed.
• source — the source node index.

Returns

A MinCut describing the partition and cut edges.

Complexity

O(V + E).

Examples

use graph_flow::{FlowGraph, edmonds_karp, min_cut};

let mut g = FlowGraph::new(4);
g.add_edge(0, 1, 10.0);
g.add_edge(0, 2, 5.0);
g.add_edge(1, 3, 10.0);
g.add_edge(2, 3, 5.0);

let max_flow = edmonds_karp(&mut g, 0, 3);
let cut = min_cut(&g, 0);

// Max-flow = min-cut capacity (Max-Flow Min-Cut theorem).
assert_eq!(max_flow, cut.capacity);
assert_eq!(cut.capacity, 15.0);