eo_mcf/lib.rs
1//! Minimum-cost flow, solved and certified.
2//!
3//! `eo-mcf` solves the integral minimum-cost-flow problem with Goldberg's
4//! cost-scaling push-relabel algorithm, and ships an independent [`verify`]
5//! subsystem that proves a given flow feasible and optimal without reference
6//! to the solver.
7//!
8//! ```
9//! use eo_mcf::{Problem, solve, verify};
10//!
11//! # fn main() -> Result<(), Box<dyn std::error::Error>> {
12//! // Move 4 units from node 0 to node 3. The direct arc is dearer than the
13//! // two-hop route, but too narrow to carry everything.
14//! let problem = Problem::builder(4)
15//! .supply(0, 4)
16//! .supply(3, -4)
17//! .edge(0, 1, 3, 1) // tail, head, capacity, cost
18//! .edge(1, 3, 3, 1)
19//! .edge(0, 2, 4, 3)
20//! .edge(2, 3, 4, 3)
21//! .build()?;
22//!
23//! let solution = solve(&problem)?;
24//! assert_eq!(solution.objective(), 3 * 2 + 1 * 6);
25//!
26//! // The answer carries its own proof: feasible, and optimal by two
27//! // independent arguments.
28//! let certificate = verify::certify(&problem, solution.flows())?;
29//! assert_eq!(certificate.objective, solution.objective());
30//! # Ok(())
31//! # }
32//! ```
33//!
34//! # Certification
35//!
36//! Min-cost flow has a useful property: **the optimal flow is generally not
37//! unique, but the optimal cost always is**, and optimality is checkable in
38//! polynomial time — two correct solvers routinely return different flows at
39//! the same cost. [`verify`] answers three questions:
40//!
41//! * **Feasible?** Conservation, bounds, integrality.
42//! * **Optimal?** Node potentials π with `c(u,v) − π(u) + π(v) ≥ 0` on every
43//! residual arc — complementary slackness, a complete proof.
44//! * **Optimal?** No negative cycle in the residual graph, decided by the
45//! exact minimum cycle mean — a second proof sharing no code with the
46//! first.
47//!
48//! The verifiers take `(&Problem, &[Flow])` and nothing else, so the solver
49//! cannot hand over its own prices and certify its own bug.
50//!
51//! # Guarantees
52//!
53//! * **Exact.** Integer arithmetic throughout; no floating point anywhere,
54//! including in the rational cycle means. Overflow is a typed error
55//! ([`arith::Overflow`]), never a wrap and never a panic.
56//! * **Deterministic.** No randomness, no hash iteration, no threads. The same
57//! input yields the same flow. With [`SolverOptions::deterministic`] the arc
58//! order is canonicalised first, so instances differing only in declaration
59//! order also yield the same flow, not merely the same cost.
60//! * **Total.** `#![forbid(unsafe_code)]`, no panicking paths in product
61//! code, no unbounded recursion, and
62//! [`Problem::memory_estimate`] states the allocation up front. The DIMACS
63//! reader will not allocate on the strength of a header it has not yet read
64//! past — see [`dimacs::DEFAULT_READ_LIMIT`].
65//! * **Portable.** Pure Rust, no C dependencies, no `fork()`, no POSIX-only
66//! calls.
67//!
68//! # References
69//!
70//! Written from the published literature — Goldberg (1997), Goldberg & Tarjan
71//! (1990, 1988), and the DIMACS format specification; no solver source was
72//! consulted. `docs/ALGORITHM.md` holds the implementer's notes and
73//! `validation/citations.toml` the full bibliography.
74
75#![forbid(unsafe_code)]
76
77mod arith;
78mod error;
79mod maxflow;
80mod network;
81mod problem;
82mod solver;
83
84pub mod dimacs;
85pub mod oracle;
86pub mod verify;
87
88pub use arith::{Capacity, Cost, Flow, Objective, Overflow, Price};
89pub use error::{BuildError, DimacsError, SolveError, VerifyError};
90pub use problem::{Arc, MAX_ARCS, MAX_NODES, Problem, ProblemBuilder};
91pub use solver::{ActiveNodeOrder, Solution, SolveStats, SolverOptions, solve, solve_with};
92pub use verify::{Certificate, certify};
93
94/// Solve and certify in one step.
95///
96/// Equivalent to [`solve`] followed by [`verify::certify`]. Useful when the
97/// caller wants the proof unconditionally rather than behind the
98/// `certify-on-solve` feature; costs an extra `O(n·m)`.
99///
100/// # Errors
101///
102/// [`SolveOrVerifyError::Solve`] if no optimal flow could be produced,
103/// [`SolveOrVerifyError::Verify`] if the flow produced fails certification —
104/// which would be a defect in this crate, reported rather than hidden.
105pub fn solve_certified(problem: &Problem) -> Result<(Solution, Certificate), SolveOrVerifyError> {
106 let solution = solve(problem)?;
107 let certificate = verify::certify(problem, solution.flows())?;
108 Ok((solution, certificate))
109}
110
111/// Failure of [`solve_certified`].
112#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
113#[non_exhaustive]
114pub enum SolveOrVerifyError {
115 /// The solve did not produce a flow.
116 #[error(transparent)]
117 Solve(#[from] SolveError),
118 /// A flow was produced but did not certify.
119 #[error(transparent)]
120 Verify(#[from] VerifyError),
121}