eo-mcf 0.1.0

Exact minimum-cost-flow solver (cost-scaling push-relabel) with independent optimality certification.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
//! The min-cost-flow instance: nodes with supplies, arcs with bounds and
//! costs.
//!
//! # The problem
//!
//! Given a directed network with node supplies `b(v)` summing to zero, arc
//! bounds `l(u,v) ≤ f(u,v) ≤ c(u,v)` and arc costs `w(u,v)`, find the integral
//! flow `f` minimising `Σ w(u,v)·f(u,v)` subject to conservation
//! `Σ_out f(v,·) − Σ_in f(·,v) = b(v)` at every node.
//!
//! Lower bounds and self-loops are part of the *stated* problem and are
//! normalised away inside the solver, never here: [`Problem`] and the flow
//! vectors the caller sees always speak the caller's arcs. That is what lets
//! the [`verify`](crate::verify) module take `(&Problem, &[Flow])` and check a
//! solution with no knowledge of how it was produced.
//!
//! # Index width
//!
//! Nodes and arcs are addressed with `u32` inside the solver's CSR arrays, so
//! both are capped at [`MAX_NODES`] / [`MAX_ARCS`]. On a 64-bit host this
//! halves the adjacency footprint against `usize` indices, which is the
//! difference between fitting a large instance in cache-friendly memory and
//! not. Instances above the cap are rejected at construction, not truncated.

use crate::arith::{Capacity, Cost, Flow, Objective, add_i128};
use crate::error::BuildError;

/// Maximum number of nodes, set by the solver's `u32` index width.
pub const MAX_NODES: usize = u32::MAX as usize;
/// Maximum number of arcs, set by the solver's `u32` index width. Each arc
/// becomes a forward/reverse pair, so the residual arc index must also fit.
pub const MAX_ARCS: usize = (u32::MAX / 2) as usize;

/// One arc of the network, in the caller's terms.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Arc {
    /// Node the arc leaves.
    pub tail: usize,
    /// Node the arc enters.
    pub head: usize,
    /// Minimum flow the arc must carry.
    pub lower: Capacity,
    /// Maximum flow the arc may carry.
    pub upper: Capacity,
    /// Cost per unit of flow. May be negative.
    pub cost: Cost,
}

/// A validated min-cost-flow instance.
///
/// Construct through [`Problem::builder`]. Every invariant the solver relies
/// on — endpoints in range, `lower ≤ upper`, supplies summing to zero — is
/// established here, once, so an invalid instance never exists.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Problem {
    node_count: usize,
    supplies: Vec<Flow>,
    arcs: Vec<Arc>,
}

/// Incremental builder for a [`Problem`].
#[derive(Debug, Clone)]
pub struct ProblemBuilder {
    node_count: usize,
    supplies: Vec<Flow>,
    arcs: Vec<Arc>,
    /// First out-of-range node id passed to [`ProblemBuilder::supply`], held
    /// so `build` can report it rather than the builder having to fail early.
    stray_supply: Option<usize>,
}

impl Problem {
    /// Start building a network with `node_count` nodes, ids `0..node_count`,
    /// every supply zero.
    #[must_use]
    pub fn builder(node_count: usize) -> ProblemBuilder {
        ProblemBuilder {
            node_count,
            supplies: vec![0; node_count.min(MAX_NODES)],
            arcs: Vec::new(),
            stray_supply: None,
        }
    }

    /// Number of nodes.
    #[must_use]
    pub fn node_count(&self) -> usize {
        self.node_count
    }

    /// Number of arcs.
    #[must_use]
    pub fn arc_count(&self) -> usize {
        self.arcs.len()
    }

    /// The arcs, in the order they were added.
    #[must_use]
    pub fn arcs(&self) -> &[Arc] {
        &self.arcs
    }

    /// Supply at every node, indexed by node id. Positive is supply, negative
    /// is demand; the vector sums to zero.
    #[must_use]
    pub fn supplies(&self) -> &[Flow] {
        &self.supplies
    }

    /// Supply at `node`, or `None` if the id is out of range.
    #[must_use]
    pub fn supply(&self, node: usize) -> Option<Flow> {
        self.supplies.get(node).copied()
    }

    /// Cost of a candidate flow vector, `Σ wₖ·fₖ`, widened to [`Objective`].
    ///
    /// Says nothing about feasibility or optimality — that is
    /// [`verify`](crate::verify)'s job. Returns an error only on overflow of
    /// the 128-bit accumulator, which needs roughly 10¹⁹ units of flow at
    /// maximum cost to reach.
    pub fn objective(&self, flows: &[Flow]) -> Result<Objective, crate::arith::Overflow> {
        let mut total: Objective = 0;
        for (arc, &f) in self.arcs.iter().zip(flows) {
            let term = crate::arith::mul_i128(
                Objective::from(arc.cost),
                Objective::from(f),
                "objective term",
            )?;
            total = add_i128(total, term, "objective")?;
        }
        Ok(total)
    }

    /// A canonical reordering of this instance's arcs, plus the permutation
    /// back to the caller's order.
    ///
    /// Arcs are sorted by `(tail, head, cost, lower, upper)`. Two instances
    /// that differ only in the order their arcs were added produce byte-equal
    /// canonical forms, which is what makes deterministic mode return the same
    /// *flow* for permuted inputs and not merely the same *cost*.
    ///
    /// The returned vector maps canonical position to original position:
    /// `original[perm[i]]` is the arc at canonical position `i`.
    #[must_use]
    pub fn canonical(&self) -> (Self, Vec<usize>) {
        let mut perm: Vec<usize> = (0..self.arcs.len()).collect();
        // Sort by the arc tuple, then by original index so that genuinely
        // identical parallel arcs keep a stable, reproducible order.
        perm.sort_by_key(|&i| {
            let a = self.arcs[i];
            (a.tail, a.head, a.cost, a.lower, a.upper, i)
        });
        let arcs = perm.iter().map(|&i| self.arcs[i]).collect();
        (
            Self {
                node_count: self.node_count,
                supplies: self.supplies.clone(),
                arcs,
            },
            perm,
        )
    }

    /// Bytes the solver will allocate for this instance, stated up front from
    /// the problem size, so a caller can budget memory before committing.
    ///
    /// Counts the residual network, the per-node solver state and the
    /// feasibility pre-check. It is an upper bound on steady-state usage, not
    /// a guarantee about transient allocation inside `Vec::with_capacity`.
    #[must_use]
    pub fn memory_estimate(&self) -> u64 {
        let n = self.node_count as u64;
        let m = self.arcs.len() as u64;
        // Residual network: head/rev/entry_arc (u32) + cap/cost (i64) over
        // 2m arcs, plus first_out over n+1 nodes.
        let residual = 2 * m * (4 + 4 + 4 + 8 + 8) + (n + 1) * 4;
        // Per-node solver state: price, excess (i64), current, queue (u32),
        // in_queue (bool).
        let per_node = n * (8 + 8 + 4 + 4 + 1);
        let per_node = per_node
            // `heur-arc-fixing`: a live-span end (u32) per node.
            + if cfg!(feature = "heur-arc-fixing") {
                n * 4
            } else {
                0
            }
            // `heur-global-update`: a distance and a lifted price (i64 each).
            + if cfg!(feature = "heur-global-update") {
                n * (8 + 8)
            } else {
                0
            }
            // That update's priority queue is one of two, never both. Both
            // take one entry per deficit seed and one per distance-improving
            // relaxation — neither does decrease-key, both leave stale
            // entries to be skipped on pop — so both are bounded by
            // `n + 2m` entries rather than by the node count. The heap's are
            // padded `(i64, u32)` pairs; the bucket arena's are `(u32, u32)`,
            // on top of `2n + 1` chain heads.
            + if cfg!(feature = "heur-bucket-update") {
                (2 * n + 1) * 4 + (n + 2 * m) * (4 + 4)
            } else if cfg!(feature = "heur-global-update") {
                (n + 2 * m) * 16
            } else {
                0
            }
            // `heur-price-refinement`: a distance and a candidate price (i64
            // each), an in-degree and a worklist slot (u32 each).
            + if cfg!(feature = "heur-price-refinement") {
                n * (8 + 8 + 4 + 4)
            } else {
                0
            };
        // Feasibility pre-check builds its own network over n+2 nodes and
        // m + n arcs, with the same per-arc layout and a level/iter array.
        let feasibility = 2 * (m + n) * (4 + 4 + 8) + (n + 2) * (4 + 4 + 4);
        // Flow vector returned to the caller.
        let result = m * 8;
        residual + per_node + feasibility + result
    }
}

impl ProblemBuilder {
    /// Set the supply at `node`. Positive is supply, negative is demand.
    ///
    /// Overwrites any previous value for that node. An out-of-range id is
    /// recorded and reported by [`build`](Self::build), so a builder chain
    /// never needs to be unwrapped mid-way — but it is **not** accommodated by
    /// growing the network. Silently extending the node space would turn a
    /// mistyped node id into a different, larger problem that solves perfectly
    /// well and answers a question nobody asked.
    #[must_use]
    pub fn supply(mut self, node: usize, value: Flow) -> Self {
        match self.supplies.get_mut(node) {
            Some(slot) => *slot = value,
            None => self.stray_supply = self.stray_supply.or(Some(node)),
        }
        self
    }

    /// Add an arc `tail → head` carrying between `lower` and `upper` units at
    /// `cost` per unit.
    #[must_use]
    pub fn arc(
        mut self,
        tail: usize,
        head: usize,
        lower: Capacity,
        upper: Capacity,
        cost: Cost,
    ) -> Self {
        self.arcs.push(Arc {
            tail,
            head,
            lower,
            upper,
            cost,
        });
        self
    }

    /// Add an arc with lower bound zero — the common case.
    #[must_use]
    pub fn edge(self, tail: usize, head: usize, capacity: Capacity, cost: Cost) -> Self {
        self.arc(tail, head, 0, capacity, cost)
    }

    /// Validate and freeze the instance.
    ///
    /// # Errors
    ///
    /// Returns [`BuildError`] if an endpoint is out of range, an arc's lower
    /// bound exceeds its capacity, the supplies do not sum to zero, or the
    /// network exceeds [`MAX_NODES`] / [`MAX_ARCS`].
    pub fn build(self) -> Result<Problem, BuildError> {
        if let Some(node) = self.stray_supply {
            return Err(BuildError::SupplyNodeOutOfRange {
                node,
                node_count: self.node_count,
            });
        }
        if self.node_count > MAX_NODES {
            return Err(BuildError::TooLarge {
                what: "nodes",
                count: self.node_count,
                max: MAX_NODES,
            });
        }
        if self.arcs.len() > MAX_ARCS {
            return Err(BuildError::TooLarge {
                what: "arcs",
                count: self.arcs.len(),
                max: MAX_ARCS,
            });
        }

        for (i, arc) in self.arcs.iter().enumerate() {
            if arc.tail >= self.node_count {
                return Err(BuildError::NodeOutOfRange {
                    arc: i,
                    node: arc.tail,
                    node_count: self.node_count,
                });
            }
            if arc.head >= self.node_count {
                return Err(BuildError::NodeOutOfRange {
                    arc: i,
                    node: arc.head,
                    node_count: self.node_count,
                });
            }
            if arc.lower > arc.upper {
                return Err(BuildError::InvalidBounds {
                    arc: i,
                    lower: arc.lower,
                    upper: arc.upper,
                });
            }
        }

        let mut supplies = self.supplies;
        supplies.resize(self.node_count, 0);

        let mut total: Objective = 0;
        for &b in &supplies {
            total = add_i128(total, Objective::from(b), "total supply")?;
        }
        if total != 0 {
            return Err(BuildError::UnbalancedSupply { total });
        }

        Ok(Problem {
            node_count: self.node_count,
            supplies,
            arcs: self.arcs,
        })
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn builds_a_balanced_instance() {
        let p = Problem::builder(3)
            .supply(0, 5)
            .supply(2, -5)
            .edge(0, 1, 5, 1)
            .edge(1, 2, 5, 1)
            .build()
            .unwrap();
        assert_eq!(p.node_count(), 3);
        assert_eq!(p.arc_count(), 2);
        assert_eq!(p.supply(0), Some(5));
        assert_eq!(p.supply(1), Some(0));
        assert_eq!(p.supply(3), None);
    }

    #[test]
    fn rejects_unbalanced_supply() {
        let err = Problem::builder(2)
            .supply(0, 5)
            .supply(1, -4)
            .build()
            .unwrap_err();
        assert_eq!(err, BuildError::UnbalancedSupply { total: 1 });
    }

    #[test]
    fn rejects_out_of_range_endpoints() {
        let err = Problem::builder(2).edge(0, 7, 1, 1).build().unwrap_err();
        assert_eq!(
            err,
            BuildError::NodeOutOfRange {
                arc: 0,
                node: 7,
                node_count: 2
            }
        );
    }

    #[test]
    fn rejects_lower_bound_above_capacity() {
        let err = Problem::builder(2).arc(0, 1, 5, 2, 0).build().unwrap_err();
        assert_eq!(
            err,
            BuildError::InvalidBounds {
                arc: 0,
                lower: 5,
                upper: 2
            }
        );
    }

    #[test]
    fn supply_on_an_unknown_node_is_reported() {
        let err = Problem::builder(2).supply(9, 3).build().unwrap_err();
        assert_eq!(
            err,
            BuildError::SupplyNodeOutOfRange {
                node: 9,
                node_count: 2
            }
        );
    }

    #[test]
    fn a_stray_supply_is_reported_even_when_the_totals_balance() {
        // The dangerous case: a mistyped node id whose value happens to
        // balance. Growing the network to fit it would build a 10-node
        // instance, solve it perfectly, and answer the wrong question.
        let err = Problem::builder(2)
            .supply(9, 3)
            .supply(0, -3)
            .build()
            .unwrap_err();
        assert_eq!(
            err,
            BuildError::SupplyNodeOutOfRange {
                node: 9,
                node_count: 2
            }
        );
    }

    #[test]
    fn objective_widens_past_i64() {
        let p = Problem::builder(2)
            .supply(0, 0)
            .edge(0, 1, i64::MAX, i64::MAX)
            .build()
            .unwrap();
        let want = Objective::from(i64::MAX) * Objective::from(i64::MAX);
        assert_eq!(p.objective(&[i64::MAX]), Ok(want));
    }

    #[test]
    fn canonical_form_is_permutation_invariant() {
        let a = Problem::builder(3)
            .supply(0, 2)
            .supply(2, -2)
            .edge(0, 1, 2, 3)
            .edge(1, 2, 2, 4)
            .edge(0, 2, 1, 9)
            .build()
            .unwrap();
        let b = Problem::builder(3)
            .supply(0, 2)
            .supply(2, -2)
            .edge(0, 2, 1, 9)
            .edge(1, 2, 2, 4)
            .edge(0, 1, 2, 3)
            .build()
            .unwrap();
        let (ca, pa) = a.canonical();
        let (cb, _) = b.canonical();
        assert_eq!(ca, cb, "canonical forms of permuted instances must agree");
        // The permutation maps canonical position back to the caller's order.
        for (i, &orig) in pa.iter().enumerate() {
            assert_eq!(ca.arcs()[i], a.arcs()[orig]);
        }
    }

    #[test]
    fn memory_estimate_grows_with_the_instance() {
        let small = Problem::builder(2).edge(0, 1, 1, 1).build().unwrap();
        let big = Problem::builder(100)
            .edge(0, 1, 1, 1)
            .edge(1, 2, 1, 1)
            .build()
            .unwrap();
        assert!(big.memory_estimate() > small.memory_estimate());
    }
}