Merge remote-tracking branch 'origin/bm/algorithms-shortest-path' into bm/dino-closure
# Conflicts:
# .gitignore
# crates/algorithms/src/shortest_paths/astar/impl.rs
# crates/algorithms/src/shortest_paths/common/path.rs
# crates/algorithms/src/shortest_paths/common/transit.rs
# crates/algorithms/src/shortest_paths/dijkstra/iter.rs
# crates/algorithms/src/shortest_paths/dijkstra/mod.rs
# crates/algorithms/src/shortest_paths/mod.rs
diff --git a/.gitattributes b/.gitattributes
new file mode 100644
index 0000000..d02eb85
--- /dev/null
+++ b/.gitattributes
@@ -0,0 +1,59 @@
+crates/algorithms/tests/cases/**/* binary=true linguist-generated=true
+crates/algorithms/tests/cases/shortest_path/max_dense_long_00.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_sparse_random_00.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/sparse_random_02.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/almost_line_00.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/almost_line_01.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/small_00.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/line_00.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_sparse_random_01.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/small_03.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/small_01.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/small_03.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/spfa_killer_00.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/example_01.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/grid_swirl_00.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_star_00.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_00.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_01.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_dense_random_01.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_sparse_random_02.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/small_04.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/example_00.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_dense_random_00.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/sparse_random_00.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_dense_long_00.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/small_04.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/sparse_random_00.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/spfa_killer_00.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/almost_line_01.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/small_00.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/grid_random_00.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_dense_zero_00.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/example_01.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_dense_random_00.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_sparse_random_00.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_sparse_random_02.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/almost_line_02.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/almost_line_02.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/small_02.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/sparse_random_01.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_handmade_00.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/line_00.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_star_01.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/small_01.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/sparse_random_01.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/sparse_random_02.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/example_00.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/grid_random_00.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/small_02.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_01.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/almost_line_00.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_dense_random_01.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_sparse_random_01.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_star_00.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_star_01.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_handmade_00.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/grid_swirl_00.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/max_dense_zero_00.out filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_00.in filter=lfs diff=lfs merge=lfs -text
diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml
index 14f7167..776fb0d 100644
--- a/.github/workflows/ci.yml
+++ b/.github/workflows/ci.yml
@@ -23,7 +23,7 @@
strategy:
fail-fast: false
matrix:
- toolchain: [ 1.65, stable, nightly ]
+ toolchain: [ 1.75, stable, nightly ]
steps:
- name: Checkout source code
@@ -78,7 +78,7 @@
strategy:
fail-fast: false
matrix:
- toolchain: [ 1.65, stable, nightly ]
+ toolchain: [ 1.75, stable, nightly ]
steps:
- name: Checkout source code
@@ -119,7 +119,7 @@
uses: dtolnay/rust-toolchain@master
with:
toolchain: nightly
- components: ${{ matrix.toolchain == 'nightly' && 'rustfmt clippy llvm-tools-preview miri' || 'rustfmt clippy' }}
+ components: rustfmt clippy llvm-tools-preview miri
- name: Cache Rust dependencies
uses: Swatinem/rust-cache@v2
diff --git a/.gitignore b/.gitignore
index c0dfc31..f4602b6 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,5 +1,6 @@
# Generated by Cargo
/target/
Cargo.lock
-
+/crates/algorithms/tests/cases/problems
+venv
crates/algorithms/benches/input
diff --git a/Cargo.toml b/Cargo.toml
index e34d026..503db1e 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -49,6 +49,7 @@
petgraph-test-utils = { path = "crates/test-utils", default-features = false }
petgraph-dino = { path = "crates/dino", default-features = false }
petgraph-utils = { path = "crates/utils", default-features = false }
+numi = { path = "crates/numi", default-features = false }
[dependencies]
petgraph-adjacency-matrix = { workspace = true, optional = true, default-features = false }
diff --git a/crates/algorithms/Cargo.toml b/crates/algorithms/Cargo.toml
index c7807c4..8e9dec9 100644
--- a/crates/algorithms/Cargo.toml
+++ b/crates/algorithms/Cargo.toml
@@ -9,7 +9,7 @@
petgraph-core = { workspace = true, features = ["alloc"] }
#petgraph-graph = { workspace = true, optional = true }
#petgraph-adjacency-matrix = { workspace = true, optional = true }
-funty.workspace = true
+numi = { workspace = true }
# Like `std::collection::HashMap`, `IndexMap` is built on top of `hashbrown`, but because
# we're already using `IndexMap` in a lot of crates I do not want to pull in `hashbrown`
# separately as it would be another version to maintain. This way we only have one version.
@@ -18,7 +18,6 @@
fixedbitset.workspace = true
error-stack.workspace = true
hashbrown = { workspace = true, features = ['ahash'] }
-num-traits = "0.2.17"
either = "1.9.0"
dary_heap = "0.3.6"
@@ -29,6 +28,7 @@
#petgraph = { workspace = true, default-features = true, features = ['proptest', 'stable-graph'] }
# petgraph is only available in integration tests, while we use petgraph-graph in unit tests
#petgraph-graph = { workspace = true, features = ['stable'] }
+numi = { workspace = true, features = ["ordered-float-impl"] }
petgraph-dino = { workspace = true }
petgraph-utils = { workspace = true }
petgraph-proptest = { workspace = true }
@@ -37,11 +37,13 @@
approx = "0.5.1"
criterion = "0.5.1"
rand = "0.8.5"
-#petgraph-test-utils.workspace = true
itertools = "0.10.5"
ordered-float = "4.1.1"
serde_json = "1.0.107"
static_assertions = "1.1.0"
+snapbox = { version = "0.4.15" }
+libtest-mimic = "0.6.1"
+ignore = "0.4.21"
[features]
default = ["std"]
@@ -76,3 +78,7 @@
[[bench]]
name = "tree"
harness = false
+
+[[test]]
+name = "shortest_paths"
+harness = false
diff --git a/crates/algorithms/src/lib.rs b/crates/algorithms/src/lib.rs
index 5c9ea82..1565897 100644
--- a/crates/algorithms/src/lib.rs
+++ b/crates/algorithms/src/lib.rs
@@ -1,4 +1,3 @@
-#![feature(return_position_impl_trait_in_trait)]
//! Graph algorithms.
//!
//! It is a goal to gradually migrate the algorithms to be based on graph traits
diff --git a/crates/algorithms/src/shortest_paths/astar/heuristic.rs b/crates/algorithms/src/shortest_paths/astar/heuristic.rs
index ecb6f3f..a6bccb6 100644
--- a/crates/algorithms/src/shortest_paths/astar/heuristic.rs
+++ b/crates/algorithms/src/shortest_paths/astar/heuristic.rs
@@ -1,4 +1,5 @@
-use petgraph_core::{base::MaybeOwned, GraphStorage, Node};
+use numi::borrow::Moo;
+use petgraph_core::{GraphStorage, Node};
pub trait GraphHeuristic<S>
where
@@ -6,18 +7,17 @@
{
type Value;
- fn estimate<'a>(&self, source: Node<'a, S>, target: Node<'a, S>)
- -> MaybeOwned<'a, Self::Value>;
+ fn estimate<'a>(&self, source: Node<'a, S>, target: Node<'a, S>) -> Moo<'a, Self::Value>;
}
impl<S, F, T> GraphHeuristic<S> for F
where
S: GraphStorage,
- F: for<'a> Fn(Node<'a, S>, Node<'a, S>) -> MaybeOwned<'a, T>,
+ F: for<'a> Fn(Node<'a, S>, Node<'a, S>) -> Moo<'a, T>,
{
type Value = T;
- fn estimate<'a>(&self, source: Node<'a, S>, target: Node<'a, S>) -> MaybeOwned<'a, T> {
+ fn estimate<'a>(&self, source: Node<'a, S>, target: Node<'a, S>) -> Moo<'a, T> {
self(source, target)
}
}
diff --git a/crates/algorithms/src/shortest_paths/astar/impl.rs b/crates/algorithms/src/shortest_paths/astar/impl.rs
index ed28e0c..263d1a8 100644
--- a/crates/algorithms/src/shortest_paths/astar/impl.rs
+++ b/crates/algorithms/src/shortest_paths/astar/impl.rs
@@ -1,14 +1,14 @@
use alloc::vec::Vec;
-use core::{hash::Hash, ops::Add};
+use core::hash::Hash;
use error_stack::{Report, Result};
use fxhash::FxBuildHasher;
use hashbrown::HashMap;
-use num_traits::Zero;
-use petgraph_core::{id::FlaggableGraphId, Graph, GraphStorage, Node};
+use numi::num::{identity::Zero, ops::AddRef};
+use petgraph_core::{Graph, GraphStorage, Node};
use crate::shortest_paths::{
- astar::{error::AStarError, heuristic::GraphHeuristic},
+ astar::{error::AStarError, heuristic::GraphHeuristic, AStarMeasure},
common::{
connections::Connections,
cost::{Cost, GraphCost},
@@ -47,8 +47,7 @@
S: GraphStorage,
S::NodeId: FlaggableGraphId<S> + Eq + Hash,
E: GraphCost<S>,
- E::Value: PartialOrd + Ord + Zero + Clone + 'graph,
- for<'a> &'a E::Value: Add<Output = E::Value>,
+ E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
C: Connections<'graph, S> + 'parent,
{
@@ -122,7 +121,8 @@
let connections = self.connections.connections(&node);
for edge in connections {
- let alternative = &self.distances[node.id()] + self.edge_cost.cost(edge).as_ref();
+ let alternative =
+ self.distances[node.id()].add_ref(self.edge_cost.cost(edge).as_ref());
let (u, v) = edge.endpoints();
let neighbour = if u.id() == node.id() { v } else { u };
@@ -133,7 +133,8 @@
}
}
- let guess = &alternative + self.heuristic.estimate(neighbour, self.target).as_ref();
+ let guess =
+ alternative.add_ref(self.heuristic.estimate(neighbour, self.target).as_ref());
self.distances.insert(neighbour.id(), alternative);
if self.predecessor_mode == PredecessorMode::Record {
diff --git a/crates/algorithms/src/shortest_paths/astar/measure.rs b/crates/algorithms/src/shortest_paths/astar/measure.rs
new file mode 100644
index 0000000..dc8878a
--- /dev/null
+++ b/crates/algorithms/src/shortest_paths/astar/measure.rs
@@ -0,0 +1,67 @@
+use numi::num::{identity::Zero, ops::AddRef};
+
+/// Automatically implemented trait for types that can be used as a measure in the Dijkstra
+///
+/// This trait is implemented for all types that implement the supertraits mentioned in the trait
+/// definition.
+/// These traits either originate from [`core`] or [`numi`].
+/// Special attention must be paid to the [`AddRef`] trait, which is a proxy trait which is
+/// implemented for types that implement: `&Self: Add<&Self, Output = Self>`.
+///
+/// # Example
+///
+/// ```rust
+/// use core::num::Wrapping;
+/// use core::num::Saturating;
+/// use ordered_float::NotNan;
+/// use petgraph_algorithms::shortest_paths::astar::AStarMeasure;
+/// use static_assertions::assert_impl_all;
+///
+/// // Some examples of types that implement DijkstraMeasure
+/// assert_impl_all!(u8: AStarMeasure);
+/// assert_impl_all!(u16: AStarMeasure);
+/// assert_impl_all!(u32: AStarMeasure);
+/// assert_impl_all!(u64: AStarMeasure);
+/// assert_impl_all!(u128: AStarMeasure);
+/// assert_impl_all!(usize: AStarMeasure);
+///
+/// assert_impl_all!(i8: AStarMeasure);
+/// assert_impl_all!(i16: AStarMeasure);
+/// assert_impl_all!(i32: AStarMeasure);
+/// assert_impl_all!(i64: AStarMeasure);
+/// assert_impl_all!(i128: AStarMeasure);
+/// assert_impl_all!(isize: AStarMeasure);
+///
+/// assert_impl_all!(NotNan<f32>: AStarMeasure);
+/// assert_impl_all!(NotNan<f64>: AStarMeasure);
+///
+/// assert_impl_all!(Wrapping<u8>: AStarMeasure);
+/// assert_impl_all!(Wrapping<u16>: AStarMeasure);
+/// assert_impl_all!(Wrapping<u32>: AStarMeasure);
+/// assert_impl_all!(Wrapping<u64>: AStarMeasure);
+/// assert_impl_all!(Wrapping<u128>: AStarMeasure);
+/// assert_impl_all!(Wrapping<usize>: AStarMeasure);
+///
+/// assert_impl_all!(Wrapping<i8>: AStarMeasure);
+/// assert_impl_all!(Wrapping<i16>: AStarMeasure);
+/// assert_impl_all!(Wrapping<i32>: AStarMeasure);
+/// assert_impl_all!(Wrapping<i64>: AStarMeasure);
+/// assert_impl_all!(Wrapping<i128>: AStarMeasure);
+///
+/// assert_impl_all!(Saturating<u8>: AStarMeasure);
+/// assert_impl_all!(Saturating<u16>: AStarMeasure);
+/// assert_impl_all!(Saturating<u32>: AStarMeasure);
+/// assert_impl_all!(Saturating<u64>: AStarMeasure);
+/// assert_impl_all!(Saturating<u128>: AStarMeasure);
+/// assert_impl_all!(Saturating<usize>: AStarMeasure);
+///
+/// assert_impl_all!(Saturating<i8>: AStarMeasure);
+/// assert_impl_all!(Saturating<i16>: AStarMeasure);
+/// assert_impl_all!(Saturating<i32>: AStarMeasure);
+/// assert_impl_all!(Saturating<i64>: AStarMeasure);
+/// assert_impl_all!(Saturating<i128>: AStarMeasure);
+/// assert_impl_all!(Saturating<isize>: AStarMeasure);
+/// ```
+pub trait AStarMeasure: Clone + PartialOrd + Ord + AddRef<Self, Output = Self> + Zero {}
+
+impl<T> AStarMeasure for T where T: Clone + PartialOrd + Ord + AddRef<Self, Output = Self> + Zero {}
diff --git a/crates/algorithms/src/shortest_paths/astar/mod.rs b/crates/algorithms/src/shortest_paths/astar/mod.rs
index 065c765..fa9935d 100644
--- a/crates/algorithms/src/shortest_paths/astar/mod.rs
+++ b/crates/algorithms/src/shortest_paths/astar/mod.rs
@@ -1,14 +1,15 @@
+//! A* shortest path algorithm.
mod error;
mod heuristic;
mod r#impl;
+mod measure;
#[cfg(test)]
mod tests;
use alloc::vec::Vec;
-use core::{hash::Hash, marker::PhantomData, ops::Add};
+use core::{hash::Hash, marker::PhantomData};
use error_stack::Result;
-use num_traits::Zero;
use petgraph_core::{
edge::marker::{Directed, Undirected},
Direction,
@@ -17,20 +18,30 @@
DirectedGraphStorage, Graph, GraphDirectionality, GraphStorage, Node,
};
-use self::{error::AStarError, r#impl::AStarImpl};
-use super::{common::transit::PredecessorMode, ShortestDistance, ShortestPath};
-use crate::{
- polyfill::IteratorExt,
- shortest_paths::{
- astar::heuristic::GraphHeuristic,
- common::{
- connections::{outgoing_connections, Connections},
- cost::{Cost, DefaultCost, GraphCost},
- route::{DirectRoute, Route},
- },
+use self::r#impl::AStarImpl;
+pub use self::{error::AStarError, heuristic::GraphHeuristic, measure::AStarMeasure};
+use super::{
+ common::{
+ connections::{outgoing_connections, Connections},
+ cost::{Cost, DefaultCost, GraphCost},
+ route::{DirectRoute, Route},
+ transit::PredecessorMode,
},
+ ShortestDistance, ShortestPath,
};
+use crate::polyfill::IteratorExt;
+/// A* shortest path algorithm.
+///
+/// A* is a shortest path algorithm that uses a heuristic to guide the search.
+/// It is an extension of Dijkstra's algorithm, and is guaranteed to find the shortest path if the
+/// heuristic is admissible.
+/// A heuristic is admissible if it never overestimates the cost to reach the goal.
+///
+/// This implementation of A* is generic over the graph directionality, edge cost, and heuristic.
+///
+/// Edge weights need to implement [`AStarMeasure`], a trait that is automatically implemented for
+/// all types that satisfy the constraints of the algorithm.
pub struct AStar<D, E, H>
where
D: GraphDirectionality,
@@ -42,6 +53,43 @@
}
impl AStar<Directed, DefaultCost, ()> {
+ /// Create a new A* instance with the default edge cost and no heuristic.
+ ///
+ /// You won't be able to run A* without providing a heuristic using [`Self::with_heuristic`].
+ ///
+ /// If instantiated for a directed graph, [`AStar`] will not implement [`ShortestPath`] and
+ /// [`ShortestDistance`] on undirected graphs.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use numi::borrow::Moo;
+ /// use petgraph_algorithms::shortest_paths::{AStar, ShortestPath};
+ /// use petgraph_core::{edge::marker::Directed, GraphStorage, Node};
+ /// use petgraph_dino::{DiDinoGraph, DinoStorage};
+ ///
+ /// // TODO: heuristic utils
+ /// fn heuristic<'graph, S>(source: Node<'graph, S>, target: Node<'graph, S>) -> Moo<'graph, i32>
+ /// where
+ /// S: GraphStorage<NodeWeight = (i32, i32), EdgeWeight = i32>,
+ /// {
+ /// let source = source.weight();
+ /// let target = target.weight();
+ ///
+ /// Moo::Owned((source.0 - target.0).abs() + (source.1 - target.1).abs())
+ /// }
+ ///
+ /// let algorithm = AStar::directed().with_heuristic(heuristic);
+ ///
+ /// let mut graph = DiDinoGraph::new();
+ /// let a = *graph.insert_node((0, 1)).id();
+ /// let b = *graph.insert_node((2, 2)).id();
+ ///
+ /// graph.insert_edge(5, &a, &b);
+ ///
+ /// let path = algorithm.path_between(&graph, &a, &b).expect("path exists");
+ /// assert_eq!(path.cost().into_value(), 5);
+ /// ```
pub fn directed() -> Self {
Self {
edge_cost: DefaultCost,
@@ -106,8 +154,7 @@
S: DirectedGraphStorage,
S::NodeId: FlaggableGraphId<S> + Eq + Hash,
E: GraphCost<S>,
- E::Value: PartialOrd + Ord + Zero + Clone + 'graph,
- for<'a> &'a E::Value: Add<Output = E::Value>,
+ E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
{
AStarImpl::new(
@@ -134,8 +181,7 @@
S: GraphStorage,
S::NodeId: FlaggableGraphId<S> + Eq + Hash,
E: GraphCost<S>,
- E::Value: PartialOrd + Ord + Zero + Clone + 'graph,
- for<'a> &'a E::Value: Add<Output = E::Value>,
+ E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
{
AStarImpl::new(
@@ -158,8 +204,7 @@
S: GraphStorage,
S::NodeId: FlaggableGraphId<S> + Eq + Hash,
E: GraphCost<S>,
- for<'a> E::Value: PartialOrd + Ord + Zero + Clone + 'a,
- for<'a> &'a E::Value: Add<Output = E::Value>,
+ E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
{
type Cost = E::Value;
@@ -228,8 +273,7 @@
S: GraphStorage,
S::NodeId: FlaggableGraphId<S> + Eq + Hash,
E: GraphCost<S>,
- for<'a> E::Value: PartialOrd + Ord + Zero + Clone + 'a,
- for<'a> &'a E::Value: Add<Output = E::Value>,
+ E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
{
type Cost = E::Value;
@@ -299,8 +343,7 @@
S: DirectedGraphStorage,
S::NodeId: FlaggableGraphId<S> + Eq + Hash,
E: GraphCost<S>,
- for<'a> E::Value: PartialOrd + Ord + Zero + Clone + 'a,
- for<'a> &'a E::Value: Add<Output = E::Value>,
+ E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
{
type Cost = E::Value;
@@ -369,8 +412,7 @@
S: DirectedGraphStorage,
S::NodeId: FlaggableGraphId<S> + Eq + Hash,
E: GraphCost<S>,
- for<'a> E::Value: PartialOrd + Ord + Zero + Clone + 'a,
- for<'a> &'a E::Value: Add<Output = E::Value>,
+ E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
{
type Cost = E::Value;
diff --git a/crates/algorithms/src/shortest_paths/astar/tests.rs b/crates/algorithms/src/shortest_paths/astar/tests.rs
index 00ca85e..f13146b 100644
--- a/crates/algorithms/src/shortest_paths/astar/tests.rs
+++ b/crates/algorithms/src/shortest_paths/astar/tests.rs
@@ -1,8 +1,9 @@
use alloc::{vec, vec::Vec};
use core::sync::atomic::{AtomicUsize, Ordering};
+use numi::borrow::Moo;
use ordered_float::NotNan;
-use petgraph_core::{base::MaybeOwned, edge::marker::Directed, Edge, GraphStorage, Node};
+use petgraph_core::{edge::marker::Directed, Edge, GraphStorage, Node};
use petgraph_dino::{DiDinoGraph, DinoStorage, EdgeId, NodeId};
use petgraph_utils::{graph, GraphCollection};
@@ -73,15 +74,14 @@
] as EdgeId
);
-const fn no_heuristic<'a, S>(_: Node<'a, S>, _: Node<'a, S>) -> MaybeOwned<'a, usize>
+const fn no_heuristic<'a, S>(_: Node<'a, S>, _: Node<'a, S>) -> Moo<'a, usize>
where
S: GraphStorage,
{
- MaybeOwned::Owned(0)
+ Moo::Owned(0)
}
// TODO: multigraph
-// TODO: more test cases
#[test]
fn directed_path_between() {
@@ -179,10 +179,10 @@
assert!(cost.is_none());
}
-fn manhattan_distance<'a, S>(
- source: Node<'a, S>,
- target: Node<'a, S>,
-) -> MaybeOwned<'a, NotNan<f32>>
+fn manhattan_distance<'graph, S>(
+ source: Node<'graph, S>,
+ target: Node<'graph, S>,
+) -> Moo<'graph, NotNan<f32>>
where
S: GraphStorage<NodeWeight = Point>,
{
@@ -192,16 +192,16 @@
let distance =
NotNan::new(source.manhattan_distance(*target)).expect("distance should be a number");
- MaybeOwned::Owned(distance)
+ Moo::Owned(distance)
}
-fn ensure_not_nan<S>(edge: Edge<S>) -> MaybeOwned<'_, NotNan<f32>>
+fn ensure_not_nan<S>(edge: Edge<S>) -> Moo<'_, NotNan<f32>>
where
S: GraphStorage<EdgeWeight = f32>,
{
let weight = NotNan::new(*edge.weight()).expect("weight should be a number");
- MaybeOwned::Owned(weight)
+ Moo::Owned(weight)
}
#[test]
@@ -211,6 +211,7 @@
let astar = AStar::directed()
.with_edge_cost(ensure_not_nan)
.with_heuristic(manhattan_distance);
+
let route = astar.path_between(&graph, &nodes.a, &nodes.f).unwrap();
let (path, cost) = route.into_parts();
@@ -264,15 +265,15 @@
] as EdgeId
);
-fn admissible_inconsistent<'a, S>(source: Node<'a, S>, target: Node<'a, S>) -> MaybeOwned<'a, usize>
+fn admissible_inconsistent<'a, S>(source: Node<'a, S>, target: Node<'a, S>) -> Moo<'a, usize>
where
S: GraphStorage,
S::NodeWeight: AsRef<str>,
{
match source.weight().as_ref() {
- "A" => MaybeOwned::Owned(9),
- "B" => MaybeOwned::Owned(6),
- _ => MaybeOwned::Owned(0),
+ "A" => Moo::Owned(9),
+ "B" => Moo::Owned(6),
+ _ => Moo::Owned(0),
}
}
@@ -323,7 +324,7 @@
#[test]
fn optimal_runtime() {
// Needed to bind the lifetime of the closure, does some compiler magic.
- fn bind<S, T>(closure: impl Fn(Edge<S>) -> MaybeOwned<T>) -> impl Fn(Edge<S>) -> MaybeOwned<T> {
+ fn bind<S, T>(closure: impl Fn(Edge<S>) -> Moo<T>) -> impl Fn(Edge<S>) -> Moo<T> {
closure
}
@@ -334,7 +335,7 @@
let astar = AStar::directed()
.with_edge_cost(bind(|edge: Edge<DinoStorage<char, usize, Directed>>| {
CALLS.fetch_add(1, Ordering::SeqCst);
- MaybeOwned::Borrowed(edge.weight())
+ Moo::Borrowed(edge.weight())
}))
.with_heuristic(no_heuristic);
diff --git a/crates/algorithms/src/shortest_paths/bellman_ford/error.rs b/crates/algorithms/src/shortest_paths/bellman_ford/error.rs
new file mode 100644
index 0000000..9117483
--- /dev/null
+++ b/crates/algorithms/src/shortest_paths/bellman_ford/error.rs
@@ -0,0 +1,20 @@
+use core::fmt::{Display, Formatter};
+
+use error_stack::Context;
+
+#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+pub enum BellmanFordError {
+ NodeNotFound,
+ NegativeCycle,
+}
+
+impl Display for BellmanFordError {
+ fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
+ match self {
+ Self::NodeNotFound => write!(f, "node not found"),
+ Self::NegativeCycle => write!(f, "negative cycle"),
+ }
+ }
+}
+
+impl Context for BellmanFordError {}
diff --git a/crates/algorithms/src/shortest_paths/bellman_ford/impl.rs b/crates/algorithms/src/shortest_paths/bellman_ford/impl.rs
new file mode 100644
index 0000000..9e44259
--- /dev/null
+++ b/crates/algorithms/src/shortest_paths/bellman_ford/impl.rs
@@ -0,0 +1,371 @@
+use alloc::vec::Vec;
+use core::hash::Hash;
+
+use error_stack::{Report, Result};
+use fxhash::FxBuildHasher;
+use hashbrown::HashMap;
+use numi::num::{identity::Zero, ops::AddRef};
+use petgraph_core::{Graph, GraphStorage, Node};
+
+use super::error::BellmanFordError;
+use crate::shortest_paths::{
+ bellman_ford::{measure::BellmanFordMeasure, CandidateOrder},
+ common::{
+ connections::Connections,
+ cost::GraphCost,
+ queue::double_ended::DoubleEndedQueue,
+ transit::{reconstruct_paths_between, PredecessorMode},
+ },
+ Cost, Path, Route,
+};
+
+fn small_label_first<'graph, S, E>(
+ node: Node<'graph, S>,
+ cost: E::Value,
+ queue: &mut DoubleEndedQueue<'graph, S, E::Value>,
+) -> bool
+where
+ S: GraphStorage,
+ S::NodeId: Eq + Hash,
+ E: GraphCost<S>,
+ E::Value: BellmanFordMeasure,
+{
+ let Some(item) = queue.peek_front() else {
+ // queue is empty, therefore we can just simply push the cost
+ return queue.push_front(node, cost);
+ };
+
+ if &cost < item.priority() {
+ // the cost is smaller than the current smallest cost, therefore we push it to the front
+
+ return queue.push_front(node, cost);
+ }
+
+ // the cost is larger than the current smallest cost, therefore we push it to the back
+ queue.push_back(node, cost)
+}
+
+fn large_label_last<'graph, S, E>(
+ node: Node<'graph, S>,
+ cost: E::Value,
+ queue: &mut DoubleEndedQueue<'graph, S, E::Value>,
+) -> bool
+where
+ S: GraphStorage,
+ S::NodeId: Eq + Hash,
+ E: GraphCost<S>,
+ E::Value: BellmanFordMeasure,
+{
+ if queue.is_empty() {
+ // queue is empty, therefore we can just simply push the cost
+ return queue.push_back(node, cost);
+ }
+
+ // always push the item to the back of the queue
+ let did_push = queue.push_back(node, cost);
+
+ let Some(average) = queue.average_priority() else {
+ // this only happens if the length is 0 or we were unable to convert the length (usize)
+ // to the value type (E::Value)
+ return did_push;
+ };
+
+ loop {
+ // TODO: should we panic here instead? This should never happen.
+ let Some(front) = queue.peek_front() else {
+ // this should never happen, but if it does, we can just stop
+ // (previous check for empty queue should have caught this)
+ return did_push;
+ };
+
+ if *front.priority() <= average {
+ // the front item is smaller than the average, therefore we can stop
+ return did_push;
+ }
+
+ let Some(front) = queue.pop_front() else {
+ // this should never happen, but if it does, we can just stop
+ // (previous check for empty queue should have caught this)
+ return did_push;
+ };
+
+ let (node, priority) = front.into_parts();
+ queue.push_back(node, priority);
+ }
+}
+
+struct Heuristic<'graph, S>
+where
+ S: GraphStorage,
+{
+ enabled: bool,
+ recent_update: HashMap<&'graph S::NodeId, (&'graph S::NodeId, &'graph S::NodeId)>,
+ predecessor: HashMap<&'graph S::NodeId, &'graph S::NodeId>,
+}
+
+impl<'graph, S> Heuristic<'graph, S>
+where
+ S: GraphStorage,
+ S::NodeId: Eq + Hash,
+{
+ fn new(enabled: bool) -> Self {
+ Self {
+ enabled,
+ recent_update: HashMap::default(),
+ predecessor: HashMap::default(),
+ }
+ }
+
+ fn update(
+ &mut self,
+ source: &'graph S::NodeId,
+ target: &'graph S::NodeId,
+ ) -> core::result::Result<(), &'graph S::NodeId> {
+ if !self.enabled {
+ return Ok(());
+ }
+
+ // source = u
+ // target = v
+
+ // the heuristic is used to find a negative cycle before it is fully constructed.
+ // this is done via an implied check over multiple iterations.
+ // if it happens that some earlier update added the target node (as signified by the recent
+ // update) we know,
+ // that we have a negative cycle
+ // as the same node would be on the same path twice.
+ if let Some((u, v)) = self.recent_update.get(source) {
+ if target == *u || target == *v {
+ return Err(target);
+ }
+ }
+
+ if self.predecessor.get(target) == Some(&source) {
+ if let Some(previous) = self.recent_update.get(source) {
+ self.recent_update.insert(target, *previous);
+ }
+ } else {
+ self.recent_update.insert(target, (source, target));
+ }
+
+ self.predecessor.insert(target, source);
+ Ok(())
+ }
+}
+
+pub(super) struct ShortestPathFasterImpl<'graph: 'parent, 'parent, S, E, G>
+where
+ S: GraphStorage,
+ E: GraphCost<S>,
+{
+ graph: &'graph Graph<S>,
+ source: Node<'graph, S>,
+
+ edge_cost: &'parent E,
+ connections: G,
+
+ predecessor_mode: PredecessorMode,
+ candidate_order: CandidateOrder,
+ negative_cycle_heuristics: bool,
+
+ distances: HashMap<&'graph S::NodeId, E::Value, FxBuildHasher>,
+ predecessors: HashMap<&'graph S::NodeId, Vec<Node<'graph, S>>, FxBuildHasher>,
+}
+
+impl<'graph: 'parent, 'parent, S, E, G> ShortestPathFasterImpl<'graph, 'parent, S, E, G>
+where
+ S: GraphStorage,
+ S::NodeId: Eq + Hash,
+ E: GraphCost<S>,
+ E::Value: BellmanFordMeasure,
+ G: Connections<'graph, S>,
+{
+ pub(super) fn new(
+ graph: &'graph Graph<S>,
+
+ edge_cost: &'parent E,
+ connections: G,
+
+ source: &'graph S::NodeId,
+
+ predecessor_mode: PredecessorMode,
+ candidate_order: CandidateOrder,
+ negative_cycle_heuristics: bool,
+ ) -> Result<Self, BellmanFordError> {
+ let source_node = graph
+ .node(source)
+ .ok_or_else(|| Report::new(BellmanFordError::NodeNotFound))?;
+
+ let mut distances = HashMap::with_hasher(FxBuildHasher::default());
+ distances.insert(source, E::Value::zero());
+
+ let mut predecessors = HashMap::with_hasher(FxBuildHasher::default());
+ predecessors.insert(source, Vec::new());
+
+ let mut this = Self {
+ graph,
+ source: source_node,
+ edge_cost,
+ connections,
+ predecessor_mode,
+ candidate_order,
+ negative_cycle_heuristics,
+ distances,
+ predecessors,
+ };
+
+ // TODO: reconstruct negative cycle (needs `NodeId` to have additional trait bounds for
+ // error-stack)
+ if this.relax().is_err() {
+ return Err(Report::new(BellmanFordError::NegativeCycle));
+ }
+
+ Ok(this)
+ }
+
+ /// Inner Relaxation Loop for the Bellman-Ford algorithm, an implementation of SPFA.
+ ///
+ /// Based on [networkx](https://github.com/networkx/networkx/blob/f93f0e2a066fc456aa447853af9d00eec1058542/networkx/algorithms/shortest_paths/weighted.py#L1363)
+ fn relax(&mut self) -> core::result::Result<(), &'graph S::NodeId> {
+ // we always need to record predecessors to be able to skip relaxations
+ let mut queue = DoubleEndedQueue::new();
+ let mut heuristic: Heuristic<'graph, S> = Heuristic::new(self.negative_cycle_heuristics);
+ let mut occurrences = HashMap::new();
+ let num_nodes = self.graph.num_nodes();
+
+ queue.push_back(self.source, E::Value::zero());
+
+ while let Some(item) = queue.pop_front() {
+ let (source, priority) = item.into_parts();
+
+ // skip relaxations if any of the predecessors of node are in the queue
+ if let Some(predecessors) = self.predecessors.get(source.id()) {
+ if predecessors
+ .iter()
+ .any(|node| queue.contains_node(node.id()))
+ {
+ continue;
+ }
+ }
+
+ let edges = self.connections.connections(&source);
+
+ for edge in edges {
+ let (u, v) = edge.endpoints();
+ let target = if u.id() == source.id() { v } else { u };
+
+ let alternative = priority.add_ref(self.edge_cost.cost(edge).as_ref());
+
+ if let Some(distance) = self.distances.get(target.id()) {
+ if alternative == *distance {
+ self.predecessors
+ .entry(target.id())
+ .or_insert_with(Vec::new)
+ .push(source);
+ continue;
+ }
+
+ if alternative >= *distance {
+ continue;
+ }
+ }
+
+ if let Err(node) = heuristic.update(source.id(), target.id()) {
+ self.predecessors
+ .entry(target.id())
+ .or_insert_with(Vec::new)
+ .push(source);
+ return Err(node);
+ };
+
+ // we have a concrete problem here: we do not update the priority in the queue
+ // if it is larger.
+ // Could we in theory use the HashBrown API here instead, referencing the item in
+ // question?
+ let did_push = match self.candidate_order {
+ CandidateOrder::SmallFirst => {
+ small_label_first::<S, E>(target, alternative.clone(), &mut queue)
+ }
+ CandidateOrder::LargeLast => {
+ large_label_last::<S, E>(target, alternative.clone(), &mut queue)
+ }
+ CandidateOrder::Naive => queue.push_back(target, alternative.clone()),
+ };
+
+ if did_push {
+ let count = occurrences.entry(target.id()).or_insert(0usize);
+ *count += 1;
+
+ // If the heuristic failed (or is disabled) this is the fail-safe mechanism
+ // to detect any negative cycles.
+ // We know that a shortest path can at most go through n nodes, therefore we
+ // can detect a negative cycle,
+ // if we have visited the same node n times.
+ //
+ // As we can only detect a negative cycle quite late this is the worst case and
+ // the heuristic should be used instead.
+ if *count == num_nodes {
+ // negative cycle detected
+ return Err(target.id());
+ }
+ }
+
+ self.distances.insert(target.id(), alternative);
+
+ // re-use the same buffer so that we don't need to allocate a new one
+ let predecessors = self
+ .predecessors
+ .entry(target.id())
+ .or_insert_with(Vec::new);
+ predecessors.clear();
+ predecessors.push(source);
+ }
+ }
+
+ Ok(())
+ }
+
+ pub(crate) fn between(mut self, target: &S::NodeId) -> Option<Route<'graph, S, E::Value>> {
+ let cost = self.distances.remove(target)?;
+ let target = self.graph.node(target)?;
+
+ let transit = if self.predecessor_mode == PredecessorMode::Record {
+ reconstruct_paths_between(&self.predecessors, self.source.id(), target)
+ .next()
+ .unwrap_or_else(Vec::new)
+ } else {
+ Vec::new()
+ };
+
+ Some(Route::new(
+ Path::new(self.source, transit, target),
+ Cost::new(cost),
+ ))
+ }
+
+ pub(crate) fn all(self) -> impl Iterator<Item = Route<'graph, S, E::Value>> {
+ let Self {
+ graph,
+ source,
+ predecessor_mode,
+ distances,
+ predecessors,
+ ..
+ } = self;
+
+ distances
+ .into_iter()
+ .filter_map(|(target, cost)| graph.node(target).map(|target| (target, cost)))
+ .map(move |(target, cost)| {
+ let transit = if predecessor_mode == PredecessorMode::Record {
+ reconstruct_paths_between(&predecessors, source.id(), target)
+ .next()
+ .unwrap_or_else(Vec::new)
+ } else {
+ Vec::new()
+ };
+
+ Route::new(Path::new(source, transit, target), Cost::new(cost))
+ })
+ }
+}
diff --git a/crates/algorithms/src/shortest_paths/bellman_ford/measure.rs b/crates/algorithms/src/shortest_paths/bellman_ford/measure.rs
new file mode 100644
index 0000000..d0ac726
--- /dev/null
+++ b/crates/algorithms/src/shortest_paths/bellman_ford/measure.rs
@@ -0,0 +1,88 @@
+use core::{
+ iter::Sum,
+ ops::{Add, Div},
+};
+
+use numi::{
+ cast::{CastFrom, TryCastFrom},
+ num::{identity::Zero, ops::AddRef},
+};
+
+/// Automatically implemented trait for types that can be used as a measure in the Bellman-Ford
+/// algorithm.
+///
+/// This trait is implemented for all types that implement the supertraits mentioned in the trait
+/// definition.
+/// These traits either originate from [`core`] or [`numi`].
+/// Special attention must be paid to the [`AddRef`] trait, which is a proxy trait which is
+/// implemented for types that implement: `&Self: Add<&Self, Output = Self>`.
+///
+/// # Example
+///
+/// ```rust
+/// use core::num::{Wrapping, Saturating};
+/// use ordered_float::NotNan;
+/// use petgraph_algorithms::shortest_paths::bellman_ford::BellmanFordMeasure;
+/// use static_assertions::assert_impl_all;
+///
+/// // Some examples of types that implement BellmanFordMeasure
+/// assert_impl_all!(u8: BellmanFordMeasure);
+/// assert_impl_all!(u16: BellmanFordMeasure);
+/// assert_impl_all!(u32: BellmanFordMeasure);
+/// assert_impl_all!(u64: BellmanFordMeasure);
+/// assert_impl_all!(u128: BellmanFordMeasure);
+/// assert_impl_all!(usize: BellmanFordMeasure);
+///
+/// assert_impl_all!(i8: BellmanFordMeasure);
+/// assert_impl_all!(i16: BellmanFordMeasure);
+/// assert_impl_all!(i32: BellmanFordMeasure);
+/// assert_impl_all!(i64: BellmanFordMeasure);
+/// assert_impl_all!(i128: BellmanFordMeasure);
+/// assert_impl_all!(isize: BellmanFordMeasure);
+///
+/// assert_impl_all!(f32: BellmanFordMeasure);
+/// assert_impl_all!(f64: BellmanFordMeasure);
+/// // `OrderedFloat` is not supported because `AddRef` isn't implemented, see:
+/// // https://github.com/reem/rust-ordered-float/issues/145
+/// assert_impl_all!(NotNan<f32>: BellmanFordMeasure);
+/// assert_impl_all!(NotNan<f64>: BellmanFordMeasure);
+///
+/// assert_impl_all!(Wrapping<u8>: BellmanFordMeasure);
+/// assert_impl_all!(Wrapping<u16>: BellmanFordMeasure);
+/// assert_impl_all!(Wrapping<u32>: BellmanFordMeasure);
+/// assert_impl_all!(Wrapping<u64>: BellmanFordMeasure);
+/// assert_impl_all!(Wrapping<u128>: BellmanFordMeasure);
+/// assert_impl_all!(Wrapping<usize>: BellmanFordMeasure);
+///
+/// assert_impl_all!(Wrapping<i8>: BellmanFordMeasure);
+/// assert_impl_all!(Wrapping<i16>: BellmanFordMeasure);
+/// assert_impl_all!(Wrapping<i32>: BellmanFordMeasure);
+/// assert_impl_all!(Wrapping<i64>: BellmanFordMeasure);
+/// assert_impl_all!(Wrapping<i128>: BellmanFordMeasure);
+///
+/// // `Saturating` currently does not implement `Sum`, see:
+/// // https://github.com/rust-lang/libs-team/issues/303
+/// ```
+pub trait BellmanFordMeasure:
+ Clone
+ + PartialOrd
+ + Add<Self, Output = Self>
+ + AddRef<Self, Output = Self>
+ + Div<Self, Output = Self>
+ + for<'a> Sum<&'a Self>
+ + TryCastFrom<usize>
+ + Zero
+{
+}
+
+impl<T> BellmanFordMeasure for T where
+ T: Clone
+ + PartialOrd
+ + Add<Self, Output = Self>
+ + AddRef<Self, Output = Self>
+ + Div<Self, Output = Self>
+ + for<'a> Sum<&'a Self>
+ + TryCastFrom<usize>
+ + Zero
+{
+}
diff --git a/crates/algorithms/src/shortest_paths/bellman_ford/mod.rs b/crates/algorithms/src/shortest_paths/bellman_ford/mod.rs
new file mode 100644
index 0000000..ecc32b8
--- /dev/null
+++ b/crates/algorithms/src/shortest_paths/bellman_ford/mod.rs
@@ -0,0 +1,540 @@
+//! An implementation of Bellman-Ford's shortest path algorithm.
+mod error;
+mod r#impl;
+mod measure;
+#[cfg(test)]
+mod tests;
+
+use alloc::vec::Vec;
+use core::hash::Hash;
+
+use error_stack::Result;
+use petgraph_core::{
+ edge::marker::{Directed, Undirected},
+ DirectedGraphStorage, Graph, GraphDirectionality, GraphStorage, Node,
+};
+
+use self::r#impl::ShortestPathFasterImpl;
+pub use self::{error::BellmanFordError, measure::BellmanFordMeasure};
+use super::{
+ common::{
+ connections::outgoing_connections,
+ cost::{DefaultCost, GraphCost},
+ transit::PredecessorMode,
+ },
+ Cost, DirectRoute, Route, ShortestDistance, ShortestPath,
+};
+use crate::polyfill::IteratorExt;
+
+/// The order in which candidates are inserted into the queue.
+///
+/// The order in which candidates are inserted into the queue can have a significant impact on the
+/// performance of the algorithm.
+///
+/// [`CandidateOrder::SmallFirst`] is the default, as it is an easy to implement heuristic, with
+/// little overhead which can exhibit good performance improvements in practice.
+///
+/// # See Also
+///
+/// - <https://www.researchgate.net/publication/274174007_An_Improved_SPFA_Algorithm_for_Single-Source_Shortest_Path_Problem_Using_Forward_Star_Data_Structure>
+// TODO: add citation about the different orders
+#[derive(Default, Debug, Copy, Clone, PartialEq, Eq)]
+pub enum CandidateOrder {
+ /// # Naive
+ ///
+ /// Push the item to the back of the queue.
+ Naive,
+
+ /// # Small Label First (SSF)
+ ///
+ /// Checks if the current value is smaller than the next value, if that is the case, push it to
+ /// the front, otherwise push it to the back.
+ #[default]
+ SmallFirst,
+
+ /// # Large Label Last (LLL)
+ ///
+ /// Push the item to the back of the queue.
+ /// Calculate the average value of the queue and as long as the next value larger than the
+ /// average value, pop it from the front and push it to the back.
+ LargeLast,
+}
+
+/// An implementation of Bellman-Ford's shortest path algorithm.
+///
+/// Bellman-Ford's algorithm is an algorithm for finding the shortest paths between a source node
+/// and all reachable nodes in a graph.
+/// Unlike Dijkstra's algorithm, Bellman-Ford's algorithm can be used on graphs with negative edge
+/// weights, as long as the graph does not contain a negative cycle reachable from the source.
+///
+/// This implementation is generic over the directionality of the graph and the cost function.
+///
+/// Edge weights need to implement [`BellmanFordMeasure`], a trait that is automatically implemented
+/// for all types that satisfy the constraints.
+///
+/// The internal implementation makes uses of Shortest Path Faster Algorithm (SPFA) which is a
+/// variant of Bellman-Ford's algorithm, with an average time complexity of `O(|E|)` on random
+/// graphs and a worst case complexity of `O(|V| * |E|)`.
+pub struct BellmanFord<D, E> {
+ direction: D,
+ edge_cost: E,
+ candidate_order: CandidateOrder,
+ negative_cycle_heuristics: bool,
+}
+
+impl BellmanFord<Directed, DefaultCost> {
+ /// Create a new instance of `BellmanFord` for a directed graph.
+ ///
+ /// If instantiated for a directed graph, [`BellmanFord`] will not implement [`ShortestPath`]
+ /// and [`ShortestDistance`] on undirected graphs.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use petgraph_algorithms::shortest_paths::{BellmanFord, ShortestPath};
+ /// use petgraph_dino::DiDinoGraph;
+ ///
+ /// let algorithm = BellmanFord::directed();
+ ///
+ /// let mut graph = DiDinoGraph::new();
+ /// let a = *graph.insert_node("A").id();
+ /// let b = *graph.insert_node("B").id();
+ ///
+ /// graph.insert_edge(2, &a, &b);
+ ///
+ /// let path = algorithm.path_between(&graph, &a, &b);
+ /// assert!(path.is_some());
+ ///
+ /// let path = algorithm.path_between(&graph, &b, &a);
+ /// assert!(path.is_none());
+ /// ```
+ pub fn directed() -> Self {
+ Self {
+ direction: Directed,
+ edge_cost: DefaultCost,
+ candidate_order: CandidateOrder::default(),
+ negative_cycle_heuristics: true,
+ }
+ }
+}
+
+impl BellmanFord<Undirected, DefaultCost> {
+ /// Create a new instance of `BellmanFord` for an undirected graph.
+ ///
+ /// If instantiated for an undirected graph, [`BellmanFord`] will treat a directed graph as
+ /// undirected.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use petgraph_algorithms::shortest_paths::{BellmanFord, ShortestPath};
+ /// use petgraph_dino::DiDinoGraph;
+ ///
+ /// let algorithm = BellmanFord::undirected();
+ ///
+ /// let mut graph = DiDinoGraph::new();
+ /// let a = *graph.insert_node("A").id();
+ /// let b = *graph.insert_node("B").id();
+ ///
+ /// graph.insert_edge(2, &a, &b);
+ ///
+ /// let path = algorithm.path_between(&graph, &a, &b);
+ /// assert!(path.is_some());
+ ///
+ /// let path = algorithm.path_between(&graph, &b, &a);
+ /// assert!(path.is_some());
+ /// ```
+ pub fn undirected() -> Self {
+ Self {
+ direction: Undirected,
+ edge_cost: DefaultCost,
+ candidate_order: CandidateOrder::default(),
+ negative_cycle_heuristics: true,
+ }
+ }
+}
+
+impl<D, E> BellmanFord<D, E>
+where
+ D: GraphDirectionality,
+{
+ /// Set the cost function for the algorithm.
+ ///
+ /// By default the algorithm will use the edge weight as the cost, this function allows you to
+ /// override that behaviour,
+ /// transforming a previously unsupported graph weight into a supported one.
+ ///
+ /// For all supported functions see [`GraphCost`].
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use numi::borrow::Moo;
+ /// use petgraph_algorithms::shortest_paths::{BellmanFord, ShortestPath};
+ /// use petgraph_core::{Edge, GraphStorage};
+ /// use petgraph_dino::DiDinoGraph;
+ ///
+ /// fn edge_cost<S>(edge: Edge<S>) -> Moo<usize>
+ /// where
+ /// S: GraphStorage,
+ /// S::EdgeWeight: AsRef<str>,
+ /// {
+ /// edge.weight().as_ref().len().into()
+ /// }
+ ///
+ /// let algorithm = BellmanFord::directed().with_edge_cost(edge_cost);
+ ///
+ /// let mut graph = DiDinoGraph::new();
+ /// let a = *graph.insert_node("A").id();
+ /// let b = *graph.insert_node("B").id();
+ ///
+ /// graph.insert_edge("AB", &a, &b);
+ ///
+ /// let path = algorithm.path_between(&graph, &a, &b);
+ /// assert!(path.is_some());
+ /// ```
+ pub fn with_edge_cost<S, F>(self, edge_cost: F) -> BellmanFord<D, F>
+ where
+ S: GraphStorage,
+ F: GraphCost<S>,
+ {
+ BellmanFord {
+ direction: self.direction,
+ edge_cost,
+ candidate_order: self.candidate_order,
+ negative_cycle_heuristics: self.negative_cycle_heuristics,
+ }
+ }
+
+ /// Set the candidate order for the algorithm.
+ ///
+ /// By default the algorithm uses the [`CandidateOrder::SmallFirst`] order, see
+ /// [`CandidateOrder`] for the different pros and cons.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use petgraph_algorithms::shortest_paths::{
+ /// bellman_ford::CandidateOrder, BellmanFord, ShortestPath,
+ /// };
+ /// use petgraph_dino::DiDinoGraph;
+ ///
+ /// let algorithm = BellmanFord::directed().with_candidate_order(CandidateOrder::LargeLast);
+ ///
+ /// let mut graph = DiDinoGraph::new();
+ /// let a = *graph.insert_node("A").id();
+ /// let b = *graph.insert_node("B").id();
+ ///
+ /// graph.insert_edge(2, &a, &b);
+ ///
+ /// let path = algorithm.path_between(&graph, &a, &b);
+ /// assert!(path.is_some());
+ /// ```
+ pub fn with_candidate_order(self, candidate_order: CandidateOrder) -> Self {
+ Self {
+ direction: self.direction,
+ edge_cost: self.edge_cost,
+ candidate_order,
+ negative_cycle_heuristics: self.negative_cycle_heuristics,
+ }
+ }
+
+ /// Enable or disable negative cycle heuristics.
+ ///
+ /// By default the algorithm will use negative cycle heuristics.
+ /// Negative cycle heuristics help to detect negative cycles in the graph early.
+ /// If the graph contains a negative cycle, the algorithm will return an error.
+ ///
+ /// In theory such heuristic can exhibit false-positives, but these haven't been observed in
+ /// practice.
+ /// The heuristic is based on the implementation of networkx and allows the algorithm to not
+ /// exhibit worst case time complexity in the case of a negative cycle.
+ ///
+ /// It is recommended to leave this option enabled.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use petgraph_algorithms::shortest_paths::{BellmanFord, ShortestPath};
+ /// use petgraph_dino::DiDinoGraph;
+ ///
+ /// let algorithm = BellmanFord::directed().with_negative_cycle_heuristics(false);
+ ///
+ /// let mut graph = DiDinoGraph::new();
+ /// let a = *graph.insert_node("A").id();
+ /// let b = *graph.insert_node("B").id();
+ ///
+ /// graph.insert_edge(2, &a, &b);
+ ///
+ /// let path = algorithm.path_between(&graph, &a, &b);
+ /// assert!(path.is_some());
+ /// ```
+ pub fn with_negative_cycle_heuristics(self, negative_cycle_heuristics: bool) -> Self {
+ Self {
+ direction: self.direction,
+ edge_cost: self.edge_cost,
+ candidate_order: self.candidate_order,
+ negative_cycle_heuristics,
+ }
+ }
+}
+
+impl<S, E> ShortestPath<S> for BellmanFord<Undirected, E>
+where
+ S: GraphStorage,
+ S::NodeId: PartialEq + Eq + Hash,
+ E: GraphCost<S>,
+ E::Value: BellmanFordMeasure,
+{
+ type Cost = E::Value;
+ type Error = BellmanFordError;
+
+ fn path_to<'graph: 'this, 'this>(
+ &'this self,
+ graph: &'graph Graph<S>,
+ target: &'graph S::NodeId,
+ ) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>>, Self::Error> {
+ let iter = self.path_from(graph, target)?;
+
+ Ok(iter.map(Route::reverse))
+ }
+
+ fn path_from<'graph: 'this, 'this>(
+ &'this self,
+ graph: &'graph Graph<S>,
+ source: &'graph <S as GraphStorage>::NodeId,
+ ) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>>, Self::Error> {
+ ShortestPathFasterImpl::new(
+ graph,
+ &self.edge_cost,
+ Node::<'graph, S>::connections as fn(&Node<'graph, S>) -> _,
+ source,
+ PredecessorMode::Record,
+ self.candidate_order,
+ self.negative_cycle_heuristics,
+ )
+ .map(ShortestPathFasterImpl::all)
+ }
+
+ fn path_between<'graph>(
+ &self,
+ graph: &'graph Graph<S>,
+ source: &'graph S::NodeId,
+ target: &'graph S::NodeId,
+ ) -> Option<Route<'graph, S, Self::Cost>> {
+ ShortestPathFasterImpl::new(
+ graph,
+ &self.edge_cost,
+ Node::<'graph, S>::connections as fn(&Node<'graph, S>) -> _,
+ source,
+ PredecessorMode::Record,
+ self.candidate_order,
+ self.negative_cycle_heuristics,
+ )
+ .ok()?
+ .between(target)
+ }
+
+ fn every_path<'graph: 'this, 'this>(
+ &'this self,
+ graph: &'graph Graph<S>,
+ ) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
+ let iter: Vec<_> = graph
+ .nodes()
+ .map(move |node| self.path_from(graph, node.id()))
+ .collect_reports()?;
+
+ Ok(iter.into_iter().flatten())
+ }
+}
+
+impl<S, E> ShortestDistance<S> for BellmanFord<Undirected, E>
+where
+ S: GraphStorage,
+ S::NodeId: Eq + Hash,
+ E: GraphCost<S>,
+ E::Value: BellmanFordMeasure,
+{
+ type Cost = E::Value;
+ type Error = BellmanFordError;
+
+ fn distance_to<'graph: 'this, 'this>(
+ &'this self,
+ graph: &'graph Graph<S>,
+ target: &'graph S::NodeId,
+ ) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>>, Self::Error> {
+ let iter = self.distance_from(graph, target)?;
+
+ Ok(iter.map(DirectRoute::reverse))
+ }
+
+ fn distance_from<'graph: 'this, 'this>(
+ &'this self,
+ graph: &'graph Graph<S>,
+ source: &'graph <S as GraphStorage>::NodeId,
+ ) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
+ let iter = ShortestPathFasterImpl::new(
+ graph,
+ &self.edge_cost,
+ Node::<'graph, S>::connections as fn(&Node<'graph, S>) -> _,
+ source,
+ PredecessorMode::Discard,
+ self.candidate_order,
+ self.negative_cycle_heuristics,
+ )?;
+
+ Ok(iter.all().map(Into::into))
+ }
+
+ fn distance_between<'graph>(
+ &self,
+ graph: &'graph Graph<S>,
+ source: &'graph S::NodeId,
+ target: &'graph S::NodeId,
+ ) -> Option<Cost<Self::Cost>> {
+ ShortestPathFasterImpl::new(
+ graph,
+ &self.edge_cost,
+ Node::<'graph, S>::connections as fn(&Node<'graph, S>) -> _,
+ source,
+ PredecessorMode::Discard,
+ self.candidate_order,
+ self.negative_cycle_heuristics,
+ )
+ .ok()?
+ .between(target)
+ .map(Route::into_cost)
+ }
+
+ fn every_distance<'graph: 'this, 'this>(
+ &'this self,
+ graph: &'graph Graph<S>,
+ ) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
+ let iter: Vec<_> = graph
+ .nodes()
+ .map(move |node| self.distance_from(graph, node.id()))
+ .collect_reports()?;
+
+ Ok(iter.into_iter().flatten())
+ }
+}
+
+impl<S, E> ShortestPath<S> for BellmanFord<Directed, E>
+where
+ S: DirectedGraphStorage,
+ S::NodeId: Eq + Hash,
+ E: GraphCost<S>,
+ E::Value: BellmanFordMeasure,
+{
+ type Cost = E::Value;
+ type Error = BellmanFordError;
+
+ fn path_from<'graph: 'this, 'this>(
+ &'this self,
+ graph: &'graph Graph<S>,
+ source: &'graph S::NodeId,
+ ) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
+ ShortestPathFasterImpl::new(
+ graph,
+ &self.edge_cost,
+ outgoing_connections as fn(&Node<'graph, S>) -> _,
+ source,
+ PredecessorMode::Record,
+ self.candidate_order,
+ self.negative_cycle_heuristics,
+ )
+ .map(ShortestPathFasterImpl::all)
+ }
+
+ fn path_between<'graph>(
+ &self,
+ graph: &'graph Graph<S>,
+ source: &'graph S::NodeId,
+ target: &'graph S::NodeId,
+ ) -> Option<Route<'graph, S, Self::Cost>> {
+ ShortestPathFasterImpl::new(
+ graph,
+ &self.edge_cost,
+ outgoing_connections as fn(&Node<'graph, S>) -> _,
+ source,
+ PredecessorMode::Record,
+ self.candidate_order,
+ self.negative_cycle_heuristics,
+ )
+ .ok()?
+ .between(target)
+ }
+
+ fn every_path<'graph: 'this, 'this>(
+ &'this self,
+ graph: &'graph Graph<S>,
+ ) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
+ let iter: Vec<_> = graph
+ .nodes()
+ .map(move |node| self.path_from(graph, node.id()))
+ .collect_reports()?;
+
+ Ok(iter.into_iter().flatten())
+ }
+}
+
+impl<S, E> ShortestDistance<S> for BellmanFord<Directed, E>
+where
+ S: DirectedGraphStorage,
+ S::NodeId: Eq + Hash,
+ E: GraphCost<S>,
+ E::Value: BellmanFordMeasure,
+{
+ type Cost = E::Value;
+ type Error = BellmanFordError;
+
+ fn distance_from<'graph: 'this, 'this>(
+ &'this self,
+ graph: &'graph Graph<S>,
+ source: &'graph <S as GraphStorage>::NodeId,
+ ) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>>, Self::Error> {
+ let iter = ShortestPathFasterImpl::new(
+ graph,
+ &self.edge_cost,
+ outgoing_connections as fn(&Node<'graph, S>) -> _,
+ source,
+ PredecessorMode::Discard,
+ self.candidate_order,
+ self.negative_cycle_heuristics,
+ )?;
+
+ Ok(iter.all().map(Into::into))
+ }
+
+ fn distance_between<'graph>(
+ &self,
+ graph: &'graph Graph<S>,
+ source: &'graph S::NodeId,
+ target: &'graph S::NodeId,
+ ) -> Option<Cost<Self::Cost>> {
+ ShortestPathFasterImpl::new(
+ graph,
+ &self.edge_cost,
+ outgoing_connections as fn(&Node<'graph, S>) -> _,
+ source,
+ PredecessorMode::Discard,
+ self.candidate_order,
+ self.negative_cycle_heuristics,
+ )
+ .ok()?
+ .between(target)
+ .map(Route::into_cost)
+ }
+
+ fn every_distance<'graph: 'this, 'this>(
+ &'this self,
+ graph: &'graph Graph<S>,
+ ) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
+ let iter: Vec<_> = graph
+ .nodes()
+ .map(move |node| self.distance_from(graph, node.id()))
+ .collect_reports()?;
+
+ Ok(iter.into_iter().flatten())
+ }
+}
diff --git a/crates/algorithms/src/shortest_paths/bellman_ford/tests.rs b/crates/algorithms/src/shortest_paths/bellman_ford/tests.rs
new file mode 100644
index 0000000..fa55e4b
--- /dev/null
+++ b/crates/algorithms/src/shortest_paths/bellman_ford/tests.rs
@@ -0,0 +1,281 @@
+use alloc::vec::Vec;
+use core::array;
+
+use petgraph_core::{
+ edge::marker::{Directed, Undirected},
+ Graph, GraphStorage, ManagedGraphId,
+};
+use petgraph_dino::{DiDinoGraph, DinoStorage, EdgeId, NodeId};
+use petgraph_utils::{graph, GraphCollection};
+
+use super::BellmanFord;
+use crate::shortest_paths::{
+ bellman_ford::error::BellmanFordError,
+ common::tests::{expected, TestCase},
+ ShortestPath,
+};
+
+graph!(
+ /// Uses the graph from networkx
+ ///
+ /// <https://github.com/networkx/networkx/blob/main/networkx/algorithms/shortest_paths/tests/test_weighted.py>
+ factory(networkx) => DiDinoGraph<&'static str, f32>;
+ [
+ a: "A",
+ b: "B",
+ c: "C",
+ d: "D",
+ e: "E",
+ ] as NodeId, [
+ ab: a -> b: 10f32,
+ ac: a -> c: 5f32,
+ bd: b -> d: 1f32,
+ bc: b -> c: 2f32,
+ de: d -> e: 1f32,
+ cb: c -> b: 3f32,
+ cd: c -> d: 5f32,
+ ce: c -> e: 2f32,
+ ea: e -> a: 7f32,
+ ed: e -> d: 6f32,
+ ] as EdgeId
+);
+
+#[test]
+fn source_does_not_exist() {
+ let GraphCollection { mut graph, .. } = networkx::create();
+
+ let f = *graph.insert_node("F").id();
+ graph.remove_node(&f);
+
+ let spfa = BellmanFord::directed();
+ let Err(received) = spfa.path_from(&graph, &f) else {
+ panic!("Expected an error");
+ };
+ let error = received.current_context();
+
+ assert_eq!(error, &BellmanFordError::NodeNotFound);
+}
+
+#[test]
+fn negative_cycle_heuristic() {
+ let mut graph = DiDinoGraph::new();
+
+ let a = *graph.insert_node("A").id();
+ let b = *graph.insert_node("B").id();
+ let c = *graph.insert_node("C").id();
+ let d = *graph.insert_node("D").id();
+
+ graph.insert_edge(-1f32, &a, &b);
+ graph.insert_edge(-1f32, &b, &c);
+ graph.insert_edge(-1f32, &c, &d);
+ graph.insert_edge(3f32, &d, &a);
+
+ let spfa = BellmanFord::directed();
+ assert!(spfa.every_path(&graph).is_ok());
+
+ let ca = *graph.insert_edge(1.999, &c, &a).id();
+ assert!(spfa.every_path(&graph).is_err());
+
+ *graph.edge_mut(&ca).unwrap().weight_mut() = 2.0;
+ assert!(spfa.every_path(&graph).is_ok());
+}
+
+fn cycle_graph<const N: usize, S>() -> (Graph<S>, [S::NodeId; N], [S::EdgeId; N])
+where
+ S: GraphStorage<NodeWeight = usize, EdgeWeight = f32>,
+ S::NodeId: ManagedGraphId + Copy,
+ S::EdgeId: ManagedGraphId + Copy,
+{
+ let mut graph = Graph::new();
+
+ let nodes: [_; N] = array::from_fn(|index| *graph.insert_node(index).id());
+
+ let edges: [_; N] = array::from_fn(|index| {
+ *graph
+ .insert_edge(1f32, &nodes[index], &nodes[(index + 1) % N])
+ .id()
+ });
+
+ (graph, nodes, edges)
+}
+
+fn complete_graph<const N: usize, S>() -> (Graph<S>, [S::NodeId; N], Vec<S::EdgeId>)
+where
+ S: GraphStorage<NodeWeight = usize, EdgeWeight = f32>,
+ S::NodeId: ManagedGraphId + Copy,
+ S::EdgeId: ManagedGraphId + Copy,
+{
+ let mut graph = Graph::new();
+
+ let nodes: [_; N] = array::from_fn(|index| *graph.insert_node(index).id());
+
+ let mut edges = Vec::with_capacity(N * (N - 1) / 2);
+
+ for i in 0..N {
+ for j in i + 1..N {
+ edges.push(*graph.insert_edge(1f32, &nodes[i], &nodes[j]).id());
+ }
+ }
+
+ (graph, nodes, edges)
+}
+
+fn path_graph<const N: usize, S>() -> (Graph<S>, [S::NodeId; N], Vec<S::EdgeId>)
+where
+ S: GraphStorage<NodeWeight = usize, EdgeWeight = f32>,
+ S::NodeId: ManagedGraphId + Copy,
+ S::EdgeId: ManagedGraphId + Copy,
+{
+ let mut graph = Graph::new();
+
+ let nodes: [_; N] = array::from_fn(|index| *graph.insert_node(index).id());
+
+ let mut edges = Vec::with_capacity(N - 1);
+
+ for i in 0..N - 1 {
+ edges.push(*graph.insert_edge(1f32, &nodes[i], &nodes[i + 1]).id());
+ }
+
+ (graph, nodes, edges)
+}
+
+#[test]
+fn negative_cycle_multigraph_directed() {
+ let (mut graph, nodes, _) = cycle_graph::<5, DinoStorage<_, _>>();
+
+ let spfa = BellmanFord::directed();
+ assert!(spfa.every_path(&graph).is_ok());
+
+ // add negative cycle between nodes 1 and 2
+ *graph.insert_edge(-7f32, &nodes[1], &nodes[2]).id();
+ assert!(spfa.every_path(&graph).is_err());
+}
+
+#[test]
+fn negative_cycle_multigraph_undirected() {
+ let (mut graph, nodes, _) = cycle_graph::<5, DinoStorage<_, _, Undirected>>();
+
+ let spfa = BellmanFord::undirected();
+ assert!(spfa.every_path(&graph).is_ok());
+
+ // add negative cycle between nodes 1 and 2
+ *graph.insert_edge(-3f32, &nodes[1], &nodes[2]).id();
+ assert!(spfa.every_path(&graph).is_err());
+}
+
+#[test]
+fn negative_self_cycle() {
+ let mut graph = DiDinoGraph::new();
+
+ let a = *graph.insert_node("A").id();
+
+ graph.insert_edge(-1f32, &a, &a);
+
+ let spfa = BellmanFord::directed();
+ assert!(spfa.every_path(&graph).is_err());
+}
+
+#[test]
+fn zero_cycle() {
+ let (mut graph, nodes, _) = cycle_graph::<5, DinoStorage<_, _>>();
+
+ let spfa = BellmanFord::directed();
+ assert!(spfa.every_path(&graph).is_ok());
+
+ // add zero cycle between nodes 2 and 3
+ let edge = *graph.insert_edge(-4f32, &nodes[2], &nodes[3]).id();
+ assert!(spfa.every_path(&graph).is_ok());
+
+ // increase that cycle to a negative cycle
+ *graph.edge_mut(&edge).unwrap().weight_mut() = -4.0001f32;
+ assert!(spfa.every_path(&graph).is_err());
+}
+
+#[test]
+fn negative_weight() {
+ let (mut graph, nodes, _) = cycle_graph::<5, DinoStorage<_, _, Directed>>();
+
+ let spfa = BellmanFord::directed();
+ assert!(spfa.every_path(&graph).is_ok());
+
+ // add negative weight to edge between nodes 1 and 2
+ graph.insert_edge(-3f32, &nodes[1], &nodes[2]);
+
+ let expected = expected!(nodes; [
+ 0 -()> 0: 0f32,
+ 0 -()> 1: 1f32,
+ 0 -(1)> 2: -2f32,
+ 0 -(1, 2)> 3: -1f32,
+ 0 -(1, 2, 3)> 4: 0f32,
+ ]);
+
+ TestCase::new(&graph, &spfa, &expected).assert_path_from(&nodes[0]);
+}
+
+#[test]
+fn not_connected() {
+ let (mut graph, nodes, _) = complete_graph::<6, DinoStorage<_, _>>();
+
+ let g = *graph.insert_node(10).id();
+ let h = *graph.insert_node(11).id();
+ let i = *graph.insert_node(12).id();
+
+ graph.insert_edge(1f32, &g, &h);
+ graph.insert_edge(1f32, &g, &i);
+
+ let spfa = BellmanFord::directed();
+
+ let expected = expected!(nodes; [
+ 0 -()> 0: 0f32,
+ 0 -()> 1: 1f32,
+ 0 -()> 2: 1f32,
+ 0 -()> 3: 1f32,
+ 0 -()> 4: 1f32,
+ 0 -()> 5: 1f32,
+ ]);
+
+ TestCase::new(&graph, &spfa, &expected).assert_path_from(&nodes[0]);
+}
+
+#[test]
+fn negative_cycle_not_connected() {
+ let (mut graph, nodes, _) = complete_graph::<6, DinoStorage<_, _>>();
+
+ let g = *graph.insert_node(10).id();
+ let h = *graph.insert_node(11).id();
+ let i = *graph.insert_node(12).id();
+
+ graph.insert_edge(1f32, &g, &h);
+ graph.insert_edge(1f32, &h, &i);
+ graph.insert_edge(-3f32, &i, &g);
+
+ let spfa = BellmanFord::directed();
+
+ let expected = expected!(nodes; [
+ 0 -()> 0: 0f32,
+ 0 -()> 1: 1f32,
+ 0 -()> 2: 1f32,
+ 0 -()> 3: 1f32,
+ 0 -()> 4: 1f32,
+ 0 -()> 5: 1f32,
+ ]);
+
+ TestCase::new(&graph, &spfa, &expected).assert_path_from(&nodes[0]);
+}
+
+#[test]
+fn path() {
+ let (graph, nodes, _) = path_graph::<5, DinoStorage<_, _>>();
+
+ let spfa = BellmanFord::directed();
+
+ let expected = expected!(nodes; [
+ 0 -()> 0: 0f32,
+ 0 -()> 1: 1f32,
+ 0 -(1)> 2: 2f32,
+ 0 -(1, 2)> 3: 3f32,
+ 0 -(1, 2, 3)> 4: 4f32,
+ ]);
+
+ TestCase::new(&graph, &spfa, &expected).assert_path_from(&nodes[0]);
+}
diff --git a/crates/algorithms/src/shortest_paths/common/closures.rs b/crates/algorithms/src/shortest_paths/common/closures.rs
new file mode 100644
index 0000000..8d701aa
--- /dev/null
+++ b/crates/algorithms/src/shortest_paths/common/closures.rs
@@ -0,0 +1,66 @@
+use core::marker::PhantomData;
+
+use numi::borrow::Moo;
+use petgraph_core::{Edge, GraphStorage, Node};
+
+use crate::shortest_paths::GraphCost;
+
+pub fn cost<S, T>(closure: impl Fn(Edge<S>) -> Moo<T>) -> impl Fn(Edge<S>) -> Moo<T> {
+ closure
+}
+
+pub fn heuristic<S, T>(
+ closure: impl for<'graph> Fn(Node<'graph, S>, Node<'graph, S>) -> Moo<'graph, T>,
+) -> impl for<'graph> Fn(Node<'graph, S>, Node<'graph, S>) -> Moo<'graph, T>
+where
+ S: GraphStorage,
+{
+ closure
+}
+
+#[cfg(test)]
+mod test {
+ use numi::borrow::Moo;
+ use petgraph_dino::DiDinoGraph;
+
+ use crate::shortest_paths::{
+ common::closures::{cost, heuristic},
+ AStar, Dijkstra, ShortestPath,
+ };
+
+ #[test]
+ fn bind_cost() {
+ let closure = cost(|edge| Moo::Borrowed(edge.weight()));
+
+ let algorithm = Dijkstra::undirected().with_edge_cost(closure);
+
+ let mut graph = DiDinoGraph::new();
+ let a = *graph.insert_node("A").id();
+ let b = *graph.insert_node("B").id();
+
+ graph.insert_edge(7, &a, &b);
+
+ let path = algorithm.path_between(&graph, &a, &b).expect("path exists");
+ }
+
+ #[test]
+ fn bind_heuristic() {
+ let closure = heuristic(|source, target| Moo::Owned(0i32));
+
+ let algorithm = AStar::undirected().with_heuristic(closure);
+
+ let mut graph = DiDinoGraph::new();
+ let a = *graph.insert_node("A").id();
+ let b = *graph.insert_node("B").id();
+
+ graph.insert_edge(7i32, &a, &b);
+
+ let path = algorithm.path_between(&graph, &a, &b).expect("path exists");
+ }
+}
+
+// pub fn bind_heuristic<S, T>(
+// closure: impl Fn(Node<S>, Node<S>) -> Moo<T>,
+// ) -> impl Fn(Node<S>, Node<S>) -> Moo<T> {
+// closure
+// }
diff --git a/crates/algorithms/src/shortest_paths/common/cost.rs b/crates/algorithms/src/shortest_paths/common/cost.rs
index 8169b0a..7cc6277 100644
--- a/crates/algorithms/src/shortest_paths/common/cost.rs
+++ b/crates/algorithms/src/shortest_paths/common/cost.rs
@@ -1,6 +1,7 @@
use core::{borrow::Borrow, fmt::Display};
-use petgraph_core::{base::MaybeOwned, Edge, GraphStorage};
+use numi::borrow::Moo;
+use petgraph_core::{Edge, GraphStorage};
#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Cost<T>(T);
@@ -59,17 +60,17 @@
{
type Value;
- fn cost<'a>(&self, edge: Edge<'a, S>) -> MaybeOwned<'a, Self::Value>;
+ fn cost<'graph>(&self, edge: Edge<'graph, S>) -> Moo<'graph, Self::Value>;
}
impl<S, F, T> GraphCost<S> for F
where
S: GraphStorage,
- F: Fn(Edge<S>) -> MaybeOwned<T>,
+ F: Fn(Edge<S>) -> Moo<T>,
{
type Value = T;
- fn cost<'a>(&self, edge: Edge<'a, S>) -> MaybeOwned<'a, T> {
+ fn cost<'graph>(&self, edge: Edge<'graph, S>) -> Moo<'graph, T> {
self(edge)
}
}
@@ -80,14 +81,15 @@
{
type Value = S::EdgeWeight;
- fn cost<'a>(&self, edge: Edge<'a, S>) -> MaybeOwned<'a, S::EdgeWeight> {
- MaybeOwned::Borrowed(edge.weight())
+ fn cost<'graph>(&self, edge: Edge<'graph, S>) -> Moo<'graph, S::EdgeWeight> {
+ Moo::Borrowed(edge.weight())
}
}
#[cfg(test)]
mod tests {
- use petgraph_core::{base::MaybeOwned, edge::marker::Directed, Edge, GraphStorage};
+ use numi::borrow::Moo;
+ use petgraph_core::{edge::marker::Directed, Edge, GraphStorage};
use petgraph_dino::DinoStorage;
use crate::shortest_paths::common::cost::{DefaultCost, GraphCost};
@@ -99,7 +101,7 @@
{
}
- fn maybe_edge_cost<S>(edge: Edge<S>) -> MaybeOwned<'_, usize>
+ fn maybe_edge_cost<S>(edge: Edge<S>) -> Moo<'_, usize>
where
S: GraphStorage,
S::EdgeWeight: AsRef<[u8]>,
diff --git a/crates/algorithms/src/shortest_paths/common/mod.rs b/crates/algorithms/src/shortest_paths/common/mod.rs
index a1fd686..ea32da1 100644
--- a/crates/algorithms/src/shortest_paths/common/mod.rs
+++ b/crates/algorithms/src/shortest_paths/common/mod.rs
@@ -1,3 +1,5 @@
+//! Common utility types, traits and functions for shortest paths algorithms.
+mod closures;
pub(super) mod connections;
pub(super) mod cost;
pub(super) mod path;
diff --git a/crates/algorithms/src/shortest_paths/common/path.rs b/crates/algorithms/src/shortest_paths/common/path.rs
index b79088e..25a4192 100644
--- a/crates/algorithms/src/shortest_paths/common/path.rs
+++ b/crates/algorithms/src/shortest_paths/common/path.rs
@@ -1,28 +1,33 @@
-use core::fmt::{Debug, Display, Formatter};
-use std::{
+use alloc::vec::Vec;
+use core::{
cmp::Ordering,
+ fmt::{Debug, Display, Formatter},
hash::{Hash, Hasher},
iter::once,
};
use petgraph_core::{GraphStorage, Node};
-pub struct Path<'a, S>
+pub struct Path<'graph, S>
where
S: GraphStorage,
{
- source: Node<'a, S>,
- target: Node<'a, S>,
+ source: Node<'graph, S>,
+ target: Node<'graph, S>,
- transit: Vec<Node<'a, S>>,
+ transit: Vec<Node<'graph, S>>,
}
-impl<'a, S> Path<'a, S>
+impl<'graph, S> Path<'graph, S>
where
S: GraphStorage,
{
#[must_use]
- pub const fn new(source: Node<'a, S>, transit: Vec<Node<'a, S>>, target: Node<'a, S>) -> Self {
+ pub fn new(
+ source: Node<'graph, S>,
+ transit: Vec<Node<'graph, S>>,
+ target: Node<'graph, S>,
+ ) -> Self {
Self {
source,
target,
@@ -31,22 +36,22 @@
}
#[must_use]
- pub const fn source(&self) -> Node<'a, S> {
+ pub const fn source(&self) -> Node<'graph, S> {
self.source
}
#[must_use]
- pub const fn target(&self) -> Node<'a, S> {
+ pub const fn target(&self) -> Node<'graph, S> {
self.target
}
#[must_use]
- pub fn transit(&self) -> &[Node<'a, S>] {
+ pub fn transit(&self) -> &[Node<'graph, S>] {
&self.transit
}
#[must_use]
- pub fn to_vec(self) -> Vec<Node<'a, S>> {
+ pub fn to_vec(self) -> Vec<Node<'graph, S>> {
let mut vec = Vec::with_capacity(self.transit.len() + 2);
vec.push(self.source);
@@ -56,7 +61,7 @@
vec
}
- pub fn iter(&self) -> impl Iterator<Item = Node<'a, S>> + '_ {
+ pub fn iter(&self) -> impl Iterator<Item = Node<'graph, S>> + '_ {
once(self.source)
.chain(self.transit.iter().copied())
.chain(once(self.target))
@@ -80,10 +85,10 @@
#[cfg(test)]
static_assertions::assert_impl_all!(Path<'_, petgraph_dino::DinoStorage<(), ()>>: Debug, Display, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Send, Sync);
-impl<'a, S> Debug for Path<'a, S>
+impl<'graph, S> Debug for Path<'graph, S>
where
S: GraphStorage,
- Node<'a, S>: Debug,
+ Node<'graph, S>: Debug,
{
fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
f.debug_struct("Path")
@@ -123,10 +128,10 @@
}
}
-impl<'a, S> PartialEq for Path<'a, S>
+impl<'graph, S> PartialEq for Path<'graph, S>
where
S: GraphStorage,
- Node<'a, S>: PartialEq,
+ Node<'graph, S>: PartialEq,
{
fn eq(&self, other: &Self) -> bool {
(&self.source, &self.target, &self.transit)
@@ -134,17 +139,17 @@
}
}
-impl<'a, S> Eq for Path<'a, S>
+impl<'graph, S> Eq for Path<'graph, S>
where
S: GraphStorage,
- Node<'a, S>: Eq,
+ Node<'graph, S>: Eq,
{
}
-impl<'a, S> PartialOrd for Path<'a, S>
+impl<'graph, S> PartialOrd for Path<'graph, S>
where
S: GraphStorage,
- Node<'a, S>: PartialOrd,
+ Node<'graph, S>: PartialOrd,
{
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
(&self.source, &self.transit, &self.target).partial_cmp(&(
@@ -155,10 +160,10 @@
}
}
-impl<'a, S> Ord for Path<'a, S>
+impl<'graph, S> Ord for Path<'graph, S>
where
S: GraphStorage,
- Node<'a, S>: Ord,
+ Node<'graph, S>: Ord,
{
fn cmp(&self, other: &Self) -> Ordering {
(&self.source, &self.transit, &self.target).cmp(&(
@@ -169,22 +174,22 @@
}
}
-impl<'a, S> Hash for Path<'a, S>
+impl<'graph, S> Hash for Path<'graph, S>
where
S: GraphStorage,
- Node<'a, S>: Hash,
+ Node<'graph, S>: Hash,
{
fn hash<H: Hasher>(&self, state: &mut H) {
(&self.source, &self.target, &self.transit).hash(state);
}
}
-impl<'a, S> IntoIterator for Path<'a, S>
+impl<'graph, S> IntoIterator for Path<'graph, S>
where
S: GraphStorage,
{
- type IntoIter = alloc::vec::IntoIter<Node<'a, S>>;
- type Item = Node<'a, S>;
+ type IntoIter = alloc::vec::IntoIter<Node<'graph, S>>;
+ type Item = Node<'graph, S>;
fn into_iter(self) -> Self::IntoIter {
self.to_vec().into_iter()
diff --git a/crates/algorithms/src/shortest_paths/common/queue/double_ended.rs b/crates/algorithms/src/shortest_paths/common/queue/double_ended.rs
index b436b88..2083b63 100644
--- a/crates/algorithms/src/shortest_paths/common/queue/double_ended.rs
+++ b/crates/algorithms/src/shortest_paths/common/queue/double_ended.rs
@@ -1,49 +1,181 @@
use alloc::collections::VecDeque;
+use core::{
+ hash::Hash,
+ iter::Sum,
+ ops::{Add, Div},
+};
+
+use fxhash::FxBuildHasher;
+use hashbrown::HashSet;
+use numi::{
+ cast::{CastFrom, CastTo, TryCastFrom},
+ num::identity::Zero,
+};
+use petgraph_core::{GraphStorage, Node};
+
+pub(in crate::shortest_paths) struct DoubleEndedQueueItem<'graph, S, T>
+where
+ S: GraphStorage,
+{
+ node: Node<'graph, S>,
+
+ priority: T,
+}
+
+impl<'graph, S, T> DoubleEndedQueueItem<'graph, S, T>
+where
+ S: GraphStorage,
+{
+ pub(in crate::shortest_paths) fn node(&self) -> Node<'graph, S> {
+ self.node
+ }
+
+ pub(in crate::shortest_paths) fn priority(&self) -> &T {
+ &self.priority
+ }
+
+ pub(in crate::shortest_paths) fn into_parts(self) -> (Node<'graph, S>, T) {
+ (self.node, self.priority)
+ }
+}
// Newtype for VecDeque<T> to avoid exposing the VecDeque type as we may decide to reimplement this.
-pub(in crate::shortest_paths) struct DoubleEndedQueue<T>(VecDeque<T>);
-
-impl<T> DoubleEndedQueue<T>
+pub(in crate::shortest_paths) struct DoubleEndedQueue<'graph, S, T>
where
- T: PartialEq,
+ S: GraphStorage,
+{
+ queue: VecDeque<DoubleEndedQueueItem<'graph, S, T>>,
+ active: HashSet<&'graph S::NodeId, FxBuildHasher>,
+}
+
+impl<'graph, S, T> DoubleEndedQueue<'graph, S, T>
+where
+ S: GraphStorage,
+ S::NodeId: Eq + Hash,
{
pub(in crate::shortest_paths) fn new() -> Self {
- Self(VecDeque::new())
+ Self {
+ queue: VecDeque::new(),
+ active: HashSet::with_hasher(FxBuildHasher::default()),
+ }
}
pub(in crate::shortest_paths) fn with_capacity(capacity: usize) -> Self {
- Self(VecDeque::with_capacity(capacity))
+ Self {
+ queue: VecDeque::with_capacity(capacity),
+ active: HashSet::with_capacity_and_hasher(capacity, FxBuildHasher::default()),
+ }
}
- pub(in crate::shortest_paths) fn push_front(&mut self, item: T) {
- self.0.push_front(item);
+ // TODO: this has potential for speedup by not needing to update the priority
+ fn update_priority(&mut self, node: Node<'graph, S>, priority: T) {
+ let id = node.id();
+
+ if let Some(item) = self.queue.iter_mut().find(|item| item.node.id() == id) {
+ item.priority = priority;
+ }
}
- pub(in crate::shortest_paths) fn push_back(&mut self, item: T) {
- self.0.push_back(item);
+ pub(in crate::shortest_paths) fn push_front(
+ &mut self,
+ node: Node<'graph, S>,
+ priority: T,
+ ) -> bool {
+ if !self.active.insert(node.id()) {
+ self.update_priority(node, priority);
+ return false;
+ }
+
+ self.queue
+ .push_front(DoubleEndedQueueItem { node, priority });
+ true
}
- pub(in crate::shortest_paths) fn pop_front(&mut self) -> Option<T> {
- self.0.pop_front()
+ pub(in crate::shortest_paths) fn push_back(
+ &mut self,
+ node: Node<'graph, S>,
+ priority: T,
+ ) -> bool {
+ if !self.active.insert(node.id()) {
+ self.update_priority(node, priority);
+ return false;
+ }
+
+ self.queue
+ .push_back(DoubleEndedQueueItem { node, priority });
+ true
}
- pub(in crate::shortest_paths) fn pop_back(&mut self) -> Option<T> {
- self.0.pop_back()
+ pub(in crate::shortest_paths) fn pop_front(
+ &mut self,
+ ) -> Option<DoubleEndedQueueItem<'graph, S, T>> {
+ let value = self.queue.pop_front()?;
+
+ self.active.remove(value.node.id());
+
+ Some(value)
}
- pub(in crate::shortest_paths) fn front(&self) -> Option<&T> {
- self.0.front()
+ pub(in crate::shortest_paths) fn pop_back(
+ &mut self,
+ ) -> Option<DoubleEndedQueueItem<'graph, S, T>> {
+ let value = self.queue.pop_back()?;
+
+ self.active.remove(value.node.id());
+
+ Some(value)
}
- pub(in crate::shortest_paths) fn back(&self) -> Option<&T> {
- self.0.back()
+ pub(in crate::shortest_paths) fn peek_front(
+ &self,
+ ) -> Option<&DoubleEndedQueueItem<'graph, S, T>> {
+ self.queue.front()
+ }
+
+ pub(in crate::shortest_paths) fn peek_back(
+ &self,
+ ) -> Option<&DoubleEndedQueueItem<'graph, S, T>> {
+ self.queue.back()
}
pub(in crate::shortest_paths) fn is_empty(&self) -> bool {
- self.0.is_empty()
+ self.queue.is_empty()
}
- pub(in crate::shortest_paths) fn contains(&self, item: &T) -> bool {
- self.0.contains(item)
+ pub(in crate::shortest_paths) fn len(&self) -> usize {
+ self.queue.len()
+ }
+
+ pub(in crate::shortest_paths) fn contains_node(&self, node: &S::NodeId) -> bool {
+ self.active.contains(node)
+ }
+}
+
+impl<'graph, S, T> DoubleEndedQueue<'graph, S, T>
+where
+ S: GraphStorage,
+{
+ pub(in crate::shortest_paths) fn average_priority(&self) -> Option<T>
+ where
+ T: Zero + Div<Output = T> + Add<Output = T> + for<'a> Sum<&'a T> + TryCastFrom<usize>,
+ {
+ let (front, back) = self.queue.as_slices();
+
+ let front_sum: T = front.iter().map(|item| &item.priority).sum();
+ let back_sum: T = back.iter().map(|item| &item.priority).sum();
+
+ let total_sum: T = front_sum + back_sum;
+
+ if self.queue.is_empty() {
+ return None;
+ }
+
+ let length: T = TryCastFrom::try_cast_from(self.queue.len()).ok()?;
+
+ if length.is_zero() {
+ return None;
+ }
+
+ Some(total_sum / length)
}
}
diff --git a/crates/algorithms/src/shortest_paths/common/route.rs b/crates/algorithms/src/shortest_paths/common/route.rs
index ef9031a..23829fc 100644
--- a/crates/algorithms/src/shortest_paths/common/route.rs
+++ b/crates/algorithms/src/shortest_paths/common/route.rs
@@ -1,28 +1,30 @@
-use core::fmt::{Debug, Display};
-use std::hash::Hash;
+use core::{
+ fmt::{Debug, Display},
+ hash::Hash,
+};
use petgraph_core::{GraphStorage, Node};
use crate::shortest_paths::common::{cost::Cost, path::Path};
-pub struct Route<'a, S, T>
+pub struct Route<'graph, S, T>
where
S: GraphStorage,
{
- path: Path<'a, S>,
+ path: Path<'graph, S>,
cost: Cost<T>,
}
-impl<'a, S, T> Route<'a, S, T>
+impl<'graph, S, T> Route<'graph, S, T>
where
S: GraphStorage,
{
- pub const fn new(path: Path<'a, S>, cost: Cost<T>) -> Self {
+ pub const fn new(path: Path<'graph, S>, cost: Cost<T>) -> Self {
Self { path, cost }
}
- pub const fn path(&self) -> &Path<'a, S> {
+ pub const fn path(&self) -> &Path<'graph, S> {
&self.path
}
@@ -34,11 +36,11 @@
self.cost
}
- pub fn into_path(self) -> Path<'a, S> {
+ pub fn into_path(self) -> Path<'graph, S> {
self.path
}
- pub fn into_parts(self) -> (Path<'a, S>, Cost<T>) {
+ pub fn into_parts(self) -> (Path<'graph, S>, Cost<T>) {
(self.path, self.cost)
}
@@ -55,10 +57,10 @@
#[cfg(test)]
static_assertions::assert_impl_all!(Route<'_, petgraph_dino::DinoStorage<(), ()>, &'static str>: Debug, Display, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Send, Sync);
-impl<'a, S, T> Debug for Route<'a, S, T>
+impl<'graph, S, T> Debug for Route<'graph, S, T>
where
S: GraphStorage,
- Node<'a, S>: Debug,
+ Node<'graph, S>: Debug,
T: Debug,
{
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
@@ -83,7 +85,7 @@
}
}
-impl<'a, S, T> Clone for Route<'a, S, T>
+impl<'graph, S, T> Clone for Route<'graph, S, T>
where
S: GraphStorage,
T: Clone,
@@ -96,10 +98,10 @@
}
}
-impl<'a, S, T> PartialEq for Route<'a, S, T>
+impl<'graph, S, T> PartialEq for Route<'graph, S, T>
where
S: GraphStorage,
- Path<'a, S>: PartialEq,
+ Path<'graph, S>: PartialEq,
T: PartialEq,
{
fn eq(&self, other: &Self) -> bool {
@@ -107,18 +109,18 @@
}
}
-impl<'a, S, T> Eq for Route<'a, S, T>
+impl<'graph, S, T> Eq for Route<'graph, S, T>
where
S: GraphStorage,
- Path<'a, S>: Eq,
+ Path<'graph, S>: Eq,
T: Eq,
{
}
-impl<'a, S, T> PartialOrd for Route<'a, S, T>
+impl<'graph, S, T> PartialOrd for Route<'graph, S, T>
where
S: GraphStorage,
- Path<'a, S>: PartialOrd,
+ Path<'graph, S>: PartialOrd,
T: PartialOrd,
{
fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
@@ -127,10 +129,10 @@
}
}
-impl<'a, S, T> Ord for Route<'a, S, T>
+impl<'graph, S, T> Ord for Route<'graph, S, T>
where
S: GraphStorage,
- Path<'a, S>: Ord,
+ Path<'graph, S>: Ord,
T: Ord,
{
fn cmp(&self, other: &Self) -> core::cmp::Ordering {
@@ -138,10 +140,10 @@
}
}
-impl<'a, S, T> Hash for Route<'a, S, T>
+impl<'graph, S, T> Hash for Route<'graph, S, T>
where
S: GraphStorage,
- Path<'a, S>: Hash,
+ Path<'graph, S>: Hash,
T: Hash,
{
fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
@@ -149,21 +151,21 @@
}
}
-pub struct DirectRoute<'a, S, T>
+pub struct DirectRoute<'graph, S, T>
where
S: GraphStorage,
{
- source: Node<'a, S>,
- target: Node<'a, S>,
+ source: Node<'graph, S>,
+ target: Node<'graph, S>,
cost: Cost<T>,
}
-impl<'a, S, T> DirectRoute<'a, S, T>
+impl<'graph, S, T> DirectRoute<'graph, S, T>
where
S: GraphStorage,
{
- pub const fn new(source: Node<'a, S>, target: Node<'a, S>, cost: Cost<T>) -> Self {
+ pub const fn new(source: Node<'graph, S>, target: Node<'graph, S>, cost: Cost<T>) -> Self {
Self {
source,
target,
@@ -171,11 +173,11 @@
}
}
- pub const fn source(&self) -> &Node<'a, S> {
+ pub const fn source(&self) -> &Node<'graph, S> {
&self.source
}
- pub const fn target(&self) -> &Node<'a, S> {
+ pub const fn target(&self) -> &Node<'graph, S> {
&self.target
}
@@ -183,7 +185,7 @@
&self.cost
}
- pub fn into_endpoints(self) -> (Node<'a, S>, Node<'a, S>) {
+ pub fn into_endpoints(self) -> (Node<'graph, S>, Node<'graph, S>) {
(self.source, self.target)
}
@@ -191,7 +193,7 @@
self.cost
}
- pub fn into_parts(self) -> (Node<'a, S>, Node<'a, S>, Cost<T>) {
+ pub fn into_parts(self) -> (Node<'graph, S>, Node<'graph, S>, Cost<T>) {
(self.source, self.target, self.cost)
}
@@ -209,10 +211,10 @@
#[cfg(test)]
static_assertions::assert_impl_all!(DirectRoute<'_, petgraph_dino::DinoStorage<(), ()>, &'static str>: Debug, Display, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Send, Sync);
-impl<'a, S, T> Debug for DirectRoute<'a, S, T>
+impl<'graph, S, T> Debug for DirectRoute<'graph, S, T>
where
S: GraphStorage,
- Node<'a, S>: Debug,
+ Node<'graph, S>: Debug,
T: Debug,
{
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
@@ -240,7 +242,7 @@
}
}
-impl<'a, S, T> Clone for DirectRoute<'a, S, T>
+impl<'graph, S, T> Clone for DirectRoute<'graph, S, T>
where
S: GraphStorage,
T: Clone,
@@ -254,10 +256,10 @@
}
}
-impl<'a, S, T> PartialEq for DirectRoute<'a, S, T>
+impl<'graph, S, T> PartialEq for DirectRoute<'graph, S, T>
where
S: GraphStorage,
- Node<'a, S>: PartialEq,
+ Node<'graph, S>: PartialEq,
T: PartialEq,
{
fn eq(&self, other: &Self) -> bool {
@@ -265,18 +267,18 @@
}
}
-impl<'a, S, T> Eq for DirectRoute<'a, S, T>
+impl<'graph, S, T> Eq for DirectRoute<'graph, S, T>
where
S: GraphStorage,
- Node<'a, S>: Eq,
+ Node<'graph, S>: Eq,
T: Eq,
{
}
-impl<'a, S, T> PartialOrd for DirectRoute<'a, S, T>
+impl<'graph, S, T> PartialOrd for DirectRoute<'graph, S, T>
where
S: GraphStorage,
- Node<'a, S>: PartialOrd,
+ Node<'graph, S>: PartialOrd,
T: PartialOrd,
{
fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
@@ -289,10 +291,10 @@
}
}
-impl<'a, S, T> Ord for DirectRoute<'a, S, T>
+impl<'graph, S, T> Ord for DirectRoute<'graph, S, T>
where
S: GraphStorage,
- Node<'a, S>: Ord,
+ Node<'graph, S>: Ord,
T: Ord,
{
fn cmp(&self, other: &Self) -> core::cmp::Ordering {
@@ -300,10 +302,10 @@
}
}
-impl<'a, S, T> Hash for DirectRoute<'a, S, T>
+impl<'graph, S, T> Hash for DirectRoute<'graph, S, T>
where
S: GraphStorage,
- Node<'a, S>: Hash,
+ Node<'graph, S>: Hash,
T: Hash,
{
fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
@@ -311,12 +313,12 @@
}
}
-impl<'a, S, T> From<Route<'a, S, T>> for DirectRoute<'a, S, T>
+impl<'graph, S, T> From<Route<'graph, S, T>> for DirectRoute<'graph, S, T>
where
S: GraphStorage,
T: Clone,
{
- fn from(route: Route<'a, S, T>) -> Self {
+ fn from(route: Route<'graph, S, T>) -> Self {
Self {
source: route.path.source(),
target: route.path.target(),
diff --git a/crates/algorithms/src/shortest_paths/common/tests.rs b/crates/algorithms/src/shortest_paths/common/tests.rs
index 1b4b9d5..0839623 100644
--- a/crates/algorithms/src/shortest_paths/common/tests.rs
+++ b/crates/algorithms/src/shortest_paths/common/tests.rs
@@ -16,14 +16,22 @@
/// readable
macro_rules! expected {
(@rule $nodes:ident; $source:ident; ($($path:ident),*) ;$target:ident; $cost:literal) => {
- Expect {
+ $crate::shortest_paths::common::tests::Expect {
source: $nodes.$source,
target: $nodes.$target,
transit: alloc::vec![$($nodes.$path),*],
cost: $cost,
}
};
- ($nodes:ident; [$($source:ident -( $($path:ident),* )> $target:ident : $cost:literal),* $(,)?]) => {
+ (@rule $nodes:ident; $source:literal; ($($path:literal),*) ;$target:literal; $cost:literal) => {
+ $crate::shortest_paths::common::tests::Expect {
+ source: $nodes[$source],
+ target: $nodes[$target],
+ transit: alloc::vec![$($nodes[$path]),*],
+ cost: $cost,
+ }
+ };
+ ($nodes:ident; [$($source:tt -( $($path:tt),* )> $target:tt : $cost:literal),* $(,)?]) => {
alloc::vec![
$(expected!(@rule $nodes; $source; ($($path),*) ;$target; $cost)),*
]
@@ -32,35 +40,32 @@
pub(in crate::shortest_paths) use expected;
-pub(in crate::shortest_paths) struct Expect<G, T>
-where
- G: GraphExt,
-{
- pub(in crate::shortest_paths) source: <G::Storage as GraphStorage>::NodeId,
- pub(in crate::shortest_paths) target: <G::Storage as GraphStorage>::NodeId,
+pub(in crate::shortest_paths) struct Expect<N, T> {
+ pub(in crate::shortest_paths) source: N,
+ pub(in crate::shortest_paths) target: N,
- pub(in crate::shortest_paths) transit: Vec<<G::Storage as GraphStorage>::NodeId>,
+ pub(in crate::shortest_paths) transit: Vec<N>,
pub(in crate::shortest_paths) cost: T,
}
-pub(in crate::shortest_paths) struct TestCase<'a, G, A, T>
+pub(in crate::shortest_paths) struct TestCase<'a, S, A, T>
where
- G: GraphExt,
+ S: GraphStorage,
{
- graph: &'a Graph<G::Storage>,
+ graph: &'a Graph<S>,
algorithm: &'a A,
- expected: &'a [Expect<G, T>],
+ expected: &'a [Expect<S::NodeId, T>],
}
-impl<'a, G, A, T> TestCase<'a, G, A, T>
+impl<'a, S, A, T> TestCase<'a, S, A, T>
where
- G: GraphExt,
+ S: GraphStorage,
{
pub(crate) const fn new(
- graph: &'a Graph<G::Storage>,
+ graph: &'a Graph<S>,
algorithm: &'a A,
- expected: &'a [Expect<G, T>],
+ expected: &'a [Expect<<S as GraphStorage>::NodeId, T>],
) -> Self {
Self {
graph,
@@ -70,17 +75,15 @@
}
}
-impl<'a, G, A, T> TestCase<'a, G, A, T>
+impl<'a, S, A, T> TestCase<'a, S, A, T>
where
- G: GraphExt,
- <G::Storage as GraphStorage>::NodeId: Eq + Hash + Debug + Display,
- A: ShortestPath<G::Storage, Cost = T>,
+ S: GraphStorage,
+ S::NodeId: Eq + Hash + Debug + Display,
+ A: ShortestPath<S, Cost = T>,
T: PartialEq + Debug,
{
- fn assert_path_routes(
- &self,
- routes: Result<impl Iterator<Item = Route<'a, G::Storage, T>>, A::Error>,
- ) {
+ #[track_caller]
+ fn assert_path_routes(&self, routes: Result<impl Iterator<Item = Route<'a, S, T>>, A::Error>) {
let mut routes: HashMap<_, _> = routes
.unwrap()
.map(|route| {
@@ -116,24 +119,23 @@
self.assert_path_routes(self.algorithm.every_path(self.graph));
}
- pub(in crate::shortest_paths) fn assert_path_from(
- &self,
- source: &<G::Storage as GraphStorage>::NodeId,
- ) {
+ #[track_caller]
+ pub(in crate::shortest_paths) fn assert_path_from(&self, source: &S::NodeId) {
self.assert_path_routes(self.algorithm.path_from(self.graph, source));
}
}
-impl<'a, G, A, T> TestCase<'a, G, A, T>
+impl<'a, S, A, T> TestCase<'a, S, A, T>
where
- G: GraphExt,
- <G::Storage as GraphStorage>::NodeId: Eq + Hash + Debug + Display,
- A: ShortestDistance<G::Storage, Cost = T>,
+ S: GraphStorage,
+ S::NodeId: Eq + Hash + Debug + Display,
+ A: ShortestDistance<S, Cost = T>,
T: PartialEq + Debug,
{
+ #[track_caller]
fn assert_distance_routes(
&self,
- routes: Result<impl Iterator<Item = DirectRoute<'a, G::Storage, T>>, A::Error>,
+ routes: Result<impl Iterator<Item = DirectRoute<'a, S, T>>, A::Error>,
) {
let mut routes: HashMap<_, _> = routes
.unwrap()
@@ -171,21 +173,8 @@
self.assert_distance_routes(self.algorithm.every_distance(self.graph));
}
- pub(in crate::shortest_paths) fn assert_distance_from(
- &self,
- source: &<G::Storage as GraphStorage>::NodeId,
- ) {
+ #[track_caller]
+ pub(in crate::shortest_paths) fn assert_distance_from(&self, source: &S::NodeId) {
self.assert_distance_routes(self.algorithm.distance_from(self.graph, source));
}
}
-
-pub(in crate::shortest_paths) trait GraphExt {
- type Storage: GraphStorage;
-}
-
-impl<S> GraphExt for Graph<S>
-where
- S: GraphStorage,
-{
- type Storage = S;
-}
diff --git a/crates/algorithms/src/shortest_paths/common/transit.rs b/crates/algorithms/src/shortest_paths/common/transit.rs
index 62f1d4e..8921358 100644
--- a/crates/algorithms/src/shortest_paths/common/transit.rs
+++ b/crates/algorithms/src/shortest_paths/common/transit.rs
@@ -1,10 +1,7 @@
-use alloc::vec::Vec;
-use core::hash::Hash;
-use petgraph_core::{
- id::{AttributeGraphId, AttributeStorage},
- GraphStorage, Node,
-};
+
+use hashbrown::{HashMap, HashSet};
+use petgraph_core::{GraphStorage, Node};
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub(in crate::shortest_paths) enum PredecessorMode {
@@ -45,3 +42,80 @@
path
}
+
+/// Reconstruct all simple paths between two nodes without those nodes being part of the path.
+///
+/// This has been adapted from the [NetworkX implementation](https://github.com/networkx/networkx/blob/f93f0e2a066fc456aa447853af9d00eec1058542/networkx/algorithms/shortest_paths/generic.py#L655)
+pub(in crate::shortest_paths) fn reconstruct_paths_between<'a, 'graph, S, H>(
+ predecessors: &'a HashMap<&'graph S::NodeId, Vec<Node<'graph, S>>, H>,
+ source: &'graph S::NodeId,
+ target: Node<'graph, S>,
+) -> impl Iterator<Item = Vec<Node<'graph, S>>> + 'a
+where
+ S: GraphStorage,
+ S::NodeId: Eq + Hash,
+ H: BuildHasher,
+{
+ let mut seen = HashSet::new();
+ seen.insert(target.id());
+
+ let mut stack = vec![(target, 0usize)];
+ let mut top = 0;
+ // by using a `yielded` boolean, we're able to suspend and resume, as in the first iteration we
+ // early return and then try "again" in the next iteration but do not early return again.
+ let mut yielded = false;
+ let mut exhausted = false;
+
+ iter::from_fn(move || {
+ if exhausted {
+ return None;
+ }
+
+ loop {
+ let (node, index) = stack[top];
+
+ if !yielded && node.id() == source {
+ // "yield" result
+ yielded = true;
+
+ // we skip the first element (target) and last element (source)
+ let mut path: Vec<_> = stack.get(1..top)?.iter().map(|(node, _)| *node).collect();
+ path.reverse();
+
+ return Some(path);
+ }
+
+ if predecessors[node.id()].len() > index {
+ stack[top].1 = index + 1;
+ let next = predecessors[node.id()][index];
+ if !seen.insert(next.id()) {
+ // value already seen
+ continue;
+ }
+
+ top += 1;
+
+ if top == stack.len() {
+ stack.push((next, 0));
+ } else {
+ stack[top] = (next, 0);
+ }
+ } else {
+ seen.remove(&node.id());
+
+ match top.checked_sub(1) {
+ Some(new_top) => top = new_top,
+ None => {
+ // we have exhausted all paths
+ exhausted = true;
+ break;
+ }
+ }
+ }
+
+ yielded = false;
+ }
+
+ None
+ })
+}
diff --git a/crates/algorithms/src/shortest_paths/deprecated_bellman_ford.rs b/crates/algorithms/src/shortest_paths/deprecated_bellman_ford.rs
deleted file mode 100644
index 25f6761..0000000
--- a/crates/algorithms/src/shortest_paths/deprecated_bellman_ford.rs
+++ /dev/null
@@ -1,298 +0,0 @@
-//! Bellman-Ford algorithms.
-
-use alloc::{vec, vec::Vec};
-
-use funty::Floating;
-use petgraph_core::deprecated::visit::{
- EdgeRef, IntoEdges, IntoNodeIdentifiers, NodeCount, NodeIndexable, VisitMap, Visitable,
-};
-
-use crate::{error::NegativeCycleError, shortest_paths::FloatMeasure};
-
-#[derive(Debug, Clone)]
-pub struct Paths<NodeId, EdgeWeight> {
- pub distances: Vec<EdgeWeight>,
- pub predecessors: Vec<Option<NodeId>>,
-}
-
-/// \[Generic\] Compute shortest paths from node `source` to all other.
-///
-/// Using the [Bellman–Ford algorithm][bf]; negative edge costs are
-/// permitted, but the graph must not have a cycle of negative weights
-/// (in that case it will return an error).
-///
-/// On success, return one vec with path costs, and another one which points
-/// out the predecessor of a node along a shortest path. The vectors
-/// are indexed by the graph's node indices.
-///
-/// [bf]: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
-///
-/// # Example
-/// ```rust
-/// use petgraph_algorithms::shortest_paths::bellman_ford;
-/// use petgraph_core::edge::Undirected;
-/// use petgraph_graph::{Graph, NodeIndex};
-///
-/// let mut g = Graph::new();
-/// let a = g.add_node(()); // node with no weight
-/// let b = g.add_node(());
-/// let c = g.add_node(());
-/// let d = g.add_node(());
-/// let e = g.add_node(());
-/// let f = g.add_node(());
-/// g.extend_with_edges(&[
-/// (0, 1, 2.0),
-/// (0, 3, 4.0),
-/// (1, 2, 1.0),
-/// (1, 5, 7.0),
-/// (2, 4, 5.0),
-/// (4, 5, 1.0),
-/// (3, 4, 1.0),
-/// ]);
-///
-/// // Graph represented with the weight of each edge
-/// //
-/// // 2 1
-/// // a ----- b ----- c
-/// // | 4 | 7 |
-/// // d f | 5
-/// // | 1 | 1 |
-/// // \------ e ------/
-///
-/// let path = bellman_ford(&g, a);
-/// assert!(path.is_ok());
-/// let path = path.unwrap();
-/// assert_eq!(path.distances, vec![0.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
-/// assert_eq!(
-/// path.predecessors,
-/// vec![None, Some(a), Some(b), Some(a), Some(d), Some(e)]
-/// );
-///
-/// // Node f (indice 5) can be reach from a with a path costing 6.
-/// // Predecessor of f is Some(e) which predecessor is Some(d) which predecessor is Some(a).
-/// // Thus the path from a to f is a <-> d <-> e <-> f
-///
-/// let graph_with_neg_cycle = Graph::<(), f32, Undirected>::from_edges(&[
-/// (0, 1, -2.0),
-/// (0, 3, -4.0),
-/// (1, 2, -1.0),
-/// (1, 5, -25.0),
-/// (2, 4, -5.0),
-/// (4, 5, -25.0),
-/// (3, 4, -1.0),
-/// ]);
-///
-/// assert!(bellman_ford(&graph_with_neg_cycle, NodeIndex::new(0)).is_err());
-/// ```
-pub fn bellman_ford<G>(
- g: G,
- source: G::NodeId,
-) -> Result<Paths<G::NodeId, G::EdgeWeight>, NegativeCycleError>
-where
- G: NodeCount + IntoNodeIdentifiers + IntoEdges + NodeIndexable,
- G::EdgeWeight: FloatMeasure,
-{
- let ix = |i| g.to_index(i);
-
- // Step 1 and Step 2: initialize and relax
- let (distances, predecessors) = bellman_ford_initialize_relax(g, source);
-
- // Step 3: check for negative weight cycle
- for i in g.node_identifiers() {
- for edge in g.edges(i) {
- let j = edge.target();
- let w = *edge.weight();
- if distances[ix(i)] + w < distances[ix(j)] {
- return Err(NegativeCycleError);
- }
- }
- }
-
- Ok(Paths {
- distances,
- predecessors,
- })
-}
-
-/// \[Generic\] Find the path of a negative cycle reachable from node `source`.
-///
-/// Using the [find_negative_cycle][nc]; will search the Graph for negative cycles using
-/// [Bellman–Ford algorithm][bf]. If no negative cycle is found the function will return `None`.
-///
-/// If a negative cycle is found from source, return one vec with a path of `NodeId`s.
-///
-/// The time complexity of this algorithm should be the same as the Bellman-Ford (O(|V|·|E|)).
-///
-/// [nc]: https://blogs.asarkar.com/assets/docs/algorithms-curated/Negative-Weight%20Cycle%20Algorithms%20-%20Huang.pdf
-/// [bf]: https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
-///
-/// # Example
-/// ```rust
-/// use petgraph_algorithms::shortest_paths::find_negative_cycle;
-/// use petgraph_core::edge::Directed;
-/// use petgraph_graph::{Graph, NodeIndex};
-///
-/// let graph_with_neg_cycle = Graph::<(), f32, Directed>::from_edges(&[
-/// (0, 1, 1.),
-/// (0, 2, 1.),
-/// (0, 3, 1.),
-/// (1, 3, 1.),
-/// (2, 1, 1.),
-/// (3, 2, -3.),
-/// ]);
-///
-/// let path = find_negative_cycle(&graph_with_neg_cycle, NodeIndex::new(0));
-/// assert_eq!(
-/// path,
-/// Some([NodeIndex::new(1), NodeIndex::new(3), NodeIndex::new(2)].to_vec())
-/// );
-/// ```
-pub fn find_negative_cycle<G>(g: G, source: G::NodeId) -> Option<Vec<G::NodeId>>
-where
- G: NodeCount + IntoNodeIdentifiers + IntoEdges + NodeIndexable + Visitable,
- G::EdgeWeight: FloatMeasure,
-{
- let ix = |i| g.to_index(i);
- let mut path = Vec::<G::NodeId>::new();
-
- // Step 1: initialize and relax
- let (distance, predecessor) = bellman_ford_initialize_relax(g, source);
-
- // Step 2: Check for negative weight cycle
- 'outer: for i in g.node_identifiers() {
- for edge in g.edges(i) {
- let j = edge.target();
- let w = *edge.weight();
- if distance[ix(i)] + w < distance[ix(j)] {
- // Step 3: negative cycle found
- let start = j;
- let mut node = start;
- let mut visited = g.visit_map();
- // Go backward in the predecessor chain
- loop {
- let ancestor = match predecessor[ix(node)] {
- Some(predecessor_node) => predecessor_node,
- None => node, // no predecessor, self cycle
- };
- // We have only 2 ways to find the cycle and break the loop:
- // 1. start is reached
- if ancestor == start {
- path.push(ancestor);
- break;
- }
- // 2. some node was reached twice
- else if visited.is_visited(&ancestor) {
- // Drop any node in path that is before the first ancestor
- let pos = path
- .iter()
- .position(|&p| p == ancestor)
- .expect("we should always have a position");
- path = path[pos..path.len()].to_vec();
-
- break;
- }
-
- // None of the above, some middle path node
- path.push(ancestor);
- visited.visit(ancestor);
- node = ancestor;
- }
- // We are done here
- break 'outer;
- }
- }
- }
-
- if !path.is_empty() {
- // Users will probably need to follow the path of the negative cycle
- // so it should be in the reverse order than it was found by the algorithm.
- path.reverse();
- Some(path)
- } else {
- None
- }
-}
-
-// Perform Step 1 and Step 2 of the Bellman-Ford algorithm.
-#[inline(always)]
-fn bellman_ford_initialize_relax<G>(
- g: G,
- source: G::NodeId,
-) -> (Vec<G::EdgeWeight>, Vec<Option<G::NodeId>>)
-where
- G: NodeCount + IntoNodeIdentifiers + IntoEdges + NodeIndexable,
- G::EdgeWeight: FloatMeasure,
-{
- // Step 1: initialize graph
- let mut predecessor = vec![None; g.node_bound()];
- let mut distance = vec![G::EdgeWeight::INFINITY; g.node_bound()];
- let ix = |i| g.to_index(i);
- distance[ix(source)] = G::EdgeWeight::POS_ZERO;
-
- // Step 2: relax edges repeatedly
- for _ in 1..g.node_count() {
- let mut did_update = false;
- for i in g.node_identifiers() {
- for edge in g.edges(i) {
- let j = edge.target();
- let w = *edge.weight();
- if distance[ix(i)] + w < distance[ix(j)] {
- distance[ix(j)] = distance[ix(i)] + w;
- predecessor[ix(j)] = Some(i);
- did_update = true;
- }
- }
- }
- if !did_update {
- break;
- }
- }
- (distance, predecessor)
-}
-
-#[cfg(test)]
-mod tests {
- use alloc::format;
-
- use petgraph_core::edge::{Directed, Undirected};
- use petgraph_graph::Graph;
- use proptest::prelude::*;
-
- use crate::shortest_paths::_bellman_ford;
-
- #[cfg(not(miri))]
- proptest! {
- #[test]
- fn positive_weights_undirected_always_ok(mut graph in any::<Graph<(), f32, Undirected, u8>>()) {
- for weight in graph.edge_weights_mut() {
- *weight = weight.abs();
- }
-
- for node in graph.node_indices() {
- _bellman_ford(&graph, node).expect("should be possible");
- }
- }
-
- #[test]
- fn positive_weights_directed_always_ok(mut graph in any::<Graph<(), f32, Directed, u8>>()) {
- for weight in graph.edge_weights_mut() {
- *weight = weight.abs();
- }
-
- for node in graph.node_indices() {
- _bellman_ford(&graph, node).expect("should be possible");
- }
- }
-
- #[test]
- fn negative_path_never_empty(graph in any::<Graph<(), f32, Directed, u8>>()) {
- for node in graph.node_indices() {
- let path = _bellman_ford::find_negative_cycle(&graph, node);
-
- if let Some(path) = path {
- prop_assert!(!path.is_empty());
- }
- }
- }
- }
-}
diff --git a/crates/algorithms/src/shortest_paths/dijkstra/iter.rs b/crates/algorithms/src/shortest_paths/dijkstra/iter.rs
index 9352e95..c998f95 100644
--- a/crates/algorithms/src/shortest_paths/dijkstra/iter.rs
+++ b/crates/algorithms/src/shortest_paths/dijkstra/iter.rs
@@ -1,11 +1,11 @@
use alloc::vec::Vec;
-use core::{hash::Hash, ops::Add};
+use core::hash::Hash;
use std::mem;
use error_stack::{Report, Result};
use fxhash::FxBuildHasher;
-use hashbrown::{hash_map::Entry, HashMap};
-use num_traits::Zero;
+use hashbrown::HashMap;
+use numi::num::{identity::Zero, ops::AddRef};
use petgraph_core::{
id::{AttributeGraphId, AttributeStorage, FlaggableGraphId},
Graph, GraphStorage, Node,
@@ -20,7 +20,7 @@
route::Route,
transit::{reconstruct_path_to, PredecessorMode},
},
- dijkstra::DijkstraError,
+ dijkstra::{measure::DijkstraMeasure, DijkstraError},
};
pub(super) struct DijkstraIter<'graph: 'parent, 'parent, S, E, G>
@@ -28,7 +28,7 @@
S: GraphStorage,
S::NodeId: FlaggableGraphId<S> + AttributeGraphId<S>,
E: GraphCost<S>,
- E::Value: Ord,
+ E::Value: DijkstraMeasure,
{
graph: &'graph Graph<S>,
queue: PriorityQueue<'graph, S, E::Value>,
@@ -54,8 +54,7 @@
S: GraphStorage,
S::NodeId: FlaggableGraphId<S> + AttributeGraphId<S>,
E: GraphCost<S>,
- E::Value: PartialOrd + Ord + Zero + Clone + 'graph,
- for<'a> &'a E::Value: Add<Output = E::Value>,
+ E::Value: DijkstraMeasure,
G: Connections<'graph, S>,
{
pub(super) fn new(
@@ -103,8 +102,7 @@
S: GraphStorage,
S::NodeId: FlaggableGraphId<S> + AttributeGraphId<S>,
E: GraphCost<S>,
- E::Value: PartialOrd + Ord + Zero + Clone + 'graph,
- for<'a> &'a E::Value: Add<Output = E::Value>,
+ E::Value: DijkstraMeasure,
G: Connections<'graph, S>,
{
type Item = Route<'graph, S, E::Value>;
diff --git a/crates/algorithms/src/shortest_paths/dijkstra/measure.rs b/crates/algorithms/src/shortest_paths/dijkstra/measure.rs
new file mode 100644
index 0000000..9598b76
--- /dev/null
+++ b/crates/algorithms/src/shortest_paths/dijkstra/measure.rs
@@ -0,0 +1,82 @@
+use numi::num::{identity::Zero, ops::AddRef};
+
+/// Automatically implemented trait for types that can be used as a measure in the Dijkstra
+/// algorithm.
+///
+/// This trait is implemented for all types that implement the supertraits mentioned in the trait
+/// definition.
+/// These traits either originate from [`core`] or [`numi`].
+/// Special attention must be paid to the [`AddRef`] trait, which is a proxy trait which is
+/// implemented for types that implement: `&Self: Add<&Self, Output = Self>`.
+///
+/// # Note on floating point types
+///
+/// This trait is not implemented for both [`f32`] and [`f64`], because they do not implement
+/// [`Ord`], which is required for the binary heap used in the Dijkstra algorithm.
+/// You can instead use [`ordered_float::NotNan`], which is a wrapper type that implements [`Ord`].
+///
+/// Be aware that [`ordered_float::OrderedFloat`] does not implement [`AddRef`] and cannot be used,
+/// for a reason as to why see [this issue](https://github.com/reem/rust-ordered-float/issues/145).
+///
+/// You can read about the reason why [`f32`] and [`f64`] do not implement [`Ord`]
+/// in the Rust documentation [here](https://doc.rust-lang.org/std/primitive.f32.html).
+///
+/// # Example
+///
+/// ```rust
+/// use core::num::Wrapping;
+/// use core::num::Saturating;
+/// use ordered_float::{NotNan, OrderedFloat};
+/// use petgraph_algorithms::shortest_paths::dijkstra::DijkstraMeasure;
+/// use static_assertions::assert_impl_all;
+///
+/// // Some examples of types that implement DijkstraMeasure
+/// assert_impl_all!(u8: DijkstraMeasure);
+/// assert_impl_all!(u16: DijkstraMeasure);
+/// assert_impl_all!(u32: DijkstraMeasure);
+/// assert_impl_all!(u64: DijkstraMeasure);
+/// assert_impl_all!(u128: DijkstraMeasure);
+/// assert_impl_all!(usize: DijkstraMeasure);
+///
+/// assert_impl_all!(i8: DijkstraMeasure);
+/// assert_impl_all!(i16: DijkstraMeasure);
+/// assert_impl_all!(i32: DijkstraMeasure);
+/// assert_impl_all!(i64: DijkstraMeasure);
+/// assert_impl_all!(i128: DijkstraMeasure);
+/// assert_impl_all!(isize: DijkstraMeasure);
+///
+/// // f32 and f64 are not implemented because they are not Ord
+/// // use `ordered_float::NotNan` instead.
+/// assert_impl_all!(NotNan<f32>: DijkstraMeasure);
+/// assert_impl_all!(NotNan<f64>: DijkstraMeasure);
+///
+/// assert_impl_all!(Wrapping<u8>: DijkstraMeasure);
+/// assert_impl_all!(Wrapping<u16>: DijkstraMeasure);
+/// assert_impl_all!(Wrapping<u32>: DijkstraMeasure);
+/// assert_impl_all!(Wrapping<u64>: DijkstraMeasure);
+/// assert_impl_all!(Wrapping<u128>: DijkstraMeasure);
+/// assert_impl_all!(Wrapping<usize>: DijkstraMeasure);
+///
+/// assert_impl_all!(Wrapping<i8>: DijkstraMeasure);
+/// assert_impl_all!(Wrapping<i16>: DijkstraMeasure);
+/// assert_impl_all!(Wrapping<i32>: DijkstraMeasure);
+/// assert_impl_all!(Wrapping<i64>: DijkstraMeasure);
+/// assert_impl_all!(Wrapping<i128>: DijkstraMeasure);
+///
+/// assert_impl_all!(Saturating<u8>: DijkstraMeasure);
+/// assert_impl_all!(Saturating<u16>: DijkstraMeasure);
+/// assert_impl_all!(Saturating<u32>: DijkstraMeasure);
+/// assert_impl_all!(Saturating<u64>: DijkstraMeasure);
+/// assert_impl_all!(Saturating<u128>: DijkstraMeasure);
+/// assert_impl_all!(Saturating<usize>: DijkstraMeasure);
+///
+/// assert_impl_all!(Saturating<i8>: DijkstraMeasure);
+/// assert_impl_all!(Saturating<i16>: DijkstraMeasure);
+/// assert_impl_all!(Saturating<i32>: DijkstraMeasure);
+/// assert_impl_all!(Saturating<i64>: DijkstraMeasure);
+/// assert_impl_all!(Saturating<i128>: DijkstraMeasure);
+/// assert_impl_all!(Saturating<isize>: DijkstraMeasure);
+/// ```
+pub trait DijkstraMeasure: Clone + PartialOrd + Ord + AddRef<Self, Output = Self> + Zero {}
+
+impl<T> DijkstraMeasure for T where T: Clone + PartialOrd + Ord + AddRef<Self, Output = Self> + Zero {}
diff --git a/crates/algorithms/src/shortest_paths/dijkstra/mod.rs b/crates/algorithms/src/shortest_paths/dijkstra/mod.rs
index a785137..69732e4 100644
--- a/crates/algorithms/src/shortest_paths/dijkstra/mod.rs
+++ b/crates/algorithms/src/shortest_paths/dijkstra/mod.rs
@@ -1,13 +1,14 @@
+//! An implementation of Dijkstra's shortest path algorithm.
mod error;
mod iter;
+mod measure;
#[cfg(test)]
mod tests;
use alloc::vec::Vec;
-use core::{hash::Hash, marker::PhantomData, ops::Add};
+use core::{hash::Hash, marker::PhantomData};
use error_stack::Result;
-use num_traits::Zero;
use petgraph_core::{
edge::marker::{Directed, Undirected},
Direction,
@@ -16,20 +17,33 @@
DirectedGraphStorage, Graph, GraphDirectionality, GraphStorage, Node,
};
-pub(crate) use self::error::DijkstraError;
use self::iter::DijkstraIter;
-use super::common::{connections::outgoing_connections, transit::PredecessorMode};
-use crate::{
- polyfill::IteratorExt,
- shortest_paths::{
- common::{
- cost::{DefaultCost, GraphCost},
- route::{DirectRoute, Route},
- },
- ShortestDistance, ShortestPath,
+pub use self::{error::DijkstraError, measure::DijkstraMeasure};
+use super::{
+ common::{
+ connections::outgoing_connections,
+ cost::{DefaultCost, GraphCost},
+ route::{DirectRoute, Route},
+ transit::PredecessorMode,
},
+ ShortestDistance, ShortestPath,
};
+use crate::polyfill::IteratorExt;
+/// An implementation of Dijkstra's shortest path algorithm.
+///
+/// Dijkstra's algorithm is an algorithm for finding the shortest paths between a source node and
+/// all reachable nodes in a graph.
+/// A limitation of Dijkstra's algorithm is that it does not work for graphs with negative edge
+/// weights.
+///
+/// This implementation is generic over the directionality of the graph and the cost function.
+///
+/// Edge weights need to implement [`DijkstraMeasure`], a trait that is automatically implemented
+/// for all types that satisfy the constraints.
+///
+/// This implementation makes use of a binary heap, giving a time complexity of `O(|E| + |V| log
+/// |E|/|V| log |V|)`
pub struct Dijkstra<D, E>
where
D: GraphDirectionality,
@@ -40,6 +54,31 @@
}
impl Dijkstra<Directed, DefaultCost> {
+ /// Create a new instance of `Dijkstra` for a directed graph.
+ ///
+ /// If instantiated for a directed graph, [`Dijkstra`] will not implement [`ShortestPath`] and
+ /// [`ShortestDistance`] on undirected graphs.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use petgraph_algorithms::shortest_paths::{Dijkstra, ShortestPath};
+ /// use petgraph_dino::DiDinoGraph;
+ ///
+ /// let algorithm = Dijkstra::directed();
+ ///
+ /// let mut graph = DiDinoGraph::new();
+ /// let a = *graph.insert_node("A").id();
+ /// let b = *graph.insert_node("B").id();
+ ///
+ /// graph.insert_edge(2, &a, &b);
+ ///
+ /// let path = algorithm.path_between(&graph, &a, &b);
+ /// assert!(path.is_some());
+ ///
+ /// let path = algorithm.path_between(&graph, &b, &a);
+ /// assert!(path.is_none());
+ /// ```
#[must_use]
pub fn directed() -> Self {
Self {
@@ -50,6 +89,31 @@
}
impl Dijkstra<Undirected, DefaultCost> {
+ /// Create a new instance of `Dijkstra` for an undirected graph.
+ ///
+ /// If instantiated for an undirected graph, [`Dijkstra`] will treat a directed graph as an
+ /// undirected graph.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use petgraph_algorithms::shortest_paths::{Dijkstra, ShortestPath};
+ /// use petgraph_dino::DiDinoGraph;
+ ///
+ /// let algorithm = Dijkstra::undirected();
+ ///
+ /// let mut graph = DiDinoGraph::new();
+ /// let a = *graph.insert_node("A").id();
+ /// let b = *graph.insert_node("B").id();
+ ///
+ /// graph.insert_edge(2, &a, &b);
+ ///
+ /// let path = algorithm.path_between(&graph, &a, &b);
+ /// assert!(path.is_some());
+ ///
+ /// let path = algorithm.path_between(&graph, &b, &a);
+ /// assert!(path.is_some());
+ /// ```
#[must_use]
pub fn undirected() -> Self {
Self {
@@ -63,6 +127,41 @@
where
D: GraphDirectionality,
{
+ /// Set the cost function for the algorithm.
+ ///
+ /// By default the algorithm will use the edge weight as the cost, this function allows you to
+ /// override that behaviour,
+ /// transforming a previously unsupported graph weight into a supported one.
+ ///
+ /// For all supported functions see [`GraphCost`].
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use numi::borrow::Moo;
+ /// use petgraph_algorithms::shortest_paths::{Dijkstra, ShortestPath};
+ /// use petgraph_core::{Edge, GraphStorage};
+ /// use petgraph_dino::DiDinoGraph;
+ ///
+ /// fn edge_cost<S>(edge: Edge<S>) -> Moo<usize>
+ /// where
+ /// S: GraphStorage,
+ /// S::EdgeWeight: AsRef<str>,
+ /// {
+ /// edge.weight().as_ref().len().into()
+ /// }
+ ///
+ /// let algorithm = Dijkstra::directed().with_edge_cost(edge_cost);
+ ///
+ /// let mut graph = DiDinoGraph::new();
+ /// let a = *graph.insert_node("A").id();
+ /// let b = *graph.insert_node("B").id();
+ ///
+ /// graph.insert_edge("AB", &a, &b);
+ ///
+ /// let path = algorithm.path_between(&graph, &a, &b);
+ /// assert!(path.is_some());
+ /// ```
pub fn with_edge_cost<S, F>(self, edge_cost: F) -> Dijkstra<D, F>
where
S: GraphStorage,
@@ -80,8 +179,7 @@
S: GraphStorage,
S::NodeId: FlaggableGraphId<S> + AttributeGraphId<S>,
E: GraphCost<S>,
- for<'a> E::Value: PartialOrd + Ord + Zero + Clone + 'a,
- for<'a> &'a E::Value: Add<Output = E::Value>,
+ E::Value: DijkstraMeasure,
{
type Cost = E::Value;
type Error = DijkstraError;
@@ -123,13 +221,49 @@
}
}
+impl<S, E> ShortestPath<S> for Dijkstra<Directed, E>
+where
+ S: DirectedGraphStorage,
+ S::NodeId: Eq + Hash,
+ E: GraphCost<S>,
+ E::Value: DijkstraMeasure,
+{
+ type Cost = E::Value;
+ type Error = DijkstraError;
+
+ fn path_from<'graph: 'this, 'this>(
+ &'this self,
+ graph: &'graph Graph<S>,
+ source: &'graph S::NodeId,
+ ) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
+ DijkstraIter::new(
+ graph,
+ &self.edge_cost,
+ outgoing_connections as fn(&Node<'graph, S>) -> _,
+ source,
+ PredecessorMode::Record,
+ )
+ }
+
+ fn every_path<'graph: 'this, 'this>(
+ &'this self,
+ graph: &'graph Graph<S>,
+ ) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
+ let iter = graph
+ .nodes()
+ .map(move |node| self.path_from(graph, node.id()))
+ .collect_reports::<Vec<_>>()?;
+
+ Ok(iter.into_iter().flatten())
+ }
+}
+
impl<S, E> ShortestDistance<S> for Dijkstra<Undirected, E>
where
S: GraphStorage,
S::NodeId: FlaggableGraphId<S> + AttributeGraphId<S>,
E: GraphCost<S>,
- for<'a> E::Value: PartialOrd + Ord + Zero + Clone + 'a,
- for<'a> &'a E::Value: Add<Output = E::Value>,
+ E::Value: DijkstraMeasure,
{
type Cost = E::Value;
type Error = DijkstraError;
@@ -173,51 +307,12 @@
}
}
-impl<S, E> ShortestPath<S> for Dijkstra<Directed, E>
-where
- S: DirectedGraphStorage,
- S::NodeId: FlaggableGraphId<S> + AttributeGraphId<S>,
- E: GraphCost<S>,
- for<'a> E::Value: PartialOrd + Ord + Zero + Clone + 'a,
- for<'a> &'a E::Value: Add<Output = E::Value>,
-{
- type Cost = E::Value;
- type Error = DijkstraError;
-
- fn path_from<'graph: 'this, 'this>(
- &'this self,
- graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- ) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
- DijkstraIter::new(
- graph,
- &self.edge_cost,
- outgoing_connections as fn(&Node<'graph, S>) -> _,
- source,
- PredecessorMode::Record,
- )
- }
-
- fn every_path<'graph: 'this, 'this>(
- &'this self,
- graph: &'graph Graph<S>,
- ) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
- let iter = graph
- .nodes()
- .map(move |node| self.path_from(graph, node.id()))
- .collect_reports::<Vec<_>>()?;
-
- Ok(iter.into_iter().flatten())
- }
-}
-
impl<S, E> ShortestDistance<S> for Dijkstra<Directed, E>
where
S: DirectedGraphStorage,
S::NodeId: FlaggableGraphId<S> + AttributeGraphId<S>,
E: GraphCost<S>,
- for<'a> E::Value: PartialOrd + Ord + Zero + Clone + 'a,
- for<'a> &'a E::Value: Add<Output = E::Value>,
+ E::Value: DijkstraMeasure,
{
type Cost = E::Value;
type Error = DijkstraError;
diff --git a/crates/algorithms/src/shortest_paths/dijkstra/tests.rs b/crates/algorithms/src/shortest_paths/dijkstra/tests.rs
index cc26098..0386ab0 100644
--- a/crates/algorithms/src/shortest_paths/dijkstra/tests.rs
+++ b/crates/algorithms/src/shortest_paths/dijkstra/tests.rs
@@ -1,6 +1,7 @@
use alloc::vec::Vec;
-use petgraph_core::{base::MaybeOwned, Edge, GraphStorage};
+use numi::borrow::Moo;
+use petgraph_core::{Edge, GraphStorage};
use petgraph_dino::{DiDinoGraph, EdgeId, NodeId};
use petgraph_utils::{graph, GraphCollection};
@@ -37,7 +38,7 @@
fn networkx_directed_expect_from(
nodes: &networkx::NodeCollection<NodeId>,
-) -> Vec<Expect<networkx::Graph, i32>> {
+) -> Vec<Expect<NodeId, i32>> {
expected!(nodes; [
a -()> a: 0,
a -(c)> b: 8,
@@ -69,7 +70,6 @@
);
// TODO: multigraph
-// TODO: more test cases
#[test]
fn path_from_directed_default_edge_cost() {
@@ -93,7 +93,7 @@
fn random_directed_expect_from(
nodes: &random::NodeCollection<NodeId>,
-) -> Vec<Expect<random::Graph, usize>> {
+) -> Vec<Expect<NodeId, usize>> {
expected!(nodes; [
a -()> a: 0,
a -()> b: 5,
@@ -104,12 +104,12 @@
])
}
-fn edge_cost<S>(edge: Edge<S>) -> MaybeOwned<'_, usize>
+fn edge_cost<S>(edge: Edge<S>) -> Moo<'_, usize>
where
S: GraphStorage,
S::EdgeWeight: AsRef<[u8]>,
{
- MaybeOwned::Owned(edge.weight().as_ref().len())
+ Moo::Owned(edge.weight().as_ref().len())
}
#[test]
@@ -134,7 +134,7 @@
fn networkx_undirected_expect_from(
nodes: &networkx::NodeCollection<NodeId>,
-) -> Vec<Expect<networkx::Graph, i32>> {
+) -> Vec<Expect<NodeId, i32>> {
expected!(nodes; [
a -()> a: 0,
a -(c)> b: 7,
@@ -166,7 +166,7 @@
fn random_undirected_expect_from(
nodes: &random::NodeCollection<NodeId>,
-) -> Vec<Expect<random::Graph, usize>> {
+) -> Vec<Expect<NodeId, usize>> {
expected!(nodes; [
a -()> a: 0,
a -()> b: 5,
diff --git a/crates/algorithms/src/shortest_paths/floyd_warshall/impl.rs b/crates/algorithms/src/shortest_paths/floyd_warshall/impl.rs
index 7977f68..3deb5a9 100644
--- a/crates/algorithms/src/shortest_paths/floyd_warshall/impl.rs
+++ b/crates/algorithms/src/shortest_paths/floyd_warshall/impl.rs
@@ -1,8 +1,11 @@
use alloc::vec::Vec;
use error_stack::{Report, Result};
-use num_traits::{CheckedAdd, Zero};
-use petgraph_core::{base::MaybeOwned, id::LinearGraphId, Graph, GraphStorage, Node};
+use numi::{
+ borrow::Moo,
+ num::{checked::CheckedAdd, identity::Zero},
+};
+use petgraph_core::{id::LinearGraphId, Graph, GraphStorage, Node};
use crate::shortest_paths::{
common::{
@@ -10,15 +13,15 @@
route::Route,
transit::PredecessorMode,
},
- floyd_warshall::{error::FloydWarshallError, matrix::SlotMatrix},
+ floyd_warshall::{error::FloydWarshallError, matrix::SlotMatrix, FloydWarshallMeasure},
Path,
};
-pub(super) fn init_directed_edge_distance<'graph, S, E>(
- matrix: &mut SlotMatrix<'graph, S, MaybeOwned<'graph, E::Value>>,
+pub(super) fn init_directed_edge_distance<'graph: 'this, 'this, S, E>(
+ matrix: &mut SlotMatrix<'graph, S, Moo<'this, E::Value>>,
u: &S::NodeId,
v: &S::NodeId,
- value: Option<MaybeOwned<'graph, E::Value>>,
+ value: Option<Moo<'this, E::Value>>,
) where
S: GraphStorage,
S::NodeId: LinearGraphId<S> + Clone,
@@ -28,11 +31,11 @@
matrix.set(u, v, value);
}
-pub(super) fn init_undirected_edge_distance<'graph, S, E>(
- matrix: &mut SlotMatrix<'graph, S, MaybeOwned<'graph, E::Value>>,
+pub(super) fn init_undirected_edge_distance<'graph: 'this, 'this, S, E>(
+ matrix: &mut SlotMatrix<'graph, S, Moo<'this, E::Value>>,
u: &S::NodeId,
v: &S::NodeId,
- value: Option<MaybeOwned<'graph, E::Value>>,
+ value: Option<Moo<'this, E::Value>>,
) where
S: GraphStorage,
S::NodeId: LinearGraphId<S> + Clone,
@@ -108,12 +111,11 @@
path.reverse();
path
}
-
-type InitEdgeDistanceFn<'graph, S, E> = fn(
- &mut SlotMatrix<'graph, S, MaybeOwned<'graph, <E as GraphCost<S>>::Value>>,
+type InitEdgeDistanceFn<'graph, 'this, S, E> = fn(
+ &mut SlotMatrix<'graph, S, Moo<'this, <E as GraphCost<S>>::Value>>,
&<S as GraphStorage>::NodeId,
&<S as GraphStorage>::NodeId,
- Option<MaybeOwned<'graph, <E as GraphCost<S>>::Value>>,
+ Option<Moo<'this, <E as GraphCost<S>>::Value>>,
);
type InitEdgePredecessorFn<'graph, S> = fn(
@@ -133,19 +135,20 @@
predecessor_mode: PredecessorMode,
- init_edge_distance: InitEdgeDistanceFn<'graph, S, E>,
+ init_edge_distance: InitEdgeDistanceFn<'graph, 'parent, S, E>,
init_edge_predecessor: InitEdgePredecessorFn<'graph, S>,
- distances: SlotMatrix<'graph, S, MaybeOwned<'graph, E::Value>>,
+ distances: SlotMatrix<'graph, S, Moo<'parent, E::Value>>,
predecessors: SlotMatrix<'graph, S, &'graph S::NodeId>,
}
+// TODO: relax `NodeId` requirements or make `Send + Sync + 'static` across the board
impl<'graph: 'parent, 'parent, S, E> FloydWarshallImpl<'graph, 'parent, S, E>
where
S: GraphStorage,
S::NodeId: LinearGraphId<S> + Clone + Send + Sync + 'static,
E: GraphCost<S>,
- E::Value: PartialOrd + CheckedAdd + Zero + Clone + 'graph,
+ E::Value: FloydWarshallMeasure,
{
pub(super) fn new(
graph: &'graph Graph<S>,
@@ -154,7 +157,7 @@
predecessor_mode: PredecessorMode,
- init_edge_distance: InitEdgeDistanceFn<'graph, S, E>,
+ init_edge_distance: InitEdgeDistanceFn<'graph, 'parent, S, E>,
init_edge_predecessor: InitEdgePredecessorFn<'graph, S>,
) -> Result<Self, FloydWarshallError> {
let distances = SlotMatrix::new(graph);
@@ -199,11 +202,8 @@
}
for node in self.graph.nodes() {
- self.distances.set(
- node.id(),
- node.id(),
- Some(MaybeOwned::Owned(E::Value::zero())),
- );
+ self.distances
+ .set(node.id(), node.id(), Some(Moo::Owned(E::Value::zero())));
if self.predecessor_mode == PredecessorMode::Record {
self.predecessors.set(node.id(), node.id(), Some(node.id()));
@@ -241,8 +241,9 @@
}
}
- self.distances
- .set(i, j, Some(MaybeOwned::Owned(alternative)));
+ // TODO: check for diagonal here and apply suggestion from paper
+
+ self.distances.set(i, j, Some(Moo::Owned(alternative)));
if self.predecessor_mode == PredecessorMode::Record {
let predecessor = self.predecessors.get(k, j).copied();
@@ -263,7 +264,7 @@
let mut result: Result<(), FloydWarshallError> = Ok(());
for index in negative_cycles {
- let Some(node) = self.distances.resolve(index).map(MaybeOwned::into_owned) else {
+ let Some(node) = self.distances.resolve(index).map(Moo::into_owned) else {
continue;
};
@@ -278,7 +279,7 @@
pub(super) fn filter(
self,
- mut filter: impl FnMut(Node<S>, Node<S>) -> bool + 'parent,
+ mut filter: impl FnMut(Node<'graph, S>, Node<'graph, S>) -> bool + 'parent,
) -> impl Iterator<Item = Route<'graph, S, E::Value>> + 'parent {
let Self {
graph,
@@ -314,4 +315,37 @@
Route::new(Path::new(source, transit, target), Cost::new(cost))
})
}
+
+ pub(super) fn pick(
+ self,
+ source: &S::NodeId,
+ target: &S::NodeId,
+ ) -> Option<Route<'graph, S, E::Value>> {
+ let Self {
+ graph,
+ distances,
+ predecessors,
+ predecessor_mode,
+ ..
+ } = self;
+
+ let source_node = graph.node(source)?;
+ let target_node = graph.node(target)?;
+
+ let cost = distances.get(source, target)?;
+ let transit = match predecessor_mode {
+ PredecessorMode::Discard => Vec::new(),
+ PredecessorMode::Record => reconstruct_path(&predecessors, source, target)
+ .into_iter()
+ .filter_map(|id| graph.node(id))
+ .collect(),
+ };
+
+ let cost = Cost::new(cost.clone().into_owned());
+
+ Some(Route::new(
+ Path::new(source_node, transit, target_node),
+ cost,
+ ))
+ }
}
diff --git a/crates/algorithms/src/shortest_paths/floyd_warshall/matrix.rs b/crates/algorithms/src/shortest_paths/floyd_warshall/matrix.rs
index e814326..83e86e7 100644
--- a/crates/algorithms/src/shortest_paths/floyd_warshall/matrix.rs
+++ b/crates/algorithms/src/shortest_paths/floyd_warshall/matrix.rs
@@ -1,7 +1,7 @@
use alloc::vec::Vec;
+use numi::borrow::Moo;
use petgraph_core::{
- base::MaybeOwned,
id::{IndexMapper, LinearGraphId},
Graph, GraphStorage,
};
@@ -30,7 +30,7 @@
}
}
- fn reverse(&self, to: usize) -> Option<MaybeOwned<T>> {
+ fn reverse(&self, to: usize) -> Option<Moo<T>> {
match self {
Self::Store(mapper) => mapper.reverse(to),
Self::Discard => None,
@@ -38,22 +38,22 @@
}
}
-pub(super) struct SlotMatrix<'a, S, T>
+pub(super) struct SlotMatrix<'graph, S, T>
where
- S: GraphStorage + 'a,
+ S: GraphStorage + 'graph,
S::NodeId: LinearGraphId<S>,
{
- mapper: MatrixIndexMapper<<S::NodeId as LinearGraphId<S>>::Mapper<'a>>,
+ mapper: MatrixIndexMapper<<S::NodeId as LinearGraphId<S>>::Mapper<'graph>>,
matrix: Vec<Option<T>>,
length: usize,
}
-impl<'a, S, T> SlotMatrix<'a, S, T>
+impl<'graph, S, T> SlotMatrix<'graph, S, T>
where
S: GraphStorage,
S::NodeId: LinearGraphId<S>,
{
- pub(crate) fn new(graph: &'a Graph<S>) -> Self {
+ pub(crate) fn new(graph: &'graph Graph<S>) -> Self {
let length = graph.num_nodes();
let mapper = MatrixIndexMapper::Store(<S::NodeId as LinearGraphId<S>>::index_mapper(
graph.storage(),
@@ -113,7 +113,7 @@
self.matrix[source * self.length + target].as_ref()
}
- pub(crate) fn resolve(&self, index: usize) -> Option<MaybeOwned<S::NodeId>> {
+ pub(crate) fn resolve(&self, index: usize) -> Option<Moo<S::NodeId>> {
self.mapper.reverse(index)
}
}
diff --git a/crates/algorithms/src/shortest_paths/floyd_warshall/measure.rs b/crates/algorithms/src/shortest_paths/floyd_warshall/measure.rs
new file mode 100644
index 0000000..cfd67be
--- /dev/null
+++ b/crates/algorithms/src/shortest_paths/floyd_warshall/measure.rs
@@ -0,0 +1,54 @@
+use numi::num::{checked::CheckedAdd, identity::Zero};
+
+/// A trait for types that can be used as edge weights in the Floyd-Warshall algorithm.
+///
+/// This trait is automatically implemented for all types that implement the supertraits mentioned
+/// in the trait definition.
+///
+/// These traits either originate from [`core`] or [`numi`].
+///
+/// # Note on floating point types
+///
+/// This trait is not implemented for both [`f32`] and [`f64`], because they do not implement
+/// [`CheckedAdd`] which is required for the Floyd-Warshall algorithm.
+/// You can instead use [`ordered_float::NotNan`], which is a wrapper type that implements
+/// [`CheckedAdd`].
+///
+/// The reason that [`f32`] and [`f64`] do not implement [`CheckedAdd`] is because they do not
+/// have the concept of an overflow, which is required for [`CheckedAdd`].
+/// If a value gets to large it will instead become [`f32::INFINITY`] or [`f64::INFINITY`].
+///
+/// # Example
+///
+/// ```rust
+/// use core::num::Wrapping;
+/// use core::num::Saturating;
+/// use ordered_float::NotNan;
+/// use petgraph_algorithms::shortest_paths::floyd_warshall::FloydWarshallMeasure;
+/// use static_assertions::assert_impl_all;
+///
+/// // Some examples of types that implement DijkstraMeasure
+/// assert_impl_all!(u8: FloydWarshallMeasure);
+/// assert_impl_all!(u16: FloydWarshallMeasure);
+/// assert_impl_all!(u32: FloydWarshallMeasure);
+/// assert_impl_all!(u64: FloydWarshallMeasure);
+/// assert_impl_all!(u128: FloydWarshallMeasure);
+/// assert_impl_all!(usize: FloydWarshallMeasure);
+///
+/// assert_impl_all!(i8: FloydWarshallMeasure);
+/// assert_impl_all!(i16: FloydWarshallMeasure);
+/// assert_impl_all!(i32: FloydWarshallMeasure);
+/// assert_impl_all!(i64: FloydWarshallMeasure);
+/// assert_impl_all!(i128: FloydWarshallMeasure);
+/// assert_impl_all!(isize: FloydWarshallMeasure);
+///
+/// // f32 and f64 are not implemented because they do not implement CheckedAdd
+/// // use `ordered_float::NotNan` instead.
+/// assert_impl_all!(NotNan<f32>: FloydWarshallMeasure);
+/// assert_impl_all!(NotNan<f64>: FloydWarshallMeasure);
+///
+/// // see `CheckedAdd` why `Wrapping<T>` and `Saturating<T>` are not implemented
+/// ```
+pub trait FloydWarshallMeasure: Clone + PartialOrd + CheckedAdd + Zero {}
+
+impl<T> FloydWarshallMeasure for T where T: Clone + PartialOrd + CheckedAdd + Zero {}
diff --git a/crates/algorithms/src/shortest_paths/floyd_warshall/mod.rs b/crates/algorithms/src/shortest_paths/floyd_warshall/mod.rs
index df0d64f..36f662e 100644
--- a/crates/algorithms/src/shortest_paths/floyd_warshall/mod.rs
+++ b/crates/algorithms/src/shortest_paths/floyd_warshall/mod.rs
@@ -1,35 +1,54 @@
+//! An implementation of the Floyd-Warshall shortest path algorithm.
mod error;
mod r#impl;
mod matrix;
+mod measure;
#[cfg(test)]
mod tests;
use core::marker::PhantomData;
use error_stack::Result;
-use num_traits::{CheckedAdd, Zero};
use petgraph_core::{
edge::marker::{Directed, Undirected},
id::LinearGraphId,
Graph, GraphStorage,
};
-use crate::shortest_paths::{
+use self::r#impl::{
+ init_directed_edge_distance, init_directed_edge_predecessor, init_undirected_edge_distance,
+ init_undirected_edge_predecessor, FloydWarshallImpl,
+};
+pub use self::{error::FloydWarshallError, measure::FloydWarshallMeasure};
+use super::{
common::{
cost::{DefaultCost, GraphCost},
route::{DirectRoute, Route},
transit::PredecessorMode,
},
- floyd_warshall::{
- error::FloydWarshallError,
- r#impl::{
- init_directed_edge_distance, init_directed_edge_predecessor,
- init_undirected_edge_distance, init_undirected_edge_predecessor, FloydWarshallImpl,
- },
- },
- ShortestDistance, ShortestPath,
+ Cost, ShortestDistance, ShortestPath,
};
+/// An implementation of the Floyd-Warshall shortest path algorithm.
+///
+/// The Floyd-Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with
+/// positive or negative edge weights (but with no negative cycles).
+/// A single execution of the algorithm will find the lengths (summed weights) of the shortest paths
+/// between all pairs of vertices, though it does not return details of the paths themselves.
+///
+/// The implementation chosen overcomes this limitation by storing the predecessor of each node in
+/// an associated matrix.
+///
+/// The algorithm is implemented for both directed and undirected graphs (undirected graphs are
+/// simply treated as directed graphs with the same edge in both directions).
+///
+/// Edge weights need to implement [`FloydWarshallMeasure`], a trait that is automatically
+/// implemented for all types that satisfy the constraints. The graph id for edges need to be
+/// linear, refer to the documentation of the graph type used for further information if graph ids
+/// implement [`LinearGraphId`].
+///
+/// The time complexity of the algorithm is `O(|V|^3)`, where `|V|` is the number of nodes in the
+/// graph.
pub struct FloydWarshall<D, E> {
edge_cost: E,
@@ -37,6 +56,31 @@
}
impl FloydWarshall<Directed, DefaultCost> {
+ /// Creates a new instance of the Floyd-Warshall shortest path algorithm for directed graphs.
+ ///
+ /// If instantiated for a directed graph, the algorithm will not implement the [`ShortestPath`]
+ /// and [`ShortestDistance`] traits for undirected graphs.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use petgraph_algorithms::shortest_paths::{FloydWarshall, ShortestPath};
+ /// use petgraph_dino::DiDinoGraph;
+ ///
+ /// let algorithm = FloydWarshall::directed();
+ ///
+ /// let mut graph = DiDinoGraph::new();
+ /// let a = *graph.insert_node("A").id();
+ /// let b = *graph.insert_node("B").id();
+ ///
+ /// graph.insert_edge(7, &a, &b);
+ ///
+ /// let path = algorithm.path_between(&graph, &a, &b);
+ /// assert!(path.is_some());
+ ///
+ /// let path = algorithm.path_between(&graph, &b, &a);
+ /// assert!(path.is_none());
+ /// ```
#[must_use]
pub fn directed() -> Self {
Self {
@@ -47,6 +91,30 @@
}
impl FloydWarshall<Undirected, DefaultCost> {
+ /// Creates a new instance of the Floyd-Warshall shortest path algorithm for undirected graphs.
+ ///
+ /// If used on a directed graph, the algorithm will treat the graph as undirected.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use petgraph_algorithms::shortest_paths::{FloydWarshall, ShortestPath};
+ /// use petgraph_dino::DiDinoGraph;
+ ///
+ /// let algorithm = FloydWarshall::undirected();
+ ///
+ /// let mut graph = DiDinoGraph::new();
+ /// let a = *graph.insert_node("A").id();
+ /// let b = *graph.insert_node("B").id();
+ ///
+ /// graph.insert_edge(7, &a, &b);
+ ///
+ /// let path = algorithm.path_between(&graph, &a, &b);
+ /// assert!(path.is_some());
+ ///
+ /// let path = algorithm.path_between(&graph, &b, &a);
+ /// assert!(path.is_some());
+ /// ```
#[must_use]
pub fn undirected() -> Self {
Self {
@@ -57,6 +125,42 @@
}
impl<D, E> FloydWarshall<D, E> {
+ /// Sets the cost function to use for the algorithm.
+ ///
+ /// By default the algorithm will use the edge weight as cost, this enables the use of a custom
+ /// edge cost function, which may transform the edge weight, which is initially incompatible
+ /// with the [`FloydWarshall`] implementation into one that is.
+ ///
+ /// # Example
+ ///
+ /// ```
+ /// use numi::borrow::Moo;
+ /// use petgraph_algorithms::shortest_paths::{FloydWarshall, ShortestPath};
+ /// use petgraph_core::{Edge, GraphStorage};
+ /// use petgraph_dino::DiDinoGraph;
+ ///
+ /// fn edge_cost<S>(edge: Edge<S>) -> Moo<usize>
+ /// where
+ /// S: GraphStorage,
+ /// S::EdgeWeight: AsRef<str>,
+ /// {
+ /// edge.weight().as_ref().len().into()
+ /// }
+ ///
+ /// let algorithm = FloydWarshall::directed().with_edge_cost(edge_cost);
+ ///
+ /// let mut graph = DiDinoGraph::new();
+ /// let a = *graph.insert_node("A").id();
+ /// let b = *graph.insert_node("B").id();
+ ///
+ /// graph.insert_edge("AB", &a, &b);
+ ///
+ /// let path = algorithm.path_between(&graph, &a, &b);
+ /// assert!(path.is_some());
+ ///
+ /// let path = algorithm.path_between(&graph, &b, &a);
+ /// assert!(path.is_none());
+ /// ```
pub fn with_edge_cost<S, F>(self, edge_cost: F) -> FloydWarshall<D, F>
where
S: GraphStorage,
@@ -74,7 +178,7 @@
S: GraphStorage,
S::NodeId: LinearGraphId<S> + Clone + Send + Sync + 'static,
E: GraphCost<S>,
- for<'a> E::Value: PartialOrd + CheckedAdd + Zero + Clone + 'a,
+ E::Value: FloydWarshallMeasure,
{
type Cost = E::Value;
type Error = FloydWarshallError;
@@ -124,11 +228,7 @@
)
.ok()?;
- r#impl
- .filter(|source_node, target_node| {
- source_node.id() == source && target_node.id() == target
- })
- .next()
+ r#impl.pick(source, target)
}
fn every_path<'graph: 'this, 'this>(
@@ -142,7 +242,7 @@
init_undirected_edge_distance::<S, E>,
init_undirected_edge_predecessor::<S>,
)
- .map(|r#impl| r#impl.filter(|_, _| true))
+ .map(move |r#impl| r#impl.filter(|_, _| true))
}
}
@@ -151,11 +251,65 @@
S: GraphStorage,
S::NodeId: LinearGraphId<S> + Clone + Send + Sync + 'static,
E: GraphCost<S>,
- for<'a> E::Value: PartialOrd + CheckedAdd + Zero + Clone + 'a,
+ E::Value: FloydWarshallMeasure,
{
type Cost = E::Value;
type Error = FloydWarshallError;
+ fn distance_to<'graph: 'this, 'this>(
+ &'this self,
+ graph: &'graph Graph<S>,
+ target: &'graph S::NodeId,
+ ) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
+ let iter = FloydWarshallImpl::new(
+ graph,
+ &self.edge_cost,
+ PredecessorMode::Discard,
+ init_undirected_edge_distance::<S, E>,
+ init_undirected_edge_predecessor::<S>,
+ )?;
+
+ Ok(iter
+ .filter(move |_, target_node| target_node.id() == target)
+ .map(From::from))
+ }
+
+ fn distance_from<'graph: 'this, 'this>(
+ &'this self,
+ graph: &'graph Graph<S>,
+ source: &'graph S::NodeId,
+ ) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
+ let iter = FloydWarshallImpl::new(
+ graph,
+ &self.edge_cost,
+ PredecessorMode::Discard,
+ init_undirected_edge_distance::<S, E>,
+ init_undirected_edge_predecessor::<S>,
+ )?;
+
+ Ok(iter
+ .filter(move |source_node, _| source_node.id() == source)
+ .map(From::from))
+ }
+
+ fn distance_between<'graph>(
+ &self,
+ graph: &'graph Graph<S>,
+ source: &'graph S::NodeId,
+ target: &'graph S::NodeId,
+ ) -> Option<Cost<Self::Cost>> {
+ let iter = FloydWarshallImpl::new(
+ graph,
+ &self.edge_cost,
+ PredecessorMode::Discard,
+ init_undirected_edge_distance::<S, E>,
+ init_undirected_edge_predecessor::<S>,
+ )
+ .ok()?;
+
+ iter.pick(source, target).map(Route::into_cost)
+ }
+
fn every_distance<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
@@ -177,7 +331,7 @@
S: GraphStorage,
S::NodeId: LinearGraphId<S> + Clone + Send + Sync + 'static,
E: GraphCost<S>,
- for<'a> E::Value: PartialOrd + CheckedAdd + Zero + Clone + 'a,
+ E::Value: FloydWarshallMeasure,
{
type Cost = E::Value;
type Error = FloydWarshallError;
@@ -228,11 +382,7 @@
)
.ok()?;
- r#impl
- .filter(|source_node, target_node| {
- source_node.id() == source && target_node.id() == target
- })
- .next()
+ r#impl.pick(source, target)
}
fn every_path<'graph: 'this, 'this>(
@@ -246,7 +396,7 @@
init_directed_edge_distance::<S, E>,
init_directed_edge_predecessor::<S>,
)
- .map(|r#impl| r#impl.filter(|_, _| true))
+ .map(move |r#impl| r#impl.filter(|_, _| true))
}
}
@@ -255,11 +405,65 @@
S: GraphStorage,
S::NodeId: LinearGraphId<S> + Clone + Send + Sync + 'static,
E: GraphCost<S>,
- for<'a> E::Value: PartialOrd + CheckedAdd + Zero + Clone + 'a,
+ E::Value: FloydWarshallMeasure,
{
type Cost = E::Value;
type Error = FloydWarshallError;
+ fn distance_to<'graph: 'this, 'this>(
+ &'this self,
+ graph: &'graph Graph<S>,
+ target: &'graph S::NodeId,
+ ) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
+ let iter = FloydWarshallImpl::new(
+ graph,
+ &self.edge_cost,
+ PredecessorMode::Discard,
+ init_directed_edge_distance::<S, E>,
+ init_directed_edge_predecessor::<S>,
+ )?;
+
+ Ok(iter
+ .filter(move |_, target_node| target_node.id() == target)
+ .map(From::from))
+ }
+
+ fn distance_from<'graph: 'this, 'this>(
+ &'this self,
+ graph: &'graph Graph<S>,
+ source: &'graph S::NodeId,
+ ) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
+ let iter = FloydWarshallImpl::new(
+ graph,
+ &self.edge_cost,
+ PredecessorMode::Discard,
+ init_directed_edge_distance::<S, E>,
+ init_directed_edge_predecessor::<S>,
+ )?;
+
+ Ok(iter
+ .filter(move |source_node, _| source_node.id() == source)
+ .map(From::from))
+ }
+
+ fn distance_between<'graph>(
+ &self,
+ graph: &'graph Graph<S>,
+ source: &'graph S::NodeId,
+ target: &'graph S::NodeId,
+ ) -> Option<Cost<Self::Cost>> {
+ let iter = FloydWarshallImpl::new(
+ graph,
+ &self.edge_cost,
+ PredecessorMode::Discard,
+ init_directed_edge_distance::<S, E>,
+ init_directed_edge_predecessor::<S>,
+ )
+ .ok()?;
+
+ iter.pick(source, target).map(Route::into_cost)
+ }
+
fn every_distance<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
diff --git a/crates/algorithms/src/shortest_paths/floyd_warshall/tests.rs b/crates/algorithms/src/shortest_paths/floyd_warshall/tests.rs
index a41d3f9..c1d970b 100644
--- a/crates/algorithms/src/shortest_paths/floyd_warshall/tests.rs
+++ b/crates/algorithms/src/shortest_paths/floyd_warshall/tests.rs
@@ -1,4 +1,4 @@
-use alloc::vec::Vec;
+use alloc::{vec, vec::Vec};
use hashbrown::HashSet;
use petgraph_dino::{DiDinoGraph, EdgeId, NodeId};
@@ -42,7 +42,7 @@
] as EdgeId
);
-fn uniform_expect(nodes: &uniform::NodeCollection<NodeId>) -> Vec<Expect<uniform::Graph, usize>> {
+fn uniform_expect(nodes: &uniform::NodeCollection<NodeId>) -> Vec<Expect<NodeId, usize>> {
expected!(nodes; [
a -()> a: 0,
a -()> b: 1,
@@ -149,7 +149,7 @@
fn directed_weighted_expect(
nodes: &weighted::NodeCollection<NodeId>,
-) -> Vec<Expect<weighted::Graph, usize>> {
+) -> Vec<Expect<NodeId, usize>> {
expected!(nodes; [
a -()> a: 0,
a -()> b: 1,
@@ -244,7 +244,7 @@
fn undirected_weighted_expect(
nodes: &weighted::NodeCollection<NodeId>,
-) -> Vec<Expect<weighted::Graph, usize>> {
+) -> Vec<Expect<NodeId, usize>> {
expected!(nodes; [
a -()> a: 0,
a -()> b: 1,
diff --git a/crates/algorithms/src/shortest_paths/mod.rs b/crates/algorithms/src/shortest_paths/mod.rs
index 8652104..fb51d08 100644
--- a/crates/algorithms/src/shortest_paths/mod.rs
+++ b/crates/algorithms/src/shortest_paths/mod.rs
@@ -1,15 +1,69 @@
-// mod astar;
+//! # Shortest Path Module
+//!
+//! This module contains traits and implementations for shortest path and shortest distance
+//! algorithms.
+//! These algorithms are used to find the shortest path or distance between two nodes in a graph.
+//!
+//! ## Traits
+//!
+//! - [`ShortestPath`]: Any implementation of this trait can be used to find the shortest path,
+//! depending on algorithm some restrictions may apply.
+//! - [`ShortestDistance`]: Any implementation of this trait can be used to find the shortest
+//! distance, depending on algorithm some restrictions may apply.
+//!
+//! ## Implementations
+//!
+//! These are the algorithms implemented in `petgraph` itself, companion crates may implement other
+//! algorithms.
+//!
+//! - [`AStar`]: An implementation of the A* shortest path algorithm.
+//! - [`BellmanFord`]: An implementation of the Bellman-Ford shortest path algorithm.
+//! - [`Dijkstra`]: An implementation of the Dijkstra's shortest path algorithm.
+//! - [`FloydWarshall`]: An implementation of the Floyd-Warshall shortest path algorithm.
+//!
+//! ## Usage
+//!
+//! Each algorithm provides methods to find the shortest path or distance from a source node to a
+//! target node, from a source node to all other nodes, and between all pairs of nodes.
+//!
+//! The [`ShortestPath`] trait provides methods to find paths, while the [`ShortestDistance`] trait
+//! provides methods to find distances.
+//! The difference between a path and a distance is that a path includes the sequence of nodes and
+//! edges, while a distance is just the sum of the weights of the edges.
+//!
+//! ## Example
+//!
+//! ```rust
+//! use petgraph_algorithms::shortest_paths::{Dijkstra, ShortestPath};
+//! use petgraph_dino::DiDinoGraph;
+//!
+//! let mut graph = DiDinoGraph::new();
+//! let a = *graph.insert_node("A").id();
+//! let b = *graph.insert_node("B").id();
+//! graph.insert_edge(7, &a, &b);
+//!
+//! let dijkstra = Dijkstra::directed();
+//! let path = dijkstra.path_between(&graph, &a, &b);
+//! assert!(path.is_some());
+//!
+//! let path = dijkstra.path_between(&graph, &b, &a);
+//! assert!(path.is_none());
+//! ```
+
+pub mod astar;
+pub mod bellman_ford;
mod common;
-mod dijkstra;
-mod floyd_warshall;
+pub mod dijkstra;
+pub mod floyd_warshall;
use error_stack::{Context, Result};
use petgraph_core::{Graph, GraphStorage};
pub use self::{
// astar::AStar,
+ bellman_ford::BellmanFord,
common::{
- cost::Cost,
+ cost::{Cost, GraphCost},
path::Path,
route::{DirectRoute, Route},
},
@@ -17,13 +71,60 @@
floyd_warshall::FloydWarshall,
};
+/// # Shortest Path
+///
+/// A shortest path algorithm is an algorithm that finds a path between two nodes in a graph such
+/// that the sum of the weights of its constituent edges is minimized.
+///
+/// Different algorithms exist to solve this problem, each with its own trade-offs, refer to the
+/// different algorithms for more information.
+///
+/// ## Shortest Path vs Shortest Distance
+///
+/// The shortest path is the path between two nodes that has the lowest cost.
+/// The shortest distance is the cost of the shortest path.
+/// You should prefer shortest distance algorithms over shortest path algorithms if you are only
+/// interested in the cost of the shortest path.
+///
+/// # Example
+///
+/// ```rust
+/// use petgraph_algorithms::shortest_paths::{Dijkstra, ShortestPath};
+/// use petgraph_dino::DiDinoGraph;
+///
+/// let mut graph = DiDinoGraph::new();
+/// let a = *graph.insert_node("A").id();
+/// let b = *graph.insert_node("B").id();
+/// let c = *graph.insert_node("C").id();
+///
+/// graph.insert_edge(7, &a, &b);
+/// graph.insert_edge(5, &b, &c);
+/// graph.insert_edge(3, &a, &c);
+///
+/// let dijkstra = Dijkstra::directed();
+/// let path = dijkstra.path_between(&graph, &a, &c).expect("path exists");
+///
+/// assert_eq!(path.cost().into_value(), 3);
+///
+/// assert_eq!(path.path().source().id(), &a);
+/// assert_eq!(path.path().target().id(), &c);
+///
+/// assert!(path.path().transit().is_empty());
+/// ```
pub trait ShortestPath<S>
where
S: GraphStorage,
{
+ /// The cost of the shortest path.
type Cost;
+
+ /// The error that can occur when computing the shortest path.
type Error: Context;
+ /// Returns the shortest path from the source to the target.
+ ///
+ /// Returns an iterator over all routes in the graph that end at the given target node.
+ // TODO: example?
fn path_to<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
@@ -34,6 +135,11 @@
Ok(iter.filter(move |route| route.path().target().id() == target))
}
+ /// Returns the shortest path from the source to the target.
+ ///
+ /// This is also known as `SSSP` (Single Source Shortest Path) problem.
+ ///
+ /// Returns an iterator over all routes in the graph that start at the given source node.
fn path_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
@@ -44,6 +150,9 @@
Ok(iter.filter(move |route| route.path().source().id() == source))
}
+ /// Returns the shortest path from the source to the target.
+ ///
+ /// This will return [`None`] if no path exists between the source and the target.
fn path_between<'graph>(
&self,
graph: &'graph Graph<S>,
@@ -55,19 +164,46 @@
.find(|route| route.path().target().id() == target)
}
+ /// Returns an iterator over all shortest paths in the graph.
+ ///
+ /// This is also known as `APSP` (All Pairs Shortest Path) problem.
+ ///
+ /// Returns an iterator over all routes in the graph.
fn every_path<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error>;
}
+/// # Shortest Distance
+///
+/// A shortest distance algorithm is an algorithm that finds the distance between two nodes in a
+/// graph such that the sum of the weights of its constituent edges is minimized.
+///
+/// Different algorithms exist to solve this problem, each with its own trade-offs, refer to the
+/// different algorithms for more information.
+///
+/// ## Shortest Path vs Shortest Distance
+///
+/// The shortest path is the path between two nodes that has the lowest cost.
+/// The shortest distance is the cost of the shortest path.
+/// You should prefer shortest distance algorithms over shortest path algorithms if you are only
+/// interested in the cost of the shortest path.
+// TODO: example?
pub trait ShortestDistance<S>
where
S: GraphStorage,
{
+ /// The cost of the shortest path.
type Cost;
+
+ /// The error that can occur when computing the shortest path.
type Error: Context;
+ /// Returns the shortest distance from the source to the target.
+ ///
+ /// Returns an iterator over all direct routes in the graph that end at the given target node.
+ /// A [`DirectRoute`] does not contain the nodes traversed, only the source and target nodes.
fn distance_to<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
@@ -77,6 +213,13 @@
Ok(iter.filter(move |route| route.target().id() == target))
}
+
+ /// Returns the shortest distance from the source to the target.
+ ///
+ /// This is also known as `SSSP` (Single Source Shortest Path) problem.
+ ///
+ /// Returns an iterator over all direct routes in the graph that start at the given source node.
+ /// A [`DirectRoute`] does not contain the nodes traversed, only the source and target nodes.
fn distance_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
@@ -86,6 +229,10 @@
Ok(iter.filter(move |route| route.source().id() == source))
}
+
+ /// Returns the shortest distance from the source to the target.
+ ///
+ /// This will return [`None`] if no path exists between the source and the target.
fn distance_between<'graph>(
&self,
graph: &'graph Graph<S>,
@@ -97,6 +244,13 @@
.find(move |route| route.source().id() == source && route.target().id() == target)
.map(|route| route.into_cost())
}
+
+ /// Returns an iterator over all shortest distances in the graph.
+ ///
+ /// This is also known as `APSP` (All Pairs Shortest Path) problem.
+ ///
+ /// Returns an iterator over all direct routes in the graph.
+ /// A [`DirectRoute`] does not contain the nodes traversed, only the source and target nodes.
fn every_distance<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
diff --git a/crates/algorithms/src/shortest_paths/shortest_path_faster/error.rs b/crates/algorithms/src/shortest_paths/shortest_path_faster/error.rs
deleted file mode 100644
index b35f836..0000000
--- a/crates/algorithms/src/shortest_paths/shortest_path_faster/error.rs
+++ /dev/null
@@ -1,18 +0,0 @@
-use core::fmt::{Display, Formatter};
-
-use error_stack::Context;
-
-#[derive(Debug)]
-pub enum ShortestPathFasterError {
- NodeNotFound,
-}
-
-impl Display for ShortestPathFasterError {
- fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
- match self {
- Self::NodeNotFound => write!(f, "node not found"),
- }
- }
-}
-
-impl Context for ShortestPathFasterError {}
diff --git a/crates/algorithms/src/shortest_paths/shortest_path_faster/iter.rs b/crates/algorithms/src/shortest_paths/shortest_path_faster/iter.rs
deleted file mode 100644
index f6c8e8d..0000000
--- a/crates/algorithms/src/shortest_paths/shortest_path_faster/iter.rs
+++ /dev/null
@@ -1,212 +0,0 @@
-use core::{hash::Hash, ops::Add};
-
-use error_stack::{Report, Result};
-use fxhash::FxBuildHasher;
-use hashbrown::{HashMap, HashSet};
-use num_traits::{Bounded, Zero};
-use petgraph_core::{Graph, GraphStorage, Node};
-
-use super::error::ShortestPathFasterError;
-use crate::shortest_paths::{
- common::{
- connections::Connections, cost::GraphCost, double_ended_queue::DoubleEndedQueue,
- intermediates::reconstruct_intermediates,
- },
- Cost, Path, Route,
-};
-
-pub(super) struct ShortestPathFasterIter<'graph: 'parent, 'parent, S, E, G>
-where
- S: GraphStorage,
- E: GraphCost<S>,
- E::Value: Ord,
-{
- graph: &'graph Graph<S>,
-
- queue: DoubleEndedQueue<&'graph S::NodeId>,
-
- edge_cost: &'parent E,
- connections: G,
-
- source: Node<'graph, S>,
-
- num_nodes: usize,
-
- iteration: usize,
- next: Option<&'graph S::NodeId>,
-
- // candidate_order: SPFACandidateOrder,
- distances: HashMap<&'graph S::NodeId, E::Value, FxBuildHasher>,
- predecessors: HashMap<&'graph S::NodeId, Option<Node<'graph, S>>, FxBuildHasher>,
- in_queue: HashSet<&'graph S::NodeId, FxBuildHasher>,
-}
-
-impl<'graph: 'parent, 'parent, S, E, G> ShortestPathFasterIter<'graph, 'parent, S, E, G>
-where
- S: GraphStorage,
- S::NodeId: PartialEq + Eq + Hash,
- E: GraphCost<S>,
- E::Value: PartialOrd + Ord + Zero + Bounded + Clone + 'graph,
- for<'a> &'a E::Value: Add<Output = E::Value>,
- G: Connections<'graph, S>,
-{
- pub(super) fn new(
- graph: &'graph Graph<S>,
-
- edge_cost: &'parent E,
- connections: G,
-
- source: &'graph S::NodeId,
- // candidate_order: SPFACandidateOrder,
- ) -> Result<Self, ShortestPathFasterError> {
- let source_node = graph
- .node(source)
- .ok_or_else(|| Report::new(ShortestPathFasterError::NodeNotFound))?;
-
- let mut queue = DoubleEndedQueue::new();
- queue.push_back(source);
-
- let mut distances = HashMap::with_hasher(FxBuildHasher::default());
- distances.insert(source, E::Value::zero());
-
- let mut predecessors = HashMap::with_hasher(FxBuildHasher::default());
- predecessors.insert(source, None);
-
- let in_queue = HashSet::with_hasher(FxBuildHasher::default());
-
- Ok(Self {
- graph,
- queue,
- edge_cost,
- connections,
- source: source_node,
- num_nodes: graph.num_nodes(),
- iteration: 0,
- next: Some(source),
- // candidate_order,
- distances,
- predecessors,
- in_queue,
- })
- }
-
- fn has_cycle(&self) -> bool {
- let mut visited = HashSet::with_hasher(FxBuildHasher::default());
- let mut on_stack = HashSet::with_hasher(FxBuildHasher::default());
- let mut stack = Vec::new();
-
- for node in self.predecessors.keys() {
- if !visited.contains(*node) {
- while let Some(Some(pre)) = self.predecessors.get(*node) {
- let predecessor_id = pre.id();
- if !visited.contains(predecessor_id) {
- visited.insert(predecessor_id);
- on_stack.insert(predecessor_id);
- stack.push(predecessor_id);
- } else {
- if on_stack.contains(predecessor_id) {
- return true;
- }
- break;
- }
- }
-
- while let Some(p) = stack.pop() {
- on_stack.remove(p);
- }
- }
- }
- false
- }
-}
-
-impl<'graph: 'parent, 'parent, S, E, G> Iterator
- for ShortestPathFasterIter<'graph, 'parent, S, E, G>
-where
- S: GraphStorage,
- S::NodeId: PartialEq + Eq + Hash,
- E: GraphCost<S>,
- E::Value: PartialOrd + Ord + Zero + Bounded + Clone + 'graph,
- for<'a> &'a E::Value: Add<Output = E::Value>,
- G: Connections<'graph, S>,
-{
- type Item = Route<'graph, S, E::Value>;
-
- // The concrete implementation is the SPFA (Shortest Path Faster Algorithm) algorithm, which is
- // a variant of Bellman-Ford that uses a queue to avoid unnecessary relaxation.
- // https://en.wikipedia.org/wiki/Shortest_path_faster_algorithm
- // We've made use of optimization techniques for candidate order
- // as well as a variation to terminate on negative cycles.
- // https://konaeakira.github.io/posts/using-the-shortest-path-faster-algorithm-to-find-negative-cycles.html
- fn next(&mut self) -> Option<Self::Item> {
- let default_distance = E::Value::max_value();
-
- let node_id = self.next?;
- let node = self.graph.node(&node_id).expect("node to be present");
- let connections = self.connections.connections(&node);
-
- for edge in connections {
- let (u, v) = edge.endpoints();
- let target = if v.id() == node_id { u.id() } else { v.id() };
-
- let next_distance_cost = &self.distances[&node_id] + self.edge_cost.cost(edge).as_ref();
-
- let distance = self.distances.get(target).unwrap_or(&default_distance);
-
- if next_distance_cost >= *distance {
- continue;
- }
-
- self.distances.insert(target, next_distance_cost);
- self.predecessors.insert(
- target,
- Some(self.graph.node(node_id).expect("node to exist")),
- );
-
- self.iteration += 1;
-
- if self.iteration == self.num_nodes {
- self.iteration = 0;
- if self.has_cycle() {
- // A shortest path can at most go to n nodes, therefore we
- // terminate early if we detected a cycle at the nth iteration
- return None;
- }
- }
-
- if !self.in_queue.contains(target) {
- self.queue.push_back(target);
- self.in_queue.insert(target);
- }
- }
-
- let Some(node) = self.queue.pop_front() else {
- // No more elements in the queue, we're done.
- self.next = None;
- return None;
- };
- self.in_queue.remove(node);
-
- self.next = Some(node);
-
- // we're currently visiting the node that has the shortest distance, therefore we know
- // that the distance is the shortest possible
- let distance = self.distances[node_id].clone();
- let intermediates = reconstruct_intermediates(&self.predecessors, node);
-
- let path = Path {
- source: self.source,
- target: self.graph.node(node).expect("node to exist"),
- intermediates,
- };
-
- Some(Route {
- path,
- cost: Cost(distance),
- })
- }
-
- fn size_hint(&self) -> (usize, Option<usize>) {
- (0, Some(self.num_nodes))
- }
-}
diff --git a/crates/algorithms/src/shortest_paths/shortest_path_faster/mod.rs b/crates/algorithms/src/shortest_paths/shortest_path_faster/mod.rs
deleted file mode 100644
index af281d5..0000000
--- a/crates/algorithms/src/shortest_paths/shortest_path_faster/mod.rs
+++ /dev/null
@@ -1,276 +0,0 @@
-mod error;
-mod iter;
-#[cfg(test)]
-mod tests;
-
-use core::{hash::Hash, ops::Add};
-
-use error_stack::Result;
-use num_traits::{Bounded, Zero};
-use petgraph_core::{
- edge::marker::{Directed, Undirected},
- DirectedGraphStorage, Graph, GraphDirectionality, GraphStorage, Node,
-};
-
-use self::{error::ShortestPathFasterError, iter::ShortestPathFasterIter};
-use super::{
- common::{
- connections::outgoing_connections,
- cost::{DefaultCost, GraphCost},
- },
- DirectRoute, Route, ShortestDistance, ShortestPath,
-};
-use crate::polyfill::IteratorExt;
-
-#[derive(Default, Debug, Copy, Clone, PartialEq, Eq)]
-pub enum SPFACandidateOrder {
- #[default]
- SmallFirst,
- LargeLast,
-}
-
-pub struct ShortestPathFaster<D, E> {
- direction: D,
- edge_cost: E,
- candidate_order: SPFACandidateOrder,
-}
-
-impl ShortestPathFaster<Directed, DefaultCost> {
- pub fn directed() -> Self {
- Self {
- direction: Directed,
- edge_cost: DefaultCost,
- candidate_order: Default::default(),
- }
- }
-}
-
-impl ShortestPathFaster<Undirected, DefaultCost> {
- pub fn undirected() -> Self {
- Self {
- direction: Undirected,
- edge_cost: DefaultCost,
- candidate_order: Default::default(),
- }
- }
-}
-
-impl<D, E> ShortestPathFaster<D, E>
-where
- D: GraphDirectionality,
-{
- pub fn with_edge_cost<S, F>(self, edge_cost: F) -> ShortestPathFaster<D, F>
- where
- S: GraphStorage,
- F: GraphCost<S>,
- {
- ShortestPathFaster {
- direction: self.direction,
- edge_cost,
- candidate_order: Default::default(),
- }
- }
-
- pub fn without_edge_cost(self) -> ShortestPathFaster<D, ()> {
- ShortestPathFaster {
- direction: self.direction,
- edge_cost: (),
- candidate_order: Default::default(),
- }
- }
-
- pub fn with_candidate_order(self, candidate_order: SPFACandidateOrder) -> Self {
- Self {
- direction: self.direction,
- edge_cost: self.edge_cost,
- candidate_order,
- }
- }
-}
-
-impl<S, E> ShortestPath<S> for ShortestPathFaster<Undirected, E>
-where
- S: GraphStorage,
- S::NodeId: PartialEq + Eq + Hash,
- E: GraphCost<S>,
- for<'a> E::Value: PartialOrd + Ord + Zero + Bounded + Clone + 'a,
- for<'a> &'a E::Value: Add<Output = E::Value>,
-{
- type Cost = E::Value;
- type Error = ShortestPathFasterError;
-
- fn path_from<'graph: 'this, 'this>(
- &'this self,
- graph: &'graph petgraph_core::Graph<S>,
- source: &'graph <S as GraphStorage>::NodeId,
- ) -> Result<impl Iterator<Item = super::Route<'graph, S, Self::Cost>>, Self::Error> {
- ShortestPathFasterIter::new(
- graph,
- &self.edge_cost,
- Node::<'graph, S>::connections as fn(&Node<'graph, S>) -> _,
- source,
- // self.candidate_order,
- )
- }
-
- fn path_to<'graph: 'this, 'this>(
- &'this self,
- graph: &'graph Graph<S>,
- target: &'graph S::NodeId,
- ) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>>, Self::Error> {
- let iter = self.path_from(graph, target)?;
-
- Ok(iter.map(Route::reverse))
- }
-
- fn every_path<'graph: 'this, 'this>(
- &'this self,
- graph: &'graph petgraph_core::Graph<S>,
- ) -> Result<impl Iterator<Item = super::Route<'graph, S, Self::Cost>> + 'this, Self::Error>
- {
- let iter = graph
- .nodes()
- .map(move |node| self.path_from(graph, node.id()))
- .collect_reports::<Vec<_>>()?;
-
- Ok(iter.into_iter().flatten())
- }
-}
-
-impl<S, E> ShortestDistance<S> for ShortestPathFaster<Undirected, E>
-where
- S: GraphStorage,
- S::NodeId: Eq + Hash,
- E: GraphCost<S>,
- for<'a> E::Value: PartialOrd + Ord + Zero + Zero + Bounded + Clone + 'a,
- for<'a> &'a E::Value: Add<Output = E::Value>,
-{
- type Cost = E::Value;
- type Error = ShortestPathFasterError;
-
- fn distance_from<'graph: 'this, 'this>(
- &'this self,
- graph: &'graph petgraph_core::Graph<S>,
- source: &'graph <S as GraphStorage>::NodeId,
- ) -> Result<impl Iterator<Item = super::DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error>
- {
- let iter = ShortestPathFasterIter::new(
- graph,
- &self.edge_cost,
- Node::<'graph, S>::connections as fn(&Node<'graph, S>) -> _,
- source,
- // self.candidate_order,
- )?;
-
- Ok(iter.map(|route| DirectRoute {
- source: route.path.source,
- target: route.path.target,
- cost: route.cost,
- }))
- }
-
- fn distance_to<'graph: 'this, 'this>(
- &'this self,
- graph: &'graph Graph<S>,
- target: &'graph S::NodeId,
- ) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>>, Self::Error> {
- let iter = self.distance_from(graph, target)?;
-
- Ok(iter.map(DirectRoute::reverse))
- }
-
- fn every_distance<'graph: 'this, 'this>(
- &'this self,
- graph: &'graph petgraph_core::Graph<S>,
- ) -> Result<impl Iterator<Item = super::DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error>
- {
- let iter = graph
- .nodes()
- .map(move |node| self.distance_from(graph, node.id()))
- .collect_reports::<Vec<_>>()?;
-
- Ok(iter.into_iter().flatten())
- }
-}
-
-impl<S, E> ShortestPath<S> for ShortestPathFaster<Directed, E>
-where
- S: DirectedGraphStorage,
- S::NodeId: Eq + Hash,
- E: GraphCost<S>,
- for<'a> E::Value: PartialOrd + Ord + Zero + Zero + Bounded + Clone + 'a,
- for<'a> &'a E::Value: Add<Output = E::Value>,
-{
- type Cost = E::Value;
- type Error = ShortestPathFasterError;
-
- fn path_from<'graph: 'this, 'this>(
- &'this self,
- graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- ) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
- ShortestPathFasterIter::new(
- graph,
- &self.edge_cost,
- outgoing_connections as fn(&Node<'graph, S>) -> _,
- source,
- // self.candidate_order,
- )
- }
-
- fn every_path<'graph: 'this, 'this>(
- &'this self,
- graph: &'graph Graph<S>,
- ) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
- let iter = graph
- .nodes()
- .map(move |node| self.path_from(graph, node.id()))
- .collect_reports::<Vec<_>>()?;
-
- Ok(iter.into_iter().flatten())
- }
-}
-
-impl<S, E> ShortestDistance<S> for ShortestPathFaster<Directed, E>
-where
- S: DirectedGraphStorage,
- S::NodeId: Eq + Hash,
- E: GraphCost<S>,
- for<'a> E::Value: PartialOrd + Ord + Zero + Zero + Bounded + Clone + 'a,
- for<'a> &'a E::Value: Add<Output = E::Value>,
-{
- type Cost = E::Value;
- type Error = ShortestPathFasterError;
-
- fn distance_from<'graph: 'this, 'this>(
- &'this self,
- graph: &'graph Graph<S>,
- source: &'graph <S as GraphStorage>::NodeId,
- ) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>>, Self::Error> {
- let iter = ShortestPathFasterIter::new(
- graph,
- &self.edge_cost,
- outgoing_connections as fn(&Node<'graph, S>) -> _,
- source,
- // self.candidate_order,
- )?;
-
- Ok(iter.map(|route| DirectRoute {
- source: route.path.source,
- target: route.path.target,
- cost: route.cost,
- }))
- }
-
- fn every_distance<'graph: 'this, 'this>(
- &'this self,
- graph: &'graph Graph<S>,
- ) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
- let iter = graph
- .nodes()
- .map(move |node| self.distance_from(graph, node.id()))
- .collect_reports::<Vec<_>>()?;
-
- Ok(iter.into_iter().flatten())
- }
-}
diff --git a/crates/algorithms/src/shortest_paths/shortest_path_faster/tests.rs b/crates/algorithms/src/shortest_paths/shortest_path_faster/tests.rs
deleted file mode 100644
index 679bde9..0000000
--- a/crates/algorithms/src/shortest_paths/shortest_path_faster/tests.rs
+++ /dev/null
@@ -1,68 +0,0 @@
-use petgraph_dino::{DiDinoGraph, EdgeId, NodeId};
-use petgraph_utils::{graph, GraphCollection};
-
-use super::ShortestPathFaster;
-use crate::shortest_paths::{
- common::tests::{assert_path, path_from},
- ShortestPath,
-};
-
-graph!(
- /// Uses the graph from networkx
- ///
- /// <https://github.com/networkx/networkx/blob/main/networkx/algorithms/shortest_paths/tests/test_weighted.py>
- factory(networkx) => DiDinoGraph<&'static str, i32>;
- [
- a: "A",
- b: "B",
- c: "C",
- d: "D",
- e: "E",
- ] as NodeId, [
- ab: a -> b: 10,
- ac: a -> c: 5,
- bd: b -> d: 1,
- bc: b -> c: 2,
- de: d -> e: 1,
- cb: c -> b: 3,
- cd: c -> d: 5,
- ce: c -> e: 2,
- ea: e -> a: 7,
- ed: e -> d: 6,
- ] as EdgeId
-);
-
-#[test]
-fn path_from_directed_default_edge_cost() {
- let GraphCollection {
- graph,
- nodes,
- edges,
- } = networkx::create();
-
- let spfa = ShortestPathFaster::directed();
- // let received = path_from(&graph, &nodes.a, &spfa);
-
- let res = spfa
- .path_from(&graph, &nodes.a)
- .unwrap()
- .map(|v| {
- v.path
- .to_vec()
- .into_iter()
- .map(|q| q.weight())
- .collect::<Vec<_>>()
- })
- .collect::<Vec<_>>();
- dbg!(&res);
- let expected = [
- (nodes.a, 0, &[nodes.a, nodes.a] as &[_]),
- (nodes.b, 8, &[nodes.a, nodes.c, nodes.b]),
- (nodes.c, 5, &[nodes.a, nodes.c]),
- (nodes.d, 9, &[nodes.a, nodes.c, nodes.b, nodes.d]),
- (nodes.e, 7, &[nodes.a, nodes.c, nodes.e]),
- ];
-
- // assert_path(received, &expected);
- assert!(false)
-}
diff --git a/crates/algorithms/tests/cases/shortest_path/almost_line_00.in b/crates/algorithms/tests/cases/shortest_path/almost_line_00.in
new file mode 100644
index 0000000..0636a0b
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/almost_line_00.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:ddcc091c3d39eef908e4de002e1b498778ad8230111c524896f4b0f7c6e9230d
+size 11500830
diff --git a/crates/algorithms/tests/cases/shortest_path/almost_line_00.out b/crates/algorithms/tests/cases/shortest_path/almost_line_00.out
new file mode 100644
index 0000000..d702078
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/almost_line_00.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:46a253236925af5a56ca1af935ff2abc65b3a4dbe1495f55d5eb8287d590a584
+size 2033784
diff --git a/crates/algorithms/tests/cases/shortest_path/almost_line_01.in b/crates/algorithms/tests/cases/shortest_path/almost_line_01.in
new file mode 100644
index 0000000..c36cd94
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/almost_line_01.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:cee45e304f24a482ad1d29b36a864e862b0bdeafae5bf30b33932d5c5d13790e
+size 11499200
diff --git a/crates/algorithms/tests/cases/shortest_path/almost_line_01.out b/crates/algorithms/tests/cases/shortest_path/almost_line_01.out
new file mode 100644
index 0000000..0d61d9b
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/almost_line_01.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:1d47fc7006a6c8ce49872dc7c8a9cf762aadcf29522a50016b370b20bdff9b16
+size 2034810
diff --git a/crates/algorithms/tests/cases/shortest_path/almost_line_02.in b/crates/algorithms/tests/cases/shortest_path/almost_line_02.in
new file mode 100644
index 0000000..826762e
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/almost_line_02.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:9d5c9229f8271d289ad59f1b3177655ff3f4b498f21344c9bdc5d1bbf973a27e
+size 7555754
diff --git a/crates/algorithms/tests/cases/shortest_path/almost_line_02.out b/crates/algorithms/tests/cases/shortest_path/almost_line_02.out
new file mode 100644
index 0000000..6a0a00b
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/almost_line_02.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:7ae2e0ff962b6545b1c4056d126bdf0fcf1f8787b169aad61622c13b41099571
+size 1829364
diff --git a/crates/algorithms/tests/cases/shortest_path/example_00.in b/crates/algorithms/tests/cases/shortest_path/example_00.in
new file mode 100644
index 0000000..51e9cb8
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/example_00.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:0868d99aa063f973bc47eb5747fd8873936754f9ab8bf295eaaf930946bed156
+size 51
diff --git a/crates/algorithms/tests/cases/shortest_path/example_00.out b/crates/algorithms/tests/cases/shortest_path/example_00.out
new file mode 100644
index 0000000..4faea9b
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/example_00.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:92ef26703823a4c8b2cc311103c1d5f8e6118dd5bf83127307ce077d9f4b65f8
+size 17
diff --git a/crates/algorithms/tests/cases/shortest_path/example_01.in b/crates/algorithms/tests/cases/shortest_path/example_01.in
new file mode 100644
index 0000000..613de1c
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/example_01.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:b1576608937a0946ebbb394d511c701d7c01d8a094e5f6e02eb80ecf5d0283d9
+size 15
diff --git a/crates/algorithms/tests/cases/shortest_path/example_01.out b/crates/algorithms/tests/cases/shortest_path/example_01.out
new file mode 100644
index 0000000..311c450
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/example_01.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:ee3aa64bb94a50845d5024cd4bd20202a4567aed5cd5328c0d97e9920775fc28
+size 3
diff --git a/crates/algorithms/tests/cases/shortest_path/grid_random_00.in b/crates/algorithms/tests/cases/shortest_path/grid_random_00.in
new file mode 100644
index 0000000..9d88f14
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/grid_random_00.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:ce2978c41a2adcfc884152fc3612e9c498fab217c5b5a918917d0e83c54beca1
+size 10921348
diff --git a/crates/algorithms/tests/cases/shortest_path/grid_random_00.out b/crates/algorithms/tests/cases/shortest_path/grid_random_00.out
new file mode 100644
index 0000000..f4df973
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/grid_random_00.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:f34e8e95d3536526bc166b5adc11b463c390163c1796f299308a47f8b4f89e72
+size 1252
diff --git a/crates/algorithms/tests/cases/shortest_path/grid_swirl_00.in b/crates/algorithms/tests/cases/shortest_path/grid_swirl_00.in
new file mode 100644
index 0000000..2a5099d
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/grid_swirl_00.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:18eb066b7261108b833de2331760ac0b5acaf6e92fa5648d9d5da6425d4f3ad5
+size 9954866
diff --git a/crates/algorithms/tests/cases/shortest_path/grid_swirl_00.out b/crates/algorithms/tests/cases/shortest_path/grid_swirl_00.out
new file mode 100644
index 0000000..36f28d8
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/grid_swirl_00.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:45ca68142b57bfee7f002364555d7bf02dcbd25e462815db2d45c823e61cf584
+size 1512442
diff --git a/crates/algorithms/tests/cases/shortest_path/line_00.in b/crates/algorithms/tests/cases/shortest_path/line_00.in
new file mode 100644
index 0000000..e04bfe3
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/line_00.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:1c34397c506a4d93e1eff89b396d697f28839453a3902e4d881ffc223766b7d9
+size 12277783
diff --git a/crates/algorithms/tests/cases/shortest_path/line_00.out b/crates/algorithms/tests/cases/shortest_path/line_00.out
new file mode 100644
index 0000000..903e1f7
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/line_00.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:7c6e51b3ce0757fe443c631b3cdfeac2216cea30b79661aa904f8187b631d41e
+size 6777789
diff --git a/crates/algorithms/tests/cases/shortest_path/max_dense_long_00.in b/crates/algorithms/tests/cases/shortest_path/max_dense_long_00.in
new file mode 100644
index 0000000..7defbbd
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_dense_long_00.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:2892ece395211550e57aefc31f1417ca7c691d6c9b27eaf4ebab006b42fd6b4e
+size 8768774
diff --git a/crates/algorithms/tests/cases/shortest_path/max_dense_long_00.out b/crates/algorithms/tests/cases/shortest_path/max_dense_long_00.out
new file mode 100644
index 0000000..85ff094
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_dense_long_00.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:6dcc5b976e90a465e0b1d7fe3cf65b4bceb29f56f6d58a6927bdf05668fe7d03
+size 5437
diff --git a/crates/algorithms/tests/cases/shortest_path/max_dense_random_00.in b/crates/algorithms/tests/cases/shortest_path/max_dense_random_00.in
new file mode 100644
index 0000000..c8851d0
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_dense_random_00.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:64c301019647dc4349a22d4e6434e5feebdb83277eefd42180c62caa66bfc5f0
+size 8774280
diff --git a/crates/algorithms/tests/cases/shortest_path/max_dense_random_00.out b/crates/algorithms/tests/cases/shortest_path/max_dense_random_00.out
new file mode 100644
index 0000000..2d8ba92
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_dense_random_00.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:93f9b983001b1ad49b6c8fd8c2e27ba98f2233975594853b580b18b34bfa162d
+size 89
diff --git a/crates/algorithms/tests/cases/shortest_path/max_dense_random_01.in b/crates/algorithms/tests/cases/shortest_path/max_dense_random_01.in
new file mode 100644
index 0000000..04e2ba9
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_dense_random_01.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:b9acf2b13b48cc4095574365880eb87a2042a83a2b7a8150037a321746d32f53
+size 8774117
diff --git a/crates/algorithms/tests/cases/shortest_path/max_dense_random_01.out b/crates/algorithms/tests/cases/shortest_path/max_dense_random_01.out
new file mode 100644
index 0000000..fb4730b
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_dense_random_01.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:3de1bcfa0bfcc3ee770ed37b5589540f86a32185342b2d798c2664c7a3d6d518
+size 72
diff --git a/crates/algorithms/tests/cases/shortest_path/max_dense_zero_00.in b/crates/algorithms/tests/cases/shortest_path/max_dense_zero_00.in
new file mode 100644
index 0000000..c776df0
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_dense_zero_00.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:2f8ea9e13435f6306e8fb27959ceef9895f0d5ddf7faf977b684d24fefcaf2e1
+size 4836119
diff --git a/crates/algorithms/tests/cases/shortest_path/max_dense_zero_00.out b/crates/algorithms/tests/cases/shortest_path/max_dense_zero_00.out
new file mode 100644
index 0000000..04a3318
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_dense_zero_00.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:4303004b151251b7956ab2483e28bae4c0e36bbd69cca31d7c60fb0ad2c0a66d
+size 12
diff --git a/crates/algorithms/tests/cases/shortest_path/max_sparse_random_00.in b/crates/algorithms/tests/cases/shortest_path/max_sparse_random_00.in
new file mode 100644
index 0000000..e95d563
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_sparse_random_00.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:e34c7ed7c0d4b4835ab4fd659585a77cdcb4dc1563c92179e24aa652eb0dd476
+size 11500586
diff --git a/crates/algorithms/tests/cases/shortest_path/max_sparse_random_00.out b/crates/algorithms/tests/cases/shortest_path/max_sparse_random_00.out
new file mode 100644
index 0000000..311c450
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_sparse_random_00.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:ee3aa64bb94a50845d5024cd4bd20202a4567aed5cd5328c0d97e9920775fc28
+size 3
diff --git a/crates/algorithms/tests/cases/shortest_path/max_sparse_random_01.in b/crates/algorithms/tests/cases/shortest_path/max_sparse_random_01.in
new file mode 100644
index 0000000..246e695
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_sparse_random_01.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:8aafa7cb1de15c876c7445d55ee9ac3c0c535eb57382dafdb9e1845fad444d97
+size 11500446
diff --git a/crates/algorithms/tests/cases/shortest_path/max_sparse_random_01.out b/crates/algorithms/tests/cases/shortest_path/max_sparse_random_01.out
new file mode 100644
index 0000000..8b36e1b
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_sparse_random_01.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:901fcb995b5ade65c8e159881c9c575ff3b9af1b25738120f06ae8cf6981acae
+size 198
diff --git a/crates/algorithms/tests/cases/shortest_path/max_sparse_random_02.in b/crates/algorithms/tests/cases/shortest_path/max_sparse_random_02.in
new file mode 100644
index 0000000..f715e71
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_sparse_random_02.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:6994f28e61bcad12d5a0d6feaa10df94f36c1eb88c32ac844ce18319c132a4cd
+size 11500081
diff --git a/crates/algorithms/tests/cases/shortest_path/max_sparse_random_02.out b/crates/algorithms/tests/cases/shortest_path/max_sparse_random_02.out
new file mode 100644
index 0000000..b3d03f8
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_sparse_random_02.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:6c98e7fec768b9fe59965f3b9b5181ae7c35e35ee57edac49c189c578a61ba0d
+size 267
diff --git a/crates/algorithms/tests/cases/shortest_path/max_star_00.in b/crates/algorithms/tests/cases/shortest_path/max_star_00.in
new file mode 100644
index 0000000..77580fa
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_star_00.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:095e698480f5ca855e715fea307baa6a6414d384b517cd194dc77fda396ecdff
+size 10833928
diff --git a/crates/algorithms/tests/cases/shortest_path/max_star_00.out b/crates/algorithms/tests/cases/shortest_path/max_star_00.out
new file mode 100644
index 0000000..66aaaab
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_star_00.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:8e36190f48f36e4fb918417f71f25170b6c87c8177b90198d26252e00079c18e
+size 81
diff --git a/crates/algorithms/tests/cases/shortest_path/max_star_01.in b/crates/algorithms/tests/cases/shortest_path/max_star_01.in
new file mode 100644
index 0000000..e41e300
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_star_01.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:36bdce1c462760d4c4f5c5e76c42bf06d6f134b71bf34eb39c7b994596ce55bc
+size 11777953
diff --git a/crates/algorithms/tests/cases/shortest_path/max_star_01.out b/crates/algorithms/tests/cases/shortest_path/max_star_01.out
new file mode 100644
index 0000000..0d41a21
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/max_star_01.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:9a7b41bbf2d24cd5ce10a32a675acf937cf3df56776d13dd075fc3df252024ae
+size 40
diff --git a/crates/algorithms/tests/cases/shortest_path/small_00.in b/crates/algorithms/tests/cases/shortest_path/small_00.in
new file mode 100644
index 0000000..3ebba19
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/small_00.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:57bcca3d9e99a79b2a3e2c560a944dac6f0647461ab51384b2e853179128396d
+size 877
diff --git a/crates/algorithms/tests/cases/shortest_path/small_00.out b/crates/algorithms/tests/cases/shortest_path/small_00.out
new file mode 100644
index 0000000..c4aeb7d
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/small_00.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:1cda3f5e6b776c0087aec2c2482c35162a0d34ee43b5601d192d8c1710d874da
+size 35
diff --git a/crates/algorithms/tests/cases/shortest_path/small_01.in b/crates/algorithms/tests/cases/shortest_path/small_01.in
new file mode 100644
index 0000000..882d182
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/small_01.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:a4f286748128eddb8f61856d21a22d75c1e3f23bd24120e064df4a98493d4917
+size 863
diff --git a/crates/algorithms/tests/cases/shortest_path/small_01.out b/crates/algorithms/tests/cases/shortest_path/small_01.out
new file mode 100644
index 0000000..b331389
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/small_01.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:17c0c7e5885e153991b09bb5736b0b5a277838c7dfb2c3f5a0ad646c4838f6ef
+size 45
diff --git a/crates/algorithms/tests/cases/shortest_path/small_02.in b/crates/algorithms/tests/cases/shortest_path/small_02.in
new file mode 100644
index 0000000..3a986f0
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/small_02.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:27c35f6fcc19c459e0efd8c3b22b69e598bba4ea14eac9e72682b06a1d2c6e8a
+size 855
diff --git a/crates/algorithms/tests/cases/shortest_path/small_02.out b/crates/algorithms/tests/cases/shortest_path/small_02.out
new file mode 100644
index 0000000..d3b6cea
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/small_02.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:ad694a5746d6f0073c119b361ec87b4a790ac8fa48f37404b4ad81f71ee6f609
+size 18
diff --git a/crates/algorithms/tests/cases/shortest_path/small_03.in b/crates/algorithms/tests/cases/shortest_path/small_03.in
new file mode 100644
index 0000000..86920fb
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/small_03.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:ebbd224df70dc5a1ad97601b5c0da26455f90e42b8ea037adca37e4991098228
+size 862
diff --git a/crates/algorithms/tests/cases/shortest_path/small_03.out b/crates/algorithms/tests/cases/shortest_path/small_03.out
new file mode 100644
index 0000000..b6622ad
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/small_03.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:a64711f7c61aae4f6e601ee09ca8e1e5533da592d87118898ff6cd66d1442594
+size 31
diff --git a/crates/algorithms/tests/cases/shortest_path/small_04.in b/crates/algorithms/tests/cases/shortest_path/small_04.in
new file mode 100644
index 0000000..21fb36f
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/small_04.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:850e20f1b0980ca4e7041b8c8c3d14d822c09d5af9f268530c99e7758f5e2576
+size 868
diff --git a/crates/algorithms/tests/cases/shortest_path/small_04.out b/crates/algorithms/tests/cases/shortest_path/small_04.out
new file mode 100644
index 0000000..dd9bd37
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/small_04.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:1a14dbe2303ef65ec8df9e16d0a48d47fac2ed2828936af9c356e61f3e1fe8c2
+size 40
diff --git a/crates/algorithms/tests/cases/shortest_path/sparse_random_00.in b/crates/algorithms/tests/cases/shortest_path/sparse_random_00.in
new file mode 100644
index 0000000..851d73d
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/sparse_random_00.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:46f93d9708bfac3ce5242665581947369001ec916210a1e7650e23ec0c42bf61
+size 9582610
diff --git a/crates/algorithms/tests/cases/shortest_path/sparse_random_00.out b/crates/algorithms/tests/cases/shortest_path/sparse_random_00.out
new file mode 100644
index 0000000..311c450
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/sparse_random_00.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:ee3aa64bb94a50845d5024cd4bd20202a4567aed5cd5328c0d97e9920775fc28
+size 3
diff --git a/crates/algorithms/tests/cases/shortest_path/sparse_random_01.in b/crates/algorithms/tests/cases/shortest_path/sparse_random_01.in
new file mode 100644
index 0000000..0d1ff35
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/sparse_random_01.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:ce729353f2b0487710ce2e2518efddfee782390e6a508912f940da8e8ff933a2
+size 9665753
diff --git a/crates/algorithms/tests/cases/shortest_path/sparse_random_01.out b/crates/algorithms/tests/cases/shortest_path/sparse_random_01.out
new file mode 100644
index 0000000..311c450
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/sparse_random_01.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:ee3aa64bb94a50845d5024cd4bd20202a4567aed5cd5328c0d97e9920775fc28
+size 3
diff --git a/crates/algorithms/tests/cases/shortest_path/sparse_random_02.in b/crates/algorithms/tests/cases/shortest_path/sparse_random_02.in
new file mode 100644
index 0000000..b4f202a
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/sparse_random_02.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:e175334fe70c3dd3a31e4e34388afa996d7bb7051239dc56af87f03caf758255
+size 8210248
diff --git a/crates/algorithms/tests/cases/shortest_path/sparse_random_02.out b/crates/algorithms/tests/cases/shortest_path/sparse_random_02.out
new file mode 100644
index 0000000..38d9620
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/sparse_random_02.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:e6e03e75ae2d0aa8da3e1bca2f62bca8c5637a4993fb28f1ffb3b4a4af88ec93
+size 131
diff --git a/crates/algorithms/tests/cases/shortest_path/spfa_killer_00.in b/crates/algorithms/tests/cases/shortest_path/spfa_killer_00.in
new file mode 100644
index 0000000..98078d1
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/spfa_killer_00.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:8da03b49ee73a638e6d3cc4217c0bf644b92cda197e20f60cdf9093d7aeb85e5
+size 7731684
diff --git a/crates/algorithms/tests/cases/shortest_path/spfa_killer_00.out b/crates/algorithms/tests/cases/shortest_path/spfa_killer_00.out
new file mode 100644
index 0000000..6cf110e
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/spfa_killer_00.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:761c118bcfb6e73ebc10b0b2c2be83eae8023889465e3b06986b6e8267e635c5
+size 1748673
diff --git a/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_handmade_00.in b/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_handmade_00.in
new file mode 100644
index 0000000..43523fc
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_handmade_00.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:c4b803ff9113fa1308dca99ac0c8bd494faa8d3fa3256f24c9b09f2c97d371d2
+size 26
diff --git a/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_handmade_00.out b/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_handmade_00.out
new file mode 100644
index 0000000..315fba6
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_handmade_00.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:46066aede3e055309cafe3371ccafcfeb8188c598cb5f7c4171d0fd0a3f846aa
+size 12
diff --git a/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_00.in b/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_00.in
new file mode 100644
index 0000000..a6d56dc
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_00.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:e9b1bbcbe57f62b7b9b96ecbd7064c80587a44f476971bd6a5109c0bc87253ad
+size 9319483
diff --git a/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_00.out b/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_00.out
new file mode 100644
index 0000000..5373aff
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_00.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:72cddb1daaa2122527535c381e5c659de149d61fad545e80ef048810a105aa0c
+size 60
diff --git a/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_01.in b/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_01.in
new file mode 100644
index 0000000..3529ccf
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_01.in
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:54ec025cf331683d9c5b72fcec87536564a5303361dfd2013eefddf801ee646e
+size 8355202
diff --git a/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_01.out b/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_01.out
new file mode 100644
index 0000000..9f9c781
--- /dev/null
+++ b/crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_01.out
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:2564cd63ffd8c46e7b44b5515c5eded6feecbb5f04dd3cb3bd6bc67da6b4c537
+size 3184996
diff --git a/crates/algorithms/tests/shortest_paths/harness.rs b/crates/algorithms/tests/shortest_paths/harness.rs
new file mode 100644
index 0000000..0930eb2
--- /dev/null
+++ b/crates/algorithms/tests/shortest_paths/harness.rs
@@ -0,0 +1,371 @@
+//! [`Harness`] for discovering test inputs and asserting against snapshot files
+//!
+//! Taken from [snapbox](https://docs.rs/snapshot) and adapted to make matrix tests possible.
+
+use std::path::Path;
+
+use hashbrown::{HashMap, HashSet};
+use ignore::{
+ overrides::{Override, OverrideBuilder},
+ WalkBuilder,
+};
+use libtest_mimic::Trial;
+use snapbox::{
+ report::{write_diff, Palette},
+ Action, Assert, Data, DataFormat, NormalizeNewlines,
+};
+
+pub struct Harness<S, T> {
+ root: std::path::PathBuf,
+ overrides: Option<Override>,
+ each: Option<&'static [&'static str]>,
+ setup: S,
+ test: T,
+ action: Action,
+}
+
+impl<S, T, I, E> Harness<S, T>
+where
+ I: std::fmt::Display,
+ E: std::fmt::Display,
+ S: Fn(std::path::PathBuf) -> Case + Send + Sync + 'static,
+ T: Fn(&Path, &'static str) -> Result<I, E> + Send + Sync + 'static + Clone,
+{
+ pub fn new(root: impl Into<std::path::PathBuf>, setup: S, test: T) -> Self {
+ Self {
+ root: root.into(),
+ overrides: None,
+ setup,
+ // in theory we would want to do this via a type-state instead,
+ // but I can't be bothered to put in the extra effort, unless we upstream this.
+ each: None,
+ test,
+ action: Action::Verify,
+ }
+ }
+
+ /// Path patterns for selecting input files
+ ///
+ /// This used gitignore syntax
+ pub fn select<'p>(mut self, patterns: impl IntoIterator<Item = &'p str>) -> Self {
+ let mut overrides = OverrideBuilder::new(&self.root);
+ for line in patterns {
+ overrides.add(line).unwrap();
+ }
+ self.overrides = Some(overrides.build().unwrap());
+ self
+ }
+
+ pub fn each(mut self, names: &'static [&'static str]) -> Self {
+ self.each = Some(names);
+ self
+ }
+
+ /// Read the failure action from an environment variable
+ pub fn action_env(mut self, var_name: &str) -> Self {
+ let action = Action::with_env_var(var_name);
+ self.action = action.unwrap_or(self.action);
+ self
+ }
+
+ /// Override the failure action
+ pub fn action(mut self, action: Action) -> Self {
+ self.action = action;
+ self
+ }
+
+ fn trials(&self, name: &'static str) -> impl IntoIterator<Item = Trial> + '_ {
+ let mut walk = WalkBuilder::new(&self.root);
+ walk.standard_filters(false);
+ let tests = walk.build().filter_map(|entry| {
+ let entry = entry.unwrap();
+ let is_dir = entry.file_type().map(|f| f.is_dir()).unwrap_or(false);
+ let path = entry.into_path();
+ if let Some(overrides) = &self.overrides {
+ overrides
+ .matched(&path, is_dir)
+ .is_whitelist()
+ .then_some(path)
+ } else {
+ Some(path)
+ }
+ });
+
+ tests.into_iter().map(move |path| {
+ let case = (self.setup)(path);
+
+ let test = self.test.clone();
+ let trial_name = if name.is_empty() {
+ case.name.clone()
+ } else {
+ format!("{name}::{}", case.name)
+ };
+ let action = self.action;
+
+ Trial::test(trial_name, move || {
+ let actual = test(&case.fixture, name)?;
+ let actual = actual.to_string();
+
+ let verify = Verifier::new();
+ verify.assert(&case.fixture, &case.expected, actual)?;
+ Ok(())
+ })
+ .with_ignored_flag(action == Action::Ignore)
+ })
+ }
+
+ /// Run tests
+ pub fn test(self) -> ! {
+ let each = self.each.unwrap_or(&[""]);
+
+ let tests = each.iter().flat_map(|name| self.trials(name)).collect();
+
+ let args = libtest_mimic::Arguments::from_args();
+ libtest_mimic::run(&args, tests).exit()
+ }
+}
+
+struct Solution {
+ cost: u64,
+ edges: usize,
+
+ path: Vec<Connection>,
+}
+
+#[derive(Debug, Copy, Clone)]
+struct Connection {
+ source: usize,
+ target: usize,
+}
+
+struct Graph {
+ nodes: usize,
+ edges_len: usize,
+
+ source: usize,
+ target: usize,
+
+ edges: HashMap<(usize, usize), u64>,
+}
+
+macro_rules! next {
+ ($iter:ident as $ty:ty) => {
+ $iter
+ .next()
+ .expect("expected token")
+ .parse::<$ty>()
+ .expect(concat!("is ", stringify!($ty)))
+ };
+}
+
+struct Verifier {
+ palette: Palette,
+}
+
+impl Verifier {
+ fn new() -> Self {
+ Self {
+ palette: Palette::color(),
+ }
+ }
+
+ fn parse_out(value: String) -> Option<Solution> {
+ let mut lines = value.lines();
+
+ let (cost, edges) = {
+ let line = lines.next().expect("at least one line");
+ let mut iter = line.split_whitespace();
+
+ let cost = next!(iter as i128);
+ if cost < 0 {
+ return None;
+ }
+ let cost = cost as u64;
+
+ let edges = next!(iter as usize);
+
+ (cost, edges)
+ };
+
+ let mut path = Vec::with_capacity(edges);
+
+ for _ in 0..edges {
+ let line = lines.next().expect("expected line");
+ let mut iter = line.split_whitespace();
+
+ let source = next!(iter as usize);
+ let target = next!(iter as usize);
+
+ path.push(Connection { source, target });
+ }
+
+ Some(Solution { cost, edges, path })
+ }
+
+ fn parse_in(value: String) -> Graph {
+ let mut lines = value.lines();
+
+ let (nodes, edges_len, source, target) = {
+ let line = lines.next().expect("at least one line");
+ let mut iter = line.split_whitespace();
+ let nodes = next!(iter as usize);
+ let edges_len = next!(iter as usize);
+ let source = next!(iter as usize);
+ let target = next!(iter as usize);
+
+ (nodes, edges_len, source, target)
+ };
+
+ let mut edges = HashMap::with_capacity(edges_len);
+
+ for _ in 0..edges_len {
+ let line = lines.next().expect("expected line");
+ let mut iter = line.split_whitespace();
+ let source = next!(iter as usize);
+ let target = next!(iter as usize);
+ let weight = next!(iter as u64);
+
+ edges.insert((source, target), weight);
+ }
+
+ Graph {
+ nodes,
+ edges_len,
+ source,
+ target,
+ edges,
+ }
+ }
+
+ fn assert(&self, graph: &Path, expected: &Path, received: String) -> snapbox::Result<()> {
+ let graph = std::fs::read_to_string(graph).map_err(snapbox::Error::new)?;
+ let graph = Self::parse_in(graph);
+
+ let expected = std::fs::read_to_string(expected).map_err(snapbox::Error::new)?;
+ let expected = Self::parse_out(expected);
+
+ let received = Self::parse_out(received);
+
+ self.verify(graph, expected, received)
+ }
+
+ /// Implementation of the algorithm used in `library-checker-problems`
+ ///
+ /// see:
+ /// <https://github.com/yosupo06/library-checker-problems/blob/1115a1bf77a8f3d66ab95e46a693a841cd4a7098/graph/shortest_path/checker.cpp>
+ fn verify(
+ &self,
+ graph: Graph,
+ expected: Option<Solution>,
+ received: Option<Solution>,
+ ) -> snapbox::Result<()> {
+ let (expected, received) = match (expected, received) {
+ (Some(expected), Some(received)) => (expected, received),
+ (None, None) => return Ok(()),
+ (Some(_), None) => panic!(
+ "{}: expected path, but didn't receive one",
+ self.palette.error("path existence differs")
+ ),
+ (None, Some(_)) => panic!(
+ "{}: received path, but didn't expect one",
+ self.palette.error("path existence differs")
+ ),
+ };
+
+ let first = expected.path.first().expect("at least one edge");
+ let last = expected.path.last().expect("at least one edge");
+
+ if first.source != graph.source {
+ panic!(
+ "{}: path starts at wrong node",
+ self.palette.error("path differs")
+ );
+ }
+
+ if last.target != graph.target {
+ panic!(
+ "{}: path ends at wrong node",
+ self.palette.error("path differs")
+ );
+ }
+
+ let mut used = HashSet::new();
+ used.insert(graph.source);
+
+ let mut total = 0;
+
+ for index in 0..expected.edges {
+ let current = expected.path[index];
+
+ if index + 1 < expected.edges {
+ let next = expected.path[index + 1];
+
+ if current.target != next.source {
+ panic!(
+ "{}: teleporting between {}th edge and {}th edge from vertex {} to {}",
+ self.palette.error("teleportation"),
+ index,
+ index + 1,
+ current.target,
+ next.source
+ );
+ }
+ }
+
+ let Some(&cost) = graph.edges.get(&(current.source, current.target)) else {
+ panic!(
+ "{}: edge from {} to {} doesn't exist",
+ self.palette.error("edge existence"),
+ current.source,
+ current.target
+ );
+ };
+
+ if used.contains(¤t.target) {
+ panic!(
+ "{}: vertex {} is used twice",
+ self.palette.error("vertex usage"),
+ current.target
+ );
+ }
+
+ used.insert(current.target);
+ total += cost;
+ }
+
+ if total != received.cost {
+ panic!(
+ "{}: total weights differ between calculated ({}) and received path ({})",
+ self.palette.error("total weight differs"),
+ total,
+ received.cost
+ )
+ }
+
+ if total > expected.cost {
+ panic!(
+ "{}: not the shortest path, shortest {}, submitted {}",
+ self.palette.error("not shortest"),
+ expected.cost,
+ total
+ )
+ }
+
+ if total < expected.cost {
+ panic!(
+ "{}: submitted solution shorter than judge's solution, submitted {}, judge {}",
+ self.palette.error("shorter"),
+ total,
+ expected.cost
+ )
+ }
+
+ Ok(())
+ }
+}
+
+pub struct Case {
+ pub name: String,
+ pub fixture: std::path::PathBuf,
+ pub expected: std::path::PathBuf,
+}
diff --git a/crates/algorithms/tests/shortest_paths/main.rs b/crates/algorithms/tests/shortest_paths/main.rs
new file mode 100644
index 0000000..5ce7a3d
--- /dev/null
+++ b/crates/algorithms/tests/shortest_paths/main.rs
@@ -0,0 +1,149 @@
+mod harness;
+
+use std::{
+ error::Error,
+ fs::File,
+ io::{BufRead, BufReader, Lines},
+ path::{Path, PathBuf},
+};
+
+use petgraph_algorithms::shortest_paths::{
+ bellman_ford::CandidateOrder, BellmanFord, Dijkstra, FloydWarshall, Route, ShortestPath,
+};
+use petgraph_dino::{DiDinoGraph, DinoStorage, EdgeId, NodeId};
+use snapbox::{utils::normalize_lines, Action};
+
+use crate::harness::{Case, Harness};
+
+fn setup(input_path: PathBuf) -> Case {
+ let name = input_path
+ .file_stem()
+ .unwrap()
+ .to_str()
+ .unwrap()
+ .to_string();
+
+ let expected = input_path.with_extension("out");
+
+ Case {
+ name,
+ fixture: input_path,
+ expected,
+ }
+}
+
+struct Parse {
+ graph: DiDinoGraph<usize, u64>,
+ source: NodeId,
+ target: NodeId,
+ nodes: Vec<NodeId>,
+ edges: Vec<EdgeId>,
+}
+
+fn read(input_path: &Path) -> Result<Parse, Box<dyn Error>> {
+ let file = File::open(input_path)?;
+ let reader = BufReader::new(file);
+
+ let input = reader.lines();
+ parse(input)
+}
+
+fn parse(mut input: Lines<impl BufRead>) -> Result<Parse, Box<dyn Error>> {
+ let meta = input.next().unwrap()?;
+ let meta = meta
+ .split_whitespace()
+ .map(|x| x.parse::<usize>())
+ .collect::<Result<Vec<_>, _>>()?;
+
+ let n = meta[0];
+ let m = meta[1];
+ let s = meta[2];
+ let t = meta[3];
+
+ let mut graph = DiDinoGraph::new();
+
+ let mut nodes = Vec::with_capacity(n);
+ for index in 0..n {
+ nodes.push(*graph.insert_node(index).id());
+ }
+
+ let mut edges = Vec::with_capacity(m);
+ for _ in 0..m {
+ let edge = input.next().unwrap()?;
+ let edge = edge
+ .split_whitespace()
+ .map(|x| x.parse::<usize>())
+ .collect::<Result<Vec<_>, _>>()?;
+
+ let u = edge[0];
+ let v = edge[1];
+ let w = edge[2] as u64;
+
+ let id = *graph.insert_edge(w, &nodes[u], &nodes[v]).id();
+ edges.push(id);
+ }
+
+ let source = nodes[s];
+ let target = nodes[t];
+
+ Ok(Parse {
+ graph,
+ source,
+ target,
+ nodes,
+ edges,
+ })
+}
+
+fn dump(route: Route<DinoStorage<usize, u64>, u64>) -> String {
+ let x = route.cost().into_value();
+ // transit are all intermediate nodes, we have to additional nodes (source and target)
+ // so we add `+ 2`, edges are between them, so we subtract `- 1`, resulting in `+ 1`
+ let y = route.path().transit().len() + 1;
+
+ let mut nodes: Vec<_> = route.into_path().into_iter().map(|x| *x.weight()).collect();
+
+ let mut output = vec![];
+ output.push(format!("{x} {y}"));
+
+ output.extend(
+ nodes
+ .iter()
+ .zip(nodes.iter().skip(1))
+ .map(|(u, v)| format!("{u} {v}")),
+ );
+
+ let mut output = output.join("\n");
+ output.push('\n');
+ output
+}
+
+fn test(input_path: &Path, name: &'static str) -> Result<String, Box<dyn Error>> {
+ let Parse {
+ graph,
+ source,
+ target,
+ ..
+ } = read(input_path)?;
+
+ let route = match name {
+ "dijkstra" => Dijkstra::directed().path_between(&graph, &source, &target),
+ "bellman_ford" => BellmanFord::directed().path_between(&graph, &source, &target),
+ "floyd_warshall" => FloydWarshall::directed().path_between(&graph, &source, &target),
+ _ => unreachable!(),
+ };
+
+ let Some(route) = route else {
+ return Ok(normalize_lines("-1\n"));
+ };
+
+ Ok(normalize_lines(&dump(route)))
+}
+
+pub fn main() {
+ Harness::new("tests/cases/shortest_path", setup, test)
+ .select(["*.in"])
+ .each(&["dijkstra", "bellman_ford", "floyd_warshall"])
+ .action(Action::Verify)
+ .test();
+}
diff --git a/crates/algorithms/tests/test_components_scc.rs b/crates/algorithms/tests/test_components_scc.BAK
similarity index 100%
rename from crates/algorithms/tests/test_components_scc.rs
rename to crates/algorithms/tests/test_components_scc.BAK
diff --git a/crates/algorithms/tests/test_cycles_feedback_arc_set.rs b/crates/algorithms/tests/test_cycles_feedback_arc_set.BAK
similarity index 100%
rename from crates/algorithms/tests/test_cycles_feedback_arc_set.rs
rename to crates/algorithms/tests/test_cycles_feedback_arc_set.BAK
diff --git a/crates/algorithms/tests/test_heuristics_matching.rs b/crates/algorithms/tests/test_heuristics_matching.BAK
similarity index 100%
rename from crates/algorithms/tests/test_heuristics_matching.rs
rename to crates/algorithms/tests/test_heuristics_matching.BAK
diff --git a/crates/algorithms/tests/test_isomorphism.rs b/crates/algorithms/tests/test_isomorphism.BAK
similarity index 100%
rename from crates/algorithms/tests/test_isomorphism.rs
rename to crates/algorithms/tests/test_isomorphism.BAK
diff --git a/crates/core/Cargo.toml b/crates/core/Cargo.toml
index b1317d3..f63d839 100644
--- a/crates/core/Cargo.toml
+++ b/crates/core/Cargo.toml
@@ -5,6 +5,7 @@
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]
+numi = { workspace = true }
fixedbitset = { workspace = true, optional = true }
bitvec = "1.0.1"
funty.workspace = true
diff --git a/crates/core/src/base/mod.rs b/crates/core/src/base/mod.rs
deleted file mode 100644
index 8ee1bf9..0000000
--- a/crates/core/src/base/mod.rs
+++ /dev/null
@@ -1,17 +0,0 @@
-//! Base types for the core crate.
-//!
-//! These are mostly analogue types that are needed to represent specific constructs that are not
-//! possible in `core` Rust.
-//!
-//! You should not rely on these types outside of petgraph specific API code, as they are very much
-//! temporary and a stand-in for a more general solution. This may include moving some of the types
-//! into their own crate.
-//!
-//! This currently includes:
-//! * [`MaybeOwned`]: A type that can either be owned or borrowed, an analogue to [`Cow`].
-//!
-//! [`Cow`]: std::borrow::Cow
-pub(crate) mod owned;
-
-pub use self::owned::MaybeOwned;
-// ^ TODO: into own crate
diff --git a/crates/core/src/error.rs b/crates/core/src/error.rs
index 06e731a..ec86092 100644
--- a/crates/core/src/error.rs
+++ b/crates/core/src/error.rs
@@ -19,7 +19,7 @@
}
#[cfg(not(feature = "std"))]
-impl Context for Error {}
+impl error_stack::Context for Error {}
#[cfg(feature = "std")]
impl std::error::Error for Error {}
diff --git a/crates/core/src/id/linear.rs b/crates/core/src/id/linear.rs
index 18789bb..d5c2f55 100644
--- a/crates/core/src/id/linear.rs
+++ b/crates/core/src/id/linear.rs
@@ -1,4 +1,6 @@
-use crate::{base::owned::MaybeOwned, id::GraphId, storage::GraphStorage};
+use numi::borrow::Moo;
+
+use crate::{id::GraphId, storage::GraphStorage};
/// Index mapper for a graph.
///
@@ -102,10 +104,8 @@
/// # Example
///
/// ```
- /// use petgraph_core::{
- /// base::MaybeOwned,
- /// id::{IndexMapper, LinearGraphId},
- /// };
+ /// use numi::borrow::Moo;
+ /// use petgraph_core::id::{IndexMapper, LinearGraphId};
/// use petgraph_dino::{DiDinoGraph, NodeId};
///
/// let mut graph = DiDinoGraph::new();
@@ -117,23 +117,23 @@
/// let mut mapper = NodeId::index_mapper(graph.storage());
///
/// let mapped = mapper.index(&a);
- /// assert_eq!(mapper.reverse(mapped), Some(MaybeOwned::Borrowed(&a)));
+ /// assert_eq!(mapper.reverse(mapped), Some(Moo::Borrowed(&a)));
/// ```
- fn reverse(&self, to: usize) -> Option<MaybeOwned<Id>>;
+ fn reverse(&self, to: usize) -> Option<Moo<Id>>;
}
/// Linear graph identifier.
///
/// A linear graph identifier is a graph identifier that has a linear mapping to a `usize` value,
-/// that mapping _may_ be continuous or discrete.
+/// that mapping must be continuous .
pub trait LinearGraphId<S>: GraphId + Sized
where
S: GraphStorage,
{
/// The index mapper for this graph identifier.
- type Mapper<'a>: IndexMapper<Self>
+ type Mapper<'graph>: IndexMapper<Self>
where
- S: 'a;
+ S: 'graph;
/// Get the index mapper for this graph identifier.
///
diff --git a/crates/core/src/lib.rs b/crates/core/src/lib.rs
index 8af05c7..ff52808 100644
--- a/crates/core/src/lib.rs
+++ b/crates/core/src/lib.rs
@@ -121,7 +121,6 @@
extern crate alloc;
pub mod attributes;
-pub mod base;
#[deprecated(since = "0.1.0")]
pub mod deprecated;
pub mod edge;
diff --git a/crates/core/src/node/mod.rs b/crates/core/src/node/mod.rs
index 215ed31..b4f01ad 100644
--- a/crates/core/src/node/mod.rs
+++ b/crates/core/src/node/mod.rs
@@ -53,8 +53,6 @@
{
storage: &'a S,
- // TODO: we might want to consider making these `MaybeOwned`, to allow for `Node` that cannot
- // borrow data.
id: &'a S::NodeId,
weight: &'a S::NodeWeight,
}
diff --git a/crates/dino/Cargo.toml b/crates/dino/Cargo.toml
index 6fdb400..758ab55 100644
--- a/crates/dino/Cargo.toml
+++ b/crates/dino/Cargo.toml
@@ -6,6 +6,7 @@
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]
+numi = { workspace = true }
petgraph-core = { workspace = true, features = ['alloc'] }
error-stack.workspace = true
diff --git a/crates/dino/src/lib.rs b/crates/dino/src/lib.rs
index 9860115..0d12dfa 100644
--- a/crates/dino/src/lib.rs
+++ b/crates/dino/src/lib.rs
@@ -101,7 +101,6 @@
//! ### Iterating over nodes and edges
// TODO
//!
-#![feature(return_position_impl_trait_in_trait)]
#![warn(missing_docs)]
#![no_std]
diff --git a/crates/dino/src/slab/mod.rs b/crates/dino/src/slab/mod.rs
index 14aea45..6321d35 100644
--- a/crates/dino/src/slab/mod.rs
+++ b/crates/dino/src/slab/mod.rs
@@ -7,7 +7,8 @@
use alloc::{vec, vec::Vec};
use core::{fmt::Debug, hash::Hash, marker::PhantomData, ptr};
-use petgraph_core::{base::MaybeOwned, id::IndexMapper};
+use numi::borrow::Moo;
+use petgraph_core::id::IndexMapper;
use crate::slab::entry::{Entry, State};
pub(crate) use crate::slab::{generation::Generation, id::EntryId, key::Key};
@@ -442,12 +443,8 @@
self.lookup[from.into_id().index()].expect("tried to access vacant entry")
}
- fn reverse(&self, to: usize) -> Option<MaybeOwned<K>> {
- self.reverse
- .get(to)
- .copied()
- .flatten()
- .map(MaybeOwned::from)
+ fn reverse(&self, to: usize) -> Option<Moo<K>> {
+ self.reverse.get(to).copied().flatten().map(Moo::from)
}
}
diff --git a/crates/numi/Cargo.toml b/crates/numi/Cargo.toml
new file mode 100644
index 0000000..0e83c28
--- /dev/null
+++ b/crates/numi/Cargo.toml
@@ -0,0 +1,15 @@
+[package]
+name = "numi"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+ordered-float = { version = "4.2.0", optional = true }
+
+[dev-dependencies]
+static_assertions = "1.1.0"
+
+[features]
+ordered-float-impl = ["dep:ordered-float"]
diff --git a/crates/numi/README.md b/crates/numi/README.md
new file mode 100644
index 0000000..1bf2e89
--- /dev/null
+++ b/crates/numi/README.md
@@ -0,0 +1,13 @@
+# Numi
+
+`numi` is a crate for primitives with a focus on numerical traits, akin to existing implementations such
+as [`num-traits`].
+The current goal of `numi` is to be a companion crate to [`num-traits`], instead of a replacement.
+
+Libraries should strive to implement these traits on their own, but as a convenience feature for early adopters default
+implementations have been provided. If you are a library author and would like to implement these traits, please open an
+issue so that the default implementations can be removed.
+
+The home of numi is yet to be decided until publication but will be
+
+[`num-traits`]: https://crates.io/crates/num-traits
diff --git a/crates/core/src/base/owned.rs b/crates/numi/src/borrow.rs
similarity index 65%
rename from crates/core/src/base/owned.rs
rename to crates/numi/src/borrow.rs
index 75c2592..711bbdd 100644
--- a/crates/core/src/base/owned.rs
+++ b/crates/numi/src/borrow.rs
@@ -1,25 +1,28 @@
-//! Collection of utility types and traits for working with values that may be owned or borrowed.
use core::{
cmp::Ordering,
fmt::{Display, Formatter},
hash::{Hash, Hasher},
};
-/// A type that may be owned or borrowed.
+/// # Maybe Owned Object
///
-/// This is analogous to [`Cow`], but without the `ToOwned` trait requirement (and therefore without
-/// the `alloc` requirement).
+/// This is analogous to [`Cow`], but without the additional [`ToOwned`] trait requirement which
+/// makes it unsuitable for `no_std` environments.
+///
+/// ## Name
+///
+/// The name `Moo` is a play on `Cow`, and is also a reference to the fact that cows moo.
+///
+/// > I totally didn't come up with the name first and then try to find an abbreviation that fit.
///
/// [`Cow`]: alloc::borrow::Cow
#[derive(Debug, Copy, Clone)]
-pub enum MaybeOwned<'a, T> {
- /// A borrowed value.
+pub enum Moo<'a, T> {
Borrowed(&'a T),
- /// An owned value.
Owned(T),
}
-impl<T> Display for MaybeOwned<'_, T>
+impl<T> Display for Moo<'_, T>
where
T: Display,
{
@@ -28,30 +31,30 @@
}
}
-impl<'a, T> From<T> for MaybeOwned<'a, T> {
+impl<'a, T> From<T> for Moo<'a, T> {
fn from(value: T) -> Self {
Self::Owned(value)
}
}
-impl<'a, T> From<&'a T> for MaybeOwned<'a, T> {
+impl<'a, T> From<&'a T> for Moo<'a, T> {
fn from(value: &'a T) -> Self {
Self::Borrowed(value)
}
}
-impl<'a, T> MaybeOwned<'a, T> {
+impl<'a, T> Moo<'a, T> {
/// Returns a mutable reference to the owned value, if any.
///
/// # Example
///
/// ```
- /// use petgraph_core::base::MaybeOwned;
+ /// use numi::borrow::Moo;
///
- /// let mut value = MaybeOwned::Owned(42);
+ /// let mut value = Moo::Owned(42);
/// assert_eq!(value.as_mut(), Some(&mut 42));
///
- /// let mut value = MaybeOwned::Borrowed(&42);
+ /// let mut value = Moo::Borrowed(&42);
/// assert_eq!(value.as_mut(), None);
/// ```
pub fn as_mut(&mut self) -> Option<&mut T> {
@@ -61,19 +64,19 @@
}
}
- /// Converts the `MaybeOwned` into an owned value.
+ /// Converts the `Moo` into an owned value.
///
/// This is a no-op if the value is already owned, and requires cloning if it is borrowed.
///
/// # Example
///
/// ```
- /// use petgraph_core::base::MaybeOwned;
+ /// use numi::borrow::Moo;
///
- /// let value = MaybeOwned::Owned(42);
+ /// let value = Moo::Owned(42);
/// assert_eq!(value.into_owned(), 42);
///
- /// let value = MaybeOwned::Borrowed(&42);
+ /// let value = Moo::Borrowed(&42);
/// assert_eq!(value.into_owned(), 42);
/// ```
pub fn into_owned(self) -> T
@@ -87,7 +90,7 @@
}
}
-impl<T> AsRef<T> for MaybeOwned<'_, T> {
+impl<T> AsRef<T> for Moo<'_, T> {
fn as_ref(&self) -> &T {
match self {
Self::Borrowed(value) => value,
@@ -96,7 +99,7 @@
}
}
-impl<T> PartialEq<T> for MaybeOwned<'_, T>
+impl<T> PartialEq<T> for Moo<'_, T>
where
T: PartialEq,
{
@@ -105,7 +108,7 @@
}
}
-impl<T> PartialEq for MaybeOwned<'_, T>
+impl<T> PartialEq for Moo<'_, T>
where
T: PartialEq,
{
@@ -114,9 +117,9 @@
}
}
-impl<T> Eq for MaybeOwned<'_, T> where T: Eq {}
+impl<T> Eq for Moo<'_, T> where T: Eq {}
-impl<T> PartialOrd<T> for MaybeOwned<'_, T>
+impl<T> PartialOrd<T> for Moo<'_, T>
where
T: PartialOrd,
{
@@ -125,7 +128,7 @@
}
}
-impl<T> PartialOrd for MaybeOwned<'_, T>
+impl<T> PartialOrd for Moo<'_, T>
where
T: PartialOrd,
{
@@ -134,7 +137,7 @@
}
}
-impl<T> Ord for MaybeOwned<'_, T>
+impl<T> Ord for Moo<'_, T>
where
T: Ord,
{
@@ -143,7 +146,7 @@
}
}
-impl<T> Hash for MaybeOwned<'_, T>
+impl<T> Hash for Moo<'_, T>
where
T: Hash,
{
diff --git a/crates/numi/src/cast.rs b/crates/numi/src/cast.rs
new file mode 100644
index 0000000..66b562f
--- /dev/null
+++ b/crates/numi/src/cast.rs
@@ -0,0 +1,172 @@
+use crate::primitive::{FromPrimitive, ToPrimitive, TryFromPrimitive};
+
+/// Cast a value from a different type.
+///
+/// This corresponds to the `as` keyword in Rust.
+///
+/// This is currently implemented for all the following types which implement `ToPrimitive` and
+/// `FromPrimitive`, which allows transparent conversion between them.
+///
+/// This means you are able to cast from [`Wrapping<u8>`] to [`Wrapping<u16>`] and [`u32`].
+///
+/// Unlike [`From`] this type does not have a blanked implementation for: `impl<T> From<T> for T`,
+/// instead it chooses to implement a blanket implementation which utilizes [`ToPrimitive`] and
+/// [`FromPrimitive`], as casting is a lossy process (corresponding to the `as` keyword), it only
+/// makes logical sense to blanket implement it on these traits instead of an identity
+/// implementation.
+///
+/// # Note
+///
+/// Unlike [`From`] and [`Into`], this trait has the following limitations, due to specialization
+/// concerns:
+/// * Implementing [`CastFrom`] does not automatically implement [`CastTo`].
+/// * [`CastTo`] is not implemented on the identity.
+///
+/// # Example
+///
+/// ```
+/// use std::num::{Saturating, Wrapping};
+///
+/// use numi::cast::CastTo;
+/// # #[cfg(feature = "ordered-float-impl")]
+/// use ordered_float::OrderedFloat;
+///
+/// let a = Wrapping(1u8);
+/// let b: Wrapping<u16> = a.cast_to();
+///
+/// // we can even cast across types!
+/// let a = Wrapping(1u8);
+/// let b: Saturating<u16> = a.cast_to();
+///
+/// # #[cfg(feature = "ordered-float-impl")]
+/// # fn ordered_float() {
+/// // ... and even across crates!
+/// // (this conversion requires the `ordered-float-impl` feature)
+/// let a = Wrapping(1u8);
+/// let b: OrderedFloat<f32> = a.cast_to();
+/// # }
+/// # #[cfg(feature = "ordered-float-impl")]
+/// # ordered_float();
+/// ```
+pub trait CastFrom<T> {
+ /// Cast a value from a different type.
+ ///
+ /// Might be lossy.
+ fn cast_from(value: T) -> Self;
+}
+
+impl<T, U> CastFrom<U> for T
+where
+ U: ToPrimitive,
+ T: FromPrimitive,
+{
+ fn cast_from(value: U) -> Self {
+ T::from_primitive(value)
+ }
+}
+
+/// Cast a value from a different type.
+///
+/// Fallible version of [`CastFrom`].
+pub trait TryCastFrom<T>: Sized {
+ /// The error type returned when the conversion fails.
+ type Error;
+
+ /// Cast a value from a different type.
+ ///
+ /// Might be lossy.
+ ///
+ /// # Errors
+ ///
+ /// Returns an error if the conversion fails.
+ fn try_cast_from(value: T) -> Result<Self, Self::Error>;
+}
+
+impl<T, U> TryCastFrom<U> for T
+where
+ U: ToPrimitive,
+ T: TryFromPrimitive,
+{
+ type Error = T::Error;
+
+ fn try_cast_from(value: U) -> Result<Self, Self::Error> {
+ T::try_from_primitive(value)
+ }
+}
+
+/// Cast a value to as different type.
+///
+/// This corresponds to the `as` keyword in Rust.
+///
+/// This is the inverse of [`CastFrom`], and is implemented for all types that implement
+/// [`CastFrom`].
+/// You should prefer to implement [`CastFrom`] instead of this trait.
+pub trait CastTo<T> {
+ fn cast_to(self) -> T;
+}
+
+impl<T, U> CastTo<U> for T
+where
+ U: CastFrom<T>,
+{
+ fn cast_to(self) -> U {
+ U::cast_from(self)
+ }
+}
+
+/// Cast a value to as different type.
+///
+/// Fallible version of [`CastTo`].
+///
+/// This is the inverse of [`TryCastFrom`], and is implemented for all types that implement
+/// [`TryCastFrom`].
+pub trait TryCastTo<T>: Sized {
+ /// The error type returned when the conversion fails.
+ type Error;
+
+ /// Cast a value to as different type.
+ ///
+ /// # Errors
+ ///
+ /// Returns an error if the conversion fails.
+ fn try_cast_to(self) -> Result<T, Self::Error>;
+}
+
+impl<T, U> TryCastTo<U> for T
+where
+ U: TryCastFrom<T>,
+{
+ type Error = U::Error;
+
+ fn try_cast_to(self) -> Result<U, Self::Error> {
+ U::try_cast_from(self)
+ }
+}
+
+#[cfg(test)]
+mod test {
+ use core::num::{Saturating, Wrapping};
+
+ use static_assertions::assert_impl_all;
+
+ use crate::cast::CastTo;
+
+ // can we do normal `as`?
+ assert_impl_all!(u8: CastTo<u16>);
+ assert_impl_all!(u16: CastTo<u8>);
+ assert_impl_all!(u16: CastTo<Wrapping<u16>>);
+
+ // can we do `as` with wrapping?
+ assert_impl_all!(Wrapping<u16>: CastTo<u16>);
+ assert_impl_all!(u16: CastTo<Wrapping<u16>>);
+
+ // can we do `as` with saturating?
+ assert_impl_all!(u16: CastTo<Saturating<u16>>);
+ assert_impl_all!(Saturating<u16>: CastTo<u16>);
+
+ assert_impl_all!(Saturating<u16>: CastTo<u8>);
+ assert_impl_all!(Saturating<u16>: CastTo<Wrapping<u32>>);
+
+ #[test]
+ fn compile() {}
+}
diff --git a/crates/numi/src/lib.rs b/crates/numi/src/lib.rs
new file mode 100644
index 0000000..77af42c
--- /dev/null
+++ b/crates/numi/src/lib.rs
@@ -0,0 +1,15 @@
+//! # Numi
+//!
+//! `numi` is a crate with a collection of common utility traits and abstractions for working with
+//! numbers and borrowed data.
+//!
+//! The library has been developed in conjunction with [`petgraph`], but is not specific to it.
+// TODO: extensive documentation with examples
+
+#![no_std]
+
+pub mod borrow;
+pub mod cast;
+mod macros;
+pub mod num;
+pub mod primitive;
diff --git a/crates/numi/src/macros.rs b/crates/numi/src/macros.rs
new file mode 100644
index 0000000..d0ba4a4
--- /dev/null
+++ b/crates/numi/src/macros.rs
@@ -0,0 +1,41 @@
+macro_rules! all_the_numbers {
+ ($name:ident) => {
+ $name!(u8);
+ $name!(u16);
+ $name!(u32);
+ $name!(u64);
+ $name!(u128);
+ $name!(usize);
+
+ $name!(i8);
+ $name!(i16);
+ $name!(i32);
+ $name!(i64);
+ $name!(i128);
+ $name!(isize);
+
+ $name!(f32);
+ $name!(f64);
+ };
+
+ (@typed $name:ident) => {
+ $name!(@int u8);
+ $name!(@int u16);
+ $name!(@int u32);
+ $name!(@int u64);
+ $name!(@int u128);
+ $name!(@int usize);
+
+ $name!(@int i8);
+ $name!(@int i16);
+ $name!(@int i32);
+ $name!(@int i64);
+ $name!(@int i128);
+ $name!(@int isize);
+
+ $name!(@float f32);
+ $name!(@float f64);
+ };
+}
+
+pub(crate) use all_the_numbers;
diff --git a/crates/numi/src/num/checked.rs b/crates/numi/src/num/checked.rs
new file mode 100644
index 0000000..4361e9a
--- /dev/null
+++ b/crates/numi/src/num/checked.rs
@@ -0,0 +1,163 @@
+//! Checked arithmetic operations.
+// TODO: more traits?
+use crate::macros::all_the_numbers;
+
+/// Addition that checks for overflow.
+///
+/// # Note
+///
+/// This trait is not implemented for [`Wrapping<T>`] because `checked_add` is defined as whenever
+/// an overflow happens, which is intentional for this type.
+///
+/// This trait is not implemented for [`Saturating<T>`] because `checked_add` is defined as whenever
+/// which does not have a concept of overflow.
+pub trait CheckedAdd: Sized {
+ /// Adds two numbers, checking for overflow. If overflow happens, `None` is returned.
+ ///
+ /// # Purity
+ ///
+ /// This function is pure.
+ fn checked_add(&self, rhs: &Self) -> Option<Self>;
+}
+
+/// Subtraction that checks for overflow.
+///
+/// # Note
+///
+/// This trait is not implemented for [`Wrapping<T>`] because `checked_sub` is defined as whenever
+/// an overflow happens, which is intentional for this type.
+///
+/// This trait is not implemented for [`Saturating<T>`] because `checked_sub` is defined as whenever
+/// which does not have a concept of overflow.
+pub trait CheckedSub: Sized {
+ /// Subtracts two numbers, checking for overflow. If overflow happens, `None` is returned.
+ ///
+ /// # Purity
+ ///
+ /// This function is pure.
+ fn checked_sub(&self, rhs: &Self) -> Option<Self>;
+}
+
+/// Multiplication that checks for overflow.
+///
+/// # Note
+///
+/// This trait is not implemented for [`Wrapping<T>`] because `checked_mul` is defined as whenever
+/// an overflow happens, which is intentional for this type.
+///
+/// This trait is not implemented for [`Saturating<T>`] because `checked_mul` is defined as whenever
+/// which does not have a concept of overflow.
+pub trait CheckedMul: Sized {
+ /// Multiplies two numbers, checking for overflow. If overflow happens, `None` is returned.
+ ///
+ /// # Purity
+ ///
+ /// This function is pure.
+ fn checked_mul(&self, rhs: &Self) -> Option<Self>;
+}
+
+/// Division that checks for overflow.
+///
+/// # Note
+///
+/// This trait is not implemented for [`Wrapping<T>`] because `checked_div` is defined as whenever
+/// an overflow happens, which is intentional for this type.
+///
+/// This trait is not implemented for [`Saturating<T>`] because `checked_div` is defined as whenever
+/// which does not have a concept of overflow.
+pub trait CheckedDiv: Sized {
+ /// Divides two numbers, checking for overflow. If overflow happens, `None` is returned.
+ ///
+ /// # Purity
+ ///
+ /// This function is pure.
+ fn checked_div(&self, rhs: &Self) -> Option<Self>;
+}
+
+macro_rules! impl_checked_add {
+ (@int $ty:ty) => {
+ impl CheckedAdd for $ty {
+ #[inline]
+ fn checked_add(&self, rhs: &Self) -> Option<Self> {
+ <$ty>::checked_add(*self, *rhs)
+ }
+ }
+
+ impl CheckedSub for $ty {
+ #[inline]
+ fn checked_sub(&self, rhs: &Self) -> Option<Self> {
+ <$ty>::checked_sub(*self, *rhs)
+ }
+ }
+
+ impl CheckedMul for $ty {
+ #[inline]
+ fn checked_mul(&self, rhs: &Self) -> Option<Self> {
+ <$ty>::checked_mul(*self, *rhs)
+ }
+ }
+
+ impl CheckedDiv for $ty {
+ #[inline]
+ fn checked_div(&self, rhs: &Self) -> Option<Self> {
+ <$ty>::checked_div(*self, *rhs)
+ }
+ }
+ };
+
+ (@float $ty:ty) => {};
+}
+
+all_the_numbers!(@typed impl_checked_add);
+
+#[cfg(feature = "ordered-float-impl")]
+impl<T> CheckedAdd for ordered_float::NotNan<T>
+where
+ T: ordered_float::FloatCore,
+{
+ fn checked_add(&self, rhs: &Self) -> Option<Self> {
+ let lhs = self.into_inner();
+ let rhs = rhs.into_inner();
+
+ Self::new(lhs + rhs).ok()
+ }
+}
+
+#[cfg(feature = "ordered-float-impl")]
+impl<T> CheckedSub for ordered_float::NotNan<T>
+where
+ T: ordered_float::FloatCore,
+{
+ fn checked_sub(&self, rhs: &Self) -> Option<Self> {
+ let lhs = self.into_inner();
+ let rhs = rhs.into_inner();
+
+ Self::new(lhs - rhs).ok()
+ }
+}
+
+#[cfg(feature = "ordered-float-impl")]
+impl<T> CheckedMul for ordered_float::NotNan<T>
+where
+ T: ordered_float::FloatCore,
+{
+ fn checked_mul(&self, rhs: &Self) -> Option<Self> {
+ let lhs = self.into_inner();
+ let rhs = rhs.into_inner();
+
+ Self::new(lhs * rhs).ok()
+ }
+}
+
+#[cfg(feature = "ordered-float-impl")]
+impl<T> CheckedDiv for ordered_float::NotNan<T>
+where
+ T: ordered_float::FloatCore,
+{
+ fn checked_div(&self, rhs: &Self) -> Option<Self> {
+ let lhs = self.into_inner();
+ let rhs = rhs.into_inner();
+
+ Self::new(lhs / rhs).ok()
+ }
+}
diff --git a/crates/numi/src/num/identity.rs b/crates/numi/src/num/identity.rs
new file mode 100644
index 0000000..63a40c6
--- /dev/null
+++ b/crates/numi/src/num/identity.rs
@@ -0,0 +1,256 @@
+//! Identity elements for numbers.
+
+use core::num::{Saturating, Wrapping};
+
+use crate::macros::all_the_numbers;
+
+/// Additive identity.
+///
+/// # Laws
+///
+/// ```text
+/// ∀ a ∈ Self: a + 0 = a
+/// ∀ a ∈ Self: 0 + a = a
+/// ```
+///
+/// # Note
+///
+/// This trait is different from [`num_traits::Zero`], as it doesn't have any supertraits and does
+/// not require [`Sized`].
+pub trait Zero {
+ /// Returns the additive identity of `Self`, `0`.
+ ///
+ /// # Purity
+ ///
+ /// This function is pure.
+ fn zero() -> Self;
+
+ /// Returns `true` if `self` is equal to the additive identity.
+ ///
+ /// # Purity
+ ///
+ /// This function is pure.
+ fn is_zero(&self) -> bool;
+}
+
+macro_rules! impl_zero {
+ (@int $ty:ty) => {
+ impl Zero for $ty {
+ #[inline]
+ fn zero() -> Self {
+ 0
+ }
+
+ #[inline]
+ fn is_zero(&self) -> bool {
+ *self == 0
+ }
+ }
+ };
+
+ (@float $ty:ty) => {
+ impl Zero for $ty {
+ #[inline]
+ fn zero() -> Self {
+ 0.0
+ }
+
+ #[inline]
+ fn is_zero(&self) -> bool {
+ *self == 0.0
+ }
+ }
+ };
+}
+
+all_the_numbers!(@typed impl_zero);
+
+impl<T> Zero for Wrapping<T>
+where
+ T: Zero,
+{
+ #[inline]
+ fn zero() -> Self {
+ Self(T::zero())
+ }
+
+ #[inline]
+ fn is_zero(&self) -> bool {
+ self.0.is_zero()
+ }
+}
+
+impl<T> Zero for Saturating<T>
+where
+ T: Zero,
+{
+ #[inline]
+ fn zero() -> Self {
+ Self(T::zero())
+ }
+
+ #[inline]
+ fn is_zero(&self) -> bool {
+ self.0.is_zero()
+ }
+}
+
+#[cfg(feature = "ordered-float-impl")]
+impl<T> Zero for ordered_float::OrderedFloat<T>
+where
+ T: Zero,
+{
+ #[inline]
+ fn zero() -> Self {
+ Self(T::zero())
+ }
+
+ #[inline]
+ fn is_zero(&self) -> bool {
+ self.0.is_zero()
+ }
+}
+
+#[cfg(feature = "ordered-float-impl")]
+impl<T> Zero for ordered_float::NotNan<T>
+where
+ T: Copy + Zero,
+{
+ #[inline]
+ fn zero() -> Self {
+ // SAFETY: `T::zero()` is always a valid `NotNan<T>`.
+ unsafe { Self::new_unchecked(T::zero()) }
+ }
+
+ #[inline]
+ fn is_zero(&self) -> bool {
+ self.into_inner().is_zero()
+ }
+}
+
+/// Multiplicative identity.
+///
+/// # Laws
+///
+/// ```text
+/// ∀ a ∈ Self: a * 1 = a
+/// ∀ a ∈ Self: 1 * a = a
+/// ```
+///
+/// # Note
+///
+/// This trait is different from [`num_traits::One`], as it doesn't have any supertraits and does
+/// not require [`Sized`].
+pub trait One {
+ /// Returns the multiplicative identity of `Self`, `1`.
+ ///
+ /// # Purity
+ ///
+ /// This function is pure.
+ fn one() -> Self;
+
+ /// Returns `true` if `self` is equal to the multiplicative identity.
+ ///
+ /// # Purity
+ ///
+ /// This function is pure.
+ fn is_one(&self) -> bool;
+}
+
+macro_rules! impl_one {
+ (@int $ty:ty) => {
+ impl One for $ty {
+ #[inline]
+ fn one() -> Self {
+ 1
+ }
+
+ #[inline]
+ fn is_one(&self) -> bool {
+ *self == 1
+ }
+ }
+ };
+
+ (@float $ty:ty) => {
+ impl One for $ty {
+ #[inline]
+ fn one() -> Self {
+ 1.0
+ }
+
+ #[inline]
+ fn is_one(&self) -> bool {
+ let difference = *self - 1.0;
+
+ // abs isn't available in no_std
+ difference < Self::EPSILON && difference > -Self::EPSILON
+ }
+ }
+ };
+}
+
+all_the_numbers!(@typed impl_one);
+
+impl<T> One for Wrapping<T>
+where
+ T: One,
+{
+ #[inline]
+ fn one() -> Self {
+ Self(T::one())
+ }
+
+ #[inline]
+ fn is_one(&self) -> bool {
+ self.0.is_one()
+ }
+}
+
+impl<T> One for Saturating<T>
+where
+ T: One,
+{
+ #[inline]
+ fn one() -> Self {
+ Self(T::one())
+ }
+
+ #[inline]
+ fn is_one(&self) -> bool {
+ self.0.is_one()
+ }
+}
+
+#[cfg(feature = "ordered-float-impl")]
+impl<T> One for ordered_float::OrderedFloat<T>
+where
+ T: One,
+{
+ #[inline]
+ fn one() -> Self {
+ Self(T::one())
+ }
+
+ #[inline]
+ fn is_one(&self) -> bool {
+ self.0.is_one()
+ }
+}
+
+#[cfg(feature = "ordered-float-impl")]
+impl<T> One for ordered_float::NotNan<T>
+where
+ T: Copy + One,
+{
+ #[inline]
+ fn one() -> Self {
+ // SAFETY: `T::one()` is always a valid `NotNan<T>`.
+ unsafe { Self::new_unchecked(T::one()) }
+ }
+
+ #[inline]
+ fn is_one(&self) -> bool {
+ self.into_inner().is_one()
+ }
+}
diff --git a/crates/numi/src/num/mod.rs b/crates/numi/src/num/mod.rs
new file mode 100644
index 0000000..ef7eb64
--- /dev/null
+++ b/crates/numi/src/num/mod.rs
@@ -0,0 +1,3 @@
+pub mod checked;
+pub mod identity;
+pub mod ops;
diff --git a/crates/numi/src/num/ops.rs b/crates/numi/src/num/ops.rs
new file mode 100644
index 0000000..5f86e47
--- /dev/null
+++ b/crates/numi/src/num/ops.rs
@@ -0,0 +1,30 @@
+use core::ops::Add;
+
+// proxy trait to not need to carry around where clause.
+/// Automatically implemented trait for adding a reference to a reference.
+///
+/// This trait is implemented for all types that implement `Add<&T, Output = T>` on `&T`.
+///
+/// This is a helper trait that shouldn't need to be implemented directly.
+/// The reason for it's existence is due to limitations in the Rust trait system.
+/// To have a similar bound on a trait that requires this as a supertrait one would need to use
+/// `where for<'a> &'a Self: Add<&'a Self, Output = Self>`, but that means that this where clause
+/// would need to be repeated every time the trait is used.
+///
+/// This limitation is known as [`implied bounds`](https://github.com/rust-lang/rust/issues/44491).
+pub trait AddRef<Rhs = Self> {
+ type Output;
+
+ fn add_ref(&self, rhs: &Rhs) -> Self::Output;
+}
+
+impl<T, Rhs, Output> AddRef<Rhs> for T
+where
+ for<'a> &'a T: Add<&'a Rhs, Output = Output>,
+{
+ type Output = Output;
+
+ fn add_ref(&self, rhs: &Rhs) -> Self::Output {
+ self + rhs
+ }
+}
diff --git a/crates/numi/src/primitive.rs b/crates/numi/src/primitive.rs
new file mode 100644
index 0000000..0b14317
--- /dev/null
+++ b/crates/numi/src/primitive.rs
@@ -0,0 +1,314 @@
+//! Conversion of arbitrary types to primitive types.
+//!
+//! This module is a collection of traits used to convert arbitrary types to primitive types.
+//!
+//! You usually don't want to use this, instead you should use [`numi::cast::CastTo`] or
+//! [`numi::cast::TryCastTo`] which are more ergonomic and provide the ability to cast between
+//! different types that can be converted from primitive types.
+use core::{
+ convert::Infallible,
+ num::{Saturating, Wrapping},
+};
+
+#[cfg(feature = "ordered-float-impl")]
+use ordered_float::{NotNan, OrderedFloat};
+
+pub trait Primitive: Copy {
+ // sadly we cannot have something like `from<T> where T: Primitive` because we cannot limit the
+ // implementations. Therefore don't know what we can expect and therefore cannot `as` them.
+ // We could in theory due this through sealing of the type, but this is something I'd like to
+ // avoid.
+
+ fn into_u8(self) -> u8;
+ fn into_u16(self) -> u16;
+ fn into_u32(self) -> u32;
+ fn into_u64(self) -> u64;
+ fn into_u128(self) -> u128;
+ fn into_usize(self) -> usize;
+
+ fn into_i8(self) -> i8;
+ fn into_i16(self) -> i16;
+ fn into_i32(self) -> i32;
+ fn into_i64(self) -> i64;
+ fn into_i128(self) -> i128;
+ fn into_isize(self) -> isize;
+
+ fn into_f32(self) -> f32;
+ fn into_f64(self) -> f64;
+
+ // fn into_bool(self) -> bool;
+ // fn into_char(self) -> char;
+}
+
+struct Proxy<T>(T);
+
+// proxy removes the `into_` prefix, makes it possible to more easily use in macros
+impl<T> Proxy<T>
+where
+ T: Primitive,
+{
+ fn u8(self) -> u8 {
+ self.0.into_u8()
+ }
+
+ fn u16(self) -> u16 {
+ self.0.into_u16()
+ }
+
+ fn u32(self) -> u32 {
+ self.0.into_u32()
+ }
+
+ fn u64(self) -> u64 {
+ self.0.into_u64()
+ }
+
+ fn u128(self) -> u128 {
+ self.0.into_u128()
+ }
+
+ fn usize(self) -> usize {
+ self.0.into_usize()
+ }
+
+ fn i8(self) -> i8 {
+ self.0.into_i8()
+ }
+
+ fn i16(self) -> i16 {
+ self.0.into_i16()
+ }
+
+ fn i32(self) -> i32 {
+ self.0.into_i32()
+ }
+
+ fn i64(self) -> i64 {
+ self.0.into_i64()
+ }
+
+ fn i128(self) -> i128 {
+ self.0.into_i128()
+ }
+
+ fn isize(self) -> isize {
+ self.0.into_isize()
+ }
+
+ fn f32(self) -> f32 {
+ self.0.into_f32()
+ }
+
+ fn f64(self) -> f64 {
+ self.0.into_f64()
+ }
+}
+
+macro_rules! impl_primitive {
+ ($ty:ident) => {
+ impl Primitive for $ty {
+ fn into_u8(self) -> u8 {
+ self as u8
+ }
+
+ fn into_u16(self) -> u16 {
+ self as u16
+ }
+
+ fn into_u32(self) -> u32 {
+ self as u32
+ }
+
+ fn into_u64(self) -> u64 {
+ self as u64
+ }
+
+ fn into_u128(self) -> u128 {
+ self as u128
+ }
+
+ fn into_usize(self) -> usize {
+ self as usize
+ }
+
+ fn into_i8(self) -> i8 {
+ self as i8
+ }
+
+ fn into_i16(self) -> i16 {
+ self as i16
+ }
+
+ fn into_i32(self) -> i32 {
+ self as i32
+ }
+
+ fn into_i64(self) -> i64 {
+ self as i64
+ }
+
+ fn into_i128(self) -> i128 {
+ self as i128
+ }
+
+ fn into_isize(self) -> isize {
+ self as isize
+ }
+
+ fn into_f32(self) -> f32 {
+ self as f32
+ }
+
+ fn into_f64(self) -> f64 {
+ self as f64
+ }
+ }
+
+ impl FromPrimitive for $ty {
+ fn from_primitive<T>(value: T) -> Self
+ where
+ T: ToPrimitive,
+ {
+ Proxy(value.into_primitive()).$ty()
+ }
+ }
+ };
+ ($($ty:ident),*) => {
+ $(impl_primitive!($ty);)*
+ };
+}
+
+impl_primitive!(
+ u8, u16, u32, u64, u128, usize, // unsigned integers
+ i8, i16, i32, i64, i128, isize, // signed integers
+ f32, f64 // floating point numbers
+);
+
+pub trait ToPrimitive {
+ type Primitive: Primitive;
+
+ fn as_primitive(&self) -> Self::Primitive;
+ fn into_primitive(self) -> Self::Primitive;
+}
+
+impl<T> ToPrimitive for T
+where
+ T: Primitive,
+{
+ type Primitive = T;
+
+ fn as_primitive(&self) -> Self::Primitive {
+ *self
+ }
+
+ fn into_primitive(self) -> Self::Primitive {
+ self
+ }
+}
+
+pub trait FromPrimitive {
+ fn from_primitive<T>(value: T) -> Self
+ where
+ T: ToPrimitive;
+}
+
+pub trait TryFromPrimitive: Sized {
+ type Error;
+
+ /// Try to convert a primitive value to `Self`.
+ ///
+ /// # Errors
+ ///
+ /// Returns an error if the conversion fails.
+ fn try_from_primitive<T>(value: T) -> Result<Self, Self::Error>
+ where
+ T: ToPrimitive;
+}
+
+impl<T> TryFromPrimitive for T
+where
+ T: FromPrimitive,
+{
+ // once never type is stable, we can use `!` instead of `Infallible`
+ type Error = Infallible;
+
+ fn try_from_primitive<U>(value: U) -> Result<Self, Self::Error>
+ where
+ U: ToPrimitive,
+ {
+ Ok(Self::from_primitive(value))
+ }
+}
+
+macro_rules! impl_newtype {
+ ($name:ident<$(|)? $($inner:ident)|*>) => {
+ $(
+ impl FromPrimitive for $name<$inner>
+ {
+ fn from_primitive<T>(value: T) -> Self where T: ToPrimitive {
+ Self(Proxy(value.into_primitive()).$inner())
+ }
+ }
+ )*
+
+ $(
+ impl ToPrimitive for $name<$inner>
+ {
+ type Primitive = $inner;
+
+ fn as_primitive(&self) -> Self::Primitive {
+ self.0
+ }
+
+ fn into_primitive(self) -> Self::Primitive {
+ self.0
+ }
+ }
+ )*
+ };
+}
+
+impl_newtype!(Wrapping<
+ | u8 | u16 | u32 | u64 | u128 | usize
+ | i8 | i16 | i32 | i64 | i128 | isize
+ | f32 | f64
+ >);
+
+impl_newtype!(Saturating<
+ | u8 | u16 | u32 | u64 | u128 | usize
+ | i8 | i16 | i32 | i64 | i128 | isize
+ | f32 | f64
+ >);
+
+#[cfg(feature = "ordered-float-impl")]
+impl_newtype!(OrderedFloat<
+ | f32 | f64
+ >);
+
+#[cfg(feature = "ordered-float-impl")]
+impl TryFromPrimitive for NotNan<f32> {
+ type Error = ordered_float::FloatIsNan;
+
+ fn try_from_primitive<T>(value: T) -> Result<Self, Self::Error>
+ where
+ T: ToPrimitive,
+ {
+ let value = value.into_primitive().into_f32();
+
+ Self::new(value)
+ }
+}
+
+#[cfg(feature = "ordered-float-impl")]
+impl TryFromPrimitive for NotNan<f64> {
+ type Error = ordered_float::FloatIsNan;
+
+ fn try_from_primitive<T>(value: T) -> Result<Self, Self::Error>
+ where
+ T: ToPrimitive,
+ {
+ let value = value.into_primitive().into_f64();
+
+ Self::new(value)
+ }
+}
diff --git a/justfile b/justfile
index bd41110..5be2e82 100644
--- a/justfile
+++ b/justfile
@@ -124,3 +124,35 @@
# Run the test suite and generate a coverage report
coverage *arguments: install-llvm-cov
cargo llvm-cov nextest --workspace --all-features --all-targets {{arguments}}
+
+######################################################################
+## Utilities
+######################################################################
+
+[private]
+clone-or-pull url path:
+ git clone "{{url}}" "{{path}}" 2>/dev/null || git -C "{{path}}" pull
+
+[private]
+generate-problem category name:
+ @echo "Generating problem {{name}}"
+ @cd "{{repo}}/crates/algorithms/tests/cases/problems" && ./venv/bin/python generate.py -p {{name}}
+
+ @echo "Copying files of problem {{name}}"
+ @mkdir -p "{{repo}}/crates/algorithms/tests/cases/{{name}}"
+ @rm -rf "{{repo}}/crates/algorithms/tests/cases/{{name}}/*"
+
+ @cp -r "{{repo}}/crates/algorithms/tests/cases/problems/{{category}}/{{name}}/in/" "{{repo}}/crates/algorithms/tests/cases/{{name}}/"
+ @cp -r "{{repo}}/crates/algorithms/tests/cases/problems/{{category}}/{{name}}/out/" "{{repo}}/crates/algorithms/tests/cases/{{name}}/"
+
+generate-problems:
+ # pull or clone repository
+ @just clone-or-pull https://github.com/yosupo06/library-checker-problems "{{repo}}/crates/algorithms/tests/cases/problems"
+ # create python virtual environment
+ @python3 -m venv crates/algorithms/tests/cases/problems/venv
+ # install dependencies
+ @crates/algorithms/tests/cases/problems/venv/bin/pip install -r crates/algorithms/tests/cases/problems/requirements.txt
+ # generate problems
+ @just generate-problem graph shortest_path
+
+
diff --git a/rust-toolchain.toml b/rust-toolchain.toml
index 9ec1184..9666a12 100644
--- a/rust-toolchain.toml
+++ b/rust-toolchain.toml
@@ -1,3 +1,3 @@
[toolchain]
-channel = "nightly-2023-10-18"
+channel = "nightly-2023-11-26"
components = ['rustfmt', 'clippy', 'llvm-tools-preview', 'miri']
