eo-mcf 0.1.0

Exact minimum-cost-flow solver (cost-scaling push-relabel) with independent optimality certification.
Documentation
//! Dinic max-flow, used as the feasibility oracle and, through
//! [`crate::oracle`], as the reference for the "zero costs ⇒ max flow"
//! property.
//!
//! Feasibility is settled *before* the scaling loop rather than inferred from
//! it. Cost scaling works on a pseudoflow and terminates when no excess
//! remains; on an infeasible instance that condition is simply never reached,
//! and a solver that discovers this by running out of patience cannot tell
//! "infeasible" from "slow". A max-flow test answers the question exactly, in
//! its own code, and lets [`SolveError::Infeasible`](crate::SolveError) carry
//! how much supply was actually routable.
//!
//! The depth-first search is iterative. A recursive blocking-flow search
//! recurses to path length, which on a long thin network is deep enough to
//! exhaust the stack — an abort no `Result` can catch, and abort is not an
//! error-reporting strategy this crate allows itself.

use crate::arith::Capacity;

/// A flow network built for one max-flow computation.
pub(crate) struct FlowNetwork {
    node_count: usize,
    first_out: Vec<u32>,
    head: Vec<u32>,
    rev: Vec<u32>,
    cap: Vec<Capacity>,
}

impl FlowNetwork {
    /// Build from `(tail, head, capacity)` triples. Every edge gets a reverse
    /// entry of capacity zero.
    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,
        }
    }

    /// Maximum flow from `source` to `sink`.
    ///
    /// Accumulated in `i128`: the value can exceed [`Capacity`] when many
    /// high-capacity arcs leave the source, and a saturated total is not a
    /// feasibility answer.
    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
    }

    /// Breadth-first layering of the residual graph. Returns whether `sink`
    /// was reached.
    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
    }

    /// Saturate every shortest augmenting path in the current level graph,
    /// depth-first, without recursion.
    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);
                // Retreat to just before the first arc this augmentation
                // saturated; everything upstream of it is still usable.
                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;
            }

            // No usable arc leaves `u` in the level graph: back out.
            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() {
        // s=0, t=3. Two disjoint paths of capacity 2 and 3, plus a cross arc.
        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() {
        // 200k nodes in a line: a recursive blocking-flow search would need a
        // 200k-deep stack here.
        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);
    }
}