use crate::arith::Capacity;
pub(crate) struct FlowNetwork {
node_count: usize,
first_out: Vec<u32>,
head: Vec<u32>,
rev: Vec<u32>,
cap: Vec<Capacity>,
}
impl FlowNetwork {
pub(crate) fn new(node_count: usize, edges: &[(u32, u32, Capacity)]) -> Self {
let mut first_out = vec![0u32; node_count + 1];
for &(u, v, _) in edges {
first_out[u as usize + 1] += 1;
first_out[v as usize + 1] += 1;
}
for i in 0..node_count {
first_out[i + 1] += first_out[i];
}
let entries = edges.len() * 2;
let mut head = vec![0u32; entries];
let mut rev = vec![0u32; entries];
let mut cap = vec![0 as Capacity; entries];
let mut cursor: Vec<u32> = first_out[..node_count].to_vec();
for &(u, v, c) in edges {
let forward = cursor[u as usize];
cursor[u as usize] += 1;
let backward = cursor[v as usize];
cursor[v as usize] += 1;
head[forward as usize] = v;
cap[forward as usize] = c;
rev[forward as usize] = backward;
head[backward as usize] = u;
cap[backward as usize] = 0;
rev[backward as usize] = forward;
}
Self {
node_count,
first_out,
head,
rev,
cap,
}
}
pub(crate) fn max_flow(&mut self, source: usize, sink: usize) -> i128 {
if source == sink || source >= self.node_count || sink >= self.node_count {
return 0;
}
let mut total: i128 = 0;
let mut level = vec![-1i32; self.node_count];
let mut iter = vec![0u32; self.node_count];
while self.build_levels(source, sink, &mut level) {
iter.copy_from_slice(&self.first_out[..self.node_count]);
total += self.blocking_flow(source, sink, &level, &mut iter);
}
total
}
fn build_levels(&self, source: usize, sink: usize, level: &mut [i32]) -> bool {
level.fill(-1);
level[source] = 0;
let mut queue = std::collections::VecDeque::with_capacity(self.node_count);
queue.push_back(source);
while let Some(u) = queue.pop_front() {
for a in self.first_out[u] as usize..self.first_out[u + 1] as usize {
let v = self.head[a] as usize;
if self.cap[a] > 0 && level[v] < 0 {
level[v] = level[u] + 1;
queue.push_back(v);
}
}
}
level[sink] >= 0
}
fn blocking_flow(
&mut self,
source: usize,
sink: usize,
level: &[i32],
iter: &mut [u32],
) -> i128 {
let mut total: i128 = 0;
let mut path: Vec<usize> = Vec::new();
let mut u = source;
loop {
if u == sink {
let Some(&bottleneck) = path.iter().map(|a| &self.cap[*a]).min() else {
break;
};
for &a in &path {
let r = self.rev[a] as usize;
self.cap[a] -= bottleneck;
self.cap[r] += bottleneck;
}
total += i128::from(bottleneck);
let cut = path.iter().position(|&a| self.cap[a] == 0).unwrap_or(0);
let resume = if cut == 0 {
source
} else {
self.head[path[cut - 1]] as usize
};
path.truncate(cut);
u = resume;
continue;
}
let mut advanced = false;
while iter[u] < self.first_out[u + 1] {
let a = iter[u] as usize;
let v = self.head[a] as usize;
if self.cap[a] > 0 && level[v] == level[u] + 1 {
path.push(a);
u = v;
advanced = true;
break;
}
iter[u] += 1;
}
if advanced {
continue;
}
if u == source {
break;
}
let Some(a) = path.pop() else { break };
let tail = self.head[self.rev[a] as usize] as usize;
iter[tail] += 1;
u = tail;
}
total
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn classic_four_node_network() {
let mut net = FlowNetwork::new(4, &[(0, 1, 3), (0, 2, 2), (1, 3, 2), (2, 3, 3), (1, 2, 5)]);
assert_eq!(net.max_flow(0, 3), 5);
}
#[test]
fn bottleneck_limits_the_value() {
let mut net = FlowNetwork::new(4, &[(0, 1, 100), (1, 2, 1), (2, 3, 100)]);
assert_eq!(net.max_flow(0, 3), 1);
}
#[test]
fn disconnected_sink_carries_no_flow() {
let mut net = FlowNetwork::new(4, &[(0, 1, 5)]);
assert_eq!(net.max_flow(0, 3), 0);
}
#[test]
fn long_chain_does_not_recurse_to_death() {
let n = 200_000;
let edges: Vec<(u32, u32, Capacity)> = (0..n as u32 - 1).map(|i| (i, i + 1, 7)).collect();
let mut net = FlowNetwork::new(n, &edges);
assert_eq!(net.max_flow(0, n - 1), 7);
}
#[test]
fn parallel_arcs_accumulate() {
let mut net = FlowNetwork::new(2, &[(0, 1, 3), (0, 1, 4), (0, 1, 5)]);
assert_eq!(net.max_flow(0, 1), 12);
}
#[test]
fn source_equal_to_sink_is_zero() {
let mut net = FlowNetwork::new(2, &[(0, 1, 3)]);
assert_eq!(net.max_flow(1, 1), 0);
}
}