oxicuda_graphalg/max_flow/
push_relabel.rs

1//! Generic Push-Relabel max flow with FIFO selection of active vertices.
2
3use std::collections::VecDeque;
4
5use crate::error::{GraphalgError, GraphalgResult};
6use crate::max_flow::edmonds_karp::FlowNetwork;
7
8pub fn push_relabel_max_flow(net: &FlowNetwork, source: usize, sink: usize) -> GraphalgResult<f64> {
9    if source >= net.n || sink >= net.n {
10        return Err(GraphalgError::SourceOutOfRange {
11            node: source.max(sink),
12            n: net.n,
13        });
14    }
15    let n = net.n;
16    let mut residual = net.clone();
17    let mut excess = vec![0.0f64; n];
18    let mut height = vec![0usize; n];
19    height[source] = n;
20    let mut in_queue = vec![false; n];
21    let mut queue: VecDeque<usize> = VecDeque::new();
22    // Initial pre-flow saturate source edges
23    for v in 0..n {
24        let c = residual.c(source, v);
25        if c > 1e-12 {
26            excess[v] += c;
27            excess[source] -= c;
28            *residual.c_mut(source, v) -= c;
29            *residual.c_mut(v, source) += c;
30            if v != sink && v != source && !in_queue[v] {
31                queue.push_back(v);
32                in_queue[v] = true;
33            }
34        }
35    }
36    while let Some(u) = queue.pop_front() {
37        in_queue[u] = false;
38        while excess[u] > 1e-12 {
39            // Try to push to a neighbor with height[u] = height[v] + 1
40            let mut pushed = false;
41            for v in 0..n {
42                if residual.c(u, v) > 1e-12 && height[u] == height[v] + 1 {
43                    let amount = excess[u].min(residual.c(u, v));
44                    *residual.c_mut(u, v) -= amount;
45                    *residual.c_mut(v, u) += amount;
46                    excess[u] -= amount;
47                    excess[v] += amount;
48                    if v != source && v != sink && !in_queue[v] {
49                        queue.push_back(v);
50                        in_queue[v] = true;
51                    }
52                    pushed = true;
53                    if excess[u] <= 1e-12 {
54                        break;
55                    }
56                }
57            }
58            if !pushed {
59                // Relabel
60                let mut min_height = usize::MAX;
61                for v in 0..n {
62                    if residual.c(u, v) > 1e-12 && height[v] < min_height {
63                        min_height = height[v];
64                    }
65                }
66                if min_height == usize::MAX {
67                    break;
68                }
69                height[u] = min_height + 1;
70            }
71        }
72    }
73    Ok(excess[sink])
74}
75
76#[cfg(test)]
77mod tests {
78    use super::*;
79
80    #[test]
81    fn pr_simple() {
82        let mut net = FlowNetwork::new(4);
83        net.add_edge(0, 1, 3.0).expect("ok");
84        net.add_edge(0, 2, 2.0).expect("ok");
85        net.add_edge(1, 3, 3.0).expect("ok");
86        net.add_edge(2, 3, 2.0).expect("ok");
87        let f = push_relabel_max_flow(&net, 0, 3).expect("ok");
88        assert!((f - 5.0).abs() < 1e-6);
89    }
90}
oxicuda_graphalg/max_flow/push_relabel.rs

oxicuda_graphalg/max_flow/
push_relabel.rs
