oxihuman_core/
max_flow_ff.rs

1// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3#![allow(dead_code)]
4
5//! Ford-Fulkerson max-flow using BFS (Edmonds-Karp).
6
7/// A flow network.
8pub struct FlowGraph {
9    pub n: usize,
10    /// `capacity[u][v]`
11    pub cap: Vec<Vec<f32>>,
12}
13
14impl FlowGraph {
15    pub fn new(n: usize) -> Self {
16        FlowGraph {
17            n,
18            cap: vec![vec![0.0; n]; n],
19        }
20    }
21}
22
23/// Create a new flow graph with `n` vertices.
24pub fn new_flow_graph(n: usize) -> FlowGraph {
25    FlowGraph::new(n)
26}
27
28/// Add a directed edge with capacity `c`.
29pub fn fg_add_edge(g: &mut FlowGraph, u: usize, v: usize, c: f32) {
30    if u < g.n && v < g.n {
31        g.cap[u][v] += c;
32    }
33}
34
35/// Return the number of nodes.
36pub fn fg_node_count(g: &FlowGraph) -> usize {
37    g.n
38}
39
40/// Run Edmonds-Karp (BFS-based Ford-Fulkerson). Returns max-flow value.
41#[allow(clippy::needless_range_loop)]
42pub fn max_flow(g: &FlowGraph, src: usize, sink: usize) -> f32 {
43    if src >= g.n || sink >= g.n || src == sink {
44        return 0.0;
45    }
46    let n = g.n;
47    let mut residual = g.cap.clone();
48    let mut total = 0.0f32;
49
50    loop {
51        /* BFS to find augmenting path */
52        let mut prev = vec![usize::MAX; n];
53        let mut visited = vec![false; n];
54        let mut queue = std::collections::VecDeque::new();
55        visited[src] = true;
56        queue.push_back(src);
57
58        while let Some(u) = queue.pop_front() {
59            if u == sink {
60                break;
61            }
62            for v in 0..n {
63                if !visited[v] && residual[u][v] > 1e-9 {
64                    visited[v] = true;
65                    prev[v] = u;
66                    queue.push_back(v);
67                }
68            }
69        }
70
71        if !visited[sink] {
72            break; /* no augmenting path */
73        }
74
75        /* find bottleneck */
76        let mut flow = f32::INFINITY;
77        let mut cur = sink;
78        while cur != src {
79            let p = prev[cur];
80            flow = flow.min(residual[p][cur]);
81            cur = p;
82        }
83
84        /* update residual graph */
85        cur = sink;
86        while cur != src {
87            let p = prev[cur];
88            residual[p][cur] -= flow;
89            residual[cur][p] += flow;
90            cur = p;
91        }
92
93        total += flow;
94    }
95    total
96}
97
98/// Return `true` if `sink` is reachable from `src` in the residual graph
99/// (i.e., flow is not yet at maximum).
100#[allow(clippy::needless_range_loop)]
101pub fn fg_has_augmenting_path(g: &FlowGraph, src: usize, sink: usize) -> bool {
102    /* thin wrapper — just try one BFS */
103    let small = FlowGraph {
104        n: g.n,
105        cap: g.cap.clone(),
106    };
107    /* a dummy call; real check: residual capacity > 0 on some path */
108    let _ = small;
109    /* Simple BFS on capacities > 0 */
110    let mut visited = vec![false; g.n];
111    let mut queue = std::collections::VecDeque::new();
112    if src < g.n {
113        visited[src] = true;
114        queue.push_back(src);
115    }
116    while let Some(u) = queue.pop_front() {
117        if u == sink {
118            return true;
119        }
120        for v in 0..g.n {
121            if !visited[v] && g.cap[u][v] > 1e-9 {
122                visited[v] = true;
123                queue.push_back(v);
124            }
125        }
126    }
127    false
128}
129
130/// Return total capacity from `src` (sum of outgoing edges).
131pub fn fg_total_capacity_from(g: &FlowGraph, src: usize) -> f32 {
132    if src >= g.n {
133        return 0.0;
134    }
135    g.cap[src].iter().sum()
136}
137
138#[cfg(test)]
139mod tests {
140    use super::*;
141
142    #[test]
143    fn test_simple_flow() {
144        let mut g = new_flow_graph(4);
145        fg_add_edge(&mut g, 0, 1, 3.0);
146        fg_add_edge(&mut g, 0, 2, 2.0);
147        fg_add_edge(&mut g, 1, 3, 3.0);
148        fg_add_edge(&mut g, 2, 3, 2.0);
149        assert!((max_flow(&g, 0, 3) - 5.0).abs() < 1e-5);
150    }
151
152    #[test]
153    fn test_no_path_returns_zero() {
154        let g = new_flow_graph(3);
155        assert_eq!(max_flow(&g, 0, 2), 0.0);
156    }
157
158    #[test]
159    fn test_bottleneck_edge() {
160        let mut g = new_flow_graph(3);
161        fg_add_edge(&mut g, 0, 1, 100.0);
162        fg_add_edge(&mut g, 1, 2, 1.0);
163        assert!((max_flow(&g, 0, 2) - 1.0).abs() < 1e-5);
164    }
165
166    #[test]
167    fn test_parallel_paths() {
168        let mut g = new_flow_graph(4);
169        fg_add_edge(&mut g, 0, 1, 5.0);
170        fg_add_edge(&mut g, 0, 2, 5.0);
171        fg_add_edge(&mut g, 1, 3, 5.0);
172        fg_add_edge(&mut g, 2, 3, 5.0);
173        assert!((max_flow(&g, 0, 3) - 10.0).abs() < 1e-5);
174    }
175
176    #[test]
177    fn test_node_count() {
178        let g = new_flow_graph(6);
179        assert_eq!(fg_node_count(&g), 6);
180    }
181
182    #[test]
183    fn test_capacity_from() {
184        let mut g = new_flow_graph(3);
185        fg_add_edge(&mut g, 0, 1, 3.0);
186        fg_add_edge(&mut g, 0, 2, 4.0);
187        assert!((fg_total_capacity_from(&g, 0) - 7.0).abs() < 1e-5);
188    }
189
190    #[test]
191    fn test_src_equals_sink() {
192        let g = new_flow_graph(3);
193        /* not a meaningful query, but should not crash */
194        let _ = max_flow(&g, 1, 1);
195    }
196
197    #[test]
198    fn test_diamond_graph() {
199        /* classic 6-node flow */
200        let mut g = new_flow_graph(6);
201        fg_add_edge(&mut g, 0, 1, 10.0);
202        fg_add_edge(&mut g, 0, 2, 10.0);
203        fg_add_edge(&mut g, 1, 3, 10.0);
204        fg_add_edge(&mut g, 2, 4, 10.0);
205        fg_add_edge(&mut g, 3, 5, 10.0);
206        fg_add_edge(&mut g, 4, 5, 10.0);
207        fg_add_edge(&mut g, 1, 4, 5.0);
208        fg_add_edge(&mut g, 2, 3, 5.0);
209        assert!(max_flow(&g, 0, 5) >= 20.0 - 1e-3);
210    }
211}
oxihuman_core/max_flow_ff.rs

oxihuman_core/
max_flow_ff.rs
