uni_algo/algo/algorithms/
dinic.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! Dinic's Max Flow Algorithm.
5//!
6//! Computes maximum flow from source to sink.
7//! Edge weights in GraphProjection are treated as capacities.
8
9use crate::algo::GraphProjection;
10use crate::algo::algorithms::Algorithm;
11use uni_common::core::id::Vid;
12
13pub struct Dinic;
14
15#[derive(Debug, Clone)]
16pub struct DinicConfig {
17    pub source: Vid,
18    pub sink: Vid,
19}
20
21impl Default for DinicConfig {
22    fn default() -> Self {
23        Self {
24            source: Vid::from(0),
25            sink: Vid::from(0),
26        }
27    }
28}
29
30pub struct DinicResult {
31    pub max_flow: f64,
32}
33
34#[derive(Clone, Copy)]
35struct Edge {
36    to: usize,
37    rev: usize, // index of reverse edge in adj[to]
38    cap: f64,
39    flow: f64,
40}
41
42impl Algorithm for Dinic {
43    type Config = DinicConfig;
44    type Result = DinicResult;
45
46    fn name() -> &'static str {
47        "dinic"
48    }
49
50    fn run(graph: &GraphProjection, config: Self::Config) -> Self::Result {
51        let source = match graph.to_slot(config.source) {
52            Some(s) => s as usize,
53            None => return DinicResult { max_flow: 0.0 },
54        };
55        let sink = match graph.to_slot(config.sink) {
56            Some(s) => s as usize,
57            None => return DinicResult { max_flow: 0.0 },
58        };
59
60        if source == sink {
61            return DinicResult {
62                max_flow: f64::INFINITY,
63            };
64        }
65
66        let n = graph.vertex_count();
67        let mut adj: Vec<Vec<Edge>> = (0..n).map(|_| Vec::new()).collect();
68
69        // Build residual graph
70        // For every edge u->v with cap C, add u->v (cap C, flow 0) and v->u (cap 0, flow 0).
71        for u in 0..n {
72            for (i, &v_u32) in graph.out_neighbors(u as u32).iter().enumerate() {
73                let v = v_u32 as usize;
74                let cap = if graph.has_weights() {
75                    graph.out_weight(u as u32, i)
76                } else {
77                    1.0
78                };
79
80                let a_len = adj[u].len();
81                let b_len = adj[v].len();
82
83                adj[u].push(Edge {
84                    to: v,
85                    rev: b_len,
86                    cap,
87                    flow: 0.0,
88                });
89                adj[v].push(Edge {
90                    to: u,
91                    rev: a_len,
92                    cap: 0.0, // Back edge capacity 0
93                    flow: 0.0,
94                });
95            }
96        }
97
98        let mut max_flow = 0.0;
99        let mut level = vec![0; n];
100
101        loop {
102            // BFS to build Level Graph
103            level.fill(i32::MAX);
104            level[source] = 0;
105            let mut queue = std::collections::VecDeque::new();
106            queue.push_back(source);
107
108            while let Some(u) = queue.pop_front() {
109                for e in &adj[u] {
110                    if e.cap - e.flow > 1e-9 && level[e.to] == i32::MAX {
111                        level[e.to] = level[u] + 1;
112                        queue.push_back(e.to);
113                    }
114                }
115            }
116
117            if level[sink] == i32::MAX {
118                break;
119            }
120
121            // DFS to push blocking flow
122            let mut ptr = vec![0; n];
123            while let Some(pushed) = dfs(source, sink, f64::INFINITY, &mut adj, &level, &mut ptr) {
124                if pushed == 0.0 {
125                    break;
126                }
127                max_flow += pushed;
128            }
129        }
130
131        DinicResult { max_flow }
132    }
133}
134
135fn dfs(
136    u: usize,
137    sink: usize,
138    pushed: f64,
139    adj: &mut [Vec<Edge>],
140    level: &[i32],
141    ptr: &mut [usize],
142) -> Option<f64> {
143    if pushed == 0.0 || u == sink {
144        return Some(pushed);
145    }
146
147    for i in ptr[u]..adj[u].len() {
148        ptr[u] = i;
149        let e = &adj[u][i];
150        if level[u] + 1 != level[e.to] || e.cap - e.flow <= 1e-9 {
151            continue;
152        }
153
154        let tr = dfs(e.to, sink, pushed.min(e.cap - e.flow), adj, level, ptr);
155        if let Some(tr) = tr {
156            if tr == 0.0 {
157                continue;
158            }
159            adj[u][i].flow += tr;
160            let rev = adj[u][i].rev;
161            let to = adj[u][i].to;
162            adj[to][rev].flow -= tr;
163            return Some(tr);
164        }
165    }
166    None
167}
168
169#[cfg(test)]
170mod tests {
171    use super::*;
172    use crate::algo::test_utils::build_test_graph;
173
174    #[test]
175    fn test_dinic_simple() {
176        // 0 -> 1 (cap 10), 1 -> 2 (cap 5)
177        // Max flow 0->2 is 5.
178        let vids = vec![Vid::from(0), Vid::from(1), Vid::from(2)];
179        let edges = vec![(Vid::from(0), Vid::from(1)), (Vid::from(1), Vid::from(2))];
180        let mut graph = build_test_graph(vids, edges);
181        // Inject weights
182        graph.out_weights = Some(vec![10.0, 5.0]);
183
184        let config = DinicConfig {
185            source: Vid::from(0),
186            sink: Vid::from(2),
187        };
188
189        let result = Dinic::run(&graph, config);
190        assert_eq!(result.max_flow, 5.0);
191    }
192}
uni_algo/algo/algorithms/dinic.rs

uni_algo/algo/algorithms/
dinic.rs
