#![no_std]
#![forbid(unsafe_code)]
#![allow(clippy::needless_range_loop)]
extern crate alloc;
use alloc::collections::{BTreeMap, BinaryHeap, VecDeque};
use alloc::vec;
use alloc::vec::Vec;
use core::cmp::Ordering;
use petgraph::graph::IndexType;
use petgraph::visit::EdgeRef;
use petgraph::Direction;
pub use petgraph;
pub use petgraph::algo::toposort;
pub use petgraph::graph::{EdgeIndex, Graph, NodeIndex};
pub use petgraph::graphmap::GraphMap;
pub use petgraph::stable_graph::StableGraph;
pub use petgraph::{Directed, Undirected};
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum GraphError {
SourceEqualsSink,
Cycle,
InvalidWeight,
}
#[derive(Debug, Clone, PartialEq)]
pub struct MaxFlow {
pub value: f64,
pub edge_flow: Vec<f64>,
}
#[derive(Clone)]
struct ResEdge {
to: usize,
cap: f64,
rev: usize,
}
pub fn max_flow<N, Ix>(
graph: &Graph<N, f64, Directed, Ix>,
source: NodeIndex<Ix>,
sink: NodeIndex<Ix>,
) -> Result<MaxFlow, GraphError>
where
Ix: IndexType,
{
if source == sink {
return Err(GraphError::SourceEqualsSink);
}
if graph.edge_weights().any(|c| !c.is_finite() || *c < 0.0) {
return Err(GraphError::InvalidWeight);
}
let n = graph.node_count();
let m = graph.edge_count();
let mut res: Vec<Vec<ResEdge>> = (0..n).map(|_| Vec::new()).collect();
let mut caps: Vec<f64> = Vec::with_capacity(m);
let mut fwd_of: Vec<(usize, usize)> = Vec::with_capacity(m);
for e in graph.edge_indices() {
let (u, v) = graph.edge_endpoints(e).unwrap();
let ui = u.index();
let vi = v.index();
let c = graph[e];
caps.push(c);
let fwd = res[ui].len();
let bwd = res[vi].len();
res[ui].push(ResEdge {
to: vi,
cap: c,
rev: bwd,
});
res[vi].push(ResEdge {
to: ui,
cap: 0.0,
rev: fwd,
});
fwd_of.push((ui, fwd));
}
let s = source.index();
let t = sink.index();
let max_cap = caps.iter().fold(0.0_f64, |acc, &c| acc.max(c));
let eps = max_cap * f64::EPSILON;
let mut total = 0.0_f64;
loop {
let mut parent: Vec<usize> = (0..n).map(|_| usize::MAX).collect();
let mut parent_edge: Vec<usize> = (0..n).map(|_| 0).collect();
let mut cap_to: Vec<f64> = (0..n).map(|_| 0.0).collect();
let mut queue: VecDeque<usize> = VecDeque::new();
queue.push_back(s);
parent[s] = s;
cap_to[s] = f64::INFINITY;
while let Some(u) = queue.pop_front() {
let mut ki = 0;
while ki < res[u].len() {
let re = &res[u][ki];
let to = re.to;
let c = re.cap;
if c > eps && parent[to] == usize::MAX {
parent[to] = u;
parent_edge[to] = ki;
cap_to[to] = cap_to[u].min(c);
if to == t {
queue.clear();
break;
}
queue.push_back(to);
}
ki += 1;
}
}
if parent[t] == usize::MAX {
break;
}
let flow = cap_to[t];
let mut v = t;
while v != s {
let u = parent[v];
let k = parent_edge[v];
res[u][k].cap -= flow;
let rev = res[u][k].rev;
res[v][rev].cap += flow;
v = u;
}
total += flow;
}
let mut edge_flow = vec![0.0_f64; m];
for (ei, &(ui, fwd)) in fwd_of.iter().enumerate() {
edge_flow[ei] = caps[ei] - res[ui][fwd].cap;
}
Ok(MaxFlow {
value: total,
edge_flow,
})
}
#[derive(Clone, Copy, PartialEq)]
struct OpenNode {
f: f64,
node: usize,
}
impl Eq for OpenNode {}
impl PartialOrd for OpenNode {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for OpenNode {
fn cmp(&self, other: &Self) -> Ordering {
other
.f
.total_cmp(&self.f)
.then_with(|| other.node.cmp(&self.node))
}
}
fn check_non_negative<N, Ix>(graph: &Graph<N, f64, Directed, Ix>) -> Result<(), GraphError>
where
Ix: IndexType,
{
if graph.edge_weights().any(|w| w.is_nan() || *w < 0.0) {
Err(GraphError::InvalidWeight)
} else {
Ok(())
}
}
pub fn dijkstra<N, Ix>(
graph: &Graph<N, f64, Directed, Ix>,
source: NodeIndex<Ix>,
target: Option<NodeIndex<Ix>>,
) -> BTreeMap<usize, f64>
where
Ix: IndexType,
{
try_dijkstra(graph, source, target).unwrap_or_else(|e| panic!("dijkstra failed: {e:?}"))
}
pub fn try_dijkstra<N, Ix>(
graph: &Graph<N, f64, Directed, Ix>,
source: NodeIndex<Ix>,
target: Option<NodeIndex<Ix>>,
) -> Result<BTreeMap<usize, f64>, GraphError>
where
Ix: IndexType,
{
check_non_negative(graph)?;
#[cfg(feature = "std")]
{
let _ = target;
use petgraph::algo::dijkstra as pg_dijkstra;
let dist = pg_dijkstra(graph, source, target, |e| *e.weight());
let mut out = BTreeMap::new();
for (k, v) in dist {
out.insert(k.index(), v);
}
Ok(out)
}
#[cfg(not(feature = "std"))]
{
Ok(in_house_dijkstra(graph, source, target))
}
}
#[cfg_attr(feature = "std", allow(dead_code))]
fn in_house_dijkstra<N, Ix>(
graph: &Graph<N, f64, Directed, Ix>,
source: NodeIndex<Ix>,
target: Option<NodeIndex<Ix>>,
) -> BTreeMap<usize, f64>
where
Ix: IndexType,
{
let mut dist: BTreeMap<usize, f64> = BTreeMap::new();
dist.insert(source.index(), 0.0);
let mut visited: BTreeMap<usize, bool> = BTreeMap::new();
let mut heap = BinaryHeap::new();
heap.push(OpenNode {
f: 0.0,
node: source.index(),
});
while let Some(OpenNode { f: d, node: u }) = heap.pop() {
if visited.contains_key(&u) {
continue; }
visited.insert(u, true);
if target.is_some_and(|tg| tg.index() == u) {
break;
}
for e in graph.edges_directed(NodeIndex::<Ix>::new(u), Direction::Outgoing) {
let v = e.target().index();
let nd = d + *e.weight();
if nd < dist.get(&v).copied().unwrap_or(f64::INFINITY) {
dist.insert(v, nd);
heap.push(OpenNode { f: nd, node: v });
}
}
}
dist
}
pub type ShortestPath<Ix> = (f64, Vec<NodeIndex<Ix>>);
pub fn dijkstra_path<N, Ix>(
graph: &Graph<N, f64, Directed, Ix>,
source: NodeIndex<Ix>,
target: NodeIndex<Ix>,
) -> Result<Option<ShortestPath<Ix>>, GraphError>
where
Ix: IndexType,
{
check_non_negative(graph)?;
let goal = target.index();
let mut dist: BTreeMap<usize, f64> = BTreeMap::new();
let mut pred: BTreeMap<usize, usize> = BTreeMap::new();
let mut settled: BTreeMap<usize, bool> = BTreeMap::new();
dist.insert(source.index(), 0.0);
let mut heap = BinaryHeap::new();
heap.push(OpenNode {
f: 0.0,
node: source.index(),
});
while let Some(OpenNode { f: d, node: u }) = heap.pop() {
if settled.contains_key(&u) {
continue;
}
settled.insert(u, true);
if u == goal {
break;
}
for e in graph.edges_directed(NodeIndex::<Ix>::new(u), Direction::Outgoing) {
let v = e.target().index();
let nd = d + *e.weight();
if nd < dist.get(&v).copied().unwrap_or(f64::INFINITY) {
dist.insert(v, nd);
pred.insert(v, u);
heap.push(OpenNode { f: nd, node: v });
}
}
}
if !settled.contains_key(&goal) {
return Ok(None);
}
let cost = dist[&goal];
let mut path = vec![NodeIndex::<Ix>::new(goal)];
let mut cur = goal;
while cur != source.index() {
cur = pred[&cur];
path.push(NodeIndex::<Ix>::new(cur));
}
path.reverse();
Ok(Some((cost, path)))
}
pub fn astar<N, Ix, F, H>(
graph: &Graph<N, f64, Directed, Ix>,
start: NodeIndex<Ix>,
is_goal: F,
heuristic: H,
) -> Option<AStarPath<Ix>>
where
Ix: IndexType,
F: Fn(NodeIndex<Ix>) -> bool,
H: Fn(NodeIndex<Ix>) -> f64,
{
try_astar(graph, start, is_goal, heuristic).unwrap_or_else(|e| panic!("astar failed: {e:?}"))
}
pub type AStarPath<Ix> = (f64, Vec<NodeIndex<Ix>>);
pub fn try_astar<N, Ix, F, H>(
graph: &Graph<N, f64, Directed, Ix>,
start: NodeIndex<Ix>,
is_goal: F,
heuristic: H,
) -> Result<Option<AStarPath<Ix>>, GraphError>
where
Ix: IndexType,
F: Fn(NodeIndex<Ix>) -> bool,
H: Fn(NodeIndex<Ix>) -> f64,
{
check_non_negative(graph)?;
let s = start.index();
let mut g_score: BTreeMap<usize, f64> = BTreeMap::new();
g_score.insert(s, 0.0);
let mut came_from: BTreeMap<usize, usize> = BTreeMap::new();
let mut open: BinaryHeap<OpenNode> = BinaryHeap::new();
let h0 = heuristic(start);
if !h0.is_nan() {
open.push(OpenNode { f: h0, node: s });
}
while let Some(OpenNode { f, node: u }) = open.pop() {
let gu = *g_score.get(&u).unwrap_or(&f64::INFINITY);
let node_u = NodeIndex::<Ix>::new(u);
if f > gu + heuristic(node_u) {
continue;
}
if is_goal(node_u) {
let mut path = Vec::new();
let mut cur = u;
path.push(NodeIndex::<Ix>::new(cur));
while let Some(&p) = came_from.get(&cur) {
path.push(NodeIndex::<Ix>::new(p));
cur = p;
}
path.reverse();
return Ok(Some((gu, path)));
}
for e in graph.edges_directed(node_u, Direction::Outgoing) {
let v = e.target().index();
let tentative = gu + *e.weight();
let vg = g_score.get(&v).copied().unwrap_or(f64::INFINITY);
if tentative < vg {
came_from.insert(v, u);
g_score.insert(v, tentative);
let f = tentative + heuristic(NodeIndex::new(v));
if !f.is_nan() {
open.push(OpenNode { f, node: v });
}
}
}
}
Ok(None)
}
pub fn bfs_order<N, E, Ty, Ix>(
graph: &petgraph::Graph<N, E, Ty, Ix>,
start: NodeIndex<Ix>,
) -> Vec<NodeIndex<Ix>>
where
Ty: petgraph::EdgeType,
Ix: IndexType,
{
let mut order = Vec::new();
let mut bfs = petgraph::visit::Bfs::new(graph, start);
while let Some(n) = bfs.next(graph) {
order.push(n);
}
order
}
pub fn dfs_order<N, E, Ty, Ix>(
graph: &petgraph::Graph<N, E, Ty, Ix>,
start: NodeIndex<Ix>,
) -> Vec<NodeIndex<Ix>>
where
Ty: petgraph::EdgeType,
Ix: IndexType,
{
let mut order = Vec::new();
let mut dfs = petgraph::visit::Dfs::new(graph, start);
while let Some(n) = dfs.next(graph) {
order.push(n);
}
order
}
pub fn has_path<N, E, Ix>(
graph: &Graph<N, E, Directed, Ix>,
from: NodeIndex<Ix>,
to: NodeIndex<Ix>,
) -> bool
where
Ix: IndexType,
{
petgraph::algo::has_path_connecting(graph, from, to, None)
}
pub fn is_cyclic<N, E, Ix>(graph: &Graph<N, E, Directed, Ix>) -> bool
where
Ix: IndexType,
{
petgraph::algo::is_cyclic_directed(graph)
}
pub fn connected_components<N, E, Ty, Ix>(graph: &petgraph::Graph<N, E, Ty, Ix>) -> usize
where
Ty: petgraph::EdgeType,
Ix: IndexType,
{
petgraph::algo::connected_components(graph)
}
pub fn strongly_connected_components<N, E, Ix>(
graph: &Graph<N, E, Directed, Ix>,
) -> Vec<Vec<NodeIndex<Ix>>>
where
Ix: IndexType,
{
petgraph::algo::tarjan_scc(graph)
}
pub fn minimum_spanning_tree<N, E, Ty, Ix>(
graph: &petgraph::Graph<N, E, Ty, Ix>,
) -> Vec<(NodeIndex<Ix>, NodeIndex<Ix>, E)>
where
N: Clone,
E: Clone + PartialOrd,
Ty: petgraph::EdgeType,
Ix: IndexType,
{
use petgraph::data::Element;
petgraph::algo::min_spanning_tree(graph)
.filter_map(|element| match element {
Element::Edge {
source,
target,
weight,
} => Some((NodeIndex::new(source), NodeIndex::new(target), weight)),
Element::Node { .. } => None,
})
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
fn small_dag() -> (Graph<&'static str, f64>, NodeIndex, NodeIndex, NodeIndex) {
let mut g: Graph<&str, f64> = Graph::new();
let a = g.add_node("a");
let b = g.add_node("b");
let c = g.add_node("c");
g.add_edge(a, b, 1.0);
g.add_edge(b, c, 1.0);
g.add_edge(a, c, 1.0);
(g, a, b, c)
}
#[test]
fn toposort_orders_dag() {
let (g, a, b, c) = {
let (g, a, b, c) = small_dag();
(g, a, b, c)
};
let order = toposort(&g, None).expect("DAG has a topological order");
let pos = |n: NodeIndex| order.iter().position(|&x| x == n).unwrap();
assert!(pos(a) < pos(b));
assert!(pos(b) < pos(c));
assert!(pos(a) < pos(c));
}
#[test]
fn dijkstra_finds_shortest_distance() {
let (g, a, _b, c) = small_dag();
let dist = dijkstra(&g, a, Some(c));
assert!((dist[&c.index()] - 1.0).abs() < 1e-12);
}
#[test]
fn dijkstra_path_reconstructs_the_shortest_route() {
let (g, a, _b, c) = small_dag();
let (cost, path) = dijkstra_path(&g, a, c).unwrap().unwrap();
assert!((cost - 1.0).abs() < 1e-12);
assert_eq!(path.first(), Some(&a));
assert_eq!(path.last(), Some(&c));
let mut total = 0.0;
for w in path.windows(2) {
let e = g.find_edge(w[0], w[1]).expect("path uses real edges");
total += g[e];
}
assert!((total - cost).abs() < 1e-12);
assert_eq!(dijkstra_path(&g, a, a).unwrap(), Some((0.0, vec![a])));
assert_eq!(dijkstra_path(&g, c, a).unwrap(), None);
}
#[test]
fn dijkstra_path_prefers_the_longer_cheaper_route() {
let mut g: Graph<(), f64> = Graph::new();
let a = g.add_node(());
let b = g.add_node(());
let c = g.add_node(());
g.add_edge(a, b, 1.0);
g.add_edge(b, c, 1.0);
g.add_edge(a, c, 5.0);
let (cost, path) = dijkstra_path(&g, a, c).unwrap().unwrap();
assert_eq!(cost, 2.0);
assert_eq!(path, vec![a, b, c]);
}
#[test]
fn astar_finds_path() {
let (g, a, _b, c) = small_dag();
let res = astar(&g, a, |n| n == c, |_| 0.0);
assert!(res.is_some());
let (cost, path) = res.unwrap();
assert!((cost - 1.0).abs() < 1e-12);
assert_eq!(path[0], a);
assert_eq!(path[path.len() - 1], c);
}
#[test]
fn max_flow_classic_network() {
let mut g: Graph<&str, f64> = Graph::new();
let s = g.add_node("s");
let a = g.add_node("a");
let b = g.add_node("b");
let t = g.add_node("t");
g.add_edge(s, a, 3.0);
g.add_edge(s, b, 2.0);
g.add_edge(a, b, 1.0);
g.add_edge(a, t, 2.0);
g.add_edge(b, t, 3.0);
let mf = max_flow(&g, s, t).unwrap();
assert!((mf.value - 5.0).abs() < 1e-9, "got {}", mf.value);
}
#[test]
fn max_flow_zero_when_no_path() {
let mut g: Graph<&str, f64> = Graph::new();
let s = g.add_node("s");
let t = g.add_node("t");
g.add_node("mid");
let mf = max_flow(&g, s, t).unwrap();
assert_eq!(mf.value, 0.0);
}
#[test]
fn max_flow_bottleneck() {
let mut g: Graph<&str, f64> = Graph::new();
let s = g.add_node("s");
let a = g.add_node("a");
let b = g.add_node("b");
let t = g.add_node("t");
g.add_edge(s, a, 3.0);
g.add_edge(s, b, 2.0);
g.add_edge(a, t, 3.0);
g.add_edge(b, t, 1.0);
let mf = max_flow(&g, s, t).unwrap();
assert!((mf.value - 4.0).abs() < 1e-9, "got {}", mf.value);
assert!(
(mf.edge_flow[0] - 3.0).abs() < 1e-9,
"s->a flow = {}",
mf.edge_flow[0]
);
assert!(
(mf.edge_flow[1] - 1.0).abs() < 1e-9,
"s->b flow = {}",
mf.edge_flow[1]
);
assert!(
(mf.edge_flow[2] - 3.0).abs() < 1e-9,
"a->t flow = {}",
mf.edge_flow[2]
);
assert!(
(mf.edge_flow[3] - 1.0).abs() < 1e-9,
"b->t flow = {}",
mf.edge_flow[3]
);
}
#[test]
fn max_flow_rejects_equal_endpoints() {
let mut g: Graph<&str, f64> = Graph::new();
let s = g.add_node("s");
assert_eq!(max_flow(&g, s, s), Err(GraphError::SourceEqualsSink));
}
#[test]
fn max_flow_keeps_small_capacities() {
let mut g: Graph<&str, f64> = Graph::new();
let s = g.add_node("s");
let t = g.add_node("t");
g.add_edge(s, t, 1e-14);
let mf = max_flow(&g, s, t).unwrap();
assert!((mf.value - 1e-14).abs() < 1e-20, "got {}", mf.value);
}
#[test]
fn max_flow_rejects_invalid_capacity() {
let mut g: Graph<&str, f64> = Graph::new();
let s = g.add_node("s");
let t = g.add_node("t");
g.add_edge(s, t, -1.0);
assert_eq!(max_flow(&g, s, t), Err(GraphError::InvalidWeight));
}
#[test]
fn astar_terminates_when_heuristic_is_infinite() {
let (g, a, _b, c) = small_dag();
let (cost, _) = astar(&g, a, |n| n == c, |_| f64::INFINITY).unwrap();
assert!((cost - 1.0).abs() < 1e-12);
let mut g2: Graph<&str, f64> = Graph::new();
let s = g2.add_node("s");
let isolated = g2.add_node("isolated");
g2.add_edge(s, s, 1.0);
assert!(astar(&g2, s, |n| n == isolated, |_| f64::INFINITY).is_none());
}
#[test]
fn astar_terminates_when_heuristic_is_nan() {
let (g, a, _b, c) = small_dag();
assert!(astar(&g, a, |n| n == c, |_| f64::NAN).is_none());
}
#[test]
fn astar_reopens_nodes_reached_by_a_cheaper_route() {
let mut g: Graph<&str, f64> = Graph::new();
let a = g.add_node("a");
let b = g.add_node("b");
let c = g.add_node("c");
g.add_edge(a, c, 10.0);
g.add_edge(a, b, 1.0);
g.add_edge(b, c, 1.0);
let (cost, path) = astar(&g, a, |n| n == c, |_| 0.0).unwrap();
assert!((cost - 2.0).abs() < 1e-12);
assert_eq!(path, vec![a, b, c]);
}
#[test]
fn try_dijkstra_rejects_negative_weight() {
let mut g: Graph<&str, f64> = Graph::new();
let a = g.add_node("a");
let b = g.add_node("b");
g.add_edge(a, b, -1.0);
assert_eq!(try_dijkstra(&g, a, None), Err(GraphError::InvalidWeight));
}
#[test]
fn try_astar_rejects_nan_weight() {
let mut g: Graph<&str, f64> = Graph::new();
let a = g.add_node("a");
let b = g.add_node("b");
g.add_edge(a, b, f64::NAN);
assert_eq!(
try_astar(&g, a, |n| n == b, |_| 0.0),
Err(GraphError::InvalidWeight)
);
}
}
#[cfg(test)]
mod traversal_tests {
use super::*;
fn chain() -> (Graph<u8, f64>, Vec<NodeIndex>) {
let mut g: Graph<u8, f64> = Graph::new();
let n: Vec<NodeIndex> = (0..5).map(|i| g.add_node(i)).collect();
g.add_edge(n[0], n[1], 1.0);
g.add_edge(n[1], n[2], 1.0);
g.add_edge(n[0], n[3], 1.0);
(g, n)
}
#[test]
fn bfs_visits_by_level() {
let (g, n) = chain();
let order = bfs_order(&g, n[0]);
assert_eq!(order[0], n[0]);
assert_eq!(order.len(), 4);
let pos = |x: NodeIndex| order.iter().position(|&y| y == x).unwrap();
assert!(pos(n[1]) < pos(n[2]));
assert!(pos(n[3]) < pos(n[2]));
assert!(!order.contains(&n[4]));
}
#[test]
fn dfs_goes_deep_first() {
let (g, n) = chain();
let order = dfs_order(&g, n[0]);
assert_eq!(order.len(), 4);
let pos = |x: NodeIndex| order.iter().position(|&y| y == x).unwrap();
assert!(pos(n[2]) < pos(n[3]) || pos(n[1]) < pos(n[3]));
assert_eq!(order[0], n[0]);
}
#[test]
fn reachability_and_cycles() {
let (mut g, n) = chain();
assert!(has_path(&g, n[0], n[2]));
assert!(!has_path(&g, n[2], n[0]));
assert!(has_path(&g, n[4], n[4]));
assert!(!is_cyclic(&g));
g.add_edge(n[2], n[0], 1.0);
assert!(is_cyclic(&g));
}
#[test]
fn components_ignore_direction() {
let (g, _) = chain();
assert_eq!(connected_components(&g), 2);
}
#[test]
fn strongly_connected_components_split_a_cycle() {
let mut g: Graph<(), ()> = Graph::new();
let a = g.add_node(());
let b = g.add_node(());
let c = g.add_node(());
g.add_edge(a, b, ());
g.add_edge(b, a, ());
g.add_edge(b, c, ());
let sccs = strongly_connected_components(&g);
assert_eq!(sccs.len(), 2);
let big = sccs.iter().find(|s| s.len() == 2).unwrap();
assert!(big.contains(&a) && big.contains(&b));
}
#[test]
fn spanning_tree_of_a_weighted_square() {
let mut g: Graph<(), f64> = Graph::new();
let n: Vec<NodeIndex> = (0..4).map(|_| g.add_node(())).collect();
g.add_edge(n[0], n[1], 1.0);
g.add_edge(n[1], n[2], 2.0);
g.add_edge(n[2], n[3], 3.0);
g.add_edge(n[3], n[0], 4.0);
g.add_edge(n[0], n[2], 10.0);
let mst = minimum_spanning_tree(&g);
assert_eq!(mst.len(), 3);
let total: f64 = mst.iter().map(|&(_, _, w)| w).sum();
assert_eq!(total, 6.0);
}
#[test]
fn spanning_forest_for_disconnected_graph() {
let (g, _) = {
let mut g: Graph<(), f64> = Graph::new();
let n: Vec<NodeIndex> = (0..4).map(|_| g.add_node(())).collect();
g.add_edge(n[0], n[1], 1.0);
g.add_edge(n[2], n[3], 2.0);
(g, n)
};
assert_eq!(minimum_spanning_tree(&g).len(), 2);
}
#[test]
fn max_flow_must_use_residual_reverse_edges() {
let mut g: Graph<&str, f64> = Graph::new();
let s = g.add_node("s");
let a = g.add_node("a");
let b = g.add_node("b");
let t = g.add_node("t");
g.add_edge(s, a, 1.0);
g.add_edge(a, b, 1.0);
g.add_edge(b, t, 1.0);
g.add_edge(s, b, 1.0);
g.add_edge(a, t, 1.0);
assert_eq!(max_flow(&g, s, t).unwrap().value, 2.0);
}
#[test]
fn max_flow_accepts_zero_capacities_and_returns_zero_without_a_path() {
let mut g: Graph<&str, f64> = Graph::new();
let s = g.add_node("s");
let t = g.add_node("t");
g.add_edge(s, t, 0.0);
assert_eq!(max_flow(&g, s, t).unwrap().value, 0.0);
}
#[test]
fn dijkstra_accepts_zero_weights() {
let mut g: Graph<u8, f64> = Graph::new();
let n: Vec<NodeIndex> = (0..3).map(|i| g.add_node(i)).collect();
g.add_edge(n[0], n[1], 0.0);
g.add_edge(n[1], n[2], 0.0);
let d = try_dijkstra(&g, n[0], None).unwrap();
assert_eq!(d[&n[2].index()], 0.0);
}
#[test]
fn dijkstra_sums_weights_along_multi_hop_paths() {
let mut g: Graph<u8, f64> = Graph::new();
let n: Vec<NodeIndex> = (0..3).map(|i| g.add_node(i)).collect();
g.add_edge(n[0], n[1], 2.0);
g.add_edge(n[1], n[2], 3.0);
let d = try_dijkstra(&g, n[0], None).unwrap();
assert_eq!(d[&n[1].index()], 2.0);
assert_eq!(d[&n[2].index()], 5.0);
}
#[test]
fn dijkstra_improves_a_tentative_distance_when_a_cheaper_route_appears() {
let mut g: Graph<u8, f64> = Graph::new();
let n: Vec<NodeIndex> = (0..3).map(|i| g.add_node(i)).collect();
g.add_edge(n[0], n[1], 5.0);
g.add_edge(n[0], n[2], 1.0);
g.add_edge(n[2], n[1], 1.0);
let d = try_dijkstra(&g, n[0], None).unwrap();
assert_eq!(d[&n[1].index()], 2.0);
let (cost, path) = dijkstra_path(&g, n[0], n[1]).unwrap().unwrap();
assert_eq!(cost, 2.0);
assert_eq!(path, vec![n[0], n[2], n[1]]);
}
#[test]
fn dijkstra_path_stops_at_the_target_not_at_the_first_settled_node() {
let mut g: Graph<u8, f64> = Graph::new();
let n: Vec<NodeIndex> = (0..4).map(|i| g.add_node(i)).collect();
g.add_edge(n[0], n[1], 1.0);
g.add_edge(n[1], n[2], 3.0);
g.add_edge(n[0], n[3], 10.0);
let (cost, path) = dijkstra_path(&g, n[0], n[2]).unwrap().unwrap();
assert_eq!(cost, 4.0);
assert_eq!(path, vec![n[0], n[1], n[2]]);
}
#[test]
fn astar_costs_sum_along_multi_hop_paths() {
let mut g: Graph<u8, f64> = Graph::new();
let n: Vec<NodeIndex> = (0..4).map(|i| g.add_node(i)).collect();
g.add_edge(n[0], n[1], 1.0);
g.add_edge(n[1], n[2], 2.0);
g.add_edge(n[2], n[3], 4.0);
g.add_edge(n[0], n[3], 20.0);
let (cost, path) = try_astar(&g, n[0], |v| v == n[3], |_| 0.0)
.unwrap()
.unwrap();
assert_eq!(cost, 7.0);
assert_eq!(path, vec![n[0], n[1], n[2], n[3]]);
}
#[test]
fn negative_weight_is_rejected_but_zero_is_not() {
let mut g: Graph<u8, f64> = Graph::new();
let a = g.add_node(0);
let b = g.add_node(1);
g.add_edge(a, b, -0.0);
assert!(try_dijkstra(&g, a, None).is_ok());
g.add_edge(b, a, -1.0);
assert!(try_dijkstra(&g, a, None).is_err());
}
}
#[cfg(test)]
mod in_house_dijkstra_tests {
use super::*;
fn random_graph(n: usize, seed: u64) -> Graph<u8, f64> {
let mut g: Graph<u8, f64> = Graph::new();
let nodes: Vec<NodeIndex> = (0..n).map(|i| g.add_node(i as u8)).collect();
let mut state = seed;
for u in 0..n {
for v in 0..n {
state = state
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
if u != v && (state >> 33) % 3 == 0 {
let w = ((state >> 40) % 9) as f64 + 0.5;
g.add_edge(nodes[u], nodes[v], w);
}
}
}
g
}
#[test]
fn in_house_dijkstra_matches_petgraph_on_random_graphs() {
for seed in 1..25u64 {
let g = random_graph(12, seed);
let source = NodeIndex::new(0);
let reference: BTreeMap<usize, f64> =
petgraph::algo::dijkstra(&g, source, None, |e| *e.weight())
.into_iter()
.map(|(k, v)| (k.index(), v))
.collect();
let ours = in_house_dijkstra(&g, source, None);
assert_eq!(ours.len(), reference.len(), "seed {seed}");
for (node, d) in &reference {
assert!((ours[node] - d).abs() < 1e-9, "seed {seed}, node {node}");
}
}
}
#[test]
fn in_house_dijkstra_stops_at_the_target_with_its_distance_settled() {
let mut g: Graph<u8, f64> = Graph::new();
let n: Vec<NodeIndex> = (0..3).map(|i| g.add_node(i)).collect();
g.add_edge(n[0], n[1], 1.0);
g.add_edge(n[1], n[2], 1.0);
let d = in_house_dijkstra(&g, n[0], Some(n[1]));
assert_eq!(d[&n[1].index()], 1.0);
}
}
#[cfg(test)]
mod max_flow_min_cut_tests {
use super::*;
fn brute_min_cut(n: usize, edges: &[(usize, usize, f64)], s: usize, t: usize) -> f64 {
let mut best = f64::INFINITY;
for mask in 0..(1u32 << n) {
if mask & (1 << s) == 0 || mask & (1 << t) != 0 {
continue;
}
let cut: f64 = edges
.iter()
.filter(|&&(u, v, _)| mask & (1 << u) != 0 && mask & (1 << v) == 0)
.map(|&(_, _, c)| c)
.sum();
best = best.min(cut);
}
best
}
#[test]
fn max_flow_equals_the_brute_force_min_cut_on_random_graphs() {
for seed in 1..300u64 {
let n = 7usize;
let mut state = seed.wrapping_mul(0x9E37_79B9_7F4A_7C15).wrapping_add(7);
let mut next = || {
state = state
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
state >> 33
};
let mut g: Graph<(), f64> = Graph::new();
let nodes: Vec<NodeIndex> = (0..n).map(|_| g.add_node(())).collect();
let mut edges = Vec::new();
for u in 0..n {
for v in 0..n {
if u != v && next() % 3 == 0 {
let c = (next() % 7 + 1) as f64;
g.add_edge(nodes[u], nodes[v], c);
edges.push((u, v, c));
}
}
}
let (s, t) = (0, n - 1);
let flow = max_flow(&g, nodes[s], nodes[t]).unwrap().value;
let cut = brute_min_cut(n, &edges, s, t);
assert!(
(flow - cut).abs() < 1e-9,
"seed {seed}: flow {flow}, cut {cut}"
);
}
}
fn floyd(n: usize, edges: &[(usize, usize, f64)]) -> Vec<Vec<f64>> {
let mut d = vec![vec![f64::INFINITY; n]; n];
for (i, row) in d.iter_mut().enumerate() {
row[i] = 0.0;
}
for &(u, v, w) in edges {
d[u][v] = d[u][v].min(w);
}
for k in 0..n {
for i in 0..n {
for j in 0..n {
let via = d[i][k] + d[k][j];
if via < d[i][j] {
d[i][j] = via;
}
}
}
}
d
}
#[test]
fn astar_with_an_admissible_heuristic_matches_the_true_distance() {
for seed in 1..200u64 {
let n = 8usize;
let mut state = seed.wrapping_mul(0x2545_F491_4F6C_DD1D).wrapping_add(3);
let mut next = || {
state = state
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
state >> 33
};
let mut g: Graph<(), f64> = Graph::new();
let nodes: Vec<NodeIndex> = (0..n).map(|_| g.add_node(())).collect();
let mut edges = Vec::new();
for u in 0..n {
for v in 0..n {
if u != v && next() % 3 == 0 {
let w = (next() % 9 + 1) as f64;
g.add_edge(nodes[u], nodes[v], w);
edges.push((u, v, w));
}
}
}
let goal = n - 1;
let d = floyd(n, &edges);
let h = |v: NodeIndex| {
let dv = d[v.index()][goal];
if dv.is_finite() {
0.5 * dv
} else {
0.0
}
};
let got = try_astar(&g, nodes[0], |v| v.index() == goal, h).unwrap();
if d[0][goal].is_finite() {
let (cost, path) = got.expect("a reachable goal must be found");
assert!(
(cost - d[0][goal]).abs() < 1e-9,
"seed {seed}: {cost} vs {}",
d[0][goal]
);
assert_eq!(path.first().map(|p| p.index()), Some(0));
assert_eq!(path.last().map(|p| p.index()), Some(goal));
} else {
assert!(
got.is_none(),
"seed {seed}: unreachable goal reported as found"
);
}
}
}
#[test]
fn bipartite_matching_networks_need_residual_reversal_and_match_min_cut() {
for seed in 1..200u64 {
let (l, r) = (4usize, 4usize);
let n = l + r + 2;
let (s, t) = (0usize, n - 1);
let mut state = seed.wrapping_mul(0x9E37_79B9_7F4A_7C15).wrapping_add(11);
let mut next = || {
state = state
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
state >> 33
};
let mut g: Graph<(), f64> = Graph::new();
let nodes: Vec<NodeIndex> = (0..n).map(|_| g.add_node(())).collect();
let mut edges = Vec::new();
for i in 0..l {
edges.push((s, 1 + i, 1.0));
}
for j in 0..r {
edges.push((1 + l + j, t, 1.0));
}
for i in 0..l {
for j in 0..r {
if next() % 2 == 0 {
edges.push((1 + i, 1 + l + j, 1.0));
}
}
}
for &(u, v, c) in &edges {
g.add_edge(nodes[u], nodes[v], c);
}
let flow = max_flow(&g, nodes[s], nodes[t]).unwrap().value;
let cut = brute_min_cut(n, &edges, s, t);
assert!(
(flow - cut).abs() < 1e-9,
"seed {seed}: flow {flow}, cut {cut}"
);
}
}
}