Skip to main content

eo_mcf/
error.rs

1//! Structured errors.
2//!
3//! Every message names the offending quantity and, where a human can act, the
4//! action. Errors are matchable so a caller can distinguish "this instance has
5//! no feasible flow" (a legitimate answer about the input) from "this solver
6//! ran out of integer range" (a limit of the implementation).
7
8use crate::arith::{Capacity, Cost, Flow, Objective, Overflow};
9
10/// Building a [`Problem`](crate::Problem) failed: the network description is
11/// not a well-formed min-cost-flow instance.
12#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
13#[non_exhaustive]
14pub enum BuildError {
15    /// An arc endpoint is not a node of this network.
16    #[error(
17        "arc {arc} references node {node}, but the network has {node_count} nodes (ids 0..{node_count})"
18    )]
19    NodeOutOfRange {
20        /// Index of the offending arc, in insertion order.
21        arc: usize,
22        /// The out-of-range endpoint.
23        node: usize,
24        /// Number of nodes declared for the network.
25        node_count: usize,
26    },
27
28    /// An arc's lower bound exceeds its capacity, so it admits no flow at all.
29    #[error("arc {arc} has lower bound {lower} above its capacity {upper}: no flow satisfies it")]
30    InvalidBounds {
31        /// Index of the offending arc, in insertion order.
32        arc: usize,
33        /// The declared lower bound.
34        lower: Capacity,
35        /// The declared capacity.
36        upper: Capacity,
37    },
38
39    /// A supply was set on a node id the network does not have.
40    ///
41    /// Reported rather than accommodated: growing the node space to fit a
42    /// mistyped id would produce a larger, different problem that solves
43    /// perfectly well and answers a question nobody asked.
44    #[error(
45        "supply set on node {node}, but the network has {node_count} nodes (ids 0..{node_count})"
46    )]
47    SupplyNodeOutOfRange {
48        /// The out-of-range node id.
49        node: usize,
50        /// Number of nodes declared for the network.
51        node_count: usize,
52    },
53
54    /// Supplies do not sum to zero, so no flow can conserve them.
55    ///
56    /// This is a statement about the instance, not a solver limitation: the
57    /// caller must balance supply against demand before solving.
58    #[error("node supplies sum to {total}, not 0: total supply must equal total demand")]
59    UnbalancedSupply {
60        /// The non-zero total.
61        total: Objective,
62    },
63
64    /// The network exceeds the crate's index width.
65    ///
66    /// Nodes and arcs are addressed with `u32` in the solver's CSR arrays;
67    /// this is a deliberate memory trade, documented in [`crate::Problem`].
68    #[error("network has {count} {what}, above the supported maximum of {max}")]
69    TooLarge {
70        /// What was counted — `"nodes"` or `"arcs"`.
71        what: &'static str,
72        /// The requested count.
73        count: usize,
74        /// The supported maximum.
75        max: usize,
76    },
77
78    /// An intermediate quantity left integer range while validating.
79    #[error(transparent)]
80    Overflow(#[from] Overflow),
81}
82
83/// Solving failed.
84#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
85#[non_exhaustive]
86pub enum SolveError {
87    /// No flow satisfies the supplies and capacities simultaneously.
88    ///
89    /// A property of the instance, established *before* the scaling loop by an
90    /// independent max-flow feasibility test, so an infeasible instance is
91    /// always reported as infeasible and never as a bogus optimum.
92    #[error("instance is infeasible: {routable} of {required} units of supply can reach a demand")]
93    Infeasible {
94        /// Units of supply that can be routed to demand.
95        routable: Objective,
96        /// Units of supply that must be routed for feasibility.
97        required: Objective,
98    },
99
100    /// A working quantity left integer range.
101    ///
102    /// Cost scaling multiplies costs by `n + 1`; very large costs on very
103    /// large networks can exceed [`Cost`]. Reduce the cost range or split the
104    /// instance — the result is not approximated.
105    #[error(transparent)]
106    Overflow(#[from] Overflow),
107
108    /// The caller's operation budget was exhausted before the solve finished.
109    #[error(
110        "operation budget of {budget} exhausted after {scaling_phases} scaling phases; raise SolverOptions::max_operations or lower the cost range"
111    )]
112    OperationBudgetExhausted {
113        /// The budget that was set.
114        budget: u64,
115        /// Scaling phases completed before the budget ran out.
116        scaling_phases: u32,
117    },
118
119    /// The solve produced a flow that failed its own certification.
120    ///
121    /// Only reachable with the `certify-on-solve` feature. It always indicates
122    /// a defect in this crate, and it is surfaced rather than swallowed: a
123    /// solver that cannot prove its own answer has no business returning it.
124    #[error("solver produced a flow that failed certification: {0} (this is a bug in eo-mcf)")]
125    SelfCertificationFailed(VerifyError),
126
127    /// A solver invariant did not hold. This is a defect in this crate.
128    ///
129    /// Reported rather than panicked because the crate's no-panic rule
130    /// applies to product code: the caller gets a bad-news value, not an
131    /// aborted process.
132    #[error("solver invariant violated: {what} (this is a bug in eo-mcf, please report it)")]
133    InvariantViolated {
134        /// Which invariant failed.
135        what: &'static str,
136    },
137}
138
139/// A certificate could not be issued: the candidate solution is not feasible,
140/// not optimal, or not a solution to this problem at all.
141///
142/// Each variant is a *counterexample*, carrying the witness that refutes the
143/// claim — the arc whose capacity is exceeded, the node whose conservation
144/// fails, the residual arc whose reduced cost is negative.
145#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
146#[non_exhaustive]
147pub enum VerifyError {
148    /// The flow vector does not have one entry per arc.
149    #[error("flow vector has {found} entries but the network has {expected} arcs")]
150    LengthMismatch {
151        /// Arcs in the network.
152        expected: usize,
153        /// Entries in the candidate flow vector.
154        found: usize,
155    },
156
157    /// Feasibility: an arc's flow is outside `[lower, upper]`.
158    #[error("arc {arc} carries {flow}, outside its bounds [{lower}, {upper}]")]
159    CapacityViolated {
160        /// Index of the offending arc.
161        arc: usize,
162        /// The flow proposed for it.
163        flow: Flow,
164        /// Its lower bound.
165        lower: Capacity,
166        /// Its capacity.
167        upper: Capacity,
168    },
169
170    /// Feasibility: flow is not conserved at a node.
171    #[error("node {node} has net outflow {net} but supply {supply}: flow is not conserved there")]
172    ConservationViolated {
173        /// The offending node.
174        node: usize,
175        /// Outflow minus inflow at the node.
176        net: Objective,
177        /// The node's declared supply.
178        supply: Flow,
179    },
180
181    /// Dual certificate: a residual arc has negative reduced cost under the recomputed
182    /// potentials, so the flow admits a cheaper rerouting and is not optimal.
183    #[error(
184        "residual arc {tail}→{head} has reduced cost {reduced_cost} < 0 under the recomputed potentials: the flow is not optimal"
185    )]
186    NegativeReducedCost {
187        /// Tail of the offending residual arc.
188        tail: usize,
189        /// Head of the offending residual arc.
190        head: usize,
191        /// Its reduced cost `c(u,v) − π(u) + π(v)`.
192        reduced_cost: Cost,
193    },
194
195    /// Dual certificate: no potential function exists, because the residual graph has a
196    /// negative cycle. Detected while computing the potentials.
197    #[error(
198        "residual graph admits no potential function: a negative-cost cycle reaches node {node}"
199    )]
200    PotentialsDoNotExist {
201        /// A node on or reachable from the offending cycle.
202        node: usize,
203    },
204
205    /// Cycle check: the residual graph contains a cycle of negative mean cost, which
206    /// can be cancelled for a strictly cheaper flow.
207    #[error(
208        "residual graph has a cycle of mean cost {numerator}/{denominator} < 0 through node {node}: the flow is not optimal"
209    )]
210    NegativeCycle {
211        /// Numerator of the exact minimum cycle mean.
212        numerator: i128,
213        /// Denominator of the exact minimum cycle mean (always positive).
214        denominator: i128,
215        /// A node lying on the offending cycle.
216        node: usize,
217    },
218
219    /// The two optimality proofs disagreed. Both are suspect until this is
220    /// resolved — by construction they cannot both be right.
221    ///
222    /// The two certifiers share no code path precisely so that this can be
223    /// observed rather than silently averaged away.
224    #[error(
225        "certifiers disagree: the dual certificate says {dual_verdict} but negative-cycle detection says {cycle_verdict} — one of them is defective"
226    )]
227    CertifiersDisagree {
228        /// What the dual certificate concluded.
229        dual_verdict: &'static str,
230        /// What negative-cycle detection concluded.
231        cycle_verdict: &'static str,
232    },
233
234    /// Cycle check: policy iteration exceeded its safety bound without converging.
235    ///
236    /// A certifier that can spin is not a certifier, so the search is bounded;
237    /// reaching the bound is reported rather than silently treated as "no
238    /// negative cycle found".
239    #[error("minimum-cycle-mean search did not converge within {iterations} iterations")]
240    CycleSearchDidNotConverge {
241        /// The bound that was reached.
242        iterations: u64,
243    },
244
245    /// An intermediate quantity left integer range while verifying.
246    #[error(transparent)]
247    Overflow(#[from] Overflow),
248}
249
250/// Reading a DIMACS min-cost-flow file failed.
251///
252/// Every variant carries the 1-based line number, because the first thing
253/// anyone does with a rejected instance is open it at that line.
254#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
255#[non_exhaustive]
256pub enum DimacsError {
257    /// No `p min <nodes> <arcs>` line was found.
258    #[error(
259        "no problem line: a DIMACS min-cost-flow file must contain one `p min <nodes> <arcs>` line"
260    )]
261    MissingProblemLine,
262
263    /// A second `p` line appeared.
264    #[error("line {line}: second problem line; exactly one `p min <nodes> <arcs>` is allowed")]
265    DuplicateProblemLine {
266        /// 1-based line number.
267        line: usize,
268    },
269
270    /// A descriptor line appeared before the problem line that sizes it.
271    #[error("line {line}: `{tag}` descriptor appears before the problem line")]
272    DescriptorBeforeProblem {
273        /// 1-based line number.
274        line: usize,
275        /// The line's leading tag.
276        tag: char,
277    },
278
279    /// The line's leading tag is not one of `c`, `p`, `n`, `a`.
280    #[error("line {line}: unknown line type `{tag}`; expected one of c, p, n, a")]
281    UnknownLineType {
282        /// 1-based line number.
283        line: usize,
284        /// The unrecognised tag.
285        tag: char,
286    },
287
288    /// A line has the wrong number of fields.
289    #[error("line {line}: `{tag}` line needs {expected} fields, found {found}")]
290    FieldCount {
291        /// 1-based line number.
292        line: usize,
293        /// The line's leading tag.
294        tag: char,
295        /// Fields the line type requires (excluding the tag).
296        expected: usize,
297        /// Fields actually present (excluding the tag).
298        found: usize,
299    },
300
301    /// A field that must be an integer is not one, or does not fit `i64`.
302    #[error("line {line}: field {field} (`{text}`) is not an integer in i64 range")]
303    BadInteger {
304        /// 1-based line number.
305        line: usize,
306        /// 1-based field index within the line, excluding the tag.
307        field: usize,
308        /// The offending text.
309        text: String,
310    },
311
312    /// The problem line declares a `min` problem type this reader does not handle.
313    #[error("line {line}: problem type `{found}` is not supported; this reader handles `min` only")]
314    UnsupportedProblemType {
315        /// 1-based line number.
316        line: usize,
317        /// The declared problem type.
318        found: String,
319    },
320
321    /// A node id is outside `1..=nodes` as declared on the problem line.
322    #[error("line {line}: node id {node} is outside 1..={node_count} declared on the problem line")]
323    NodeOutOfRange {
324        /// 1-based line number.
325        line: usize,
326        /// The offending node id.
327        node: i64,
328        /// Node count from the problem line.
329        node_count: usize,
330    },
331
332    /// A node's supply was declared twice.
333    #[error("line {line}: supply for node {node} declared twice")]
334    DuplicateSupply {
335        /// 1-based line number.
336        line: usize,
337        /// The doubly-declared node.
338        node: usize,
339    },
340
341    /// The file holds a different number of arcs than the problem line declares.
342    #[error("problem line declares {declared} arcs but the file holds {found}")]
343    ArcCountMismatch {
344        /// Arc count from the problem line.
345        declared: usize,
346        /// Arc lines actually read.
347        found: usize,
348    },
349
350    /// The problem line declares a network larger than the reader was allowed
351    /// to allocate.
352    ///
353    /// Raised before anything proportional to the declared size is allocated:
354    /// the header is a claim about the file, and acting on it unweighed is how
355    /// a few bytes of input ask for gigabytes of memory.
356    #[error(
357        "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"
358    )]
359    DeclaredSizeExceedsLimit {
360        /// 1-based line number.
361        line: usize,
362        /// Node count from the problem line.
363        node_count: usize,
364        /// Bytes the reader would have to allocate to accept it. A *lower*
365        /// bound: the product saturates at [`u64::MAX`], so a declared count
366        /// absurd enough to overflow reports the saturated value rather than
367        /// the true one. It is still enough to justify the refusal.
368        required: u64,
369        /// Bytes the reader was allowed to spend.
370        limit: u64,
371    },
372
373    /// A declared size is negative or does not fit `usize`.
374    #[error("line {line}: declared {what} of {value} is not a valid count")]
375    BadCount {
376        /// 1-based line number.
377        line: usize,
378        /// Which count — `"node count"` or `"arc count"`.
379        what: &'static str,
380        /// The offending value.
381        value: i64,
382    },
383
384    /// The parsed network is not a well-formed instance.
385    #[error(transparent)]
386    Build(#[from] BuildError),
387}