Skip to main content

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}