eo_mcf/problem.rs
1//! The min-cost-flow instance: nodes with supplies, arcs with bounds and
2//! costs.
3//!
4//! # The problem
5//!
6//! Given a directed network with node supplies `b(v)` summing to zero, arc
7//! bounds `l(u,v) ≤ f(u,v) ≤ c(u,v)` and arc costs `w(u,v)`, find the integral
8//! flow `f` minimising `Σ w(u,v)·f(u,v)` subject to conservation
9//! `Σ_out f(v,·) − Σ_in f(·,v) = b(v)` at every node.
10//!
11//! Lower bounds and self-loops are part of the *stated* problem and are
12//! normalised away inside the solver, never here: [`Problem`] and the flow
13//! vectors the caller sees always speak the caller's arcs. That is what lets
14//! the [`verify`](crate::verify) module take `(&Problem, &[Flow])` and check a
15//! solution with no knowledge of how it was produced.
16//!
17//! # Index width
18//!
19//! Nodes and arcs are addressed with `u32` inside the solver's CSR arrays, so
20//! both are capped at [`MAX_NODES`] / [`MAX_ARCS`]. On a 64-bit host this
21//! halves the adjacency footprint against `usize` indices, which is the
22//! difference between fitting a large instance in cache-friendly memory and
23//! not. Instances above the cap are rejected at construction, not truncated.
24
25use crate::arith::{Capacity, Cost, Flow, Objective, add_i128};
26use crate::error::BuildError;
27
28/// Maximum number of nodes, set by the solver's `u32` index width.
29pub const MAX_NODES: usize = u32::MAX as usize;
30/// Maximum number of arcs, set by the solver's `u32` index width. Each arc
31/// becomes a forward/reverse pair, so the residual arc index must also fit.
32pub const MAX_ARCS: usize = (u32::MAX / 2) as usize;
33
34/// One arc of the network, in the caller's terms.
35#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
36pub struct Arc {
37 /// Node the arc leaves.
38 pub tail: usize,
39 /// Node the arc enters.
40 pub head: usize,
41 /// Minimum flow the arc must carry.
42 pub lower: Capacity,
43 /// Maximum flow the arc may carry.
44 pub upper: Capacity,
45 /// Cost per unit of flow. May be negative.
46 pub cost: Cost,
47}
48
49/// A validated min-cost-flow instance.
50///
51/// Construct through [`Problem::builder`]. Every invariant the solver relies
52/// on — endpoints in range, `lower ≤ upper`, supplies summing to zero — is
53/// established here, once, so an invalid instance never exists.
54#[derive(Debug, Clone, PartialEq, Eq)]
55pub struct Problem {
56 node_count: usize,
57 supplies: Vec<Flow>,
58 arcs: Vec<Arc>,
59}
60
61/// Incremental builder for a [`Problem`].
62#[derive(Debug, Clone)]
63pub struct ProblemBuilder {
64 node_count: usize,
65 supplies: Vec<Flow>,
66 arcs: Vec<Arc>,
67 /// First out-of-range node id passed to [`ProblemBuilder::supply`], held
68 /// so `build` can report it rather than the builder having to fail early.
69 stray_supply: Option<usize>,
70}
71
72impl Problem {
73 /// Start building a network with `node_count` nodes, ids `0..node_count`,
74 /// every supply zero.
75 #[must_use]
76 pub fn builder(node_count: usize) -> ProblemBuilder {
77 ProblemBuilder {
78 node_count,
79 supplies: vec![0; node_count.min(MAX_NODES)],
80 arcs: Vec::new(),
81 stray_supply: None,
82 }
83 }
84
85 /// Number of nodes.
86 #[must_use]
87 pub fn node_count(&self) -> usize {
88 self.node_count
89 }
90
91 /// Number of arcs.
92 #[must_use]
93 pub fn arc_count(&self) -> usize {
94 self.arcs.len()
95 }
96
97 /// The arcs, in the order they were added.
98 #[must_use]
99 pub fn arcs(&self) -> &[Arc] {
100 &self.arcs
101 }
102
103 /// Supply at every node, indexed by node id. Positive is supply, negative
104 /// is demand; the vector sums to zero.
105 #[must_use]
106 pub fn supplies(&self) -> &[Flow] {
107 &self.supplies
108 }
109
110 /// Supply at `node`, or `None` if the id is out of range.
111 #[must_use]
112 pub fn supply(&self, node: usize) -> Option<Flow> {
113 self.supplies.get(node).copied()
114 }
115
116 /// Cost of a candidate flow vector, `Σ wₖ·fₖ`, widened to [`Objective`].
117 ///
118 /// Says nothing about feasibility or optimality — that is
119 /// [`verify`](crate::verify)'s job. Returns an error only on overflow of
120 /// the 128-bit accumulator, which needs roughly 10¹⁹ units of flow at
121 /// maximum cost to reach.
122 pub fn objective(&self, flows: &[Flow]) -> Result<Objective, crate::arith::Overflow> {
123 let mut total: Objective = 0;
124 for (arc, &f) in self.arcs.iter().zip(flows) {
125 let term = crate::arith::mul_i128(
126 Objective::from(arc.cost),
127 Objective::from(f),
128 "objective term",
129 )?;
130 total = add_i128(total, term, "objective")?;
131 }
132 Ok(total)
133 }
134
135 /// A canonical reordering of this instance's arcs, plus the permutation
136 /// back to the caller's order.
137 ///
138 /// Arcs are sorted by `(tail, head, cost, lower, upper)`. Two instances
139 /// that differ only in the order their arcs were added produce byte-equal
140 /// canonical forms, which is what makes deterministic mode return the same
141 /// *flow* for permuted inputs and not merely the same *cost*.
142 ///
143 /// The returned vector maps canonical position to original position:
144 /// `original[perm[i]]` is the arc at canonical position `i`.
145 #[must_use]
146 pub fn canonical(&self) -> (Self, Vec<usize>) {
147 let mut perm: Vec<usize> = (0..self.arcs.len()).collect();
148 // Sort by the arc tuple, then by original index so that genuinely
149 // identical parallel arcs keep a stable, reproducible order.
150 perm.sort_by_key(|&i| {
151 let a = self.arcs[i];
152 (a.tail, a.head, a.cost, a.lower, a.upper, i)
153 });
154 let arcs = perm.iter().map(|&i| self.arcs[i]).collect();
155 (
156 Self {
157 node_count: self.node_count,
158 supplies: self.supplies.clone(),
159 arcs,
160 },
161 perm,
162 )
163 }
164
165 /// Bytes the solver will allocate for this instance, stated up front from
166 /// the problem size, so a caller can budget memory before committing.
167 ///
168 /// Counts the residual network, the per-node solver state and the
169 /// feasibility pre-check. It is an upper bound on steady-state usage, not
170 /// a guarantee about transient allocation inside `Vec::with_capacity`.
171 #[must_use]
172 pub fn memory_estimate(&self) -> u64 {
173 let n = self.node_count as u64;
174 let m = self.arcs.len() as u64;
175 // Residual network: head/rev/entry_arc (u32) + cap/cost (i64) over
176 // 2m arcs, plus first_out over n+1 nodes.
177 let residual = 2 * m * (4 + 4 + 4 + 8 + 8) + (n + 1) * 4;
178 // Per-node solver state: price, excess (i64), current, queue (u32),
179 // in_queue (bool).
180 let per_node = n * (8 + 8 + 4 + 4 + 1);
181 let per_node = per_node
182 // `heur-arc-fixing`: a live-span end (u32) per node.
183 + if cfg!(feature = "heur-arc-fixing") {
184 n * 4
185 } else {
186 0
187 }
188 // `heur-global-update`: a distance and a lifted price (i64 each).
189 + if cfg!(feature = "heur-global-update") {
190 n * (8 + 8)
191 } else {
192 0
193 }
194 // That update's priority queue is one of two, never both. Both
195 // take one entry per deficit seed and one per distance-improving
196 // relaxation — neither does decrease-key, both leave stale
197 // entries to be skipped on pop — so both are bounded by
198 // `n + 2m` entries rather than by the node count. The heap's are
199 // padded `(i64, u32)` pairs; the bucket arena's are `(u32, u32)`,
200 // on top of `2n + 1` chain heads.
201 + if cfg!(feature = "heur-bucket-update") {
202 (2 * n + 1) * 4 + (n + 2 * m) * (4 + 4)
203 } else if cfg!(feature = "heur-global-update") {
204 (n + 2 * m) * 16
205 } else {
206 0
207 }
208 // `heur-price-refinement`: a distance and a candidate price (i64
209 // each), an in-degree and a worklist slot (u32 each).
210 + if cfg!(feature = "heur-price-refinement") {
211 n * (8 + 8 + 4 + 4)
212 } else {
213 0
214 };
215 // Feasibility pre-check builds its own network over n+2 nodes and
216 // m + n arcs, with the same per-arc layout and a level/iter array.
217 let feasibility = 2 * (m + n) * (4 + 4 + 8) + (n + 2) * (4 + 4 + 4);
218 // Flow vector returned to the caller.
219 let result = m * 8;
220 residual + per_node + feasibility + result
221 }
222}
223
224impl ProblemBuilder {
225 /// Set the supply at `node`. Positive is supply, negative is demand.
226 ///
227 /// Overwrites any previous value for that node. An out-of-range id is
228 /// recorded and reported by [`build`](Self::build), so a builder chain
229 /// never needs to be unwrapped mid-way — but it is **not** accommodated by
230 /// growing the network. Silently extending the node space would turn a
231 /// mistyped node id into a different, larger problem that solves perfectly
232 /// well and answers a question nobody asked.
233 #[must_use]
234 pub fn supply(mut self, node: usize, value: Flow) -> Self {
235 match self.supplies.get_mut(node) {
236 Some(slot) => *slot = value,
237 None => self.stray_supply = self.stray_supply.or(Some(node)),
238 }
239 self
240 }
241
242 /// Add an arc `tail → head` carrying between `lower` and `upper` units at
243 /// `cost` per unit.
244 #[must_use]
245 pub fn arc(
246 mut self,
247 tail: usize,
248 head: usize,
249 lower: Capacity,
250 upper: Capacity,
251 cost: Cost,
252 ) -> Self {
253 self.arcs.push(Arc {
254 tail,
255 head,
256 lower,
257 upper,
258 cost,
259 });
260 self
261 }
262
263 /// Add an arc with lower bound zero — the common case.
264 #[must_use]
265 pub fn edge(self, tail: usize, head: usize, capacity: Capacity, cost: Cost) -> Self {
266 self.arc(tail, head, 0, capacity, cost)
267 }
268
269 /// Validate and freeze the instance.
270 ///
271 /// # Errors
272 ///
273 /// Returns [`BuildError`] if an endpoint is out of range, an arc's lower
274 /// bound exceeds its capacity, the supplies do not sum to zero, or the
275 /// network exceeds [`MAX_NODES`] / [`MAX_ARCS`].
276 pub fn build(self) -> Result<Problem, BuildError> {
277 if let Some(node) = self.stray_supply {
278 return Err(BuildError::SupplyNodeOutOfRange {
279 node,
280 node_count: self.node_count,
281 });
282 }
283 if self.node_count > MAX_NODES {
284 return Err(BuildError::TooLarge {
285 what: "nodes",
286 count: self.node_count,
287 max: MAX_NODES,
288 });
289 }
290 if self.arcs.len() > MAX_ARCS {
291 return Err(BuildError::TooLarge {
292 what: "arcs",
293 count: self.arcs.len(),
294 max: MAX_ARCS,
295 });
296 }
297
298 for (i, arc) in self.arcs.iter().enumerate() {
299 if arc.tail >= self.node_count {
300 return Err(BuildError::NodeOutOfRange {
301 arc: i,
302 node: arc.tail,
303 node_count: self.node_count,
304 });
305 }
306 if arc.head >= self.node_count {
307 return Err(BuildError::NodeOutOfRange {
308 arc: i,
309 node: arc.head,
310 node_count: self.node_count,
311 });
312 }
313 if arc.lower > arc.upper {
314 return Err(BuildError::InvalidBounds {
315 arc: i,
316 lower: arc.lower,
317 upper: arc.upper,
318 });
319 }
320 }
321
322 let mut supplies = self.supplies;
323 supplies.resize(self.node_count, 0);
324
325 let mut total: Objective = 0;
326 for &b in &supplies {
327 total = add_i128(total, Objective::from(b), "total supply")?;
328 }
329 if total != 0 {
330 return Err(BuildError::UnbalancedSupply { total });
331 }
332
333 Ok(Problem {
334 node_count: self.node_count,
335 supplies,
336 arcs: self.arcs,
337 })
338 }
339}
340
341#[cfg(test)]
342mod tests {
343 use super::*;
344
345 #[test]
346 fn builds_a_balanced_instance() {
347 let p = Problem::builder(3)
348 .supply(0, 5)
349 .supply(2, -5)
350 .edge(0, 1, 5, 1)
351 .edge(1, 2, 5, 1)
352 .build()
353 .unwrap();
354 assert_eq!(p.node_count(), 3);
355 assert_eq!(p.arc_count(), 2);
356 assert_eq!(p.supply(0), Some(5));
357 assert_eq!(p.supply(1), Some(0));
358 assert_eq!(p.supply(3), None);
359 }
360
361 #[test]
362 fn rejects_unbalanced_supply() {
363 let err = Problem::builder(2)
364 .supply(0, 5)
365 .supply(1, -4)
366 .build()
367 .unwrap_err();
368 assert_eq!(err, BuildError::UnbalancedSupply { total: 1 });
369 }
370
371 #[test]
372 fn rejects_out_of_range_endpoints() {
373 let err = Problem::builder(2).edge(0, 7, 1, 1).build().unwrap_err();
374 assert_eq!(
375 err,
376 BuildError::NodeOutOfRange {
377 arc: 0,
378 node: 7,
379 node_count: 2
380 }
381 );
382 }
383
384 #[test]
385 fn rejects_lower_bound_above_capacity() {
386 let err = Problem::builder(2).arc(0, 1, 5, 2, 0).build().unwrap_err();
387 assert_eq!(
388 err,
389 BuildError::InvalidBounds {
390 arc: 0,
391 lower: 5,
392 upper: 2
393 }
394 );
395 }
396
397 #[test]
398 fn supply_on_an_unknown_node_is_reported() {
399 let err = Problem::builder(2).supply(9, 3).build().unwrap_err();
400 assert_eq!(
401 err,
402 BuildError::SupplyNodeOutOfRange {
403 node: 9,
404 node_count: 2
405 }
406 );
407 }
408
409 #[test]
410 fn a_stray_supply_is_reported_even_when_the_totals_balance() {
411 // The dangerous case: a mistyped node id whose value happens to
412 // balance. Growing the network to fit it would build a 10-node
413 // instance, solve it perfectly, and answer the wrong question.
414 let err = Problem::builder(2)
415 .supply(9, 3)
416 .supply(0, -3)
417 .build()
418 .unwrap_err();
419 assert_eq!(
420 err,
421 BuildError::SupplyNodeOutOfRange {
422 node: 9,
423 node_count: 2
424 }
425 );
426 }
427
428 #[test]
429 fn objective_widens_past_i64() {
430 let p = Problem::builder(2)
431 .supply(0, 0)
432 .edge(0, 1, i64::MAX, i64::MAX)
433 .build()
434 .unwrap();
435 let want = Objective::from(i64::MAX) * Objective::from(i64::MAX);
436 assert_eq!(p.objective(&[i64::MAX]), Ok(want));
437 }
438
439 #[test]
440 fn canonical_form_is_permutation_invariant() {
441 let a = Problem::builder(3)
442 .supply(0, 2)
443 .supply(2, -2)
444 .edge(0, 1, 2, 3)
445 .edge(1, 2, 2, 4)
446 .edge(0, 2, 1, 9)
447 .build()
448 .unwrap();
449 let b = Problem::builder(3)
450 .supply(0, 2)
451 .supply(2, -2)
452 .edge(0, 2, 1, 9)
453 .edge(1, 2, 2, 4)
454 .edge(0, 1, 2, 3)
455 .build()
456 .unwrap();
457 let (ca, pa) = a.canonical();
458 let (cb, _) = b.canonical();
459 assert_eq!(ca, cb, "canonical forms of permuted instances must agree");
460 // The permutation maps canonical position back to the caller's order.
461 for (i, &orig) in pa.iter().enumerate() {
462 assert_eq!(ca.arcs()[i], a.arcs()[orig]);
463 }
464 }
465
466 #[test]
467 fn memory_estimate_grows_with_the_instance() {
468 let small = Problem::builder(2).edge(0, 1, 1, 1).build().unwrap();
469 let big = Problem::builder(100)
470 .edge(0, 1, 1, 1)
471 .edge(1, 2, 1, 1)
472 .build()
473 .unwrap();
474 assert!(big.memory_estimate() > small.memory_estimate());
475 }
476}