graph_flow/
min_cut.rs

1//! Minimum s-t cut from a completed max-flow computation.
2//!
3//! By the **Max-Flow Min-Cut theorem**, the value of the maximum flow from
4//! source `s` to sink `t` equals the capacity of the minimum cut separating
5//! `s` from `t`. After running a max-flow algorithm, the min-cut can be read
6//! directly from the residual graph in O(V + E).
7
8use crate::FlowGraph;
9use std::collections::VecDeque;
10
11/// The result of a minimum s-t cut computation.
12///
13/// The cut partitions the graph's nodes into two sets: `source_side` (nodes
14/// reachable from the source in the residual graph) and `sink_side` (all
15/// other nodes). Every edge crossing from `source_side` to `sink_side` in the
16/// **original** graph is a cut edge; their capacity sum equals the max flow.
17#[derive(Debug, Clone)]
18pub struct MinCut {
19    /// Nodes reachable from the source in the residual graph after max-flow.
20    ///
21    /// This is the source partition `S` of the min-cut `(S, T)`.
22    pub source_side: Vec<usize>,
23    /// Nodes **not** reachable from the source in the residual graph.
24    ///
25    /// This is the sink partition `T` of the min-cut `(S, T)`.
26    pub sink_side: Vec<usize>,
27    /// The cut edges: `(u, v)` pairs where `u ∈ source_side`, `v ∈ sink_side`,
28    /// and there is a forward edge `u → v` in the original graph.
29    pub cut_edges: Vec<(usize, usize)>,
30    /// Total capacity of all cut edges. Equals the maximum flow value by the
31    /// Max-Flow Min-Cut theorem.
32    pub capacity: f64,
33}
34
35/// Computes the minimum s-t cut from a [`FlowGraph`] on which a max-flow
36/// algorithm has already been run.
37///
38/// The function does **not** run max-flow itself — call [`edmonds_karp`] or
39/// [`ford_fulkerson`] first, then pass the same graph here.
40///
41/// # How it works
42///
43/// After max-flow saturates the network, BFS from `source` in the **residual**
44/// graph (only traversing edges with positive remaining capacity) discovers all
45/// nodes still reachable from `source`. These form the source side `S` of the
46/// cut. Every original edge crossing from `S` to `T = V \ S` is a cut edge.
47///
48/// # Arguments
49///
50/// - `graph` — a [`FlowGraph`] after max-flow has been computed.
51/// - `source` — the source node index.
52///
53/// # Returns
54///
55/// A [`MinCut`] describing the partition and cut edges.
56///
57/// # Complexity
58///
59/// O(V + E).
60///
61/// # Examples
62///
63/// ```
64/// use graph_flow::{FlowGraph, edmonds_karp, min_cut};
65///
66/// let mut g = FlowGraph::new(4);
67/// g.add_edge(0, 1, 10.0);
68/// g.add_edge(0, 2, 5.0);
69/// g.add_edge(1, 3, 10.0);
70/// g.add_edge(2, 3, 5.0);
71///
72/// let max_flow = edmonds_karp(&mut g, 0, 3);
73/// let cut = min_cut(&g, 0);
74///
75/// // Max-flow = min-cut capacity (Max-Flow Min-Cut theorem).
76/// assert_eq!(max_flow, cut.capacity);
77/// assert_eq!(cut.capacity, 15.0);
78/// ```
79///
80/// [`edmonds_karp`]: crate::edmonds_karp::edmonds_karp
81/// [`ford_fulkerson`]: crate::ford_fulkerson::ford_fulkerson
82pub fn min_cut(graph: &FlowGraph, source: usize) -> MinCut {
83    // BFS over the residual graph to find all nodes reachable from source.
84    let reachable = residual_reachable(graph, source);
85
86    let mut source_side = Vec::new();
87    let mut sink_side = Vec::new();
88
89    for (node, &is_reachable) in reachable.iter().enumerate() {
90        if is_reachable {
91            source_side.push(node);
92        } else {
93            sink_side.push(node);
94        }
95    }
96
97    // Collect cut edges and sum their original capacities.
98    let mut cut_edges = Vec::new();
99    let mut capacity = 0.0f64;
100
101    for &u in &source_side {
102        for edge in &graph.adjacency[u] {
103            // A cut edge goes from source_side to sink_side and has positive
104            // original capacity (not a reverse/residual-only edge).
105            if !reachable[edge.to] && edge.capacity > 0.0 {
106                cut_edges.push((u, edge.to));
107                capacity += edge.capacity;
108            }
109        }
110    }
111
112    MinCut {
113        source_side,
114        sink_side,
115        cut_edges,
116        capacity,
117    }
118}
119
120/// BFS over the residual graph (only edges with `residual() > 0`).
121///
122/// Returns a boolean array where `reachable[v]` is `true` iff `v` is
123/// reachable from `source` via edges with positive residual capacity.
124fn residual_reachable(graph: &FlowGraph, source: usize) -> Vec<bool> {
125    let n = graph.node_count();
126    let mut reachable = vec![false; n];
127    let mut queue = VecDeque::new();
128
129    reachable[source] = true;
130    queue.push_back(source);
131
132    while let Some(node) = queue.pop_front() {
133        for edge in &graph.adjacency[node] {
134            if !reachable[edge.to] && edge.residual() > 0.0 {
135                reachable[edge.to] = true;
136                queue.push_back(edge.to);
137            }
138        }
139    }
140
141    reachable
142}
graph_flow/min_cut.rs

graph_flow/
min_cut.rs
