Skip to main content

tpt_math_graph/
lib.rs

1#![no_std]
2#![forbid(unsafe_code)]
3#![allow(clippy::needless_range_loop)]
4//! Graph mathematics for the `tpt-math` substrate.
5//!
6//! `tpt-math-graph` wraps [`petgraph`] (dual `Apache-2.0 OR MIT`, `no_std` +
7//! `alloc`) for the adjacency structures, topological sort and shortest-path
8//! algorithms, and builds the **max-flow** solver in-house on top (petgraph
9//! has no built-in max-flow — an upstream feature request has been open since
10//! 2021).
11//!
12//! # Wrap-vs-in-house split
13//!
14//! * **Thin wrap** — [`Graph`], [`StableGraph`], [`GraphMap`], [`NodeIndex`],
15//!   [`EdgeIndex`], [`Directed`]/[`Undirected`], and [`toposort`] are re-exported
16//!   directly from `petgraph`.
17//! * **In-house** — [`max_flow`] (Edmonds–Karp) is implemented here, operating
18//!   on `petgraph`'s directed [`Graph`] with `f64` edge capacities.
19//!
20//! [`petgraph`]: petgraph
21//!
22//! # Features
23//!
24//! * `std` (default) — enable the `std` support of dependencies.
25//! * `alloc` — signal allocator availability (the algorithms need it).
26//!
27//! # Examples
28//!
29//! ```
30//! use tpt_math_graph::{Graph, Directed, NodeIndex};
31//!
32//! let mut g: Graph<&str, f64> = Graph::new();
33//! let a = g.add_node("a");
34//! let b = g.add_node("b");
35//! g.add_edge(a, b, 1.0);
36//! assert_eq!(g.node_count(), 2);
37//! ```
38
39extern crate alloc;
40
41use alloc::collections::{BTreeMap, BinaryHeap, VecDeque};
42use alloc::vec;
43use alloc::vec::Vec;
44use core::cmp::Ordering;
45
46use petgraph::graph::IndexType;
47use petgraph::visit::EdgeRef;
48use petgraph::Direction;
49
50pub use petgraph;
51
52// Re-export the adjacency types so downstream code can build graphs through
53// `tpt-math-graph` without naming `petgraph` directly.
54pub use petgraph::algo::toposort;
55pub use petgraph::graph::{EdgeIndex, Graph, NodeIndex};
56pub use petgraph::graphmap::GraphMap;
57pub use petgraph::stable_graph::StableGraph;
58pub use petgraph::{Directed, Undirected};
59
60/// Errors returned by the graph algorithms in this crate.
61#[derive(Debug, Clone, PartialEq, Eq)]
62#[non_exhaustive]
63pub enum GraphError {
64    /// The requested operation cannot run because the source equals the sink.
65    SourceEqualsSink,
66    /// A topological sort was requested on a graph that contains a cycle.
67    Cycle,
68    /// An edge weight (or, for [`max_flow`], a capacity) is negative, NaN or,
69    /// for capacities, infinite. Dijkstra and A* require non-negative weights.
70    InvalidWeight,
71}
72
73// ===========================================================================
74// In-house max-flow (Edmonds–Karp)
75// ===========================================================================
76
77/// The result of a [`max_flow`] computation.
78#[derive(Debug, Clone, PartialEq)]
79pub struct MaxFlow {
80    /// Total flow from source to sink.
81    pub value: f64,
82    /// Flow on each original directed edge, indexed by `EdgeIndex::index()`.
83    pub edge_flow: Vec<f64>,
84}
85
86#[derive(Clone)]
87struct ResEdge {
88    to: usize,
89    cap: f64,
90    rev: usize,
91}
92
93/// Compute the maximum flow from `source` to `sink` in a directed
94/// [`Graph`] whose edge weights are capacities (`f64`).
95///
96/// Uses the Edmonds–Karp algorithm (BFS-augmented Ford–Fulkerson) over an
97/// in-house residual graph, so it needs no `std` collections.
98pub fn max_flow<N, Ix>(
99    graph: &Graph<N, f64, Directed, Ix>,
100    source: NodeIndex<Ix>,
101    sink: NodeIndex<Ix>,
102) -> Result<MaxFlow, GraphError>
103where
104    Ix: IndexType,
105{
106    if source == sink {
107        return Err(GraphError::SourceEqualsSink);
108    }
109    if graph.edge_weights().any(|c| !c.is_finite() || *c < 0.0) {
110        return Err(GraphError::InvalidWeight);
111    }
112    let n = graph.node_count();
113    let m = graph.edge_count();
114    let mut res: Vec<Vec<ResEdge>> = (0..n).map(|_| Vec::new()).collect();
115    let mut caps: Vec<f64> = Vec::with_capacity(m);
116    // For each original edge, record the (node, residual-entry) of its forward
117    // residual edge so we can recover the realised flow at the end.
118    let mut fwd_of: Vec<(usize, usize)> = Vec::with_capacity(m);
119
120    for e in graph.edge_indices() {
121        let (u, v) = graph.edge_endpoints(e).unwrap();
122        let ui = u.index();
123        let vi = v.index();
124        let c = graph[e];
125        caps.push(c);
126        let fwd = res[ui].len();
127        let bwd = res[vi].len();
128        res[ui].push(ResEdge {
129            to: vi,
130            cap: c,
131            rev: bwd,
132        });
133        res[vi].push(ResEdge {
134            to: ui,
135            cap: 0.0,
136            rev: fwd,
137        });
138        fwd_of.push((ui, fwd));
139    }
140
141    let s = source.index();
142    let t = sink.index();
143    // Residual capacities are considered present while they exceed a tiny
144    // tolerance *relative to the largest capacity*, so small-but-real
145    // capacities are kept while rounding residue is still ignored.
146    let max_cap = caps.iter().fold(0.0_f64, |acc, &c| acc.max(c));
147    let eps = max_cap * f64::EPSILON;
148    let mut total = 0.0_f64;
149
150    loop {
151        let mut parent: Vec<usize> = (0..n).map(|_| usize::MAX).collect();
152        let mut parent_edge: Vec<usize> = (0..n).map(|_| 0).collect();
153        let mut cap_to: Vec<f64> = (0..n).map(|_| 0.0).collect();
154        let mut queue: VecDeque<usize> = VecDeque::new();
155        queue.push_back(s);
156        parent[s] = s;
157        cap_to[s] = f64::INFINITY;
158
159        while let Some(u) = queue.pop_front() {
160            let mut ki = 0;
161            while ki < res[u].len() {
162                let re = &res[u][ki];
163                let to = re.to;
164                let c = re.cap;
165                if c > eps && parent[to] == usize::MAX {
166                    parent[to] = u;
167                    parent_edge[to] = ki;
168                    cap_to[to] = cap_to[u].min(c);
169                    if to == t {
170                        queue.clear();
171                        break;
172                    }
173                    queue.push_back(to);
174                }
175                ki += 1;
176            }
177        }
178
179        if parent[t] == usize::MAX {
180            break;
181        }
182        let flow = cap_to[t];
183        let mut v = t;
184        while v != s {
185            let u = parent[v];
186            let k = parent_edge[v];
187            res[u][k].cap -= flow;
188            let rev = res[u][k].rev;
189            res[v][rev].cap += flow;
190            v = u;
191        }
192        total += flow;
193    }
194
195    let mut edge_flow = vec![0.0_f64; m];
196    for (ei, &(ui, fwd)) in fwd_of.iter().enumerate() {
197        edge_flow[ei] = caps[ei] - res[ui][fwd].cap;
198    }
199
200    Ok(MaxFlow {
201        value: total,
202        edge_flow,
203    })
204}
205
206// ===========================================================================
207// Convenience shortest-path wrappers (in-house, on petgraph Graph)
208// ===========================================================================
209
210/// Open-set entry for Dijkstra and A*, ordered so that [`BinaryHeap`] pops the
211/// smallest `f` first. Only non-NaN keys are ever inserted.
212#[derive(Clone, Copy, PartialEq)]
213struct OpenNode {
214    f: f64,
215    node: usize,
216}
217
218impl Eq for OpenNode {}
219
220impl PartialOrd for OpenNode {
221    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
222        Some(self.cmp(other))
223    }
224}
225
226impl Ord for OpenNode {
227    fn cmp(&self, other: &Self) -> Ordering {
228        other
229            .f
230            .total_cmp(&self.f)
231            .then_with(|| other.node.cmp(&self.node))
232    }
233}
234
235/// Reject negative and NaN edge weights, which Dijkstra and A* cannot handle.
236fn check_non_negative<N, Ix>(graph: &Graph<N, f64, Directed, Ix>) -> Result<(), GraphError>
237where
238    Ix: IndexType,
239{
240    if graph.edge_weights().any(|w| w.is_nan() || *w < 0.0) {
241        Err(GraphError::InvalidWeight)
242    } else {
243        Ok(())
244    }
245}
246
247/// Shortest-path distance from `source` to `target` via Dijkstra, using edge
248/// weights as non-negative costs. Returns `None` if `target` is unreachable.
249///
250/// # Panics
251///
252/// Panics if any edge weight is negative or NaN. Use [`try_dijkstra`] to get
253/// an error instead.
254pub fn dijkstra<N, Ix>(
255    graph: &Graph<N, f64, Directed, Ix>,
256    source: NodeIndex<Ix>,
257    target: Option<NodeIndex<Ix>>,
258) -> BTreeMap<usize, f64>
259where
260    Ix: IndexType,
261{
262    try_dijkstra(graph, source, target).unwrap_or_else(|e| panic!("dijkstra failed: {e:?}"))
263}
264
265/// Fallible [`dijkstra`].
266///
267/// # Errors
268///
269/// Returns [`GraphError::InvalidWeight`] if any edge weight is negative or NaN.
270pub fn try_dijkstra<N, Ix>(
271    graph: &Graph<N, f64, Directed, Ix>,
272    source: NodeIndex<Ix>,
273    target: Option<NodeIndex<Ix>>,
274) -> Result<BTreeMap<usize, f64>, GraphError>
275where
276    Ix: IndexType,
277{
278    check_non_negative(graph)?;
279    // Reuse petgraph's Dijkstra when on `std`; in `no_std` run the same
280    // algorithm over our own binary heap so it stays allocator-only.
281    #[cfg(feature = "std")]
282    {
283        let _ = target;
284        use petgraph::algo::dijkstra as pg_dijkstra;
285        let dist = pg_dijkstra(graph, source, target, |e| *e.weight());
286        let mut out = BTreeMap::new();
287        for (k, v) in dist {
288            out.insert(k.index(), v);
289        }
290        Ok(out)
291    }
292    #[cfg(not(feature = "std"))]
293    {
294        Ok(in_house_dijkstra(graph, source, target))
295    }
296}
297
298/// Dijkstra over the crate's own binary heap, with no `std` collections.
299///
300/// The default `std` build calls petgraph instead, so this function is what the
301/// `no_std` build runs. It stays compiled under `std` too, and a test checks that
302/// it agrees with petgraph on the same graphs.
303#[cfg_attr(feature = "std", allow(dead_code))]
304fn in_house_dijkstra<N, Ix>(
305    graph: &Graph<N, f64, Directed, Ix>,
306    source: NodeIndex<Ix>,
307    target: Option<NodeIndex<Ix>>,
308) -> BTreeMap<usize, f64>
309where
310    Ix: IndexType,
311{
312    let mut dist: BTreeMap<usize, f64> = BTreeMap::new();
313    dist.insert(source.index(), 0.0);
314    let mut visited: BTreeMap<usize, bool> = BTreeMap::new();
315    let mut heap = BinaryHeap::new();
316    heap.push(OpenNode {
317        f: 0.0,
318        node: source.index(),
319    });
320    while let Some(OpenNode { f: d, node: u }) = heap.pop() {
321        if visited.contains_key(&u) {
322            continue; // settled earlier with a distance no larger than `d`
323        }
324        visited.insert(u, true);
325        if target.is_some_and(|tg| tg.index() == u) {
326            break;
327        }
328        for e in graph.edges_directed(NodeIndex::<Ix>::new(u), Direction::Outgoing) {
329            let v = e.target().index();
330            let nd = d + *e.weight();
331            if nd < dist.get(&v).copied().unwrap_or(f64::INFINITY) {
332                dist.insert(v, nd);
333                heap.push(OpenNode { f: nd, node: v });
334            }
335        }
336    }
337    dist
338}
339
340/// A path as its total cost and the node sequence from source to target.
341pub type ShortestPath<Ix> = (f64, Vec<NodeIndex<Ix>>);
342
343/// Shortest path from `source` to `target`, as its total cost and the node
344/// sequence `source, …, target`.
345///
346/// Returns `Ok(None)` when `target` is unreachable. Uses the in-house Dijkstra
347/// loop on every feature set, so the predecessor bookkeeping is the same under
348/// `std` and `no_std`. [`dijkstra`] returns distances only.
349///
350/// # Errors
351///
352/// Returns [`GraphError::InvalidWeight`] if any edge weight is negative or NaN.
353///
354/// # Examples
355///
356/// ```
357/// use tpt_math_graph::{Graph, NodeIndex};
358///
359/// let mut g: Graph<(), f64> = Graph::new();
360/// let a = g.add_node(());
361/// let b = g.add_node(());
362/// let c = g.add_node(());
363/// g.add_edge(a, b, 1.0);
364/// g.add_edge(b, c, 1.0);
365/// g.add_edge(a, c, 5.0);
366/// let (cost, path) = tpt_math_graph::dijkstra_path(&g, a, c).unwrap().unwrap();
367/// assert_eq!(cost, 2.0);
368/// assert_eq!(path, vec![a, b, c]);
369/// ```
370pub fn dijkstra_path<N, Ix>(
371    graph: &Graph<N, f64, Directed, Ix>,
372    source: NodeIndex<Ix>,
373    target: NodeIndex<Ix>,
374) -> Result<Option<ShortestPath<Ix>>, GraphError>
375where
376    Ix: IndexType,
377{
378    check_non_negative(graph)?;
379    let goal = target.index();
380    let mut dist: BTreeMap<usize, f64> = BTreeMap::new();
381    let mut pred: BTreeMap<usize, usize> = BTreeMap::new();
382    let mut settled: BTreeMap<usize, bool> = BTreeMap::new();
383    dist.insert(source.index(), 0.0);
384    let mut heap = BinaryHeap::new();
385    heap.push(OpenNode {
386        f: 0.0,
387        node: source.index(),
388    });
389    while let Some(OpenNode { f: d, node: u }) = heap.pop() {
390        if settled.contains_key(&u) {
391            continue;
392        }
393        settled.insert(u, true);
394        if u == goal {
395            break;
396        }
397        for e in graph.edges_directed(NodeIndex::<Ix>::new(u), Direction::Outgoing) {
398            let v = e.target().index();
399            let nd = d + *e.weight();
400            if nd < dist.get(&v).copied().unwrap_or(f64::INFINITY) {
401                dist.insert(v, nd);
402                pred.insert(v, u);
403                heap.push(OpenNode { f: nd, node: v });
404            }
405        }
406    }
407    if !settled.contains_key(&goal) {
408        return Ok(None);
409    }
410    let cost = dist[&goal];
411    let mut path = vec![NodeIndex::<Ix>::new(goal)];
412    let mut cur = goal;
413    while cur != source.index() {
414        cur = pred[&cur];
415        path.push(NodeIndex::<Ix>::new(cur));
416    }
417    path.reverse();
418    Ok(Some((cost, path)))
419}
420
421/// A* shortest path from `start` to the first node satisfying `is_goal`,
422/// using edge weights as costs and `heuristic` as the admissible estimate.
423/// Returns `(cost, path)` or `None` if no path exists.
424///
425/// # Panics
426///
427/// Panics if any edge weight is negative or NaN. Use [`try_astar`] to get an
428/// error instead.
429pub fn astar<N, Ix, F, H>(
430    graph: &Graph<N, f64, Directed, Ix>,
431    start: NodeIndex<Ix>,
432    is_goal: F,
433    heuristic: H,
434) -> Option<AStarPath<Ix>>
435where
436    Ix: IndexType,
437    F: Fn(NodeIndex<Ix>) -> bool,
438    H: Fn(NodeIndex<Ix>) -> f64,
439{
440    try_astar(graph, start, is_goal, heuristic).unwrap_or_else(|e| panic!("astar failed: {e:?}"))
441}
442
443/// The cost and node sequence of a shortest path found by A*.
444pub type AStarPath<Ix> = (f64, Vec<NodeIndex<Ix>>);
445
446/// Fallible [`astar`].
447///
448/// # Errors
449///
450/// Returns [`GraphError::InvalidWeight`] if any edge weight is negative or NaN.
451pub fn try_astar<N, Ix, F, H>(
452    graph: &Graph<N, f64, Directed, Ix>,
453    start: NodeIndex<Ix>,
454    is_goal: F,
455    heuristic: H,
456) -> Result<Option<AStarPath<Ix>>, GraphError>
457where
458    Ix: IndexType,
459    F: Fn(NodeIndex<Ix>) -> bool,
460    H: Fn(NodeIndex<Ix>) -> f64,
461{
462    check_non_negative(graph)?;
463    let s = start.index();
464    let mut g_score: BTreeMap<usize, f64> = BTreeMap::new();
465    g_score.insert(s, 0.0);
466    let mut came_from: BTreeMap<usize, usize> = BTreeMap::new();
467    let mut open: BinaryHeap<OpenNode> = BinaryHeap::new();
468    let h0 = heuristic(start);
469    if !h0.is_nan() {
470        open.push(OpenNode { f: h0, node: s });
471    }
472
473    // Each push follows a strict improvement of some g-score, so the search
474    // terminates on a finite graph whatever the heuristic returns.
475    while let Some(OpenNode { f, node: u }) = open.pop() {
476        let gu = *g_score.get(&u).unwrap_or(&f64::INFINITY);
477        let node_u = NodeIndex::<Ix>::new(u);
478        // Skip stale entries: a cheaper route to `u` was found after this push.
479        if f > gu + heuristic(node_u) {
480            continue;
481        }
482        if is_goal(node_u) {
483            // Reconstruct path.
484            let mut path = Vec::new();
485            let mut cur = u;
486            path.push(NodeIndex::<Ix>::new(cur));
487            while let Some(&p) = came_from.get(&cur) {
488                path.push(NodeIndex::<Ix>::new(p));
489                cur = p;
490            }
491            path.reverse();
492            return Ok(Some((gu, path)));
493        }
494
495        for e in graph.edges_directed(node_u, Direction::Outgoing) {
496            let v = e.target().index();
497            let tentative = gu + *e.weight();
498            let vg = g_score.get(&v).copied().unwrap_or(f64::INFINITY);
499            if tentative < vg {
500                came_from.insert(v, u);
501                g_score.insert(v, tentative);
502                let f = tentative + heuristic(NodeIndex::new(v));
503                if !f.is_nan() {
504                    open.push(OpenNode { f, node: v });
505                }
506            }
507        }
508    }
509    Ok(None)
510}
511
512// ===========================================================================
513// Traversal, spanning trees and components (thin wraps over petgraph)
514// ===========================================================================
515
516/// Nodes reachable from `start` in breadth-first order, `start` first.
517///
518/// Edges are followed in their stored direction for directed graphs.
519pub fn bfs_order<N, E, Ty, Ix>(
520    graph: &petgraph::Graph<N, E, Ty, Ix>,
521    start: NodeIndex<Ix>,
522) -> Vec<NodeIndex<Ix>>
523where
524    Ty: petgraph::EdgeType,
525    Ix: IndexType,
526{
527    let mut order = Vec::new();
528    let mut bfs = petgraph::visit::Bfs::new(graph, start);
529    while let Some(n) = bfs.next(graph) {
530        order.push(n);
531    }
532    order
533}
534
535/// Nodes reachable from `start` in depth-first (preorder) order, `start` first.
536///
537/// Edges are followed in their stored direction for directed graphs.
538pub fn dfs_order<N, E, Ty, Ix>(
539    graph: &petgraph::Graph<N, E, Ty, Ix>,
540    start: NodeIndex<Ix>,
541) -> Vec<NodeIndex<Ix>>
542where
543    Ty: petgraph::EdgeType,
544    Ix: IndexType,
545{
546    let mut order = Vec::new();
547    let mut dfs = petgraph::visit::Dfs::new(graph, start);
548    while let Some(n) = dfs.next(graph) {
549        order.push(n);
550    }
551    order
552}
553
554/// Whether a directed path from `from` to `to` exists (`from == to` is `true`).
555pub fn has_path<N, E, Ix>(
556    graph: &Graph<N, E, Directed, Ix>,
557    from: NodeIndex<Ix>,
558    to: NodeIndex<Ix>,
559) -> bool
560where
561    Ix: IndexType,
562{
563    petgraph::algo::has_path_connecting(graph, from, to, None)
564}
565
566/// Whether the directed graph contains a cycle.
567pub fn is_cyclic<N, E, Ix>(graph: &Graph<N, E, Directed, Ix>) -> bool
568where
569    Ix: IndexType,
570{
571    petgraph::algo::is_cyclic_directed(graph)
572}
573
574/// The number of connected components of an undirected graph.
575///
576/// Edge directions are ignored. For a directed graph this counts the weakly
577/// connected components.
578pub fn connected_components<N, E, Ty, Ix>(graph: &petgraph::Graph<N, E, Ty, Ix>) -> usize
579where
580    Ty: petgraph::EdgeType,
581    Ix: IndexType,
582{
583    petgraph::algo::connected_components(graph)
584}
585
586/// The strongly connected components of a directed graph, in reverse
587/// topological order of the condensation (Tarjan's algorithm).
588pub fn strongly_connected_components<N, E, Ix>(
589    graph: &Graph<N, E, Directed, Ix>,
590) -> Vec<Vec<NodeIndex<Ix>>>
591where
592    Ix: IndexType,
593{
594    petgraph::algo::tarjan_scc(graph)
595}
596
597/// A minimum spanning forest, as `(source, target, weight)` triples.
598///
599/// Edge directions are ignored. Each component of the input contributes a
600/// spanning tree, so a disconnected graph yields a forest. Ties are broken by
601/// petgraph's ordering, so the result is deterministic for a given graph.
602///
603/// The total weight can be summed by the caller; the edges are returned in the
604/// order Kruskal's algorithm accepts them.
605pub fn minimum_spanning_tree<N, E, Ty, Ix>(
606    graph: &petgraph::Graph<N, E, Ty, Ix>,
607) -> Vec<(NodeIndex<Ix>, NodeIndex<Ix>, E)>
608where
609    N: Clone,
610    E: Clone + PartialOrd,
611    Ty: petgraph::EdgeType,
612    Ix: IndexType,
613{
614    use petgraph::data::Element;
615    petgraph::algo::min_spanning_tree(graph)
616        .filter_map(|element| match element {
617            Element::Edge {
618                source,
619                target,
620                weight,
621            } => Some((NodeIndex::new(source), NodeIndex::new(target), weight)),
622            Element::Node { .. } => None,
623        })
624        .collect()
625}
626
627// ===========================================================================
628// Tests
629// ===========================================================================
630
631#[cfg(test)]
632mod tests {
633    use super::*;
634
635    fn small_dag() -> (Graph<&'static str, f64>, NodeIndex, NodeIndex, NodeIndex) {
636        let mut g: Graph<&str, f64> = Graph::new();
637        let a = g.add_node("a");
638        let b = g.add_node("b");
639        let c = g.add_node("c");
640        g.add_edge(a, b, 1.0);
641        g.add_edge(b, c, 1.0);
642        g.add_edge(a, c, 1.0);
643        (g, a, b, c)
644    }
645
646    #[test]
647    fn toposort_orders_dag() {
648        let (g, a, b, c) = {
649            let (g, a, b, c) = small_dag();
650            // rename to avoid unused
651            (g, a, b, c)
652        };
653        let order = toposort(&g, None).expect("DAG has a topological order");
654        let pos = |n: NodeIndex| order.iter().position(|&x| x == n).unwrap();
655        assert!(pos(a) < pos(b));
656        assert!(pos(b) < pos(c));
657        assert!(pos(a) < pos(c));
658    }
659
660    #[test]
661    fn dijkstra_finds_shortest_distance() {
662        let (g, a, _b, c) = small_dag();
663        let dist = dijkstra(&g, a, Some(c));
664        // Direct a->c costs 1.0; a->b->c also costs 2.0; shortest is 1.0.
665        assert!((dist[&c.index()] - 1.0).abs() < 1e-12);
666    }
667
668    #[test]
669    fn dijkstra_path_reconstructs_the_shortest_route() {
670        let (g, a, _b, c) = small_dag();
671        // Direct a->c and a->b->c both cost 1.0 in small_dag, so a tie is allowed.
672        let (cost, path) = dijkstra_path(&g, a, c).unwrap().unwrap();
673        assert!((cost - 1.0).abs() < 1e-12);
674        assert_eq!(path.first(), Some(&a));
675        assert_eq!(path.last(), Some(&c));
676        // Path edges must exist and sum to the cost.
677        let mut total = 0.0;
678        for w in path.windows(2) {
679            let e = g.find_edge(w[0], w[1]).expect("path uses real edges");
680            total += g[e];
681        }
682        assert!((total - cost).abs() < 1e-12);
683        assert_eq!(dijkstra_path(&g, a, a).unwrap(), Some((0.0, vec![a])));
684        assert_eq!(dijkstra_path(&g, c, a).unwrap(), None);
685    }
686
687    #[test]
688    fn dijkstra_path_prefers_the_longer_cheaper_route() {
689        let mut g: Graph<(), f64> = Graph::new();
690        let a = g.add_node(());
691        let b = g.add_node(());
692        let c = g.add_node(());
693        g.add_edge(a, b, 1.0);
694        g.add_edge(b, c, 1.0);
695        g.add_edge(a, c, 5.0);
696        let (cost, path) = dijkstra_path(&g, a, c).unwrap().unwrap();
697        assert_eq!(cost, 2.0);
698        assert_eq!(path, vec![a, b, c]);
699    }
700
701    #[test]
702    fn astar_finds_path() {
703        let (g, a, _b, c) = small_dag();
704        let res = astar(&g, a, |n| n == c, |_| 0.0);
705        assert!(res.is_some());
706        let (cost, path) = res.unwrap();
707        assert!((cost - 1.0).abs() < 1e-12);
708        assert_eq!(path[0], a);
709        assert_eq!(path[path.len() - 1], c);
710    }
711
712    #[test]
713    fn max_flow_classic_network() {
714        // s -> a (3), s -> b (2), a -> b (1), a -> t (2), b -> t (3).
715        // Min cut = 5 (source out-capacity = sink in-capacity), so max flow = 5.
716        let mut g: Graph<&str, f64> = Graph::new();
717        let s = g.add_node("s");
718        let a = g.add_node("a");
719        let b = g.add_node("b");
720        let t = g.add_node("t");
721        g.add_edge(s, a, 3.0);
722        g.add_edge(s, b, 2.0);
723        g.add_edge(a, b, 1.0);
724        g.add_edge(a, t, 2.0);
725        g.add_edge(b, t, 3.0);
726        let mf = max_flow(&g, s, t).unwrap();
727        assert!((mf.value - 5.0).abs() < 1e-9, "got {}", mf.value);
728    }
729
730    #[test]
731    fn max_flow_zero_when_no_path() {
732        let mut g: Graph<&str, f64> = Graph::new();
733        let s = g.add_node("s");
734        let t = g.add_node("t");
735        g.add_node("mid");
736        let mf = max_flow(&g, s, t).unwrap();
737        assert_eq!(mf.value, 0.0);
738    }
739
740    #[test]
741    fn max_flow_bottleneck() {
742        // s -> a (3), s -> b (2); a -> t (3), b -> t (1); no a<->b edge.
743        // Sink in-capacity = 3 + 1 = 4, so max flow is capped at 4.
744        let mut g: Graph<&str, f64> = Graph::new();
745        let s = g.add_node("s");
746        let a = g.add_node("a");
747        let b = g.add_node("b");
748        let t = g.add_node("t");
749        g.add_edge(s, a, 3.0);
750        g.add_edge(s, b, 2.0);
751        g.add_edge(a, t, 3.0);
752        g.add_edge(b, t, 1.0);
753        let mf = max_flow(&g, s, t).unwrap();
754        assert!((mf.value - 4.0).abs() < 1e-9, "got {}", mf.value);
755        // b->t caps at 1, so s->b carries exactly 1; the rest (3) goes s->a -> a->t.
756        assert!(
757            (mf.edge_flow[0] - 3.0).abs() < 1e-9,
758            "s->a flow = {}",
759            mf.edge_flow[0]
760        );
761        assert!(
762            (mf.edge_flow[1] - 1.0).abs() < 1e-9,
763            "s->b flow = {}",
764            mf.edge_flow[1]
765        );
766        assert!(
767            (mf.edge_flow[2] - 3.0).abs() < 1e-9,
768            "a->t flow = {}",
769            mf.edge_flow[2]
770        );
771        assert!(
772            (mf.edge_flow[3] - 1.0).abs() < 1e-9,
773            "b->t flow = {}",
774            mf.edge_flow[3]
775        );
776    }
777
778    #[test]
779    fn max_flow_rejects_equal_endpoints() {
780        let mut g: Graph<&str, f64> = Graph::new();
781        let s = g.add_node("s");
782        assert_eq!(max_flow(&g, s, s), Err(GraphError::SourceEqualsSink));
783    }
784
785    #[test]
786    fn max_flow_keeps_small_capacities() {
787        // A fixed 1e-12 cutoff used to discard this edge entirely.
788        let mut g: Graph<&str, f64> = Graph::new();
789        let s = g.add_node("s");
790        let t = g.add_node("t");
791        g.add_edge(s, t, 1e-14);
792        let mf = max_flow(&g, s, t).unwrap();
793        assert!((mf.value - 1e-14).abs() < 1e-20, "got {}", mf.value);
794    }
795
796    #[test]
797    fn max_flow_rejects_invalid_capacity() {
798        let mut g: Graph<&str, f64> = Graph::new();
799        let s = g.add_node("s");
800        let t = g.add_node("t");
801        g.add_edge(s, t, -1.0);
802        assert_eq!(max_flow(&g, s, t), Err(GraphError::InvalidWeight));
803    }
804
805    #[test]
806    fn astar_terminates_when_heuristic_is_infinite() {
807        // Every open node has f = inf. The old scan never removed anything and
808        // looped forever; the search must now finish. The goal is reachable,
809        // so it is still found with the true cost.
810        let (g, a, _b, c) = small_dag();
811        let (cost, _) = astar(&g, a, |n| n == c, |_| f64::INFINITY).unwrap();
812        assert!((cost - 1.0).abs() < 1e-12);
813
814        // The original hang: the goal is unreachable and every f is infinite.
815        let mut g2: Graph<&str, f64> = Graph::new();
816        let s = g2.add_node("s");
817        let isolated = g2.add_node("isolated");
818        g2.add_edge(s, s, 1.0);
819        assert!(astar(&g2, s, |n| n == isolated, |_| f64::INFINITY).is_none());
820    }
821
822    #[test]
823    fn astar_terminates_when_heuristic_is_nan() {
824        let (g, a, _b, c) = small_dag();
825        assert!(astar(&g, a, |n| n == c, |_| f64::NAN).is_none());
826    }
827
828    #[test]
829    fn astar_reopens_nodes_reached_by_a_cheaper_route() {
830        // a -> c costs 10 directly, but a -> b -> c costs 2. Whichever route
831        // reaches c first, the reported cost must be the cheaper one.
832        let mut g: Graph<&str, f64> = Graph::new();
833        let a = g.add_node("a");
834        let b = g.add_node("b");
835        let c = g.add_node("c");
836        g.add_edge(a, c, 10.0);
837        g.add_edge(a, b, 1.0);
838        g.add_edge(b, c, 1.0);
839        let (cost, path) = astar(&g, a, |n| n == c, |_| 0.0).unwrap();
840        assert!((cost - 2.0).abs() < 1e-12);
841        assert_eq!(path, vec![a, b, c]);
842    }
843
844    #[test]
845    fn try_dijkstra_rejects_negative_weight() {
846        let mut g: Graph<&str, f64> = Graph::new();
847        let a = g.add_node("a");
848        let b = g.add_node("b");
849        g.add_edge(a, b, -1.0);
850        assert_eq!(try_dijkstra(&g, a, None), Err(GraphError::InvalidWeight));
851    }
852
853    #[test]
854    fn try_astar_rejects_nan_weight() {
855        let mut g: Graph<&str, f64> = Graph::new();
856        let a = g.add_node("a");
857        let b = g.add_node("b");
858        g.add_edge(a, b, f64::NAN);
859        assert_eq!(
860            try_astar(&g, a, |n| n == b, |_| 0.0),
861            Err(GraphError::InvalidWeight)
862        );
863    }
864}
865
866#[cfg(test)]
867mod traversal_tests {
868    use super::*;
869
870    fn chain() -> (Graph<u8, f64>, Vec<NodeIndex>) {
871        // 0 -> 1 -> 2, 0 -> 3, 4 isolated.
872        let mut g: Graph<u8, f64> = Graph::new();
873        let n: Vec<NodeIndex> = (0..5).map(|i| g.add_node(i)).collect();
874        g.add_edge(n[0], n[1], 1.0);
875        g.add_edge(n[1], n[2], 1.0);
876        g.add_edge(n[0], n[3], 1.0);
877        (g, n)
878    }
879
880    #[test]
881    fn bfs_visits_by_level() {
882        let (g, n) = chain();
883        let order = bfs_order(&g, n[0]);
884        assert_eq!(order[0], n[0]);
885        assert_eq!(order.len(), 4);
886        // Both children of 0 come before the grandchild 2.
887        let pos = |x: NodeIndex| order.iter().position(|&y| y == x).unwrap();
888        assert!(pos(n[1]) < pos(n[2]));
889        assert!(pos(n[3]) < pos(n[2]));
890        assert!(!order.contains(&n[4]));
891    }
892
893    #[test]
894    fn dfs_goes_deep_first() {
895        let (g, n) = chain();
896        let order = dfs_order(&g, n[0]);
897        // Preorder: 0, then the first child's subtree before its sibling.
898        assert_eq!(order.len(), 4);
899        let pos = |x: NodeIndex| order.iter().position(|&y| y == x).unwrap();
900        assert!(pos(n[2]) < pos(n[3]) || pos(n[1]) < pos(n[3]));
901        assert_eq!(order[0], n[0]);
902    }
903
904    #[test]
905    fn reachability_and_cycles() {
906        let (mut g, n) = chain();
907        assert!(has_path(&g, n[0], n[2]));
908        assert!(!has_path(&g, n[2], n[0]));
909        assert!(has_path(&g, n[4], n[4]));
910        assert!(!is_cyclic(&g));
911        g.add_edge(n[2], n[0], 1.0);
912        assert!(is_cyclic(&g));
913    }
914
915    #[test]
916    fn components_ignore_direction() {
917        let (g, _) = chain();
918        // {0,1,2,3} and {4}.
919        assert_eq!(connected_components(&g), 2);
920    }
921
922    #[test]
923    fn strongly_connected_components_split_a_cycle() {
924        let mut g: Graph<(), ()> = Graph::new();
925        let a = g.add_node(());
926        let b = g.add_node(());
927        let c = g.add_node(());
928        g.add_edge(a, b, ());
929        g.add_edge(b, a, ());
930        g.add_edge(b, c, ());
931        let sccs = strongly_connected_components(&g);
932        assert_eq!(sccs.len(), 2);
933        let big = sccs.iter().find(|s| s.len() == 2).unwrap();
934        assert!(big.contains(&a) && big.contains(&b));
935    }
936
937    #[test]
938    fn spanning_tree_of_a_weighted_square() {
939        // Square 0-1-2-3-0 with a heavy diagonal 0-2 that must be skipped.
940        let mut g: Graph<(), f64> = Graph::new();
941        let n: Vec<NodeIndex> = (0..4).map(|_| g.add_node(())).collect();
942        g.add_edge(n[0], n[1], 1.0);
943        g.add_edge(n[1], n[2], 2.0);
944        g.add_edge(n[2], n[3], 3.0);
945        g.add_edge(n[3], n[0], 4.0);
946        g.add_edge(n[0], n[2], 10.0);
947        let mst = minimum_spanning_tree(&g);
948        assert_eq!(mst.len(), 3);
949        let total: f64 = mst.iter().map(|&(_, _, w)| w).sum();
950        assert_eq!(total, 6.0);
951    }
952
953    #[test]
954    fn spanning_forest_for_disconnected_graph() {
955        let (g, _) = {
956            let mut g: Graph<(), f64> = Graph::new();
957            let n: Vec<NodeIndex> = (0..4).map(|_| g.add_node(())).collect();
958            g.add_edge(n[0], n[1], 1.0);
959            g.add_edge(n[2], n[3], 2.0);
960            (g, n)
961        };
962        // Two components, so two edges: a forest with n - c = 2 edges.
963        assert_eq!(minimum_spanning_tree(&g).len(), 2);
964    }
965
966    /// The classic augmenting-path example that needs a residual (reverse) edge:
967    /// the first path s→a→b→t must be partly undone to reach flow 2.
968    #[test]
969    fn max_flow_must_use_residual_reverse_edges() {
970        let mut g: Graph<&str, f64> = Graph::new();
971        let s = g.add_node("s");
972        let a = g.add_node("a");
973        let b = g.add_node("b");
974        let t = g.add_node("t");
975        g.add_edge(s, a, 1.0);
976        g.add_edge(a, b, 1.0);
977        g.add_edge(b, t, 1.0);
978        g.add_edge(s, b, 1.0);
979        g.add_edge(a, t, 1.0);
980        assert_eq!(max_flow(&g, s, t).unwrap().value, 2.0);
981    }
982
983    #[test]
984    fn max_flow_accepts_zero_capacities_and_returns_zero_without_a_path() {
985        let mut g: Graph<&str, f64> = Graph::new();
986        let s = g.add_node("s");
987        let t = g.add_node("t");
988        g.add_edge(s, t, 0.0);
989        assert_eq!(max_flow(&g, s, t).unwrap().value, 0.0);
990    }
991
992    #[test]
993    fn dijkstra_accepts_zero_weights() {
994        let mut g: Graph<u8, f64> = Graph::new();
995        let n: Vec<NodeIndex> = (0..3).map(|i| g.add_node(i)).collect();
996        g.add_edge(n[0], n[1], 0.0);
997        g.add_edge(n[1], n[2], 0.0);
998        let d = try_dijkstra(&g, n[0], None).unwrap();
999        assert_eq!(d[&n[2].index()], 0.0);
1000    }
1001
1002    #[test]
1003    fn dijkstra_sums_weights_along_multi_hop_paths() {
1004        // 0 →(2) 1 →(3) 2: the distance to 2 is 5.
1005        let mut g: Graph<u8, f64> = Graph::new();
1006        let n: Vec<NodeIndex> = (0..3).map(|i| g.add_node(i)).collect();
1007        g.add_edge(n[0], n[1], 2.0);
1008        g.add_edge(n[1], n[2], 3.0);
1009        let d = try_dijkstra(&g, n[0], None).unwrap();
1010        assert_eq!(d[&n[1].index()], 2.0);
1011        assert_eq!(d[&n[2].index()], 5.0);
1012    }
1013
1014    #[test]
1015    fn dijkstra_improves_a_tentative_distance_when_a_cheaper_route_appears() {
1016        // Direct edge 0→1 costs 5, but 0→2→1 costs 2 and must replace it.
1017        let mut g: Graph<u8, f64> = Graph::new();
1018        let n: Vec<NodeIndex> = (0..3).map(|i| g.add_node(i)).collect();
1019        g.add_edge(n[0], n[1], 5.0);
1020        g.add_edge(n[0], n[2], 1.0);
1021        g.add_edge(n[2], n[1], 1.0);
1022        let d = try_dijkstra(&g, n[0], None).unwrap();
1023        assert_eq!(d[&n[1].index()], 2.0);
1024        let (cost, path) = dijkstra_path(&g, n[0], n[1]).unwrap().unwrap();
1025        assert_eq!(cost, 2.0);
1026        assert_eq!(path, vec![n[0], n[2], n[1]]);
1027    }
1028
1029    #[test]
1030    fn dijkstra_path_stops_at_the_target_not_at_the_first_settled_node() {
1031        // Node 1 is settled first (weight 1) but is not the target; the target 2
1032        // is reached at cost 4 through node 1.
1033        let mut g: Graph<u8, f64> = Graph::new();
1034        let n: Vec<NodeIndex> = (0..4).map(|i| g.add_node(i)).collect();
1035        g.add_edge(n[0], n[1], 1.0);
1036        g.add_edge(n[1], n[2], 3.0);
1037        g.add_edge(n[0], n[3], 10.0);
1038        let (cost, path) = dijkstra_path(&g, n[0], n[2]).unwrap().unwrap();
1039        assert_eq!(cost, 4.0);
1040        assert_eq!(path, vec![n[0], n[1], n[2]]);
1041    }
1042
1043    #[test]
1044    fn astar_costs_sum_along_multi_hop_paths() {
1045        let mut g: Graph<u8, f64> = Graph::new();
1046        let n: Vec<NodeIndex> = (0..4).map(|i| g.add_node(i)).collect();
1047        g.add_edge(n[0], n[1], 1.0);
1048        g.add_edge(n[1], n[2], 2.0);
1049        g.add_edge(n[2], n[3], 4.0);
1050        g.add_edge(n[0], n[3], 20.0);
1051        let (cost, path) = try_astar(&g, n[0], |v| v == n[3], |_| 0.0)
1052            .unwrap()
1053            .unwrap();
1054        assert_eq!(cost, 7.0);
1055        assert_eq!(path, vec![n[0], n[1], n[2], n[3]]);
1056    }
1057
1058    #[test]
1059    fn negative_weight_is_rejected_but_zero_is_not() {
1060        let mut g: Graph<u8, f64> = Graph::new();
1061        let a = g.add_node(0);
1062        let b = g.add_node(1);
1063        g.add_edge(a, b, -0.0);
1064        assert!(try_dijkstra(&g, a, None).is_ok());
1065        g.add_edge(b, a, -1.0);
1066        assert!(try_dijkstra(&g, a, None).is_err());
1067    }
1068}
1069
1070#[cfg(test)]
1071mod in_house_dijkstra_tests {
1072    use super::*;
1073
1074    /// A deterministic pseudo-random weighted digraph on `n` nodes.
1075    fn random_graph(n: usize, seed: u64) -> Graph<u8, f64> {
1076        let mut g: Graph<u8, f64> = Graph::new();
1077        let nodes: Vec<NodeIndex> = (0..n).map(|i| g.add_node(i as u8)).collect();
1078        let mut state = seed;
1079        for u in 0..n {
1080            for v in 0..n {
1081                state = state
1082                    .wrapping_mul(6364136223846793005)
1083                    .wrapping_add(1442695040888963407);
1084                if u != v && (state >> 33) % 3 == 0 {
1085                    let w = ((state >> 40) % 9) as f64 + 0.5;
1086                    g.add_edge(nodes[u], nodes[v], w);
1087                }
1088            }
1089        }
1090        g
1091    }
1092
1093    #[test]
1094    fn in_house_dijkstra_matches_petgraph_on_random_graphs() {
1095        for seed in 1..25u64 {
1096            let g = random_graph(12, seed);
1097            let source = NodeIndex::new(0);
1098            let reference: BTreeMap<usize, f64> =
1099                petgraph::algo::dijkstra(&g, source, None, |e| *e.weight())
1100                    .into_iter()
1101                    .map(|(k, v)| (k.index(), v))
1102                    .collect();
1103            let ours = in_house_dijkstra(&g, source, None);
1104            assert_eq!(ours.len(), reference.len(), "seed {seed}");
1105            for (node, d) in &reference {
1106                assert!((ours[node] - d).abs() < 1e-9, "seed {seed}, node {node}");
1107            }
1108        }
1109    }
1110
1111    #[test]
1112    fn in_house_dijkstra_stops_at_the_target_with_its_distance_settled() {
1113        let mut g: Graph<u8, f64> = Graph::new();
1114        let n: Vec<NodeIndex> = (0..3).map(|i| g.add_node(i)).collect();
1115        g.add_edge(n[0], n[1], 1.0);
1116        g.add_edge(n[1], n[2], 1.0);
1117        let d = in_house_dijkstra(&g, n[0], Some(n[1]));
1118        assert_eq!(d[&n[1].index()], 1.0);
1119    }
1120}
1121
1122#[cfg(test)]
1123mod max_flow_min_cut_tests {
1124    use super::*;
1125
1126    /// Minimum s–t cut by enumerating every vertex subset that contains `s` and
1127    /// not `t`. Max-flow equals this value (max-flow min-cut theorem).
1128    fn brute_min_cut(n: usize, edges: &[(usize, usize, f64)], s: usize, t: usize) -> f64 {
1129        let mut best = f64::INFINITY;
1130        for mask in 0..(1u32 << n) {
1131            if mask & (1 << s) == 0 || mask & (1 << t) != 0 {
1132                continue;
1133            }
1134            let cut: f64 = edges
1135                .iter()
1136                .filter(|&&(u, v, _)| mask & (1 << u) != 0 && mask & (1 << v) == 0)
1137                .map(|&(_, _, c)| c)
1138                .sum();
1139            best = best.min(cut);
1140        }
1141        best
1142    }
1143
1144    #[test]
1145    fn max_flow_equals_the_brute_force_min_cut_on_random_graphs() {
1146        for seed in 1..300u64 {
1147            let n = 7usize;
1148            let mut state = seed.wrapping_mul(0x9E37_79B9_7F4A_7C15).wrapping_add(7);
1149            let mut next = || {
1150                state = state
1151                    .wrapping_mul(6364136223846793005)
1152                    .wrapping_add(1442695040888963407);
1153                state >> 33
1154            };
1155            let mut g: Graph<(), f64> = Graph::new();
1156            let nodes: Vec<NodeIndex> = (0..n).map(|_| g.add_node(())).collect();
1157            let mut edges = Vec::new();
1158            for u in 0..n {
1159                for v in 0..n {
1160                    if u != v && next() % 3 == 0 {
1161                        // Integer capacities keep the comparison exact.
1162                        let c = (next() % 7 + 1) as f64;
1163                        g.add_edge(nodes[u], nodes[v], c);
1164                        edges.push((u, v, c));
1165                    }
1166                }
1167            }
1168            let (s, t) = (0, n - 1);
1169            let flow = max_flow(&g, nodes[s], nodes[t]).unwrap().value;
1170            let cut = brute_min_cut(n, &edges, s, t);
1171            assert!(
1172                (flow - cut).abs() < 1e-9,
1173                "seed {seed}: flow {flow}, cut {cut}"
1174            );
1175        }
1176    }
1177
1178    /// All-pairs shortest distances by Floyd–Warshall (test oracle).
1179    fn floyd(n: usize, edges: &[(usize, usize, f64)]) -> Vec<Vec<f64>> {
1180        let mut d = vec![vec![f64::INFINITY; n]; n];
1181        for (i, row) in d.iter_mut().enumerate() {
1182            row[i] = 0.0;
1183        }
1184        for &(u, v, w) in edges {
1185            d[u][v] = d[u][v].min(w);
1186        }
1187        for k in 0..n {
1188            for i in 0..n {
1189                for j in 0..n {
1190                    let via = d[i][k] + d[k][j];
1191                    if via < d[i][j] {
1192                        d[i][j] = via;
1193                    }
1194                }
1195            }
1196        }
1197        d
1198    }
1199
1200    #[test]
1201    fn astar_with_an_admissible_heuristic_matches_the_true_distance() {
1202        // h(v) = ½·dist(v, goal) never overestimates, so A* must return the true
1203        // distance. A non-zero heuristic also exercises the f = g + h bookkeeping.
1204        for seed in 1..200u64 {
1205            let n = 8usize;
1206            let mut state = seed.wrapping_mul(0x2545_F491_4F6C_DD1D).wrapping_add(3);
1207            let mut next = || {
1208                state = state
1209                    .wrapping_mul(6364136223846793005)
1210                    .wrapping_add(1442695040888963407);
1211                state >> 33
1212            };
1213            let mut g: Graph<(), f64> = Graph::new();
1214            let nodes: Vec<NodeIndex> = (0..n).map(|_| g.add_node(())).collect();
1215            let mut edges = Vec::new();
1216            for u in 0..n {
1217                for v in 0..n {
1218                    if u != v && next() % 3 == 0 {
1219                        let w = (next() % 9 + 1) as f64;
1220                        g.add_edge(nodes[u], nodes[v], w);
1221                        edges.push((u, v, w));
1222                    }
1223                }
1224            }
1225            let goal = n - 1;
1226            let d = floyd(n, &edges);
1227            let h = |v: NodeIndex| {
1228                let dv = d[v.index()][goal];
1229                if dv.is_finite() {
1230                    0.5 * dv
1231                } else {
1232                    0.0
1233                }
1234            };
1235            let got = try_astar(&g, nodes[0], |v| v.index() == goal, h).unwrap();
1236            if d[0][goal].is_finite() {
1237                let (cost, path) = got.expect("a reachable goal must be found");
1238                assert!(
1239                    (cost - d[0][goal]).abs() < 1e-9,
1240                    "seed {seed}: {cost} vs {}",
1241                    d[0][goal]
1242                );
1243                assert_eq!(path.first().map(|p| p.index()), Some(0));
1244                assert_eq!(path.last().map(|p| p.index()), Some(goal));
1245            } else {
1246                assert!(
1247                    got.is_none(),
1248                    "seed {seed}: unreachable goal reported as found"
1249                );
1250            }
1251        }
1252    }
1253
1254    /// Unit-capacity bipartite matching networks. Augmenting paths here often
1255    /// have to cancel earlier flow along reverse residual edges, so this forces
1256    /// the residual bookkeeping the random graphs above rarely exercise.
1257    #[test]
1258    fn bipartite_matching_networks_need_residual_reversal_and_match_min_cut() {
1259        for seed in 1..200u64 {
1260            let (l, r) = (4usize, 4usize);
1261            // Nodes: 0 = source, 1..=l left, l+1..=l+r right, last = sink.
1262            let n = l + r + 2;
1263            let (s, t) = (0usize, n - 1);
1264            let mut state = seed.wrapping_mul(0x9E37_79B9_7F4A_7C15).wrapping_add(11);
1265            let mut next = || {
1266                state = state
1267                    .wrapping_mul(6364136223846793005)
1268                    .wrapping_add(1442695040888963407);
1269                state >> 33
1270            };
1271            let mut g: Graph<(), f64> = Graph::new();
1272            let nodes: Vec<NodeIndex> = (0..n).map(|_| g.add_node(())).collect();
1273            let mut edges = Vec::new();
1274            for i in 0..l {
1275                edges.push((s, 1 + i, 1.0));
1276            }
1277            for j in 0..r {
1278                edges.push((1 + l + j, t, 1.0));
1279            }
1280            for i in 0..l {
1281                for j in 0..r {
1282                    if next() % 2 == 0 {
1283                        edges.push((1 + i, 1 + l + j, 1.0));
1284                    }
1285                }
1286            }
1287            for &(u, v, c) in &edges {
1288                g.add_edge(nodes[u], nodes[v], c);
1289            }
1290            let flow = max_flow(&g, nodes[s], nodes[t]).unwrap().value;
1291            let cut = brute_min_cut(n, &edges, s, t);
1292            assert!(
1293                (flow - cut).abs() < 1e-9,
1294                "seed {seed}: flow {flow}, cut {cut}"
1295            );
1296        }
1297    }
1298}