1#![no_std]
2#![forbid(unsafe_code)]
3#![allow(clippy::needless_range_loop)]
4extern 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
52pub 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#[derive(Debug, Clone, PartialEq, Eq)]
62#[non_exhaustive]
63pub enum GraphError {
64 SourceEqualsSink,
66 Cycle,
68 InvalidWeight,
71}
72
73#[derive(Debug, Clone, PartialEq)]
79pub struct MaxFlow {
80 pub value: f64,
82 pub edge_flow: Vec<f64>,
84}
85
86#[derive(Clone)]
87struct ResEdge {
88 to: usize,
89 cap: f64,
90 rev: usize,
91}
92
93pub 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 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 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#[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
235fn 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
247pub 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
265pub 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 #[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#[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; }
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
340pub type ShortestPath<Ix> = (f64, Vec<NodeIndex<Ix>>);
342
343pub 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
421pub 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
443pub type AStarPath<Ix> = (f64, Vec<NodeIndex<Ix>>);
445
446pub 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 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 if f > gu + heuristic(node_u) {
480 continue;
481 }
482 if is_goal(node_u) {
483 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
512pub 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
535pub 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
554pub 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
566pub 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
574pub 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
586pub 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
597pub 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#[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 (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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 assert_eq!(minimum_spanning_tree(&g).len(), 2);
964 }
965
966 #[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 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 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 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 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 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 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 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 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 #[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 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}