oxicuda_graphalg/max_flow/
min_cut.rs

1//! Min cut via residual reachability from max flow.
2
3use std::collections::VecDeque;
4
5use crate::error::{GraphalgError, GraphalgResult};
6use crate::max_flow::edmonds_karp::FlowNetwork;
7
8#[derive(Debug, Clone)]
9pub struct MinCut {
10    pub value: f64,
11    pub source_side: Vec<usize>,
12    pub cut_edges: Vec<(usize, usize, f64)>,
13}
14
15/// Computes the s-t min cut by running Edmonds-Karp and then taking residual reachability from `source`.
16pub fn min_cut_from_max_flow(
17    net: &FlowNetwork,
18    source: usize,
19    sink: usize,
20) -> GraphalgResult<MinCut> {
21    if source >= net.n || sink >= net.n {
22        return Err(GraphalgError::SourceOutOfRange {
23            node: source.max(sink),
24            n: net.n,
25        });
26    }
27    let n = net.n;
28    let mut residual = net.clone();
29    let mut max_flow = 0.0;
30    loop {
31        let mut parent = vec![usize::MAX; n];
32        parent[source] = source;
33        let mut q: VecDeque<usize> = VecDeque::new();
34        q.push_back(source);
35        let mut found = false;
36        while let Some(u) = q.pop_front() {
37            if u == sink {
38                found = true;
39                break;
40            }
41            for v in 0..n {
42                if parent[v] == usize::MAX && residual.c(u, v) > 1e-12 {
43                    parent[v] = u;
44                    q.push_back(v);
45                }
46            }
47        }
48        if !found {
49            break;
50        }
51        let mut bottleneck = f64::INFINITY;
52        let mut v = sink;
53        while v != source {
54            let u = parent[v];
55            bottleneck = bottleneck.min(residual.c(u, v));
56            v = u;
57        }
58        let mut v = sink;
59        while v != source {
60            let u = parent[v];
61            *residual.c_mut(u, v) -= bottleneck;
62            *residual.c_mut(v, u) += bottleneck;
63            v = u;
64        }
65        max_flow += bottleneck;
66    }
67    // Find reachable set in residual graph from source
68    let mut reach = vec![false; n];
69    reach[source] = true;
70    let mut q: VecDeque<usize> = VecDeque::new();
71    q.push_back(source);
72    while let Some(u) = q.pop_front() {
73        for v in 0..n {
74            if !reach[v] && residual.c(u, v) > 1e-12 {
75                reach[v] = true;
76                q.push_back(v);
77            }
78        }
79    }
80    let mut source_side = Vec::new();
81    let mut cut_edges = Vec::new();
82    for u in 0..n {
83        if reach[u] {
84            source_side.push(u);
85            for v in 0..n {
86                if !reach[v] && net.c(u, v) > 1e-12 {
87                    cut_edges.push((u, v, net.c(u, v)));
88                }
89            }
90        }
91    }
92    Ok(MinCut {
93        value: max_flow,
94        source_side,
95        cut_edges,
96    })
97}
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102
103    #[test]
104    fn min_cut_eq_max_flow() {
105        let mut net = FlowNetwork::new(4);
106        net.add_edge(0, 1, 3.0).expect("ok");
107        net.add_edge(0, 2, 2.0).expect("ok");
108        net.add_edge(1, 3, 3.0).expect("ok");
109        net.add_edge(2, 3, 2.0).expect("ok");
110        let mc = min_cut_from_max_flow(&net, 0, 3).expect("ok");
111        let cut: f64 = mc.cut_edges.iter().map(|e| e.2).sum();
112        assert!((mc.value - cut).abs() < 1e-9);
113    }
114}
oxicuda_graphalg/max_flow/min_cut.rs

oxicuda_graphalg/max_flow/
min_cut.rs
