Skip to main content

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}