eo-mcf 0.1.0

Exact minimum-cost-flow solver (cost-scaling push-relabel) with independent optimality certification.
Documentation
//! Checked integer arithmetic.
//!
//! Cost scaling multiplies every arc cost by `n + 1` and then carries node
//! prices that grow with ε, so the working numbers are much larger than the
//! numbers the caller supplied. A silent wraparound here would not crash —
//! it would return a *plausible but wrong* optimum, and the certifiers
//! would happily certify the wrong problem. Every widening operation on the
//! solver's hot path is therefore checked, and overflow is a typed error
//! ([`Overflow`]) that travels out to the caller. Nothing here panics.

/// An intermediate quantity did not fit its integer type.
///
/// The `what` field names the quantity, so the message points at the step
/// that overflowed rather than at a generic arithmetic failure.
#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
#[error("integer overflow computing {what}")]
#[non_exhaustive]
pub struct Overflow {
    /// The quantity being computed when the range was exceeded.
    pub what: &'static str,
}

impl Overflow {
    /// Construct an overflow report for `what`.
    #[must_use]
    pub const fn new(what: &'static str) -> Self {
        Self { what }
    }
}

/// Arc cost, as supplied by the caller and as scaled internally.
pub type Cost = i64;
/// Arc capacity and residual capacity.
pub type Capacity = i64;
/// Flow on an arc, and node excess.
pub type Flow = i64;
/// Node price (solver) or potential (dual certificate).
pub type Price = i64;
/// Total cost of a flow. Widened: `Σ cost × flow` outgrows [`Cost`] routinely.
pub type Objective = i128;

#[inline]
pub(crate) fn add(a: i64, b: i64, what: &'static str) -> Result<i64, Overflow> {
    a.checked_add(b).ok_or(Overflow::new(what))
}

#[inline]
pub(crate) fn sub(a: i64, b: i64, what: &'static str) -> Result<i64, Overflow> {
    a.checked_sub(b).ok_or(Overflow::new(what))
}

#[inline]
pub(crate) fn mul(a: i64, b: i64, what: &'static str) -> Result<i64, Overflow> {
    a.checked_mul(b).ok_or(Overflow::new(what))
}

#[inline]
pub(crate) fn neg(a: i64, what: &'static str) -> Result<i64, Overflow> {
    a.checked_neg().ok_or(Overflow::new(what))
}

#[inline]
pub(crate) fn add_i128(a: i128, b: i128, what: &'static str) -> Result<i128, Overflow> {
    a.checked_add(b).ok_or(Overflow::new(what))
}

#[inline]
pub(crate) fn mul_i128(a: i128, b: i128, what: &'static str) -> Result<i128, Overflow> {
    a.checked_mul(b).ok_or(Overflow::new(what))
}

/// Reduced cost `c_π(u,v) = c(u,v) − π(u) + π(v)`, checked.
///
/// This is the sign convention used throughout the crate, for both the
/// solver's prices and the dual certificate's potentials: a residual arc is
/// *admissible* when its reduced cost is negative, and a flow is optimal
/// exactly when no residual arc has negative reduced cost.
#[inline]
pub(crate) fn reduced_cost(
    cost: Cost,
    price_tail: Price,
    price_head: Price,
) -> Result<Cost, Overflow> {
    let t = sub(cost, price_tail, "reduced cost")?;
    add(t, price_head, "reduced cost")
}

/// Greatest common divisor of two non-negative values (Euclid).
///
/// Used to normalise the exact rational cycle means in the cycle certifier so
/// that equal means compare equal as `(numerator, denominator)` pairs.
#[inline]
pub(crate) const fn gcd(mut a: u128, mut b: u128) -> u128 {
    while b != 0 {
        let t = a % b;
        a = b;
        b = t;
    }
    a
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn checked_ops_report_the_quantity_that_overflowed() {
        assert_eq!(add(i64::MAX, 1, "q"), Err(Overflow::new("q")));
        assert_eq!(sub(i64::MIN, 1, "q"), Err(Overflow::new("q")));
        assert_eq!(mul(i64::MAX, 2, "q"), Err(Overflow::new("q")));
        assert_eq!(neg(i64::MIN, "q"), Err(Overflow::new("q")));
    }

    #[test]
    fn checked_ops_pass_values_through_at_the_type_bounds() {
        assert_eq!(add(i64::MAX - 1, 1, "q"), Ok(i64::MAX));
        assert_eq!(sub(i64::MIN + 1, 1, "q"), Ok(i64::MIN));
        assert_eq!(mul(i64::MIN / 2, 2, "q"), Ok(i64::MIN));
        assert_eq!(neg(i64::MIN + 1, "q"), Ok(i64::MAX));
    }

    #[test]
    fn reduced_cost_follows_the_declared_convention() {
        // c_π(u,v) = c − π(u) + π(v)
        assert_eq!(reduced_cost(10, 3, 1), Ok(8));
        assert_eq!(reduced_cost(10, 1, 3), Ok(12));
        assert_eq!(reduced_cost(0, 5, 5), Ok(0));
        assert_eq!(
            reduced_cost(1, i64::MIN, 0),
            Err(Overflow::new("reduced cost"))
        );
    }

    #[test]
    fn gcd_normalises_rationals() {
        assert_eq!(gcd(12, 18), 6);
        assert_eq!(gcd(7, 13), 1);
        assert_eq!(gcd(0, 5), 5);
        assert_eq!(gcd(5, 0), 5);
    }
}