eo-mcf 0.1.0

Exact minimum-cost-flow solver (cost-scaling push-relabel) with independent optimality certification.
Documentation
//! Structured errors.
//!
//! Every message names the offending quantity and, where a human can act, the
//! action. Errors are matchable so a caller can distinguish "this instance has
//! no feasible flow" (a legitimate answer about the input) from "this solver
//! ran out of integer range" (a limit of the implementation).

use crate::arith::{Capacity, Cost, Flow, Objective, Overflow};

/// Building a [`Problem`](crate::Problem) failed: the network description is
/// not a well-formed min-cost-flow instance.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
#[non_exhaustive]
pub enum BuildError {
    /// An arc endpoint is not a node of this network.
    #[error(
        "arc {arc} references node {node}, but the network has {node_count} nodes (ids 0..{node_count})"
    )]
    NodeOutOfRange {
        /// Index of the offending arc, in insertion order.
        arc: usize,
        /// The out-of-range endpoint.
        node: usize,
        /// Number of nodes declared for the network.
        node_count: usize,
    },

    /// An arc's lower bound exceeds its capacity, so it admits no flow at all.
    #[error("arc {arc} has lower bound {lower} above its capacity {upper}: no flow satisfies it")]
    InvalidBounds {
        /// Index of the offending arc, in insertion order.
        arc: usize,
        /// The declared lower bound.
        lower: Capacity,
        /// The declared capacity.
        upper: Capacity,
    },

    /// A supply was set on a node id the network does not have.
    ///
    /// Reported rather than accommodated: growing the node space to fit a
    /// mistyped id would produce a larger, different problem that solves
    /// perfectly well and answers a question nobody asked.
    #[error(
        "supply set on node {node}, but the network has {node_count} nodes (ids 0..{node_count})"
    )]
    SupplyNodeOutOfRange {
        /// The out-of-range node id.
        node: usize,
        /// Number of nodes declared for the network.
        node_count: usize,
    },

    /// Supplies do not sum to zero, so no flow can conserve them.
    ///
    /// This is a statement about the instance, not a solver limitation: the
    /// caller must balance supply against demand before solving.
    #[error("node supplies sum to {total}, not 0: total supply must equal total demand")]
    UnbalancedSupply {
        /// The non-zero total.
        total: Objective,
    },

    /// The network exceeds the crate's index width.
    ///
    /// Nodes and arcs are addressed with `u32` in the solver's CSR arrays;
    /// this is a deliberate memory trade, documented in [`crate::Problem`].
    #[error("network has {count} {what}, above the supported maximum of {max}")]
    TooLarge {
        /// What was counted — `"nodes"` or `"arcs"`.
        what: &'static str,
        /// The requested count.
        count: usize,
        /// The supported maximum.
        max: usize,
    },

    /// An intermediate quantity left integer range while validating.
    #[error(transparent)]
    Overflow(#[from] Overflow),
}

/// Solving failed.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
#[non_exhaustive]
pub enum SolveError {
    /// No flow satisfies the supplies and capacities simultaneously.
    ///
    /// A property of the instance, established *before* the scaling loop by an
    /// independent max-flow feasibility test, so an infeasible instance is
    /// always reported as infeasible and never as a bogus optimum.
    #[error("instance is infeasible: {routable} of {required} units of supply can reach a demand")]
    Infeasible {
        /// Units of supply that can be routed to demand.
        routable: Objective,
        /// Units of supply that must be routed for feasibility.
        required: Objective,
    },

    /// A working quantity left integer range.
    ///
    /// Cost scaling multiplies costs by `n + 1`; very large costs on very
    /// large networks can exceed [`Cost`]. Reduce the cost range or split the
    /// instance — the result is not approximated.
    #[error(transparent)]
    Overflow(#[from] Overflow),

    /// The caller's operation budget was exhausted before the solve finished.
    #[error(
        "operation budget of {budget} exhausted after {scaling_phases} scaling phases; raise SolverOptions::max_operations or lower the cost range"
    )]
    OperationBudgetExhausted {
        /// The budget that was set.
        budget: u64,
        /// Scaling phases completed before the budget ran out.
        scaling_phases: u32,
    },

    /// The solve produced a flow that failed its own certification.
    ///
    /// Only reachable with the `certify-on-solve` feature. It always indicates
    /// a defect in this crate, and it is surfaced rather than swallowed: a
    /// solver that cannot prove its own answer has no business returning it.
    #[error("solver produced a flow that failed certification: {0} (this is a bug in eo-mcf)")]
    SelfCertificationFailed(VerifyError),

    /// A solver invariant did not hold. This is a defect in this crate.
    ///
    /// Reported rather than panicked because the crate's no-panic rule
    /// applies to product code: the caller gets a bad-news value, not an
    /// aborted process.
    #[error("solver invariant violated: {what} (this is a bug in eo-mcf, please report it)")]
    InvariantViolated {
        /// Which invariant failed.
        what: &'static str,
    },
}

/// A certificate could not be issued: the candidate solution is not feasible,
/// not optimal, or not a solution to this problem at all.
///
/// Each variant is a *counterexample*, carrying the witness that refutes the
/// claim — the arc whose capacity is exceeded, the node whose conservation
/// fails, the residual arc whose reduced cost is negative.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
#[non_exhaustive]
pub enum VerifyError {
    /// The flow vector does not have one entry per arc.
    #[error("flow vector has {found} entries but the network has {expected} arcs")]
    LengthMismatch {
        /// Arcs in the network.
        expected: usize,
        /// Entries in the candidate flow vector.
        found: usize,
    },

    /// Feasibility: an arc's flow is outside `[lower, upper]`.
    #[error("arc {arc} carries {flow}, outside its bounds [{lower}, {upper}]")]
    CapacityViolated {
        /// Index of the offending arc.
        arc: usize,
        /// The flow proposed for it.
        flow: Flow,
        /// Its lower bound.
        lower: Capacity,
        /// Its capacity.
        upper: Capacity,
    },

    /// Feasibility: flow is not conserved at a node.
    #[error("node {node} has net outflow {net} but supply {supply}: flow is not conserved there")]
    ConservationViolated {
        /// The offending node.
        node: usize,
        /// Outflow minus inflow at the node.
        net: Objective,
        /// The node's declared supply.
        supply: Flow,
    },

    /// Dual certificate: a residual arc has negative reduced cost under the recomputed
    /// potentials, so the flow admits a cheaper rerouting and is not optimal.
    #[error(
        "residual arc {tail}→{head} has reduced cost {reduced_cost} < 0 under the recomputed potentials: the flow is not optimal"
    )]
    NegativeReducedCost {
        /// Tail of the offending residual arc.
        tail: usize,
        /// Head of the offending residual arc.
        head: usize,
        /// Its reduced cost `c(u,v) − π(u) + π(v)`.
        reduced_cost: Cost,
    },

    /// Dual certificate: no potential function exists, because the residual graph has a
    /// negative cycle. Detected while computing the potentials.
    #[error(
        "residual graph admits no potential function: a negative-cost cycle reaches node {node}"
    )]
    PotentialsDoNotExist {
        /// A node on or reachable from the offending cycle.
        node: usize,
    },

    /// Cycle check: the residual graph contains a cycle of negative mean cost, which
    /// can be cancelled for a strictly cheaper flow.
    #[error(
        "residual graph has a cycle of mean cost {numerator}/{denominator} < 0 through node {node}: the flow is not optimal"
    )]
    NegativeCycle {
        /// Numerator of the exact minimum cycle mean.
        numerator: i128,
        /// Denominator of the exact minimum cycle mean (always positive).
        denominator: i128,
        /// A node lying on the offending cycle.
        node: usize,
    },

    /// The two optimality proofs disagreed. Both are suspect until this is
    /// resolved — by construction they cannot both be right.
    ///
    /// The two certifiers share no code path precisely so that this can be
    /// observed rather than silently averaged away.
    #[error(
        "certifiers disagree: the dual certificate says {dual_verdict} but negative-cycle detection says {cycle_verdict} — one of them is defective"
    )]
    CertifiersDisagree {
        /// What the dual certificate concluded.
        dual_verdict: &'static str,
        /// What negative-cycle detection concluded.
        cycle_verdict: &'static str,
    },

    /// Cycle check: policy iteration exceeded its safety bound without converging.
    ///
    /// A certifier that can spin is not a certifier, so the search is bounded;
    /// reaching the bound is reported rather than silently treated as "no
    /// negative cycle found".
    #[error("minimum-cycle-mean search did not converge within {iterations} iterations")]
    CycleSearchDidNotConverge {
        /// The bound that was reached.
        iterations: u64,
    },

    /// An intermediate quantity left integer range while verifying.
    #[error(transparent)]
    Overflow(#[from] Overflow),
}

/// Reading a DIMACS min-cost-flow file failed.
///
/// Every variant carries the 1-based line number, because the first thing
/// anyone does with a rejected instance is open it at that line.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
#[non_exhaustive]
pub enum DimacsError {
    /// No `p min <nodes> <arcs>` line was found.
    #[error(
        "no problem line: a DIMACS min-cost-flow file must contain one `p min <nodes> <arcs>` line"
    )]
    MissingProblemLine,

    /// A second `p` line appeared.
    #[error("line {line}: second problem line; exactly one `p min <nodes> <arcs>` is allowed")]
    DuplicateProblemLine {
        /// 1-based line number.
        line: usize,
    },

    /// A descriptor line appeared before the problem line that sizes it.
    #[error("line {line}: `{tag}` descriptor appears before the problem line")]
    DescriptorBeforeProblem {
        /// 1-based line number.
        line: usize,
        /// The line's leading tag.
        tag: char,
    },

    /// The line's leading tag is not one of `c`, `p`, `n`, `a`.
    #[error("line {line}: unknown line type `{tag}`; expected one of c, p, n, a")]
    UnknownLineType {
        /// 1-based line number.
        line: usize,
        /// The unrecognised tag.
        tag: char,
    },

    /// A line has the wrong number of fields.
    #[error("line {line}: `{tag}` line needs {expected} fields, found {found}")]
    FieldCount {
        /// 1-based line number.
        line: usize,
        /// The line's leading tag.
        tag: char,
        /// Fields the line type requires (excluding the tag).
        expected: usize,
        /// Fields actually present (excluding the tag).
        found: usize,
    },

    /// A field that must be an integer is not one, or does not fit `i64`.
    #[error("line {line}: field {field} (`{text}`) is not an integer in i64 range")]
    BadInteger {
        /// 1-based line number.
        line: usize,
        /// 1-based field index within the line, excluding the tag.
        field: usize,
        /// The offending text.
        text: String,
    },

    /// The problem line declares a `min` problem type this reader does not handle.
    #[error("line {line}: problem type `{found}` is not supported; this reader handles `min` only")]
    UnsupportedProblemType {
        /// 1-based line number.
        line: usize,
        /// The declared problem type.
        found: String,
    },

    /// A node id is outside `1..=nodes` as declared on the problem line.
    #[error("line {line}: node id {node} is outside 1..={node_count} declared on the problem line")]
    NodeOutOfRange {
        /// 1-based line number.
        line: usize,
        /// The offending node id.
        node: i64,
        /// Node count from the problem line.
        node_count: usize,
    },

    /// A node's supply was declared twice.
    #[error("line {line}: supply for node {node} declared twice")]
    DuplicateSupply {
        /// 1-based line number.
        line: usize,
        /// The doubly-declared node.
        node: usize,
    },

    /// The file holds a different number of arcs than the problem line declares.
    #[error("problem line declares {declared} arcs but the file holds {found}")]
    ArcCountMismatch {
        /// Arc count from the problem line.
        declared: usize,
        /// Arc lines actually read.
        found: usize,
    },

    /// The problem line declares a network larger than the reader was allowed
    /// to allocate.
    ///
    /// Raised before anything proportional to the declared size is allocated:
    /// the header is a claim about the file, and acting on it unweighed is how
    /// a few bytes of input ask for gigabytes of memory.
    #[error(
        "line {line}: {node_count} declared nodes need at least {required} bytes, above the reader's limit of {limit}; pass a larger limit to `dimacs::read_within` if the instance really is this large"
    )]
    DeclaredSizeExceedsLimit {
        /// 1-based line number.
        line: usize,
        /// Node count from the problem line.
        node_count: usize,
        /// Bytes the reader would have to allocate to accept it. A *lower*
        /// bound: the product saturates at [`u64::MAX`], so a declared count
        /// absurd enough to overflow reports the saturated value rather than
        /// the true one. It is still enough to justify the refusal.
        required: u64,
        /// Bytes the reader was allowed to spend.
        limit: u64,
    },

    /// A declared size is negative or does not fit `usize`.
    #[error("line {line}: declared {what} of {value} is not a valid count")]
    BadCount {
        /// 1-based line number.
        line: usize,
        /// Which count — `"node count"` or `"arc count"`.
        what: &'static str,
        /// The offending value.
        value: i64,
    },

    /// The parsed network is not a well-formed instance.
    #[error(transparent)]
    Build(#[from] BuildError),
}