eo_mcf/solver.rs
1//! Cost-scaling push-relabel minimum-cost-flow solver.
2//!
3//! Implemented from the published literature — Goldberg (1997) for the
4//! scaling structure and the efficiency heuristics, Goldberg & Tarjan (1990)
5//! for successive approximation, Goldberg & Tarjan (1988) for push-relabel
6//! itself. See `docs/ALGORITHM.md` for the implementer's notes.
7//!
8//! # Sign convention
9//!
10//! Reduced cost is `c_p(u,v) = c(u,v) − p(u) + p(v)`
11//! [cite: AHUJA-MAGNANTI-ORLIN §9.3]. A pseudoflow `f` with prices `p` is
12//! **ε-optimal** when every residual arc satisfies `c_p(u,v) ≥ −ε`. A residual
13//! arc is **admissible** when `c_p(u,v) < 0`, so `push` moves flow down a price
14//! gradient and `relabel` *raises* `p(u)`.
15//!
16//! ⚠ **Goldberg (1997) uses the mirror convention**, so this marker used to
17//! point at the wrong paper. Its §2.1 defines
18//! `c_p(v,w) = c(v,w) + p(v) − p(w)`, and its `relabel` correspondingly
19//! *decreases* `p(v)` to `max over residual (v,w) of [p(w) − c(v,w) − ε]`
20//! (§2.2). The two differ by the sign of `p` and describe the same algorithm;
21//! lifting a formula out of that paper without flipping it inverts `relabel`.
22//! The form above is Ahuja–Magnanti–Orlin's, and it is the one this whole
23//! crate uses, including [`crate::verify`].
24//!
25//! # Why the answer is exact
26//!
27//! Costs are multiplied by `n + 1` before scaling begins. With integral costs,
28//! a flow that is ε-optimal for `ε < 1/n` is optimal
29//! [cite: GOLDBERG-TARJAN-1990 §2.2 Thm 2.3; GOLDBERG-1997 §2.1], so scaling
30//! down to `ε = 1` in the multiplied units — i.e. `1/(n+1) < 1/n` in the
31//! caller's units — terminates at a provable optimum rather than near one.
32//! Nothing is rounded, and the objective is recomputed from the caller's own
33//! arcs at the end, not accumulated along the way.
34//!
35//! The ε-relaxation of complementary slackness this rests on is due to
36//! Bertsekas [cite: BERTSEKAS-1988 §2]: Goldberg & Tarjan attribute the
37//! `ε < 1/n` theorem to him by name, and Goldberg (1997) §1 names "the
38//! relaxation method of Bertsekas" as one of the three ingredients the method
39//! combines.
40//!
41//! # Determinism
42//!
43//! There is no randomness, no floating point and no hash iteration anywhere on
44//! this path, so a given instance always yields the same flow on the same
45//! build. [`SolverOptions::deterministic`] goes further and canonicalises the
46//! arc order first, so instances that differ only in the order their arcs were
47//! declared also yield the same flow.
48
49use crate::arith::{Capacity, Cost, Flow, Objective, Overflow, Price, add, mul, reduced_cost, sub};
50use crate::error::SolveError;
51use crate::maxflow::FlowNetwork;
52use crate::network::{Normalized, normalize};
53use crate::problem::Problem;
54
55/// Distance sentinel for a node the global-update sweep never reached.
56#[cfg(feature = "heur-global-update")]
57const UNREACHED: i64 = i64::MAX;
58
59/// End-of-chain sentinel for the Dial bucket arena, and — since it is the one
60/// index no entry may occupy — the arena's capacity limit.
61#[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
62const BUCKET_NIL: u32 = u32::MAX;
63
64/// Order in which nodes with excess are selected for discharge.
65///
66/// The choice affects running time and *which* optimal flow is returned when
67/// several are optimal, which is why it is explicit rather than incidental.
68#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
69#[non_exhaustive]
70pub enum ActiveNodeOrder {
71 /// First in, first out. The default: it bounds the number of passes over
72 /// the active set and behaves predictably on layered networks.
73 #[default]
74 Fifo,
75 /// Last in, first out. Cheaper bookkeeping, better locality on some
76 /// instances, worse worst case.
77 Lifo,
78}
79
80/// Knobs for a solve. Defaults are the measured-good settings; every field is
81/// a documented trade, not a magic number.
82#[derive(Debug, Clone, PartialEq, Eq)]
83#[non_exhaustive]
84pub struct SolverOptions {
85 /// Canonicalise the arc order before solving, so permuted-but-equal
86 /// instances return the same flow and not merely the same cost.
87 ///
88 /// Costs one sort of the arc list. The solver is deterministic either way;
89 /// this makes it *canonical*.
90 ///
91 /// # The exact claim
92 ///
93 /// Canonical **up to permutation within a group of identical parallel
94 /// arcs** — arcs agreeing in tail, head, bounds and cost. That caveat is
95 /// not an implementation shortcut, it is forced: such arcs are
96 /// indistinguishable, so if the flow were required to be identical under
97 /// every relabelling of them, they would all have to carry equal flow, and
98 /// two identical arcs sharing three units of an integral flow cannot. For
99 /// every distinguishable arc the flow is exactly reproducible, and the
100 /// multiset of flows over each identical group is too.
101 pub deterministic: bool,
102
103 /// Scaling factor α: ε shrinks by this much each phase. Clamped to ≥ 2.
104 ///
105 /// Larger α means fewer phases doing more work each.
106 ///
107 /// **The default is 32, which is measured, not inherited** — and, now
108 /// that the paper has been verified against, consistent with it: CS 1.0
109 /// defaults to α = 12 [cite: GOLDBERG-1997 §4.1] and Goldberg reports the
110 /// method robust for α between 4 and 50, with differences usually under
111 /// 2× [cite: GOLDBERG-1997 §7]. (An earlier revision of this crate
112 /// attributed "8–16" to this paper; the paper says no such thing — that
113 /// range appears in Király & Kovács as "8 to 24"
114 /// [cite: KIRALY-KOVACS-2012 §3.3].) This crate shipped 8 until it was
115 /// measured, at which point α = 32 was 1.9× faster than α = 8 on a
116 /// 140×140 grid, monotone from 2 to 64 across every family; re-measured
117 /// unchanged with arc fixing and price refinement on (2026-08-07). The
118 /// sweep has not been checked against adversarial families, which this
119 /// crate does not yet generate.
120 ///
121 /// Run `cargo run --release --example bench` for the current sweep.
122 pub scaling_factor: u32,
123
124 /// Active-node selection order.
125 pub selection: ActiveNodeOrder,
126
127 /// Upper bound on pushes plus relabels, after which the solve gives up
128 /// with [`SolveError::OperationBudgetExhausted`].
129 ///
130 /// `None` — the default — means no bound: the algorithm terminates on its
131 /// own, and an arbitrary cap would turn a slow solve into a wrong answer.
132 /// The engine sets this when it owns a time budget (design law 4).
133 pub max_operations: Option<u64>,
134}
135
136impl Default for SolverOptions {
137 fn default() -> Self {
138 Self {
139 deterministic: false,
140 scaling_factor: 32,
141 selection: ActiveNodeOrder::Fifo,
142 max_operations: None,
143 }
144 }
145}
146
147impl SolverOptions {
148 /// Set [`deterministic`](Self::deterministic).
149 ///
150 /// The struct is `#[non_exhaustive]`, so adding a knob later cannot break
151 /// a caller — which also means it cannot be built with a struct
152 /// expression. These setters are how it is configured.
153 #[must_use]
154 pub fn with_deterministic(mut self, deterministic: bool) -> Self {
155 self.deterministic = deterministic;
156 self
157 }
158
159 /// Set [`scaling_factor`](Self::scaling_factor). Values below 2 are
160 /// clamped to 2 at solve time.
161 #[must_use]
162 pub fn with_scaling_factor(mut self, scaling_factor: u32) -> Self {
163 self.scaling_factor = scaling_factor;
164 self
165 }
166
167 /// Set [`selection`](Self::selection).
168 #[must_use]
169 pub fn with_selection(mut self, selection: ActiveNodeOrder) -> Self {
170 self.selection = selection;
171 self
172 }
173
174 /// Set [`max_operations`](Self::max_operations).
175 #[must_use]
176 pub fn with_max_operations(mut self, max_operations: Option<u64>) -> Self {
177 self.max_operations = max_operations;
178 self
179 }
180}
181
182/// What the solve did. Trend data for benchmarking; also the evidence that a
183/// heuristic changed the *path* to the optimum and not the optimum itself.
184#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
185#[non_exhaustive]
186pub struct SolveStats {
187 /// Scaling phases executed — refines run, plus phases skipped whole by
188 /// price refinement (so `refinement_skips ≤ scaling_phases`).
189 pub scaling_phases: u32,
190 /// Flow-moving operations.
191 pub pushes: u64,
192 /// Price increases.
193 pub relabels: u64,
194 /// Global price recomputations (`heur-global-update`).
195 pub global_updates: u64,
196 /// Relabels triggered by push-lookahead (`heur-push-lookahead`).
197 pub lookahead_relabels: u64,
198 /// Arcs proved unable to change flow again and retired from every hot
199 /// loop at a phase boundary (`heur-arc-fixing`). Counts arcs, i.e. entry
200 /// pairs.
201 pub arcs_fixed: u64,
202 /// Phases skipped entirely because the previous flow re-verified as
203 /// ε-optimal for the new ε under adjusted potentials
204 /// (`heur-price-refinement`). Each one is a whole refine that never ran.
205 pub refinement_skips: u64,
206 /// Relaxations the bucket sweep declined to pursue because the improved
207 /// distance lay past its ceiling (`heur-bucket-update`). Counts *events*,
208 /// not nodes: a node whose over-ceiling label improves repeatedly is
209 /// counted each time. Nonzero means the `2n + 1` bucket array is binding
210 /// and the sweep is truncating — sound, but a route change against the
211 /// unbounded heap sweep, so it is measured rather than assumed.
212 pub update_truncations: u64,
213 /// The scaling loop stopped early because the flow was already provably
214 /// optimal, rather than running every phase down to ε = 1.
215 pub early_exit: bool,
216}
217
218/// An optimal flow, with the evidence to check it.
219#[derive(Debug, Clone, PartialEq, Eq)]
220pub struct Solution {
221 flows: Vec<Flow>,
222 objective: Objective,
223 prices: Vec<Price>,
224 stats: SolveStats,
225}
226
227impl Solution {
228 /// Flow on each arc, in the caller's arc order, including lower bounds.
229 #[must_use]
230 pub fn flows(&self) -> &[Flow] {
231 &self.flows
232 }
233
234 /// Total cost `Σ wₖ·fₖ`.
235 ///
236 /// Unique across all optimal flows, which is what makes it the right thing
237 /// to compare against an oracle. Two correct algorithms may return
238 /// different flows; they may not return different costs.
239 #[must_use]
240 pub fn objective(&self) -> Objective {
241 self.objective
242 }
243
244 /// The solver's own final prices.
245 ///
246 /// Exposed because a caller may want the duals. **Not** an optimality
247 /// certificate: prices produced by a buggy solver would certify that same
248 /// bug. [`crate::verify`] therefore does not accept them — its entry
249 /// points take only the problem and the flow, and recompute potentials
250 /// from scratch.
251 #[must_use]
252 pub fn prices(&self) -> &[Price] {
253 &self.prices
254 }
255
256 /// Work done reaching this solution.
257 #[must_use]
258 pub fn stats(&self) -> SolveStats {
259 self.stats
260 }
261}
262
263/// Solve `problem` with default options.
264///
265/// # Errors
266///
267/// [`SolveError::Infeasible`] if no flow satisfies the supplies and bounds;
268/// [`SolveError::Overflow`] if the scaled costs or prices leave `i64`.
269pub fn solve(problem: &Problem) -> Result<Solution, SolveError> {
270 solve_with(problem, &SolverOptions::default())
271}
272
273/// Solve `problem` with explicit options.
274///
275/// # Errors
276///
277/// As [`solve`], plus [`SolveError::OperationBudgetExhausted`] when
278/// [`SolverOptions::max_operations`] is set and reached.
279pub fn solve_with(problem: &Problem, options: &SolverOptions) -> Result<Solution, SolveError> {
280 if !options.deterministic {
281 return solve_inner(problem, options);
282 }
283 // Canonical mode: solve the canonicalised instance, then restate the flow
284 // in the caller's arc order. Node ids and supplies are untouched, so the
285 // prices come back unchanged.
286 let (canonical, perm) = problem.canonical();
287 let solved = solve_inner(&canonical, options)?;
288 let mut flows = vec![0 as Flow; problem.arc_count()];
289 for (canonical_index, &original_index) in perm.iter().enumerate() {
290 flows[original_index] = solved.flows[canonical_index];
291 }
292 Ok(Solution { flows, ..solved })
293}
294
295fn solve_inner(problem: &Problem, options: &SolverOptions) -> Result<Solution, SolveError> {
296 let normalized = normalize(problem)?;
297 check_feasible(&normalized)?;
298
299 let mut engine = Engine::new(normalized, options)?;
300 engine.run()?;
301
302 let normalized = engine.normalized;
303 let flows = normalized.reconstruct();
304 let objective = problem.objective(&flows)?;
305
306 // `certify-on-solve`: prove every answer before returning it. Off by
307 // default because certification is O(n·m) — but when it is on it must
308 // actually run, and a solve that cannot certify its own output is a defect
309 // reported to the caller rather than a result handed over quietly.
310 #[cfg(feature = "certify-on-solve")]
311 if let Err(error) = crate::verify::certify(problem, &flows) {
312 return Err(SolveError::SelfCertificationFailed(error));
313 }
314
315 Ok(Solution {
316 flows,
317 objective,
318 prices: engine.price,
319 stats: engine.stats,
320 })
321}
322
323/// Reject infeasible instances before any scaling happens.
324///
325/// Routes every unit of (post-normalisation) supply to demand through a
326/// max-flow computation. Feasible exactly when all of it arrives.
327fn check_feasible(normalized: &Normalized) -> Result<(), SolveError> {
328 let node_count = normalized.res.node_count;
329 let source = node_count;
330 let sink = node_count + 1;
331
332 let mut edges: Vec<(u32, u32, Capacity)> = normalized.forward_arcs().collect();
333 let mut required: i128 = 0;
334 for (v, &excess) in normalized.excess.iter().enumerate() {
335 let node = u32::try_from(v).map_err(|_| SolveError::InvariantViolated {
336 what: "node index exceeds u32 after a successful build",
337 })?;
338 match excess.cmp(&0) {
339 std::cmp::Ordering::Greater => {
340 edges.push((source as u32, node, excess));
341 required += i128::from(excess);
342 }
343 std::cmp::Ordering::Less => {
344 let demand = excess
345 .checked_neg()
346 .ok_or_else(|| Overflow::new("node demand after lower-bound substitution"))?;
347 edges.push((node, sink as u32, demand));
348 }
349 std::cmp::Ordering::Equal => {}
350 }
351 }
352
353 let routable = FlowNetwork::new(node_count + 2, &edges).max_flow(source, sink);
354 if routable == required {
355 Ok(())
356 } else {
357 Err(SolveError::Infeasible { routable, required })
358 }
359}
360
361/// Solver state for one instance.
362struct Engine {
363 normalized: Normalized,
364 price: Vec<Price>,
365 /// Current-arc pointer per node: arcs before it are known inadmissible
366 /// under the current prices, so a discharge never rescans them.
367 current: Vec<u32>,
368 queue: std::collections::VecDeque<u32>,
369 queued: Vec<bool>,
370 selection: ActiveNodeOrder,
371 alpha: Cost,
372 budget: Option<u64>,
373 operations: u64,
374 relabels_since_update: u64,
375 stats: SolveStats,
376 /// Scratch for the global update, held across calls so a solve allocates
377 /// them once instead of once per update (`heur-global-update`).
378 #[cfg(feature = "heur-global-update")]
379 update_dist: Vec<i64>,
380 #[cfg(feature = "heur-global-update")]
381 update_lifted: Vec<Price>,
382 #[cfg(all(feature = "heur-global-update", not(feature = "heur-bucket-update")))]
383 update_heap: std::collections::BinaryHeap<std::cmp::Reverse<(i64, u32)>>,
384 /// Dial buckets for the price-update sweep (`heur-bucket-update`): one
385 /// chain head per distance in `0..=2n`. Sized once, reused by every
386 /// update.
387 #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
388 bucket_head: Vec<u32>,
389 /// Chain entries as `(node, next)`. One `Vec` rather than two parallel
390 /// ones so the two halves cannot drift apart, and `u32` rather than
391 /// `usize` because both fields are bounded by the residual entry count:
392 /// 8 bytes per entry instead of 12, on the largest node-proportional
393 /// allocation the engine makes. Reserved to its bound up front, so a
394 /// sweep never reallocates.
395 #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
396 bucket_arena: Vec<(u32, u32)>,
397 /// Highest distance the bucket array can hold, i.e. `2n`.
398 #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
399 bucket_ceiling: i64,
400 /// Scratch for price refinement, held across phases
401 /// (`heur-price-refinement`): per-node distances in units of ε, in-degree
402 /// counters for the topological pass, the FIFO worklist, and the
403 /// candidate prices computed aside.
404 #[cfg(feature = "heur-price-refinement")]
405 refine_dist: Vec<i64>,
406 #[cfg(feature = "heur-price-refinement")]
407 refine_indegree: Vec<u32>,
408 #[cfg(feature = "heur-price-refinement")]
409 refine_queue: std::collections::VecDeque<u32>,
410 #[cfg(feature = "heur-price-refinement")]
411 refine_price: Vec<Price>,
412}
413
414impl Engine {
415 fn new(normalized: Normalized, options: &SolverOptions) -> Result<Self, SolveError> {
416 let node_count = normalized.res.node_count;
417 // `2n + 1` buckets: prices move by O(nε) within a refine, so the
418 // sweep never needs to represent a larger distance
419 // [cite: GOLDBERG-1997 §3.1; GOLDBERG-1995-SP §6].
420 #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
421 let bucket_count = node_count.saturating_mul(2).saturating_add(1);
422 // One arena entry per deficit seed and per distance-improving
423 // relaxation, so the sweep can never need more than this — reserve it
424 // once rather than growing inside the hot loop.
425 #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
426 let arena_bound = node_count.saturating_add(normalized.res.head.len());
427 Ok(Self {
428 price: vec![0 as Price; node_count],
429 current: vec![0; node_count],
430 queue: std::collections::VecDeque::with_capacity(node_count),
431 queued: vec![false; node_count],
432 selection: options.selection,
433 alpha: Cost::from(options.scaling_factor.max(2)),
434 budget: options.max_operations,
435 operations: 0,
436 relabels_since_update: 0,
437 stats: SolveStats::default(),
438 #[cfg(feature = "heur-global-update")]
439 update_dist: vec![0; node_count],
440 #[cfg(feature = "heur-global-update")]
441 update_lifted: Vec::with_capacity(node_count),
442 #[cfg(all(feature = "heur-global-update", not(feature = "heur-bucket-update")))]
443 update_heap: std::collections::BinaryHeap::with_capacity(node_count),
444 #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
445 bucket_head: vec![BUCKET_NIL; bucket_count],
446 #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
447 bucket_arena: Vec::with_capacity(arena_bound),
448 #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
449 bucket_ceiling: (bucket_count - 1) as i64,
450 #[cfg(feature = "heur-price-refinement")]
451 refine_dist: vec![0; node_count],
452 #[cfg(feature = "heur-price-refinement")]
453 refine_indegree: vec![0; node_count],
454 #[cfg(feature = "heur-price-refinement")]
455 refine_queue: std::collections::VecDeque::with_capacity(node_count),
456 #[cfg(feature = "heur-price-refinement")]
457 refine_price: Vec::with_capacity(node_count),
458 normalized,
459 })
460 }
461
462 /// The scaling loop: multiply costs into the exact range, then refine ε
463 /// down to 1.
464 fn run(&mut self) -> Result<(), SolveError> {
465 let node_count = self.normalized.res.node_count;
466 if node_count == 0 || self.normalized.res.head.is_empty() {
467 return Ok(());
468 }
469
470 // Cost multiplication (see the module note on exactness).
471 let scale = Cost::try_from(node_count)
472 .ok()
473 .and_then(|n| n.checked_add(1))
474 .ok_or_else(|| Overflow::new("cost scale factor n + 1"))?;
475 let mut max_abs: Cost = 1;
476 for slot in &mut self.normalized.res.cost {
477 let scaled = mul(*slot, scale, "scaled arc cost")?;
478 *slot = scaled;
479 let magnitude = scaled
480 .checked_abs()
481 .ok_or_else(|| Overflow::new("magnitude of scaled arc cost"))?;
482 max_abs = max_abs.max(magnitude);
483 }
484
485 // f = 0 with p = 0 is max|c|-optimal: every residual arc is a forward
486 // arc, and its reduced cost is its cost, which is ≥ −max|c|.
487 let mut eps = max_abs;
488 loop {
489 eps = if eps <= 1 {
490 1
491 } else {
492 (eps / self.alpha).max(1)
493 };
494
495 // Price refinement: from the second phase on — earlier there is a
496 // pseudoflow, not a flow, and skipping refine would strand its
497 // excesses — try to re-verify the standing flow as ε-optimal for
498 // the new ε with adjusted potentials, and skip the whole refine
499 // when that succeeds. The flow is untouched, so a skipped phase
500 // is neutral by construction. Goldberg applies the heuristic on
501 // exactly this schedule: every scaling iteration except the first
502 // [cite: GOLDBERG-1997 §6].
503 #[cfg(feature = "heur-price-refinement")]
504 let skipped = self.stats.scaling_phases > 0 && self.price_refine(eps)?;
505 #[cfg(not(feature = "heur-price-refinement"))]
506 let skipped = false;
507
508 if skipped {
509 self.stats.refinement_skips += 1;
510 } else if self.refine(eps)? {
511 // Already exactly optimal — every remaining phase is a no-op.
512 self.stats.scaling_phases += 1;
513 self.stats.early_exit = true;
514 return Ok(());
515 }
516 self.stats.scaling_phases += 1;
517
518 // The phase ended with an ε-optimal flow — refine produced one,
519 // or refinement proved one — which is the exact hypothesis of the
520 // fixing theorem: arc fixing is done after every execution of
521 // refine [cite: GOLDBERG-1997 §3.3]. Pointless after the final
522 // phase; the solve is over.
523 #[cfg(feature = "heur-arc-fixing")]
524 if eps > 1 {
525 self.fix_at_boundary(eps)?;
526 }
527
528 if eps == 1 {
529 return Ok(());
530 }
531 }
532 }
533
534 /// Retire every live residual entry whose reduced cost exceeds `2nε`,
535 /// together with its partner, at a phase boundary where the flow is
536 /// ε-optimal [cite: GOLDBERG-1997 §3.3].
537 ///
538 /// # Why the flow on such an arc can never change again
539 ///
540 /// Goldberg states the threshold and attributes the justification to
541 /// Goldberg & Tarjan and to Tardos [cite: GOLDBERG-1997 §3.3, citing
542 /// GOLDBERG-TARJAN-1990; TARDOS-1985]. The argument, reproduced here so
543 /// this crate does not rest on an uncheckable step
544 /// (`docs/ALGORITHM.md` §7.4): let `(f, p)` be ε-optimal on the current
545 /// live network and `a` a live residual entry with `c_p(a) > 2nε ≥
546 /// (2n−1)ε`. Suppose some later flow `f′` of the same (live) problem,
547 /// ε′-optimal for any `ε′ ≤ ε`, differs from `f` on `a`. The circulation
548 /// `f′ − f` decomposes into simple cycles; one of them, `Γ`, moves flow
549 /// on `a` or on its partner.
550 ///
551 /// * If `f′(a) > f(a)`, then `Γ ∋ a` is residual in `G_f`, so its cost is
552 /// `c(Γ) = Σ_Γ c_p > 2nε − (n−1)ε > nε`; but `Γ` reversed is residual
553 /// in `G_{f′}`, so `c(Γ) ≤ nε′ ≤ nε` — contradiction.
554 /// * If `f′(a) < f(a)`, the partner entry would have to be residual in
555 /// `G_f` with `c_p = −c_p(a) < −ε`, contradicting ε-optimality; so the
556 /// flow sits at the bound that direction cannot leave.
557 ///
558 /// Every subsequent state of this solver — and every optimal flow, which
559 /// is 0-optimal — is such an `f′`, so freezing the pair and solving the
560 /// reduced problem loses nothing: an optimal flow of the reduced problem
561 /// plus the frozen values is an optimal flow of the unreduced one, by
562 /// induction over boundaries. The reduced problem stays feasible for the
563 /// same reason — the restriction of any optimal flow witnesses it — so
564 /// an active node always keeps a live residual path to a deficit and
565 /// `relabel` cannot starve. No un-fixing pass is needed at this
566 /// threshold: the theorem quantifies over the entire rest of the solve.
567 #[cfg(feature = "heur-arc-fixing")]
568 fn fix_at_boundary(&mut self, eps: Cost) -> Result<(), SolveError> {
569 let node_count = self.normalized.res.node_count;
570 let Some(threshold) = Cost::try_from(node_count)
571 .ok()
572 .and_then(|n| n.checked_mul(2))
573 .and_then(|n2| n2.checked_mul(eps))
574 else {
575 // Unrepresentable threshold: fix nothing. A heuristic must never
576 // turn a solvable instance into an error.
577 return Ok(());
578 };
579
580 for u in 0..node_count {
581 let mut i = self.normalized.res.first_out[u] as usize;
582 while i < self.normalized.res.active_end[u] as usize {
583 let res = &self.normalized.res;
584 if res.cap[i] > 0 {
585 let v = res.head[i] as usize;
586 // A heuristic never gets to be the error site: if this
587 // reduced cost overflows, abandon the scan and let the
588 // mainline saturation pass, which computes the very same
589 // value, be the one that reports it.
590 let Ok(rc) = reduced_cost(res.cost[i], self.price[u], self.price[v]) else {
591 return Ok(());
592 };
593 if rc > threshold {
594 self.normalized.res.fix_pair(i, u);
595 self.stats.arcs_fixed += 1;
596 // A live entry was swapped into `i`; re-examine it.
597 continue;
598 }
599 }
600 i += 1;
601 }
602 }
603 // One pass over the live entries; charge it like the update sweep.
604 self.charge_many(node_count as u64)
605 }
606
607 /// Try to prove the current *flow* ε-optimal for the new, smaller ε by
608 /// adjusting potentials only, and skip the whole refine when it verifies
609 /// [cite: GOLDBERG-1997 §3.2; KIRALY-KOVACS-2012 §3.3].
610 ///
611 /// Follows the pass structure of Goldberg's price refine heuristic. Each
612 /// pass topologically sorts the admissible graph — a cycle there fails
613 /// the attempt immediately, which is what makes failure cheap — then
614 /// computes nonpositive approximate distances `d` in units of ε over the
615 /// admissible DAG and raises every price by `−d(v)·ε`. If the flow now
616 /// verifies ε-optimal the phase is skipped; otherwise the raise is kept —
617 /// following the paper's observation that the work is not lost — and
618 /// another pass runs, up to a small cap. Without the bucket sharpening
619 /// (below), a kept raise repairs admissible arcs but can push
620 /// non-admissible residual arcs further below −ε for the next refine to
621 /// saturate; measured across the benchmark families the keep is a large
622 /// net win in the default composition (2026-08-07 report), which is why
623 /// it stays.
624 /// One deliberate simplification against the paper: the bucket-based
625 /// sharpening pass over non-admissible arcs (from the scaling
626 /// shortest-paths algorithm [cite: GOLDBERG-1995-SP]) is not implemented;
627 /// it improves how often a pass suffices, never what a success means.
628 ///
629 /// **A skip does not rest on the search being right.** Every raise is
630 /// computed aside and adopted only whole, and the skip itself is gated on
631 /// an explicit `c_p ≥ −ε` re-check of every live residual arc — the
632 /// certifier discipline applied inside the solver. A defect in the pass
633 /// can only fail to find a certificate, never manufacture one. Overflow
634 /// anywhere abandons the attempt without adopting the offending pass's
635 /// raise, so every adopted price state is one whose live residual
636 /// reduced costs the mainline can compute.
637 ///
638 /// Prices only ever rise here (`d ≤ 0`), matching the rest of the
639 /// solver; under `heur-arc-fixing` the scan covers live arcs only — the
640 /// reduced problem is the one being solved, and fixed arcs stay fixed
641 /// because the fixing theorem is a statement about flows, indifferent to
642 /// potentials.
643 #[cfg(feature = "heur-price-refinement")]
644 fn price_refine(&mut self, eps: Cost) -> Result<bool, SolveError> {
645 // The paper bounds passes by O(n); in practice success comes in the
646 // first couple and failure announces itself as an admissible cycle in
647 // the very first, so a small cap only trims pathological attempts.
648 const PASS_CAP: u32 = 8;
649
650 let node_count = self.normalized.res.node_count;
651 for _ in 0..PASS_CAP {
652 // Kahn's algorithm over the admissible subgraph (live residual
653 // arcs with negative reduced cost). Deterministic: the initial
654 // queue is filled in node order and processed FIFO.
655 self.refine_indegree.clear();
656 self.refine_indegree.resize(node_count, 0);
657 for u in 0..node_count {
658 for a in self.normalized.res.out_arcs(u) {
659 if self.normalized.res.cap[a] <= 0 {
660 continue;
661 }
662 let v = self.normalized.res.head[a] as usize;
663 // Abandon on overflow rather than erroring the solve: a
664 // heuristic never gets to be the error site, and the
665 // mainline refine computes the same value anyway.
666 let Ok(rc) =
667 reduced_cost(self.normalized.res.cost[a], self.price[u], self.price[v])
668 else {
669 return Ok(false);
670 };
671 if rc < 0 {
672 self.refine_indegree[v] += 1;
673 }
674 }
675 }
676 self.refine_queue.clear();
677 for v in 0..node_count {
678 if self.refine_indegree[v] == 0 {
679 self.refine_queue.push_back(v as u32);
680 }
681 }
682
683 // Process in topological order, relaxing d(w) ≤ d(v) + ⌈c_p/ε⌉
684 // over admissible arcs; d ≤ 0, in units of ε. For an admissible
685 // arc, ⌈c_p/ε⌉ = −⌊−c_p/ε⌋.
686 self.refine_dist.clear();
687 self.refine_dist.resize(node_count, 0);
688 let mut processed = 0usize;
689 while let Some(u) = self.refine_queue.pop_front() {
690 let u = u as usize;
691 processed += 1;
692 let du = self.refine_dist[u];
693 for a in self.normalized.res.out_arcs(u) {
694 if self.normalized.res.cap[a] <= 0 {
695 continue;
696 }
697 let v = self.normalized.res.head[a] as usize;
698 let Ok(rc) =
699 reduced_cost(self.normalized.res.cost[a], self.price[u], self.price[v])
700 else {
701 return Ok(false);
702 };
703 if rc >= 0 {
704 continue;
705 }
706 // ⌈rc/ε⌉ for rc < 0, ε ≥ 1, as (rc + ε − 1) ⌊/⌋ ε — no
707 // negation, so rc = i64::MIN has no panic path; the sum
708 // cannot overflow because rc is negative and ε − 1 ≥ 0.
709 let step = rc.saturating_add(eps - 1).div_euclid(eps);
710 let candidate = du.saturating_add(step);
711 if candidate < self.refine_dist[v] {
712 self.refine_dist[v] = candidate;
713 }
714 self.refine_indegree[v] -= 1;
715 if self.refine_indegree[v] == 0 {
716 self.refine_queue.push_back(v as u32);
717 }
718 }
719 }
720 if processed < node_count {
721 // An admissible cycle. Its total reduced cost — equal to its
722 // true cost — is negative, so the flow is not optimal, and
723 // the topological pass this procedure repairs prices with
724 // cannot exist. Whether some other potentials could still
725 // certify ε-optimality (a short cycle of mean ≥ −ε might) is
726 // deliberately not decided: the paper's procedure fails the
727 // attempt on admissible cycles, and failing is conservative —
728 // after one linear-time pass.
729 self.charge_many(node_count as u64)?;
730 return Ok(false);
731 }
732
733 // Raise prices by −d(v)·ε, computed aside, adopted only whole.
734 let mut candidate = std::mem::take(&mut self.refine_price);
735 candidate.clear();
736 let mut raised_any = false;
737 for (&d, &price) in self.refine_dist.iter().zip(&self.price) {
738 let Some(units) = d.checked_neg() else {
739 self.refine_price = candidate;
740 return Ok(false);
741 };
742 raised_any |= units > 0;
743 let Ok(lift) = mul(units, eps, "refinement price lift") else {
744 self.refine_price = candidate;
745 return Ok(false);
746 };
747 let Ok(price) = add(price, lift, "refined price") else {
748 self.refine_price = candidate;
749 return Ok(false);
750 };
751 candidate.push(price);
752 }
753 // The gate runs against the candidate BEFORE adoption, for two
754 // verdicts at once: ε-optimality of the unchanged flow, arc by
755 // arc, and — the reason it must precede `copy_from_slice` —
756 // representability of every live residual reduced cost under the
757 // candidate prices. Adopting first would let a raise whose
758 // reduced costs overflow become the solver's state, surfacing
759 // later as a solve error on an instance that solves with the
760 // heuristic off. Gate-then-adopt keeps every adopted state one
761 // the mainline can compute over.
762 let mut certified = true;
763 'verify: for u in 0..node_count {
764 for a in self.normalized.res.out_arcs(u) {
765 if self.normalized.res.cap[a] <= 0 {
766 continue;
767 }
768 let v = self.normalized.res.head[a] as usize;
769 let Ok(rc) =
770 reduced_cost(self.normalized.res.cost[a], candidate[u], candidate[v])
771 else {
772 // Unrepresentable under the raise: abandon without
773 // adopting it. Prices stay at the last adopted —
774 // hence representable — state.
775 self.refine_price = candidate;
776 return Ok(false);
777 };
778 if rc < -eps {
779 certified = false;
780 break 'verify;
781 }
782 }
783 }
784
785 self.price.copy_from_slice(&candidate);
786 self.refine_price = candidate;
787 self.charge_many(node_count as u64)?;
788
789 if certified {
790 return Ok(true);
791 }
792 if !raised_any {
793 // A fixpoint that still fails cannot improve on repetition.
794 return Ok(false);
795 }
796 }
797 Ok(false)
798 }
799
800 /// One scaling phase: turn an ε′-optimal flow into an ε-optimal flow.
801 ///
802 /// Returns `true` when the flow is already **exactly** optimal, so the
803 /// caller can stop the scaling loop entirely.
804 fn refine(&mut self, eps: Cost) -> Result<bool, SolveError> {
805 let node_count = self.normalized.res.node_count;
806
807 // Saturating every admissible arc leaves a pseudoflow whose residual
808 // arcs all have non-negative reduced cost — 0-optimal, hence ε-optimal
809 // for the new, smaller ε. Excess appears; the rest of the phase
810 // eliminates it without ever dropping below −ε.
811 let mut saturated_any = false;
812 for u in 0..node_count {
813 for a in self.normalized.res.out_arcs(u) {
814 if self.normalized.res.cap[a] <= 0 {
815 continue;
816 }
817 let v = self.normalized.res.head[a] as usize;
818 if reduced_cost(self.normalized.res.cost[a], self.price[u], self.price[v])? < 0 {
819 let delta = self.normalized.res.cap[a];
820 self.normalized.excess[u] =
821 sub(self.normalized.excess[u], delta, "node excess")?;
822 self.normalized.excess[v] =
823 add(self.normalized.excess[v], delta, "node excess")?;
824 self.normalized.res.push(a, delta);
825 saturated_any = true;
826 }
827 }
828 }
829
830 // The saturation pass computes, for free, the one fact that can end the
831 // solve early: if it saturated nothing then every residual arc has
832 // c_p ≥ 0 under the current prices, and if nothing holds excess then
833 // the pseudoflow is a flow. A flow whose residual arcs all have
834 // non-negative reduced cost satisfies complementary slackness exactly
835 // — ε = 0, not ε = 1 — so it is optimal and every remaining phase
836 // would do nothing. Costs one bool; on long thin networks it skips
837 // most of the schedule.
838 if !saturated_any && !self.normalized.excess.iter().any(|&e| e > 0) {
839 return Ok(true);
840 }
841
842 self.current
843 .copy_from_slice(&self.normalized.res.first_out[..node_count]);
844 self.queue.clear();
845 self.queued.iter_mut().for_each(|q| *q = false);
846 for u in 0..node_count {
847 if self.normalized.excess[u] > 0 {
848 self.activate(u);
849 }
850 }
851
852 self.relabels_since_update = 0;
853 self.global_update(eps)?;
854
855 while let Some(u) = self.next_active() {
856 if self.normalized.excess[u] <= 0 {
857 continue;
858 }
859 self.discharge(u, eps)?;
860
861 // Prices drift as relabels accumulate; recomputing them globally
862 // once per n relabels keeps the admissible graph pointed at the
863 // deficits instead of letting it decay — the paper's starting
864 // point for the update frequency [cite: GOLDBERG-1997 §3.1].
865 if self.relabels_since_update >= node_count as u64 {
866 self.relabels_since_update = 0;
867 self.global_update(eps)?;
868 self.current
869 .copy_from_slice(&self.normalized.res.first_out[..node_count]);
870 }
871 }
872 Ok(false)
873 }
874
875 /// Move all excess off `u`, relabelling whenever no admissible arc remains.
876 ///
877 /// Push, relabel, the current-arc pointer and this loop are the max-flow
878 /// push-relabel method with reduced costs in place of distance labels
879 /// [cite: GOLDBERG-TARJAN-1988]. Goldberg (1997) §1 describes the method as
880 /// combining cost scaling with "the push-relabel maximum flow method of
881 /// Goldberg and Tarjan", and its §2.2 specifies the current-arc pointer in
882 /// the form used here: set to the node's first arc initially and after each
883 /// relabel of that node.
884 fn discharge(&mut self, u: usize, eps: Cost) -> Result<(), SolveError> {
885 // Spans only shrink at phase boundaries, never inside a refine, so
886 // the live end can be cached for the whole call.
887 let span_end = self.normalized.res.live_end(u);
888
889 while self.normalized.excess[u] > 0 {
890 while self.current[u] < span_end {
891 let a = self.current[u] as usize;
892 if self.normalized.res.cap[a] <= 0 {
893 self.current[u] += 1;
894 continue;
895 }
896 let v = self.normalized.res.head[a] as usize;
897 if reduced_cost(self.normalized.res.cost[a], self.price[u], self.price[v])? >= 0 {
898 self.current[u] += 1;
899 continue;
900 }
901
902 // Pushing into a node that cannot pass the flow on just moves
903 // the excess one hop and comes straight back. Relabel it first.
904 if self.lookahead(v, eps)? {
905 continue;
906 }
907
908 let delta = self.normalized.excess[u].min(self.normalized.res.cap[a]);
909 let was_active = self.normalized.excess[v] > 0;
910 self.normalized.res.push(a, delta);
911 self.normalized.excess[u] -= delta;
912 self.normalized.excess[v] = add(self.normalized.excess[v], delta, "node excess")?;
913 self.stats.pushes += 1;
914 self.charge()?;
915 if !was_active && self.normalized.excess[v] > 0 {
916 self.activate(v);
917 }
918 if self.normalized.excess[u] == 0 {
919 return Ok(());
920 }
921 }
922
923 if !self.relabel(u, eps)? {
924 // Feasibility was established up front, so an active node
925 // always retains a residual arc towards a deficit — and under
926 // arc fixing, a live one: the reduced problem left by sound
927 // boundary fixing is itself feasible
928 // (`docs/ALGORITHM.md` §7.4).
929 return Err(SolveError::InvariantViolated {
930 what: "active node has excess but no residual outgoing arc",
931 });
932 }
933 self.current[u] = self.normalized.res.first_out[u];
934 }
935 Ok(())
936 }
937
938 /// Raise `p(u)` by the least amount that makes one live residual arc
939 /// admissible, keeping every live residual arc at `c_p ≥ −ε`.
940 ///
941 /// Returns `false` when `u` has no live residual outgoing arc at all.
942 fn relabel(&mut self, u: usize, eps: Cost) -> Result<bool, SolveError> {
943 let mut best: Option<Cost> = None;
944 for a in self.normalized.res.out_arcs(u) {
945 if self.normalized.res.cap[a] <= 0 {
946 continue;
947 }
948 let v = self.normalized.res.head[a] as usize;
949 let candidate = add(
950 self.normalized.res.cost[a],
951 self.price[v],
952 "relabel candidate",
953 )?;
954 best = Some(best.map_or(candidate, |b: Cost| b.min(candidate)));
955 }
956 let Some(minimum) = best else {
957 return Ok(false);
958 };
959
960 let raised = add(minimum, eps, "relabelled price")?;
961 if raised <= self.price[u] {
962 return Err(SolveError::InvariantViolated {
963 what: "relabel did not raise the price of an unadmissible node",
964 });
965 }
966 self.price[u] = raised;
967 self.stats.relabels += 1;
968 self.relabels_since_update += 1;
969 self.charge()?;
970 Ok(true)
971 }
972
973 /// Does `v` have an admissible residual arc under the current prices?
974 ///
975 /// Scans from `v`'s **current-arc pointer**, not from the start of its
976 /// span, and advances it over what it rejects. Arcs before the pointer are
977 /// already known inadmissible, and the discipline that establishes that
978 /// (§ `discharge`) holds for `v` whoever is asking. Restarting the scan
979 /// each time re-examined the same dead arcs on every push into `v`, which
980 /// is why push-lookahead measured as a *loss* on dense bipartite families:
981 /// the work was quadratic in `v`'s degree rather than amortised.
982 #[cfg(feature = "heur-push-lookahead")]
983 fn has_admissible(&mut self, v: usize) -> Result<bool, Overflow> {
984 let span_end = self.normalized.res.live_end(v);
985 while self.current[v] < span_end {
986 let a = self.current[v] as usize;
987 if self.normalized.res.cap[a] > 0 {
988 let w = self.normalized.res.head[a] as usize;
989 if reduced_cost(self.normalized.res.cost[a], self.price[v], self.price[w])? < 0 {
990 return Ok(true);
991 }
992 }
993 self.current[v] += 1;
994 }
995 Ok(false)
996 }
997
998 /// Push-lookahead. Returns whether prices changed, in which case
999 /// the caller must re-evaluate the arc it was about to push along.
1000 #[cfg(feature = "heur-push-lookahead")]
1001 fn lookahead(&mut self, v: usize, eps: Cost) -> Result<bool, SolveError> {
1002 // Only for a node with *exactly* zero excess, and this is not a
1003 // refinement — it is the difference between terminating and not.
1004 //
1005 // A node with negative excess is a deficit: it absorbs flow, which is
1006 // the whole objective, so pushing into it is productive and relabelling
1007 // it is actively wrong. Doing so raises the price the excess is trying
1008 // to descend towards, the excess chases it, and the two escalate
1009 // without bound. A node with positive excess is already active and
1010 // will discharge itself. Only the zero-excess case — where an arriving
1011 // unit must immediately be passed on — is worth looking ahead for.
1012 if self.normalized.excess[v] != 0 || self.has_admissible(v)? {
1013 return Ok(false);
1014 }
1015 if !self.relabel(v, eps)? {
1016 return Ok(false);
1017 }
1018 self.current[v] = self.normalized.res.first_out[v];
1019 self.stats.lookahead_relabels += 1;
1020 Ok(true)
1021 }
1022
1023 #[cfg(not(feature = "heur-push-lookahead"))]
1024 #[allow(clippy::unnecessary_wraps)]
1025 fn lookahead(&mut self, _v: usize, _eps: Cost) -> Result<bool, SolveError> {
1026 Ok(false)
1027 }
1028
1029 /// Global price update: recompute every price from the distance
1030 /// to the nearest deficit, measured in units of ε — the set-relabel /
1031 /// price-update heuristic [cite: GOLDBERG-1997 §3.1].
1032 ///
1033 /// Arc lengths are `ℓ(v,w) = max(0, ⌊c_p(v,w)/ε⌋ + 1)`, which are
1034 /// non-negative, so a Dijkstra-style sweep suffices. Raising `p(v)` by
1035 /// `d(v)·ε` preserves ε-optimality: on any residual arc the reduced cost
1036 /// changes by `(d(w) − d(v))·ε ≥ −ℓ(v,w)·ε`, and `c_p − ℓ·ε ≥ −ε` by
1037 /// construction.
1038 ///
1039 /// The sweep itself is [`Self::update_sweep`], which has two
1040 /// implementations — a binary heap, and the Dial-style buckets of
1041 /// `heur-bucket-update` — each seeding itself from the deficits, since
1042 /// the two queues are seeded differently. The unreachable fallback and
1043 /// adopt-or-abandon below are shared.
1044 #[cfg(feature = "heur-global-update")]
1045 fn global_update(&mut self, eps: Cost) -> Result<(), SolveError> {
1046 let node_count = self.normalized.res.node_count;
1047
1048 // Scratch held on the engine and reserved to its worst case in
1049 // `Engine::new`, so an update allocates nothing however often it runs.
1050 self.update_dist.clear();
1051 self.update_dist.resize(node_count, UNREACHED);
1052
1053 if !self.update_sweep(eps)? {
1054 // No deficit anywhere: nothing to measure distances to.
1055 return Ok(());
1056 }
1057
1058 // Nodes that cannot reach any deficit are raised by the largest finite
1059 // distance. Anything less would leave an arc from a raised node into
1060 // an unraised one with a reduced cost below −ε.
1061 //
1062 // Distances are additionally truncated at the sweep's ceiling, which
1063 // is finite only under `heur-bucket-update`. Truncating a
1064 // shortest-distance labelling at a *uniform* cap preserves the
1065 // relaxation invariant `d(v) ≤ d(w) + ℓ(v,w)` that the ε-optimality
1066 // argument above needs — either both sides are below the cap and
1067 // nothing changed, or the left side is the cap and the right is at
1068 // least it.
1069 //
1070 // The two rules meet in one case worth spelling out, because the
1071 // ceiling changes the old reasoning. Without a ceiling, a residual
1072 // arc `v→w` whose head is reachable forces its tail to be reachable
1073 // too, so an unreachable node never sits above a reachable one. With
1074 // a ceiling, `v` *can* stay unreachable while `w` merely sits past
1075 // the ceiling, unscanned, so that implication no longer holds on its
1076 // own — but if anything was truncated then the fallback, taken over
1077 // the *truncated* distances, is the ceiling itself, and `v` and `w`
1078 // are lifted by the same amount. Computing the fallback after
1079 // `min(ceiling)` rather than before is what makes that true; the
1080 // `.map()` below is load-bearing, not cosmetic.
1081 let ceiling = self.sweep_ceiling();
1082 let fallback = self
1083 .update_dist
1084 .iter()
1085 .copied()
1086 .filter(|&d| d != UNREACHED)
1087 .map(|d| d.min(ceiling))
1088 .max()
1089 .unwrap_or(0);
1090
1091 // Compute the new prices aside and adopt them only if every one fits.
1092 // A heuristic may change the route to the optimum; it may never change
1093 // whether an instance is solvable, so an overflow here abandons the
1094 // update instead of failing the solve.
1095 let mut lifted = std::mem::take(&mut self.update_lifted);
1096 lifted.clear();
1097 for (&distance, &price) in self.update_dist.iter().zip(&self.price) {
1098 let d = if distance == UNREACHED {
1099 fallback
1100 } else {
1101 distance.min(ceiling)
1102 };
1103 let Ok(lift) = mul(d, eps, "global update price lift") else {
1104 self.update_lifted = lifted;
1105 return Ok(());
1106 };
1107 let Ok(price) = add(price, lift, "globally updated price") else {
1108 self.update_lifted = lifted;
1109 return Ok(());
1110 };
1111 lifted.push(price);
1112 }
1113 self.price.copy_from_slice(&lifted);
1114 self.update_lifted = lifted;
1115
1116 self.stats.global_updates += 1;
1117 // The sweep touched every node and every residual arc; charge for it.
1118 self.charge_many(node_count as u64)?;
1119 Ok(())
1120 }
1121
1122 /// Largest distance the sweep can report, in units of ε. Unbounded for
1123 /// the heap sweep; the bucket count for the bucket sweep.
1124 #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
1125 #[inline]
1126 fn sweep_ceiling(&self) -> i64 {
1127 self.bucket_ceiling
1128 }
1129
1130 /// The heap sweep represents any distance an `i64` can hold, so nothing
1131 /// is ever truncated and `min(ceiling)` in [`Self::global_update`] is a
1132 /// no-op.
1133 #[cfg(all(feature = "heur-global-update", not(feature = "heur-bucket-update")))]
1134 #[inline]
1135 #[allow(clippy::unused_self)]
1136 fn sweep_ceiling(&self) -> i64 {
1137 i64::MAX
1138 }
1139
1140 /// Fill `update_dist` with each node's distance to the nearest deficit
1141 /// over *residual* arcs, in units of ε. Returns `false` when the instance
1142 /// has no deficit at all, in which case there is nothing to update.
1143 ///
1144 /// Binary-heap sweep: `O(m log n)`, ties broken by node id so the heap
1145 /// order is total and the result is reproducible across platforms.
1146 #[cfg(all(feature = "heur-global-update", not(feature = "heur-bucket-update")))]
1147 fn update_sweep(&mut self, eps: Cost) -> Result<bool, SolveError> {
1148 use std::cmp::Reverse;
1149
1150 self.update_heap.clear();
1151 for (v, &excess) in self.normalized.excess.iter().enumerate() {
1152 if excess < 0 {
1153 self.update_dist[v] = 0;
1154 self.update_heap.push(Reverse((0, v as u32)));
1155 }
1156 }
1157 if self.update_heap.is_empty() {
1158 return Ok(false);
1159 }
1160
1161 while let Some(Reverse((d, w))) = self.update_heap.pop() {
1162 let w = w as usize;
1163 if d > self.update_dist[w] {
1164 continue;
1165 }
1166 for a in self.normalized.res.out_arcs(w) {
1167 let Some((v, candidate)) = self.relax(a, w, d, eps)? else {
1168 continue;
1169 };
1170 self.update_dist[v] = candidate;
1171 self.update_heap.push(Reverse((candidate, v as u32)));
1172 }
1173 }
1174 Ok(true)
1175 }
1176
1177 /// Dial-style bucket sweep: `O(m + n)` with constant amortised queue cost,
1178 /// which is what the reference implementation uses for this heuristic
1179 /// [cite: GOLDBERG-1997 §3.1; GOLDBERG-1995-SP §6, §9].
1180 ///
1181 /// Lengths are non-negative integers and a scan of bucket `i` can only
1182 /// insert into bucket `i` or above, so one monotone pass over the bucket
1183 /// array visits every node in non-decreasing distance order — Dijkstra's
1184 /// order, without a heap. Buckets are singly-linked through an arena, and
1185 /// a decrease-key is a plain re-insertion: the older entry is left in
1186 /// place and skipped when popped, since `update_dist` is the authority on
1187 /// a node's current distance.
1188 ///
1189 /// The array holds `2n + 1` buckets, so the ceiling is `2n`. Prices move
1190 /// by `O(nε)` within a refine, so the sweep *chooses not to pursue* a
1191 /// distance beyond that — it does arise, and often: nodes past the
1192 /// ceiling are recorded but not inserted, which is the truncation
1193 /// [`Self::global_update`] accounts for and `update_truncations` counts.
1194 #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
1195 fn update_sweep(&mut self, eps: Cost) -> Result<bool, SolveError> {
1196 let ceiling = self.bucket_ceiling;
1197 self.bucket_head.fill(BUCKET_NIL);
1198 self.bucket_arena.clear();
1199
1200 let mut seeded = false;
1201 for v in 0..self.normalized.res.node_count {
1202 if self.normalized.excess[v] < 0 {
1203 self.update_dist[v] = 0;
1204 // Seeds cannot exhaust the arena: there are at most `n` of
1205 // them and `n ≤ MAX_NODES = u32::MAX`, so the last seed's
1206 // index is below the `BUCKET_NIL` sentinel. Silently dropping
1207 // a *deficit* would be unsound — it would leave a distance-0
1208 // node unscanned while its neighbours took the fallback — so
1209 // this is asserted rather than assumed.
1210 let pushed = self.bucket_push(0, v);
1211 debug_assert!(pushed, "a deficit seed must always fit the arena");
1212 seeded = true;
1213 }
1214 }
1215 if !seeded {
1216 return Ok(false);
1217 }
1218
1219 // Walk only as far as the buckets actually reach. The array is sized
1220 // for the worst case (`2n`), but a sweep whose furthest node settles
1221 // at distance 3 has no business stepping over the other `2n − 3`
1222 // empty chains. Insertions never target a bucket below the current
1223 // index, so tracking the high-water mark as we go is enough.
1224 let mut index: i64 = 0;
1225 let mut highest: i64 = 0;
1226 while index <= highest {
1227 loop {
1228 let entry = self.bucket_head[index as usize];
1229 if entry == BUCKET_NIL {
1230 break;
1231 }
1232 let (node, next) = self.bucket_arena[entry as usize];
1233 self.bucket_head[index as usize] = next;
1234 let w = node as usize;
1235 // Stale entry from a decrease-key, or a node already scanned
1236 // at a smaller distance.
1237 if self.update_dist[w] != index {
1238 continue;
1239 }
1240 for a in self.normalized.res.out_arcs(w) {
1241 let Some((v, candidate)) = self.relax(a, w, index, eps)? else {
1242 continue;
1243 };
1244 self.update_dist[v] = candidate;
1245 // Past the ceiling — or, unreachably in practice, past
1246 // what the arena can index — the distance is recorded but
1247 // never scanned, and truncated back to the ceiling when
1248 // the lift is applied. Both are the same sound
1249 // truncation, and both are counted.
1250 if candidate <= ceiling && self.bucket_push(candidate as usize, v) {
1251 highest = highest.max(candidate);
1252 } else {
1253 self.stats.update_truncations += 1;
1254 }
1255 }
1256 }
1257 index += 1;
1258 }
1259 Ok(true)
1260 }
1261
1262 /// Relax the residual arc that enters `w` through out-entry `a`, given
1263 /// `w`'s settled distance `d`. Returns the tail and its improved distance,
1264 /// or `None` when the arc is not residual or offers no improvement.
1265 ///
1266 /// The sweep runs backwards — reaching `v` from `w` means `v` can send
1267 /// flow towards `w` — so the arc examined is the *reverse* entry of `a`.
1268 /// Under arc fixing only live spans are walked, and a live entry's partner
1269 /// is live too, so fixed arcs are never seen: the update serves the
1270 /// reduced problem, which is the one being solved
1271 /// (`docs/ALGORITHM.md` §7.4).
1272 #[cfg(feature = "heur-global-update")]
1273 #[inline]
1274 fn relax(
1275 &self,
1276 a: usize,
1277 w: usize,
1278 d: i64,
1279 eps: Cost,
1280 ) -> Result<Option<(usize, i64)>, SolveError> {
1281 let incoming = self.normalized.res.rev[a] as usize;
1282 if self.normalized.res.cap[incoming] <= 0 {
1283 return Ok(None);
1284 }
1285 let v = self.normalized.res.head[a] as usize;
1286 let rc = reduced_cost(
1287 self.normalized.res.cost[incoming],
1288 self.price[v],
1289 self.price[w],
1290 )?;
1291 let length = rc.div_euclid(eps).saturating_add(1).max(0);
1292 let candidate = d.saturating_add(length);
1293 if candidate < self.update_dist[v] {
1294 Ok(Some((v, candidate)))
1295 } else {
1296 Ok(None)
1297 }
1298 }
1299
1300 /// Prepend `node` to bucket `index`. Returns `false` only if the arena
1301 /// has reached the one index it may not use — `BUCKET_NIL` — which needs
1302 /// more entries than a representable instance can produce; the caller
1303 /// then treats the node as truncated, which is sound for the same reason
1304 /// the ceiling is.
1305 #[cfg(all(feature = "heur-global-update", feature = "heur-bucket-update"))]
1306 #[inline]
1307 fn bucket_push(&mut self, index: usize, node: usize) -> bool {
1308 let Ok(entry) = u32::try_from(self.bucket_arena.len()) else {
1309 return false;
1310 };
1311 if entry == BUCKET_NIL {
1312 return false;
1313 }
1314 self.bucket_arena
1315 .push((node as u32, self.bucket_head[index]));
1316 self.bucket_head[index] = entry;
1317 true
1318 }
1319
1320 #[cfg(not(feature = "heur-global-update"))]
1321 #[allow(clippy::unnecessary_wraps)]
1322 fn global_update(&mut self, _eps: Cost) -> Result<(), SolveError> {
1323 Ok(())
1324 }
1325
1326 fn activate(&mut self, v: usize) {
1327 if self.queued[v] {
1328 return;
1329 }
1330 self.queued[v] = true;
1331 match self.selection {
1332 ActiveNodeOrder::Fifo => self.queue.push_back(v as u32),
1333 ActiveNodeOrder::Lifo => self.queue.push_front(v as u32),
1334 }
1335 }
1336
1337 fn next_active(&mut self) -> Option<usize> {
1338 let v = self.queue.pop_front()? as usize;
1339 self.queued[v] = false;
1340 Some(v)
1341 }
1342
1343 /// Charge one unit against the caller's operation budget.
1344 fn charge(&mut self) -> Result<(), SolveError> {
1345 self.charge_many(1)
1346 }
1347
1348 /// Charge `units` against the caller's operation budget.
1349 ///
1350 /// Pushes and relabels are not the only work worth charging for: a global
1351 /// update sweeps the whole graph and, measured, dominates the running time
1352 /// on the shapes this crate exists to serve. A budget that ignored it
1353 /// would not be a time proxy at all — the same instance can differ by more
1354 /// than an order of magnitude in operations-per-second depending on how
1355 /// often the sweep runs.
1356 fn charge_many(&mut self, units: u64) -> Result<(), SolveError> {
1357 self.operations = self.operations.saturating_add(units);
1358 match self.budget {
1359 Some(budget) if self.operations > budget => Err(SolveError::OperationBudgetExhausted {
1360 budget,
1361 scaling_phases: self.stats.scaling_phases,
1362 }),
1363 _ => Ok(()),
1364 }
1365 }
1366}