feat(algorithms): algorithm implementations
diff --git a/crates/algorithms/src/shortest_paths/astar/impl.rs b/crates/algorithms/src/shortest_paths/astar/impl.rs
index 17bf976..a8d1869 100644
--- a/crates/algorithms/src/shortest_paths/astar/impl.rs
+++ b/crates/algorithms/src/shortest_paths/astar/impl.rs
@@ -19,7 +19,6 @@
Path,
};
-// The graph must outlive the A* instance
pub(super) struct AStarImpl<'graph: 'parent, 'parent, S, E, H, C>
where
S: GraphStorage,
@@ -27,6 +26,7 @@
E: GraphCost<S>,
E::Value: Ord,
{
+ graph: &'graph Graph<S>,
queue: PriorityQueue<'graph, S, E::Value>,
edge_cost: &'parent E,
@@ -39,8 +39,8 @@
predecessor_mode: PredecessorMode,
distances: <S::NodeId as AssociativeGraphId<S>>::AttributeMapper<'graph, E::Value>,
- predecessors:
- <S::NodeId as AssociativeGraphId<S>>::AttributeMapper<'graph, Option<Node<'graph, S>>>,
+ estimates: <S::NodeId as AssociativeGraphId<S>>::AttributeMapper<'graph, E::Value>,
+ predecessors: <S::NodeId as AssociativeGraphId<S>>::AttributeMapper<'graph, Option<S::NodeId>>,
}
impl<'graph: 'parent, 'parent, S, E, H, C> AStarImpl<'graph, 'parent, S, E, H, C>
@@ -72,15 +72,18 @@
.node(target)
.ok_or_else(|| Report::new(AStarError::NodeNotFound))?;
+ let estimate = heuristic.estimate(source_node, target_node);
+
let mut queue = PriorityQueue::new(graph.storage());
- queue.push(
- source_node,
- heuristic.estimate(source_node, target_node).into_owned(),
- );
+ queue.check_admissibility = false;
+
+ queue.push(source_node.id(), estimate.clone().into_owned());
let mut distances = <S::NodeId as AssociativeGraphId<S>>::attribute_mapper(graph.storage());
distances.set(source, E::Value::zero());
+ let estimates = <S::NodeId as AssociativeGraphId<S>>::attribute_mapper(graph.storage());
+
let mut predecessors =
<S::NodeId as AssociativeGraphId<S>>::attribute_mapper(graph.storage());
if predecessor_mode == PredecessorMode::Record {
@@ -88,6 +91,7 @@
}
Ok(Self {
+ graph,
queue,
edge_cost,
@@ -100,33 +104,52 @@
predecessor_mode,
distances,
+ estimates,
predecessors,
})
}
pub(super) fn find(mut self) -> Option<Route<'graph, S, E::Value>> {
- while let Some(PriorityQueueItem { node, .. }) = self.queue.pop_min() {
- if node.id() == self.target.id() {
+ while let Some(PriorityQueueItem {
+ node,
+ priority: current_estimate,
+ }) = self.queue.pop_min()
+ {
+ if node == self.target.id() {
let transit = if self.predecessor_mode == PredecessorMode::Record {
- reconstruct_path_to(&self.predecessors, node.id())
+ reconstruct_path_to::<S>(&self.predecessors, node)
+ .into_iter()
+ .filter_map(|id| self.graph.node(id))
+ .collect()
} else {
Vec::new()
};
- let distance = self.distances.get(node.id())?.clone();
+ let distance = self.distances.get(node)?.clone();
return Some(Route::new(
Path::new(self.source, transit, self.target),
Cost::new(distance),
));
}
- let connections = self.connections.connections(&node);
+ if let Some(estimate) = self.estimates.get_mut(node) {
+ // if the current estimate is better than the estimate in the queue, skip this node
+ if *estimate <= current_estimate {
+ continue;
+ }
+
+ *estimate = current_estimate;
+ } else {
+ self.estimates.set(node, current_estimate);
+ }
+
+ let connections = self.connections.connections(node);
for edge in connections {
- let source_distance = self.distances.get(node.id())?;
+ let source_distance = self.distances.get(node)?;
let alternative = source_distance.add_ref(self.edge_cost.cost(edge).as_ref());
let (u, v) = edge.endpoints();
- let neighbour = if u.id() == node.id() { v } else { u };
+ let neighbour = if u.id() == node { v } else { u };
if let Some(distance) = self.distances.get(neighbour.id()) {
if alternative >= *distance {
@@ -142,7 +165,7 @@
self.predecessors.set(neighbour.id(), Some(node));
}
- self.queue.decrease_priority(neighbour, guess);
+ self.queue.decrease_priority(neighbour.id(), guess);
}
}
diff --git a/crates/algorithms/src/shortest_paths/astar/mod.rs b/crates/algorithms/src/shortest_paths/astar/mod.rs
index e21aa79..4109c44 100644
--- a/crates/algorithms/src/shortest_paths/astar/mod.rs
+++ b/crates/algorithms/src/shortest_paths/astar/mod.rs
@@ -20,14 +20,14 @@
pub use self::{error::AStarError, heuristic::GraphHeuristic, measure::AStarMeasure};
use super::{
common::{
- connections::{outgoing_connections, Connections},
+ connections::Connections,
cost::{Cost, DefaultCost, GraphCost},
route::{DirectRoute, Route},
transit::PredecessorMode,
},
ShortestDistance, ShortestPath,
};
-use crate::polyfill::IteratorExt;
+use crate::{polyfill::IteratorExt, shortest_paths::common::connections::NodeConnections};
/// A* shortest path algorithm.
///
@@ -159,7 +159,7 @@
graph,
&self.edge_cost,
&self.heuristic,
- outgoing_connections as fn(&Node<'graph, S>) -> _,
+ NodeConnections::directed(graph.storage()),
source,
target,
intermediates,
@@ -186,7 +186,7 @@
graph,
&self.edge_cost,
&self.heuristic,
- Node::<'graph, S>::connections as fn(&Node<'graph, S>) -> _,
+ NodeConnections::undirected(graph.storage()),
source,
target,
intermediates,
diff --git a/crates/algorithms/src/shortest_paths/astar/tests.rs b/crates/algorithms/src/shortest_paths/astar/tests.rs
index f13146b..8ff18c1 100644
--- a/crates/algorithms/src/shortest_paths/astar/tests.rs
+++ b/crates/algorithms/src/shortest_paths/astar/tests.rs
@@ -88,7 +88,7 @@
let GraphCollection { graph, nodes, .. } = networkx::create();
let astar = AStar::directed().with_heuristic(no_heuristic);
- let route = astar.path_between(&graph, &nodes.s, &nodes.v).unwrap();
+ let route = astar.path_between(&graph, nodes.s, nodes.v).unwrap();
let (path, cost) = route.into_parts();
let nodes: Vec<_> = path
@@ -106,7 +106,7 @@
let GraphCollection { graph, nodes, .. } = networkx::create();
let astar = AStar::directed().with_heuristic(no_heuristic);
- let route = astar.path_between(&graph, &nodes.s, &nodes.z);
+ let route = astar.path_between(&graph, nodes.s, nodes.z);
assert!(route.is_none());
}
@@ -116,7 +116,7 @@
let GraphCollection { graph, nodes, .. } = networkx::create();
let astar = AStar::undirected().with_heuristic(no_heuristic);
- let route = astar.path_between(&graph, &nodes.s, &nodes.v).unwrap();
+ let route = astar.path_between(&graph, nodes.s, nodes.v).unwrap();
let (path, cost) = route.into_parts();
let nodes: Vec<_> = path
@@ -134,7 +134,7 @@
let GraphCollection { graph, nodes, .. } = networkx::create();
let astar = AStar::undirected().with_heuristic(no_heuristic);
- let route = astar.path_between(&graph, &nodes.s, &nodes.z);
+ let route = astar.path_between(&graph, nodes.s, nodes.z);
assert!(route.is_none());
}
@@ -144,7 +144,7 @@
let GraphCollection { graph, nodes, .. } = networkx::create();
let astar = AStar::directed().with_heuristic(no_heuristic);
- let cost = astar.distance_between(&graph, &nodes.s, &nodes.v).unwrap();
+ let cost = astar.distance_between(&graph, nodes.s, nodes.v).unwrap();
assert_eq!(cost.into_value(), 9);
}
@@ -154,7 +154,7 @@
let GraphCollection { graph, nodes, .. } = networkx::create();
let astar = AStar::directed().with_heuristic(no_heuristic);
- let cost = astar.distance_between(&graph, &nodes.s, &nodes.z);
+ let cost = astar.distance_between(&graph, nodes.s, nodes.z);
assert!(cost.is_none());
}
@@ -164,7 +164,7 @@
let GraphCollection { graph, nodes, .. } = networkx::create();
let astar = AStar::undirected().with_heuristic(no_heuristic);
- let cost = astar.distance_between(&graph, &nodes.s, &nodes.v).unwrap();
+ let cost = astar.distance_between(&graph, nodes.s, nodes.v).unwrap();
assert_eq!(cost.into_value(), 8);
}
@@ -174,7 +174,7 @@
let GraphCollection { graph, nodes, .. } = networkx::create();
let astar = AStar::undirected().with_heuristic(no_heuristic);
- let cost = astar.distance_between(&graph, &nodes.s, &nodes.z);
+ let cost = astar.distance_between(&graph, nodes.s, nodes.z);
assert!(cost.is_none());
}
@@ -212,17 +212,17 @@
.with_edge_cost(ensure_not_nan)
.with_heuristic(manhattan_distance);
- let route = astar.path_between(&graph, &nodes.a, &nodes.f).unwrap();
+ let route = astar.path_between(&graph, nodes.a, nodes.f).unwrap();
let (path, cost) = route.into_parts();
- let path: Vec<_> = path.to_vec().into_iter().map(|node| *node.id()).collect();
+ let path: Vec<_> = path.to_vec().into_iter().map(|node| node.id()).collect();
assert_eq!(path, [nodes.a, nodes.b, nodes.f]);
- let a = graph.node(&nodes.a).unwrap();
- let b = graph.node(&nodes.b).unwrap();
- let f = graph.node(&nodes.f).unwrap();
+ let a = graph.node(nodes.a).unwrap();
+ let b = graph.node(nodes.b).unwrap();
+ let f = graph.node(nodes.f).unwrap();
assert_eq!(
cost.into_value(),
@@ -237,11 +237,11 @@
let astar = AStar::directed()
.with_edge_cost(ensure_not_nan)
.with_heuristic(manhattan_distance);
- let cost = astar.distance_between(&graph, &nodes.a, &nodes.f).unwrap();
+ let cost = astar.distance_between(&graph, nodes.a, nodes.f).unwrap();
- let a = graph.node(&nodes.a).unwrap();
- let b = graph.node(&nodes.b).unwrap();
- let f = graph.node(&nodes.f).unwrap();
+ let a = graph.node(nodes.a).unwrap();
+ let b = graph.node(nodes.b).unwrap();
+ let f = graph.node(nodes.f).unwrap();
assert_eq!(
cost.into_value(),
@@ -294,11 +294,11 @@
let GraphCollection { graph, nodes, .. } = inconsistent::create();
let astar = AStar::directed().with_heuristic(admissible_inconsistent);
- let route = astar.path_between(&graph, &nodes.a, &nodes.d).unwrap();
+ let route = astar.path_between(&graph, nodes.a, nodes.d).unwrap();
let (path, cost) = route.into_parts();
- let path: Vec<_> = path.to_vec().into_iter().map(|node| *node.id()).collect();
+ let path: Vec<_> = path.to_vec().into_iter().map(|node| node.id()).collect();
assert_eq!(path, [nodes.a, nodes.b, nodes.c, nodes.d]);
assert_eq!(cost.into_value(), 9);
@@ -339,7 +339,7 @@
}))
.with_heuristic(no_heuristic);
- astar.path_between(&graph, &nodes.a, &nodes.e).unwrap();
+ astar.path_between(&graph, nodes.a, nodes.e).unwrap();
// A* is runtime optimal in the sense it won't expand more nodes than needed, for the given
// heuristic. Here, A* should expand, in order: A, B, C, D, E. This should should ask for
diff --git a/crates/algorithms/src/shortest_paths/bellman_ford/impl.rs b/crates/algorithms/src/shortest_paths/bellman_ford/impl.rs
index 128cbba..f0b9963 100644
--- a/crates/algorithms/src/shortest_paths/bellman_ford/impl.rs
+++ b/crates/algorithms/src/shortest_paths/bellman_ford/impl.rs
@@ -248,7 +248,7 @@
}
}
- let edges = self.connections.connections(&source);
+ let edges = self.connections.connections(source.id());
for edge in edges {
let (u, v) = edge.endpoints();
diff --git a/crates/algorithms/src/shortest_paths/bellman_ford/mod.rs b/crates/algorithms/src/shortest_paths/bellman_ford/mod.rs
index a1d4c1d..24875b7 100644
--- a/crates/algorithms/src/shortest_paths/bellman_ford/mod.rs
+++ b/crates/algorithms/src/shortest_paths/bellman_ford/mod.rs
@@ -11,20 +11,19 @@
use error_stack::Result;
use petgraph_core::{
edge::marker::{Directed, Undirected},
- DirectedGraphStorage, Graph, GraphDirectionality, GraphStorage, Node,
+ DirectedGraphStorage, Graph, GraphDirectionality, GraphStorage,
};
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;
+use crate::{polyfill::IteratorExt, shortest_paths::common::connections::NodeConnections};
/// The order in which candidates are inserted into the queue.
///
@@ -230,6 +229,7 @@
/// let path = algorithm.path_between(&graph, &a, &b);
/// assert!(path.is_some());
/// ```
+ #[must_use]
pub fn with_candidate_order(self, candidate_order: CandidateOrder) -> Self {
Self {
direction: self.direction,
@@ -269,6 +269,7 @@
/// let path = algorithm.path_between(&graph, &a, &b);
/// assert!(path.is_some());
/// ```
+ #[must_use]
pub fn with_negative_cycle_heuristics(self, negative_cycle_heuristics: bool) -> Self {
Self {
direction: self.direction,
@@ -307,7 +308,7 @@
ShortestPathFasterImpl::new(
graph,
&self.edge_cost,
- Node::<'graph, S>::connections as fn(&Node<'graph, S>) -> _,
+ NodeConnections::undirected(graph.storage()),
source,
PredecessorMode::Record,
self.candidate_order,
@@ -325,7 +326,7 @@
ShortestPathFasterImpl::new(
graph,
&self.edge_cost,
- Node::<'graph, S>::connections as fn(&Node<'graph, S>) -> _,
+ NodeConnections::undirected(graph.storage()),
source,
PredecessorMode::Record,
self.candidate_order,
@@ -376,7 +377,7 @@
let iter = ShortestPathFasterImpl::new(
graph,
&self.edge_cost,
- Node::<'graph, S>::connections as fn(&Node<'graph, S>) -> _,
+ NodeConnections::undirected(graph.storage()),
source,
PredecessorMode::Discard,
self.candidate_order,
@@ -386,16 +387,16 @@
Ok(iter.all().map(Into::into))
}
- fn distance_between<'graph>(
+ fn distance_between(
&self,
- graph: &'graph Graph<S>,
+ graph: &Graph<S>,
source: S::NodeId,
target: S::NodeId,
) -> Option<Cost<Self::Cost>> {
ShortestPathFasterImpl::new(
graph,
&self.edge_cost,
- Node::<'graph, S>::connections as fn(&Node<'graph, S>) -> _,
+ NodeConnections::undirected(graph.storage()),
source,
PredecessorMode::Discard,
self.candidate_order,
@@ -437,7 +438,7 @@
ShortestPathFasterImpl::new(
graph,
&self.edge_cost,
- outgoing_connections as fn(&Node<'graph, S>) -> _,
+ NodeConnections::directed(graph.storage()),
source,
PredecessorMode::Record,
self.candidate_order,
@@ -455,7 +456,7 @@
ShortestPathFasterImpl::new(
graph,
&self.edge_cost,
- outgoing_connections as fn(&Node<'graph, S>) -> _,
+ NodeConnections::directed(graph.storage()),
source,
PredecessorMode::Record,
self.candidate_order,
@@ -496,7 +497,7 @@
let iter = ShortestPathFasterImpl::new(
graph,
&self.edge_cost,
- outgoing_connections as fn(&Node<'graph, S>) -> _,
+ NodeConnections::directed(graph.storage()),
source,
PredecessorMode::Discard,
self.candidate_order,
@@ -506,16 +507,16 @@
Ok(iter.all().map(Into::into))
}
- fn distance_between<'graph>(
+ fn distance_between(
&self,
- graph: &'graph Graph<S>,
+ graph: &Graph<S>,
source: S::NodeId,
target: S::NodeId,
) -> Option<Cost<Self::Cost>> {
ShortestPathFasterImpl::new(
graph,
&self.edge_cost,
- outgoing_connections as fn(&Node<'graph, S>) -> _,
+ NodeConnections::directed(graph.storage()),
source,
PredecessorMode::Discard,
self.candidate_order,
diff --git a/crates/algorithms/src/shortest_paths/bellman_ford/tests.rs b/crates/algorithms/src/shortest_paths/bellman_ford/tests.rs
index fa55e4b..3295888 100644
--- a/crates/algorithms/src/shortest_paths/bellman_ford/tests.rs
+++ b/crates/algorithms/src/shortest_paths/bellman_ford/tests.rs
@@ -44,11 +44,11 @@
fn source_does_not_exist() {
let GraphCollection { mut graph, .. } = networkx::create();
- let f = *graph.insert_node("F").id();
- graph.remove_node(&f);
+ let f = graph.insert_node("F").id();
+ graph.remove_node(f);
let spfa = BellmanFord::directed();
- let Err(received) = spfa.path_from(&graph, &f) else {
+ let Err(received) = spfa.path_from(&graph, f) else {
panic!("Expected an error");
};
let error = received.current_context();
@@ -60,23 +60,23 @@
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();
+ 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);
+ 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();
+ 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;
+ *graph.edge_mut(ca).unwrap().weight_mut() = 2.0;
assert!(spfa.every_path(&graph).is_ok());
}
@@ -88,11 +88,11 @@
{
let mut graph = Graph::new();
- let nodes: [_; N] = array::from_fn(|index| *graph.insert_node(index).id());
+ 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])
+ graph
+ .insert_edge(1f32, nodes[index], nodes[(index + 1) % N])
.id()
});
@@ -107,13 +107,13 @@
{
let mut graph = Graph::new();
- let nodes: [_; N] = array::from_fn(|index| *graph.insert_node(index).id());
+ 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());
+ edges.push(graph.insert_edge(1f32, nodes[i], nodes[j]).id());
}
}
@@ -128,12 +128,12 @@
{
let mut graph = Graph::new();
- let nodes: [_; N] = array::from_fn(|index| *graph.insert_node(index).id());
+ 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());
+ edges.push(graph.insert_edge(1f32, nodes[i], nodes[i + 1]).id());
}
(graph, nodes, edges)
@@ -147,7 +147,7 @@
assert!(spfa.every_path(&graph).is_ok());
// add negative cycle between nodes 1 and 2
- *graph.insert_edge(-7f32, &nodes[1], &nodes[2]).id();
+ graph.insert_edge(-7f32, nodes[1], nodes[2]);
assert!(spfa.every_path(&graph).is_err());
}
@@ -159,7 +159,7 @@
assert!(spfa.every_path(&graph).is_ok());
// add negative cycle between nodes 1 and 2
- *graph.insert_edge(-3f32, &nodes[1], &nodes[2]).id();
+ graph.insert_edge(-3f32, nodes[1], nodes[2]);
assert!(spfa.every_path(&graph).is_err());
}
@@ -167,9 +167,9 @@
fn negative_self_cycle() {
let mut graph = DiDinoGraph::new();
- let a = *graph.insert_node("A").id();
+ let a = graph.insert_node("A").id();
- graph.insert_edge(-1f32, &a, &a);
+ graph.insert_edge(-1f32, a, a);
let spfa = BellmanFord::directed();
assert!(spfa.every_path(&graph).is_err());
@@ -183,11 +183,11 @@
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();
+ 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;
+ *graph.edge_mut(edge).unwrap().weight_mut() = -4.0001f32;
assert!(spfa.every_path(&graph).is_err());
}
@@ -199,7 +199,7 @@
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]);
+ graph.insert_edge(-3f32, nodes[1], nodes[2]);
let expected = expected!(nodes; [
0 -()> 0: 0f32,
@@ -209,19 +209,19 @@
0 -(1, 2, 3)> 4: 0f32,
]);
- TestCase::new(&graph, &spfa, &expected).assert_path_from(&nodes[0]);
+ 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();
+ 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);
+ graph.insert_edge(1f32, g, h);
+ graph.insert_edge(1f32, g, i);
let spfa = BellmanFord::directed();
@@ -234,20 +234,20 @@
0 -()> 5: 1f32,
]);
- TestCase::new(&graph, &spfa, &expected).assert_path_from(&nodes[0]);
+ 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();
+ 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);
+ graph.insert_edge(1f32, g, h);
+ graph.insert_edge(1f32, h, i);
+ graph.insert_edge(-3f32, i, g);
let spfa = BellmanFord::directed();
@@ -260,7 +260,7 @@
0 -()> 5: 1f32,
]);
- TestCase::new(&graph, &spfa, &expected).assert_path_from(&nodes[0]);
+ TestCase::new(&graph, &spfa, &expected).assert_path_from(nodes[0]);
}
#[test]
@@ -277,5 +277,5 @@
0 -(1, 2, 3)> 4: 4f32,
]);
- TestCase::new(&graph, &spfa, &expected).assert_path_from(&nodes[0]);
+ 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
index 8d701aa..90fd2ed 100644
--- a/crates/algorithms/src/shortest_paths/common/closures.rs
+++ b/crates/algorithms/src/shortest_paths/common/closures.rs
@@ -35,12 +35,12 @@
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();
+ let a = graph.insert_node("A").id();
+ let b = graph.insert_node("B").id();
- graph.insert_edge(7, &a, &b);
+ graph.insert_edge(7, a, b);
- let path = algorithm.path_between(&graph, &a, &b).expect("path exists");
+ let path = algorithm.path_between(&graph, a, b).expect("path exists");
}
#[test]
@@ -50,12 +50,12 @@
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();
+ let a = graph.insert_node("A").id();
+ let b = graph.insert_node("B").id();
- graph.insert_edge(7i32, &a, &b);
+ graph.insert_edge(7i32, a, b);
- let path = algorithm.path_between(&graph, &a, &b).expect("path exists");
+ let path = algorithm.path_between(&graph, a, b).expect("path exists");
}
}
diff --git a/crates/algorithms/src/shortest_paths/common/queue/priority.rs b/crates/algorithms/src/shortest_paths/common/queue/priority.rs
index 57e0272..24de078 100644
--- a/crates/algorithms/src/shortest_paths/common/queue/priority.rs
+++ b/crates/algorithms/src/shortest_paths/common/queue/priority.rs
@@ -3,7 +3,7 @@
use petgraph_core::{
id::{AssociativeGraphId, BooleanMapper},
- GraphStorage, Node,
+ GraphStorage,
};
pub(in crate::shortest_paths) struct PriorityQueueItem<I, T> {
@@ -48,6 +48,7 @@
T: Ord,
{
heap: BinaryHeap<PriorityQueueItem<S::NodeId, T>>,
+ pub(crate) check_admissibility: bool,
flags: <S::NodeId as AssociativeGraphId<S>>::BooleanMapper<'a>,
}
@@ -62,6 +63,7 @@
pub(in crate::shortest_paths) fn new(storage: &'a S) -> Self {
Self {
heap: BinaryHeap::new(),
+ check_admissibility: true,
flags: <S::NodeId as AssociativeGraphId<S>>::boolean_mapper(storage),
}
}
@@ -81,7 +83,7 @@
#[inline]
pub(in crate::shortest_paths) fn decrease_priority(&mut self, node: S::NodeId, priority: T) {
- if self.has_been_visited(node) {
+ if self.check_admissibility && self.has_been_visited(node) {
return;
}
@@ -93,7 +95,7 @@
loop {
let item = self.heap.pop()?;
- if self.has_been_visited(item.node) {
+ if self.check_admissibility && self.has_been_visited(item.node) {
continue;
}
diff --git a/crates/algorithms/src/shortest_paths/common/tests.rs b/crates/algorithms/src/shortest_paths/common/tests.rs
index 0839623..629ff62 100644
--- a/crates/algorithms/src/shortest_paths/common/tests.rs
+++ b/crates/algorithms/src/shortest_paths/common/tests.rs
@@ -95,8 +95,8 @@
.collect();
for expect in self.expected {
- let source = &expect.source;
- let target = &expect.target;
+ let source = expect.source;
+ let target = expect.target;
let route = routes.remove(&(source, target)).expect("route not found");
@@ -106,7 +106,7 @@
assert_eq!(path.target().id(), target, "target of {source} -> {target}");
assert_eq!(
path.transit().iter().map(Node::id).collect::<Vec<_>>(),
- expect.transit.iter().collect::<Vec<_>>(),
+ expect.transit.iter().copied().collect::<Vec<_>>(),
"transit of {source} -> {target}"
);
assert_eq!(*cost.value(), expect.cost, "cost of {source} -> {target}");
@@ -120,7 +120,7 @@
}
#[track_caller]
- pub(in crate::shortest_paths) fn assert_path_from(&self, source: &S::NodeId) {
+ pub(in crate::shortest_paths) fn assert_path_from(&self, source: S::NodeId) {
self.assert_path_routes(self.algorithm.path_from(self.graph, source));
}
}
@@ -143,8 +143,8 @@
.collect();
for expect in self.expected {
- let source = &expect.source;
- let target = &expect.target;
+ let source = expect.source;
+ let target = expect.target;
let route = routes.remove(&(source, target)).expect("route not found");
@@ -174,7 +174,7 @@
}
#[track_caller]
- pub(in crate::shortest_paths) fn assert_distance_from(&self, source: &S::NodeId) {
+ pub(in crate::shortest_paths) fn assert_distance_from(&self, source: S::NodeId) {
self.assert_distance_routes(self.algorithm.distance_from(self.graph, source));
}
}
diff --git a/crates/algorithms/src/shortest_paths/common/transit.rs b/crates/algorithms/src/shortest_paths/common/transit.rs
index 28d2451..cd7f47e 100644
--- a/crates/algorithms/src/shortest_paths/common/transit.rs
+++ b/crates/algorithms/src/shortest_paths/common/transit.rs
@@ -110,13 +110,12 @@
} 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;
- }
+ if let Some(new_top) = top.checked_sub(1) {
+ top = new_top;
+ } else {
+ // we have exhausted all paths
+ exhausted = true;
+ break;
}
}
diff --git a/crates/algorithms/src/shortest_paths/dijkstra/iter.rs b/crates/algorithms/src/shortest_paths/dijkstra/iter.rs
index 2cf3776..f2972f3 100644
--- a/crates/algorithms/src/shortest_paths/dijkstra/iter.rs
+++ b/crates/algorithms/src/shortest_paths/dijkstra/iter.rs
@@ -193,6 +193,7 @@
let transit = if self.predecessor_mode == PredecessorMode::Discard {
Vec::new()
} else {
+ // TODO: cache via dedicated structure
reconstruct_path_to::<S>(&self.predecessors, node)
.into_iter()
.filter_map(|id| self.graph.node(id))
diff --git a/crates/algorithms/src/shortest_paths/dijkstra/tests.rs b/crates/algorithms/src/shortest_paths/dijkstra/tests.rs
index 0386ab0..c6ee7fa 100644
--- a/crates/algorithms/src/shortest_paths/dijkstra/tests.rs
+++ b/crates/algorithms/src/shortest_paths/dijkstra/tests.rs
@@ -78,7 +78,7 @@
let dijkstra = Dijkstra::directed();
- TestCase::new(&graph, &dijkstra, &expected).assert_path_from(&nodes.a);
+ TestCase::new(&graph, &dijkstra, &expected).assert_path_from(nodes.a);
}
#[test]
@@ -88,7 +88,7 @@
let dijkstra = Dijkstra::directed();
- TestCase::new(&graph, &dijkstra, &expected).assert_distance_from(&nodes.a);
+ TestCase::new(&graph, &dijkstra, &expected).assert_distance_from(nodes.a);
}
fn random_directed_expect_from(
@@ -119,7 +119,7 @@
let dijkstra = Dijkstra::directed().with_edge_cost(edge_cost);
let expected = random_directed_expect_from(&nodes);
- TestCase::new(&graph, &dijkstra, &expected).assert_path_from(&nodes.a);
+ TestCase::new(&graph, &dijkstra, &expected).assert_path_from(nodes.a);
}
#[test]
@@ -129,7 +129,7 @@
let dijkstra = Dijkstra::directed().with_edge_cost(edge_cost);
let expected = random_directed_expect_from(&nodes);
- TestCase::new(&graph, &dijkstra, &expected).assert_distance_from(&nodes.a);
+ TestCase::new(&graph, &dijkstra, &expected).assert_distance_from(nodes.a);
}
fn networkx_undirected_expect_from(
@@ -151,7 +151,7 @@
let dijkstra = Dijkstra::undirected();
let expected = networkx_undirected_expect_from(&nodes);
- TestCase::new(&graph, &dijkstra, &expected).assert_path_from(&nodes.a);
+ TestCase::new(&graph, &dijkstra, &expected).assert_path_from(nodes.a);
}
#[test]
@@ -161,7 +161,7 @@
let dijkstra = Dijkstra::undirected();
let expected = networkx_undirected_expect_from(&nodes);
- TestCase::new(&graph, &dijkstra, &expected).assert_distance_from(&nodes.a);
+ TestCase::new(&graph, &dijkstra, &expected).assert_distance_from(nodes.a);
}
fn random_undirected_expect_from(
@@ -184,7 +184,7 @@
let dijkstra = Dijkstra::undirected().with_edge_cost(edge_cost);
let expected = random_undirected_expect_from(&nodes);
- TestCase::new(&graph, &dijkstra, &expected).assert_path_from(&nodes.a);
+ TestCase::new(&graph, &dijkstra, &expected).assert_path_from(nodes.a);
}
#[test]
@@ -194,7 +194,7 @@
let dijkstra = Dijkstra::undirected().with_edge_cost(edge_cost);
let expected = random_undirected_expect_from(&nodes);
- TestCase::new(&graph, &dijkstra, &expected).assert_distance_from(&nodes.a);
+ TestCase::new(&graph, &dijkstra, &expected).assert_distance_from(nodes.a);
}
#[test]
@@ -204,7 +204,7 @@
let dijkstra = Dijkstra::directed();
let top3: Vec<_> = dijkstra
- .path_from(&graph, &nodes.a)
+ .path_from(&graph, nodes.a)
.unwrap()
.take(3)
.collect();
diff --git a/crates/algorithms/src/shortest_paths/floyd_warshall/tests.rs b/crates/algorithms/src/shortest_paths/floyd_warshall/tests.rs
index c1d970b..1bd28b0 100644
--- a/crates/algorithms/src/shortest_paths/floyd_warshall/tests.rs
+++ b/crates/algorithms/src/shortest_paths/floyd_warshall/tests.rs
@@ -184,7 +184,7 @@
let floyd_warshall = FloydWarshall::directed();
let route = floyd_warshall
- .path_between(&graph, &nodes.a, &nodes.c)
+ .path_between(&graph, nodes.a, nodes.c)
.unwrap();
let (path, cost) = route.into_parts();
@@ -192,7 +192,7 @@
assert_eq!(
path.to_vec()
.into_iter()
- .map(|node| *node.id())
+ .map(|node| node.id())
.collect::<Vec<_>>(),
vec![nodes.a, nodes.b, nodes.c]
);
@@ -204,14 +204,14 @@
let floyd_warshall = FloydWarshall::directed();
- let paths = floyd_warshall.path_from(&graph, &nodes.a).unwrap();
+ let paths = floyd_warshall.path_from(&graph, nodes.a).unwrap();
let mut expected: HashSet<_> = [nodes.a, nodes.b, nodes.c, nodes.d].into_iter().collect();
// cost is tested above, this just checks that the filter is correct.
for route in paths {
- assert_eq!(*route.path().source().id(), nodes.a);
- assert!(expected.remove(route.path().target().id()));
+ assert_eq!(route.path().source().id(), nodes.a);
+ assert!(expected.remove(&route.path().target().id()));
}
}
@@ -221,14 +221,14 @@
let floyd_warshall = FloydWarshall::directed();
- let paths = floyd_warshall.path_to(&graph, &nodes.c).unwrap();
+ let paths = floyd_warshall.path_to(&graph, nodes.c).unwrap();
let mut expected: HashSet<_> = [nodes.a, nodes.b, nodes.c].into_iter().collect();
// cost is tested above, this just checks that the filter is correct.
for route in paths {
- assert!(expected.remove(route.path().source().id()));
- assert_eq!(*route.path().target().id(), nodes.c);
+ assert!(expected.remove(&route.path().source().id()));
+ assert_eq!(route.path().target().id(), nodes.c);
}
}
@@ -285,7 +285,7 @@
let floyd_warshall = FloydWarshall::undirected();
let route = floyd_warshall
- .path_between(&graph, &nodes.a, &nodes.c)
+ .path_between(&graph, nodes.a, nodes.c)
.unwrap();
let (path, cost) = route.into_parts();
@@ -293,7 +293,7 @@
assert_eq!(
path.to_vec()
.into_iter()
- .map(|node| *node.id())
+ .map(|node| node.id())
.collect::<Vec<_>>(),
vec![nodes.a, nodes.b, nodes.c]
);
@@ -305,14 +305,14 @@
let floyd_warshall = FloydWarshall::undirected();
- let paths = floyd_warshall.path_from(&graph, &nodes.a).unwrap();
+ let paths = floyd_warshall.path_from(&graph, nodes.a).unwrap();
let mut expected: HashSet<_> = [nodes.a, nodes.b, nodes.c, nodes.d].into_iter().collect();
// cost is tested above, this just checks that the filter is correct.
for route in paths {
- assert_eq!(*route.path().source().id(), nodes.a);
- assert!(expected.remove(route.path().target().id()));
+ assert_eq!(route.path().source().id(), nodes.a);
+ assert!(expected.remove(&route.path().target().id()));
}
}
@@ -322,14 +322,14 @@
let floyd_warshall = FloydWarshall::undirected();
- let paths = floyd_warshall.path_to(&graph, &nodes.c).unwrap();
+ let paths = floyd_warshall.path_to(&graph, nodes.c).unwrap();
let mut expected: HashSet<_> = [nodes.a, nodes.b, nodes.c, nodes.d].into_iter().collect();
// cost is tested above, this just checks that the filter is correct.
for route in paths {
- assert!(expected.remove(route.path().source().id()));
- assert_eq!(*route.path().target().id(), nodes.c);
+ assert!(expected.remove(&route.path().source().id()));
+ assert_eq!(route.path().target().id(), nodes.c);
}
}
diff --git a/crates/algorithms/src/shortest_paths/mod.rs b/crates/algorithms/src/shortest_paths/mod.rs
index a30ea63..c199eaf 100644
--- a/crates/algorithms/src/shortest_paths/mod.rs
+++ b/crates/algorithms/src/shortest_paths/mod.rs
@@ -50,8 +50,8 @@
//! assert!(path.is_none());
//! ```
-// pub mod astar;
-// pub mod bellman_ford;
+pub mod astar;
+pub mod bellman_ford;
mod common;
pub mod dijkstra;
pub mod floyd_warshall;
@@ -60,8 +60,8 @@
use petgraph_core::{Graph, GraphStorage};
pub use self::{
- // astar::AStar,
- // bellman_ford::BellmanFord,
+ astar::AStar,
+ bellman_ford::BellmanFord,
common::{
cost::{Cost, GraphCost},
path::Path,
@@ -242,7 +242,7 @@
self.every_distance(graph)
.ok()?
.find(move |route| route.source().id() == source && route.target().id() == target)
- .map(|route| route.into_cost())
+ .map(DirectRoute::into_cost)
}
/// Returns an iterator over all shortest distances in the graph.
diff --git a/crates/algorithms/tests/shortest_paths/main.rs b/crates/algorithms/tests/shortest_paths/main.rs
index 5ce7a3d..e2fbafb 100644
--- a/crates/algorithms/tests/shortest_paths/main.rs
+++ b/crates/algorithms/tests/shortest_paths/main.rs
@@ -8,7 +8,7 @@
};
use petgraph_algorithms::shortest_paths::{
- bellman_ford::CandidateOrder, BellmanFord, Dijkstra, FloydWarshall, Route, ShortestPath,
+ BellmanFord, Dijkstra, FloydWarshall, Route, ShortestPath,
};
use petgraph_dino::{DiDinoGraph, DinoStorage, EdgeId, NodeId};
use snapbox::{utils::normalize_lines, Action};
@@ -18,10 +18,10 @@
fn setup(input_path: PathBuf) -> Case {
let name = input_path
.file_stem()
- .unwrap()
+ .expect("file stem")
.to_str()
- .unwrap()
- .to_string();
+ .expect("to str")
+ .to_owned();
let expected = input_path.with_extension("out");
@@ -49,10 +49,10 @@
}
fn parse(mut input: Lines<impl BufRead>) -> Result<Parse, Box<dyn Error>> {
- let meta = input.next().unwrap()?;
+ let meta = input.next().expect("first line")?;
let meta = meta
.split_whitespace()
- .map(|x| x.parse::<usize>())
+ .map(str::parse::<usize>)
.collect::<Result<Vec<_>, _>>()?;
let n = meta[0];
@@ -64,22 +64,22 @@
let mut nodes = Vec::with_capacity(n);
for index in 0..n {
- nodes.push(*graph.insert_node(index).id());
+ 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 = input.next().expect("edge")?;
let edge = edge
.split_whitespace()
- .map(|x| x.parse::<usize>())
+ .map(str::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();
+ let id = graph.insert_edge(w, nodes[u], nodes[v]).id();
edges.push(id);
}
@@ -101,7 +101,7 @@
// 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 nodes: Vec<_> = route.into_path().into_iter().map(|x| *x.weight()).collect();
let mut output = vec![];
output.push(format!("{x} {y}"));
@@ -127,9 +127,9 @@
} = 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),
+ "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!(),
};
diff --git a/crates/utils/src/lib.rs b/crates/utils/src/lib.rs
index 40e3939..bd87a13 100644
--- a/crates/utils/src/lib.rs
+++ b/crates/utils/src/lib.rs
@@ -65,7 +65,7 @@
$graph:ident; $output:ident; $name:ident[$($id:ident : $attr:expr),* $(,)?]
) => {
let $output = $name {
- $($id: *$graph.insert_node($attr).id(),)*
+ $($id: $graph.insert_node($attr).id(),)*
};
};
@@ -73,17 +73,17 @@
@insert: edge
$graph:ident; $nodes:ident; $source:ident; $target:ident; $attr:expr
) => {
- *$graph.insert_edge($attr, &$nodes.$source, &$nodes.$target).id()
+ $graph.insert_edge($attr, $nodes.$source, $nodes.$target).id()
};
(
@insert: edge
$graph:ident; $nodes:ident; $source:ident; $target:ident; @{ $attr:expr }
) => {{
- let $source = $graph.node(&$nodes.$source).unwrap().weight();
- let $target = $graph.node(&$nodes.$target).unwrap().weight();
+ let $source = $graph.node($nodes.$source).unwrap().weight();
+ let $target = $graph.node($nodes.$target).unwrap().weight();
- *$graph.insert_edge($attr, &$nodes.$source, &$nodes.$target).id()
+ $graph.insert_edge($attr, $nodes.$source, $nodes.$target).id()
}};
(
