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}