eo-mcf 0.1.0

Exact minimum-cost-flow solver (cost-scaling push-relabel) with independent optimality certification.
Documentation
//! Minimum-cost flow, solved and certified.
//!
//! `eo-mcf` solves the integral minimum-cost-flow problem with Goldberg's
//! cost-scaling push-relabel algorithm, and ships an independent [`verify`]
//! subsystem that proves a given flow feasible and optimal without reference
//! to the solver.
//!
//! ```
//! use eo_mcf::{Problem, solve, verify};
//!
//! # fn main() -> Result<(), Box<dyn std::error::Error>> {
//! // Move 4 units from node 0 to node 3. The direct arc is dearer than the
//! // two-hop route, but too narrow to carry everything.
//! let problem = Problem::builder(4)
//!     .supply(0, 4)
//!     .supply(3, -4)
//!     .edge(0, 1, 3, 1)   // tail, head, capacity, cost
//!     .edge(1, 3, 3, 1)
//!     .edge(0, 2, 4, 3)
//!     .edge(2, 3, 4, 3)
//!     .build()?;
//!
//! let solution = solve(&problem)?;
//! assert_eq!(solution.objective(), 3 * 2 + 1 * 6);
//!
//! // The answer carries its own proof: feasible, and optimal by two
//! // independent arguments.
//! let certificate = verify::certify(&problem, solution.flows())?;
//! assert_eq!(certificate.objective, solution.objective());
//! # Ok(())
//! # }
//! ```
//!
//! # Certification
//!
//! Min-cost flow has a useful property: **the optimal flow is generally not
//! unique, but the optimal cost always is**, and optimality is checkable in
//! polynomial time — two correct solvers routinely return different flows at
//! the same cost. [`verify`] answers three questions:
//!
//! * **Feasible?** Conservation, bounds, integrality.
//! * **Optimal?** Node potentials π with `c(u,v) − π(u) + π(v) ≥ 0` on every
//!   residual arc — complementary slackness, a complete proof.
//! * **Optimal?** No negative cycle in the residual graph, decided by the
//!   exact minimum cycle mean — a second proof sharing no code with the
//!   first.
//!
//! The verifiers take `(&Problem, &[Flow])` and nothing else, so the solver
//! cannot hand over its own prices and certify its own bug.
//!
//! # Guarantees
//!
//! * **Exact.** Integer arithmetic throughout; no floating point anywhere,
//!   including in the rational cycle means. Overflow is a typed error
//!   ([`arith::Overflow`]), never a wrap and never a panic.
//! * **Deterministic.** No randomness, no hash iteration, no threads. The same
//!   input yields the same flow. With [`SolverOptions::deterministic`] the arc
//!   order is canonicalised first, so instances differing only in declaration
//!   order also yield the same flow, not merely the same cost.
//! * **Total.** `#![forbid(unsafe_code)]`, no panicking paths in product
//!   code, no unbounded recursion, and
//!   [`Problem::memory_estimate`] states the allocation up front. The DIMACS
//!   reader will not allocate on the strength of a header it has not yet read
//!   past — see [`dimacs::DEFAULT_READ_LIMIT`].
//! * **Portable.** Pure Rust, no C dependencies, no `fork()`, no POSIX-only
//!   calls.
//!
//! # References
//!
//! Written from the published literature — Goldberg (1997), Goldberg & Tarjan
//! (1990, 1988), and the DIMACS format specification; no solver source was
//! consulted. `docs/ALGORITHM.md` holds the implementer's notes and
//! `validation/citations.toml` the full bibliography.

#![forbid(unsafe_code)]

mod arith;
mod error;
mod maxflow;
mod network;
mod problem;
mod solver;

pub mod dimacs;
pub mod oracle;
pub mod verify;

pub use arith::{Capacity, Cost, Flow, Objective, Overflow, Price};
pub use error::{BuildError, DimacsError, SolveError, VerifyError};
pub use problem::{Arc, MAX_ARCS, MAX_NODES, Problem, ProblemBuilder};
pub use solver::{ActiveNodeOrder, Solution, SolveStats, SolverOptions, solve, solve_with};
pub use verify::{Certificate, certify};

/// Solve and certify in one step.
///
/// Equivalent to [`solve`] followed by [`verify::certify`]. Useful when the
/// caller wants the proof unconditionally rather than behind the
/// `certify-on-solve` feature; costs an extra `O(n·m)`.
///
/// # Errors
///
/// [`SolveOrVerifyError::Solve`] if no optimal flow could be produced,
/// [`SolveOrVerifyError::Verify`] if the flow produced fails certification —
/// which would be a defect in this crate, reported rather than hidden.
pub fn solve_certified(problem: &Problem) -> Result<(Solution, Certificate), SolveOrVerifyError> {
    let solution = solve(problem)?;
    let certificate = verify::certify(problem, solution.flows())?;
    Ok((solution, certificate))
}

/// Failure of [`solve_certified`].
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
#[non_exhaustive]
pub enum SolveOrVerifyError {
    /// The solve did not produce a flow.
    #[error(transparent)]
    Solve(#[from] SolveError),
    /// A flow was produced but did not certify.
    #[error(transparent)]
    Verify(#[from] VerifyError),
}