oxicuda_graphalg/max_flow/
dinic.rs

1//! Dinic's max flow: level-graph + blocking-flow DFS. O(V^2 E).
2
3use std::collections::VecDeque;
4
5use crate::error::{GraphalgError, GraphalgResult};
6use crate::max_flow::edmonds_karp::FlowNetwork;
7
8/// Dinic's algorithm using a dense residual matrix.
9pub fn dinic_max_flow(net: &FlowNetwork, source: usize, sink: usize) -> GraphalgResult<f64> {
10    if source >= net.n || sink >= net.n {
11        return Err(GraphalgError::SourceOutOfRange {
12            node: source.max(sink),
13            n: net.n,
14        });
15    }
16    let mut residual = net.clone();
17    let mut max_flow = 0.0;
18    let n = net.n;
19    loop {
20        // BFS to build level graph
21        let mut level = vec![i64::MAX; n];
22        level[source] = 0;
23        let mut q: VecDeque<usize> = VecDeque::new();
24        q.push_back(source);
25        while let Some(u) = q.pop_front() {
26            for v in 0..n {
27                if level[v] == i64::MAX && residual.c(u, v) > 1e-12 {
28                    level[v] = level[u] + 1;
29                    q.push_back(v);
30                }
31            }
32        }
33        if level[sink] == i64::MAX {
34            break;
35        }
36        // DFS to push blocking flow
37        let mut next_idx = vec![0usize; n];
38        loop {
39            let pushed = dfs_push(
40                &mut residual,
41                source,
42                sink,
43                f64::INFINITY,
44                &level,
45                &mut next_idx,
46            );
47            if pushed <= 1e-15 {
48                break;
49            }
50            max_flow += pushed;
51        }
52    }
53    Ok(max_flow)
54}
55
56fn dfs_push(
57    residual: &mut FlowNetwork,
58    u: usize,
59    sink: usize,
60    pushed: f64,
61    level: &[i64],
62    next_idx: &mut [usize],
63) -> f64 {
64    if u == sink {
65        return pushed;
66    }
67    let n = residual.n;
68    while next_idx[u] < n {
69        let v = next_idx[u];
70        if residual.c(u, v) > 1e-12 && level[v] == level[u] + 1 {
71            let bottleneck = pushed.min(residual.c(u, v));
72            let res = dfs_push(residual, v, sink, bottleneck, level, next_idx);
73            if res > 1e-15 {
74                *residual.c_mut(u, v) -= res;
75                *residual.c_mut(v, u) += res;
76                return res;
77            }
78        }
79        next_idx[u] += 1;
80    }
81    0.0
82}
83
84#[cfg(test)]
85mod tests {
86    use super::*;
87
88    #[test]
89    fn dinic_simple() {
90        let mut net = FlowNetwork::new(4);
91        net.add_edge(0, 1, 3.0).expect("ok");
92        net.add_edge(0, 2, 2.0).expect("ok");
93        net.add_edge(1, 3, 3.0).expect("ok");
94        net.add_edge(2, 3, 2.0).expect("ok");
95        let f = dinic_max_flow(&net, 0, 3).expect("ok");
96        assert!((f - 5.0).abs() < 1e-9);
97    }
98}
oxicuda_graphalg/max_flow/dinic.rs

oxicuda_graphalg/max_flow/
dinic.rs
