feat(algorithms): (WIP) enforce Copy `GraphId`
diff --git a/crates/algorithms/benches/shortest_paths/large.rs b/crates/algorithms/benches/shortest_paths/large.rs
index 6a0871c..18a31ef 100644
--- a/crates/algorithms/benches/shortest_paths/large.rs
+++ b/crates/algorithms/benches/shortest_paths/large.rs
@@ -167,7 +167,7 @@
let mut graph = DiDinoGraph::<Node, u128>::with_capacity(Some(nodes.len()), Some(edges.len()));
for (id, x, y) in nodes {
- let node_id = *graph.insert_node(Node { id, x, y }).id();
+ let node_id = graph.insert_node(Node { id, x, y }).id();
lookup.insert(id, node_id);
if source.is_none() {
@@ -179,7 +179,7 @@
let source = lookup[&source];
let target = lookup[&target];
- graph.insert_edge(weight, &source, &target);
+ graph.insert_edge(weight, source, target);
}
(source.expect("source available"), graph)
@@ -195,7 +195,7 @@
bench.iter(|| {
for distances in dijkstra
- .distance_from(&graph, &source)
+ .distance_from(&graph, source)
.expect("route available")
{
black_box(distances);
diff --git a/crates/algorithms/src/shortest_paths/astar/impl.rs b/crates/algorithms/src/shortest_paths/astar/impl.rs
index 026da15..17bf976 100644
--- a/crates/algorithms/src/shortest_paths/astar/impl.rs
+++ b/crates/algorithms/src/shortest_paths/astar/impl.rs
@@ -3,7 +3,7 @@
use error_stack::{Report, Result};
use numi::num::{identity::Zero, ops::AddRef};
use petgraph_core::{
- id::{AssociativeGraphId, AttributeMapper, FlaggableGraphId},
+ id::{AssociativeGraphId, AttributeMapper},
Graph, GraphStorage, Node,
};
@@ -23,7 +23,7 @@
pub(super) struct AStarImpl<'graph: 'parent, 'parent, S, E, H, C>
where
S: GraphStorage,
- S::NodeId: FlaggableGraphId<S> + AssociativeGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
E: GraphCost<S>,
E::Value: Ord,
{
@@ -46,7 +46,7 @@
impl<'graph: 'parent, 'parent, S, E, H, C> AStarImpl<'graph, 'parent, S, E, H, C>
where
S: GraphStorage,
- S::NodeId: FlaggableGraphId<S> + AssociativeGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
E: GraphCost<S>,
E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
@@ -59,8 +59,8 @@
heuristic: &'parent H,
connections: C,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ source: S::NodeId,
+ target: S::NodeId,
predecessor_mode: PredecessorMode,
) -> Result<Self, AStarError> {
diff --git a/crates/algorithms/src/shortest_paths/astar/mod.rs b/crates/algorithms/src/shortest_paths/astar/mod.rs
index 6f6ddfd..e21aa79 100644
--- a/crates/algorithms/src/shortest_paths/astar/mod.rs
+++ b/crates/algorithms/src/shortest_paths/astar/mod.rs
@@ -7,12 +7,12 @@
mod tests;
use alloc::vec::Vec;
-use core::{hash::Hash, marker::PhantomData};
+use core::marker::PhantomData;
use error_stack::Result;
use petgraph_core::{
edge::marker::{Directed, Undirected},
- id::{AssociativeGraphId, FlaggableGraphId},
+ id::AssociativeGraphId,
DirectedGraphStorage, Graph, GraphDirectionality, GraphStorage, Node,
};
@@ -144,13 +144,13 @@
fn call<'graph: 'this, 'this, S>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ source: S::NodeId,
+ target: S::NodeId,
intermediates: PredecessorMode,
) -> Result<AStarImpl<'graph, 'this, S, E, H, impl Connections<'graph, S> + 'this>, AStarError>
where
S: DirectedGraphStorage,
- S::NodeId: FlaggableGraphId<S> + AssociativeGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
E: GraphCost<S>,
E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
@@ -171,13 +171,13 @@
fn call<'graph: 'this, 'this, S>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ source: S::NodeId,
+ target: S::NodeId,
intermediates: PredecessorMode,
) -> Result<AStarImpl<'graph, 'this, S, E, H, impl Connections<'graph, S> + 'this>, AStarError>
where
S: GraphStorage,
- S::NodeId: FlaggableGraphId<S> + AssociativeGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
E: GraphCost<S>,
E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
@@ -200,7 +200,7 @@
impl<S, E, H> ShortestPath<S> for AStar<Undirected, E, H>
where
S: GraphStorage,
- S::NodeId: FlaggableGraphId<S> + AssociativeGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
E: GraphCost<S>,
E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
@@ -211,7 +211,7 @@
fn path_to<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- target: &'graph S::NodeId,
+ target: S::NodeId,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
let sources = graph.nodes().map(|node| node.id());
@@ -225,7 +225,7 @@
fn path_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
let targets = graph.nodes().map(|node| node.id());
@@ -239,8 +239,8 @@
fn path_between<'graph>(
&self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ source: S::NodeId,
+ target: S::NodeId,
) -> Option<Route<'graph, S, Self::Cost>> {
self.call(graph, source, target, PredecessorMode::Record)
.ok()?
@@ -269,7 +269,7 @@
impl<S, E, H> ShortestDistance<S> for AStar<Undirected, E, H>
where
S: GraphStorage,
- S::NodeId: FlaggableGraphId<S> + AssociativeGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
E: GraphCost<S>,
E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
@@ -280,7 +280,7 @@
fn distance_to<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- target: &'graph S::NodeId,
+ target: S::NodeId,
) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
let sources = graph.nodes().map(|node| node.id());
@@ -294,7 +294,7 @@
fn distance_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
let targets = graph.nodes().map(|node| node.id());
@@ -305,11 +305,11 @@
Ok(AStarImpl::find_all_direct(iter))
}
- fn distance_between<'graph>(
+ fn distance_between(
&self,
- graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ graph: &Graph<S>,
+ source: S::NodeId,
+ target: S::NodeId,
) -> Option<Cost<Self::Cost>> {
self.call(graph, source, target, PredecessorMode::Discard)
.ok()?
@@ -339,7 +339,7 @@
impl<S, E, H> ShortestPath<S> for AStar<Directed, E, H>
where
S: DirectedGraphStorage,
- S::NodeId: FlaggableGraphId<S> + AssociativeGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
E: GraphCost<S>,
E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
@@ -350,7 +350,7 @@
fn path_to<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- target: &'graph S::NodeId,
+ target: S::NodeId,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
let sources = graph.nodes().map(|node| node.id());
@@ -364,7 +364,7 @@
fn path_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
let targets = graph.nodes().map(|node| node.id());
@@ -378,8 +378,8 @@
fn path_between<'graph>(
&self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ source: S::NodeId,
+ target: S::NodeId,
) -> Option<Route<'graph, S, Self::Cost>> {
self.call(graph, source, target, PredecessorMode::Record)
.ok()?
@@ -408,7 +408,7 @@
impl<S, E, H> ShortestDistance<S> for AStar<Directed, E, H>
where
S: DirectedGraphStorage,
- S::NodeId: FlaggableGraphId<S> + AssociativeGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
E: GraphCost<S>,
E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
@@ -419,7 +419,7 @@
fn distance_to<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- target: &'graph S::NodeId,
+ target: S::NodeId,
) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
let sources = graph.nodes().map(|node| node.id());
@@ -433,7 +433,7 @@
fn distance_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
let targets = graph.nodes().map(|node| node.id());
@@ -444,11 +444,11 @@
Ok(AStarImpl::find_all_direct(iter))
}
- fn distance_between<'graph>(
+ fn distance_between(
&self,
- graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ graph: &Graph<S>,
+ source: S::NodeId,
+ target: S::NodeId,
) -> Option<Cost<Self::Cost>> {
self.call(graph, source, target, PredecessorMode::Discard)
.ok()?
diff --git a/crates/algorithms/src/shortest_paths/bellman_ford/impl.rs b/crates/algorithms/src/shortest_paths/bellman_ford/impl.rs
index 9e44259..128cbba 100644
--- a/crates/algorithms/src/shortest_paths/bellman_ford/impl.rs
+++ b/crates/algorithms/src/shortest_paths/bellman_ford/impl.rs
@@ -94,16 +94,16 @@
}
}
-struct Heuristic<'graph, S>
+struct Heuristic<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>,
+ recent_update: HashMap<S::NodeId, (S::NodeId, S::NodeId)>,
+ predecessor: HashMap<S::NodeId, S::NodeId>,
}
-impl<'graph, S> Heuristic<'graph, S>
+impl<S> Heuristic<S>
where
S: GraphStorage,
S::NodeId: Eq + Hash,
@@ -118,9 +118,9 @@
fn update(
&mut self,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
- ) -> core::result::Result<(), &'graph S::NodeId> {
+ source: S::NodeId,
+ target: S::NodeId,
+ ) -> core::result::Result<(), S::NodeId> {
if !self.enabled {
return Ok(());
}
@@ -134,14 +134,14 @@
// 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 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) {
+ if self.predecessor.get(&target) == Some(&source) {
+ if let Some(previous) = self.recent_update.get(&source) {
self.recent_update.insert(target, *previous);
}
} else {
@@ -168,8 +168,8 @@
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>,
+ distances: HashMap<S::NodeId, E::Value, FxBuildHasher>,
+ predecessors: HashMap<S::NodeId, Vec<Node<'graph, S>>, FxBuildHasher>,
}
impl<'graph: 'parent, 'parent, S, E, G> ShortestPathFasterImpl<'graph, 'parent, S, E, G>
@@ -186,7 +186,7 @@
edge_cost: &'parent E,
connections: G,
- source: &'graph S::NodeId,
+ source: S::NodeId,
predecessor_mode: PredecessorMode,
candidate_order: CandidateOrder,
@@ -226,10 +226,10 @@
/// 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> {
+ fn relax(&mut self) -> core::result::Result<(), 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 heuristic: Heuristic<S> = Heuristic::new(self.negative_cycle_heuristics);
let mut occurrences = HashMap::new();
let num_nodes = self.graph.num_nodes();
@@ -239,10 +239,10 @@
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 let Some(predecessors) = self.predecessors.get(&source.id()) {
if predecessors
.iter()
- .any(|node| queue.contains_node(node.id()))
+ .any(|node| queue.contains_node(&node.id()))
{
continue;
}
@@ -256,7 +256,7 @@
let alternative = priority.add_ref(self.edge_cost.cost(edge).as_ref());
- if let Some(distance) = self.distances.get(target.id()) {
+ if let Some(distance) = self.distances.get(&target.id()) {
if alternative == *distance {
self.predecessors
.entry(target.id())
@@ -325,8 +325,8 @@
Ok(())
}
- pub(crate) fn between(mut self, target: &S::NodeId) -> Option<Route<'graph, S, E::Value>> {
- let cost = self.distances.remove(target)?;
+ 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 {
diff --git a/crates/algorithms/src/shortest_paths/bellman_ford/mod.rs b/crates/algorithms/src/shortest_paths/bellman_ford/mod.rs
index ecc32b8..a1d4c1d 100644
--- a/crates/algorithms/src/shortest_paths/bellman_ford/mod.rs
+++ b/crates/algorithms/src/shortest_paths/bellman_ford/mod.rs
@@ -292,7 +292,7 @@
fn path_to<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- target: &'graph S::NodeId,
+ target: S::NodeId,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>>, Self::Error> {
let iter = self.path_from(graph, target)?;
@@ -302,7 +302,7 @@
fn path_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph <S as GraphStorage>::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>>, Self::Error> {
ShortestPathFasterImpl::new(
graph,
@@ -319,8 +319,8 @@
fn path_between<'graph>(
&self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ source: S::NodeId,
+ target: S::NodeId,
) -> Option<Route<'graph, S, Self::Cost>> {
ShortestPathFasterImpl::new(
graph,
@@ -361,7 +361,7 @@
fn distance_to<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- target: &'graph S::NodeId,
+ target: S::NodeId,
) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>>, Self::Error> {
let iter = self.distance_from(graph, target)?;
@@ -371,7 +371,7 @@
fn distance_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph <S as GraphStorage>::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
let iter = ShortestPathFasterImpl::new(
graph,
@@ -389,8 +389,8 @@
fn distance_between<'graph>(
&self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ source: S::NodeId,
+ target: S::NodeId,
) -> Option<Cost<Self::Cost>> {
ShortestPathFasterImpl::new(
graph,
@@ -432,7 +432,7 @@
fn path_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
ShortestPathFasterImpl::new(
graph,
@@ -449,8 +449,8 @@
fn path_between<'graph>(
&self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ source: S::NodeId,
+ target: S::NodeId,
) -> Option<Route<'graph, S, Self::Cost>> {
ShortestPathFasterImpl::new(
graph,
@@ -491,7 +491,7 @@
fn distance_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph <S as GraphStorage>::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>>, Self::Error> {
let iter = ShortestPathFasterImpl::new(
graph,
@@ -509,8 +509,8 @@
fn distance_between<'graph>(
&self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ source: S::NodeId,
+ target: S::NodeId,
) -> Option<Cost<Self::Cost>> {
ShortestPathFasterImpl::new(
graph,
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 2083b63..97783ff 100644
--- a/crates/algorithms/src/shortest_paths/common/queue/double_ended.rs
+++ b/crates/algorithms/src/shortest_paths/common/queue/double_ended.rs
@@ -7,10 +7,7 @@
use fxhash::FxBuildHasher;
use hashbrown::HashSet;
-use numi::{
- cast::{CastFrom, CastTo, TryCastFrom},
- num::identity::Zero,
-};
+use numi::{cast::TryCastFrom, num::identity::Zero};
use petgraph_core::{GraphStorage, Node};
pub(in crate::shortest_paths) struct DoubleEndedQueueItem<'graph, S, T>
@@ -45,7 +42,7 @@
S: GraphStorage,
{
queue: VecDeque<DoubleEndedQueueItem<'graph, S, T>>,
- active: HashSet<&'graph S::NodeId, FxBuildHasher>,
+ active: HashSet<S::NodeId, FxBuildHasher>,
}
impl<'graph, S, T> DoubleEndedQueue<'graph, S, T>
@@ -111,7 +108,7 @@
) -> Option<DoubleEndedQueueItem<'graph, S, T>> {
let value = self.queue.pop_front()?;
- self.active.remove(value.node.id());
+ self.active.remove(&value.node.id());
Some(value)
}
@@ -121,7 +118,7 @@
) -> Option<DoubleEndedQueueItem<'graph, S, T>> {
let value = self.queue.pop_back()?;
- self.active.remove(value.node.id());
+ self.active.remove(&value.node.id());
Some(value)
}
diff --git a/crates/algorithms/src/shortest_paths/common/queue/priority.rs b/crates/algorithms/src/shortest_paths/common/queue/priority.rs
index cd73810..53591dd 100644
--- a/crates/algorithms/src/shortest_paths/common/queue/priority.rs
+++ b/crates/algorithms/src/shortest_paths/common/queue/priority.rs
@@ -2,7 +2,7 @@
use core::cmp::Ordering;
use petgraph_core::{
- id::{BooleanMapper, FlaggableGraphId},
+ id::{AssociativeGraphId, BooleanMapper},
GraphStorage, Node,
};
@@ -55,25 +55,25 @@
pub(in crate::shortest_paths) struct PriorityQueue<'a, S, T>
where
S: GraphStorage,
- S::NodeId: FlaggableGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
T: Ord,
{
heap: BinaryHeap<PriorityQueueItem<'a, S, T>>,
- flags: <S::NodeId as FlaggableGraphId<S>>::Store<'a>,
+ flags: <S::NodeId as AssociativeGraphId<S>>::BooleanMapper<'a>,
}
impl<'a, S, T> PriorityQueue<'a, S, T>
where
S: GraphStorage,
- S::NodeId: FlaggableGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
T: Ord,
{
#[inline]
pub(in crate::shortest_paths) fn new(storage: &'a S) -> Self {
Self {
heap: BinaryHeap::new(),
- flags: <S::NodeId as FlaggableGraphId<S>>::flag_store(storage),
+ flags: <S::NodeId as AssociativeGraphId<S>>::boolean_mapper(storage),
}
}
@@ -81,12 +81,12 @@
self.heap.push(PriorityQueueItem { node, priority });
}
- pub(in crate::shortest_paths) fn visit(&mut self, id: &'a S::NodeId) {
+ pub(in crate::shortest_paths) fn visit(&mut self, id: S::NodeId) {
self.flags.set(id, true);
}
#[inline]
- pub(in crate::shortest_paths) fn has_been_visited(&self, id: &'a S::NodeId) -> bool {
+ pub(in crate::shortest_paths) fn has_been_visited(&self, id: S::NodeId) -> bool {
self.flags.index(id)
}
diff --git a/crates/algorithms/src/shortest_paths/common/transit.rs b/crates/algorithms/src/shortest_paths/common/transit.rs
index 438c823..cfed6e0 100644
--- a/crates/algorithms/src/shortest_paths/common/transit.rs
+++ b/crates/algorithms/src/shortest_paths/common/transit.rs
@@ -16,10 +16,13 @@
Record,
}
-pub(in crate::shortest_paths) fn reconstruct_path_to<'a, S>(
- predecessors: &<S::NodeId as AssociativeGraphId<S>>::AttributeMapper<'a, Option<Node<'a, S>>>,
- target: &'a S::NodeId,
-) -> Vec<Node<'a, S>>
+pub(in crate::shortest_paths) fn reconstruct_path_to<'graph, S>(
+ predecessors: &<S::NodeId as AssociativeGraphId<S>>::AttributeMapper<
+ 'graph,
+ Option<Node<'graph, S>>,
+ >,
+ target: S::NodeId,
+) -> Vec<Node<'graph, S>>
where
S: GraphStorage,
S::NodeId: AssociativeGraphId<S>,
@@ -54,8 +57,8 @@
///
/// 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,
+ predecessors: &'a HashMap<S::NodeId, Vec<Node<'graph, S>>, H>,
+ source: S::NodeId,
target: Node<'graph, S>,
) -> impl Iterator<Item = Vec<Node<'graph, S>>> + 'a
where
@@ -92,9 +95,9 @@
return Some(path);
}
- if predecessors[node.id()].len() > index {
+ if predecessors[&node.id()].len() > index {
stack[top].1 = index + 1;
- let next = predecessors[node.id()][index];
+ let next = predecessors[&node.id()][index];
if !seen.insert(next.id()) {
// value already seen
continue;
diff --git a/crates/algorithms/src/shortest_paths/dijkstra/iter.rs b/crates/algorithms/src/shortest_paths/dijkstra/iter.rs
index 020efe5..4299d90 100644
--- a/crates/algorithms/src/shortest_paths/dijkstra/iter.rs
+++ b/crates/algorithms/src/shortest_paths/dijkstra/iter.rs
@@ -4,7 +4,7 @@
use error_stack::{Report, Result};
use numi::num::{identity::Zero, ops::AddRef};
use petgraph_core::{
- id::{AssociativeGraphId, AttributeMapper, FlaggableGraphId},
+ id::{AssociativeGraphId, AttributeMapper},
Graph, GraphStorage, Node,
};
@@ -23,7 +23,7 @@
pub(super) struct DijkstraIter<'graph: 'parent, 'parent, S, E, G>
where
S: GraphStorage,
- S::NodeId: FlaggableGraphId<S> + AssociativeGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
E: GraphCost<S>,
E::Value: DijkstraMeasure,
{
@@ -50,7 +50,7 @@
impl<'graph: 'parent, 'parent, S, E, G> DijkstraIter<'graph, 'parent, S, E, G>
where
S: GraphStorage,
- S::NodeId: FlaggableGraphId<S> + AssociativeGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
E: GraphCost<S>,
E::Value: DijkstraMeasure,
G: Connections<'graph, S>,
@@ -61,7 +61,7 @@
edge_cost: &'parent E,
connections: G,
- source: &'graph S::NodeId,
+ source: S::NodeId,
predecessor_mode: PredecessorMode,
) -> Result<Self, DijkstraError> {
@@ -99,7 +99,7 @@
impl<'graph: 'parent, 'parent, S, E, G> Iterator for DijkstraIter<'graph, 'parent, S, E, G>
where
S: GraphStorage,
- S::NodeId: FlaggableGraphId<S> + AssociativeGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
E: GraphCost<S>,
E::Value: DijkstraMeasure,
G: Connections<'graph, S>,
diff --git a/crates/algorithms/src/shortest_paths/dijkstra/mod.rs b/crates/algorithms/src/shortest_paths/dijkstra/mod.rs
index 2d7cd5f..14ba3d7 100644
--- a/crates/algorithms/src/shortest_paths/dijkstra/mod.rs
+++ b/crates/algorithms/src/shortest_paths/dijkstra/mod.rs
@@ -11,7 +11,7 @@
use error_stack::Result;
use petgraph_core::{
edge::marker::{Directed, Undirected},
- id::{AssociativeGraphId, FlaggableGraphId},
+ id::AssociativeGraphId,
DirectedGraphStorage, Graph, GraphDirectionality, GraphStorage, Node,
};
@@ -175,7 +175,7 @@
impl<S, E> ShortestPath<S> for Dijkstra<Undirected, E>
where
S: GraphStorage,
- S::NodeId: FlaggableGraphId<S> + AssociativeGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
E: GraphCost<S>,
E::Value: DijkstraMeasure,
{
@@ -185,7 +185,7 @@
fn path_to<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- target: &'graph S::NodeId,
+ target: S::NodeId,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>>, Self::Error> {
let iter = self.path_from(graph, target)?;
@@ -195,7 +195,7 @@
fn path_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
DijkstraIter::new(
graph,
@@ -222,7 +222,7 @@
impl<S, E> ShortestPath<S> for Dijkstra<Directed, E>
where
S: DirectedGraphStorage,
- S::NodeId: FlaggableGraphId<S> + AssociativeGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
E: GraphCost<S>,
E::Value: DijkstraMeasure,
{
@@ -232,7 +232,7 @@
fn path_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
DijkstraIter::new(
graph,
@@ -259,7 +259,7 @@
impl<S, E> ShortestDistance<S> for Dijkstra<Undirected, E>
where
S: GraphStorage,
- S::NodeId: FlaggableGraphId<S> + AssociativeGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
E: GraphCost<S>,
E::Value: DijkstraMeasure,
{
@@ -269,7 +269,7 @@
fn distance_to<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- target: &'graph S::NodeId,
+ target: S::NodeId,
) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>>, Self::Error> {
let iter = self.distance_from(graph, target)?;
@@ -279,7 +279,7 @@
fn distance_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph <S as GraphStorage>::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
let iter = DijkstraIter::new(
graph,
@@ -308,7 +308,7 @@
impl<S, E> ShortestDistance<S> for Dijkstra<Directed, E>
where
S: DirectedGraphStorage,
- S::NodeId: FlaggableGraphId<S> + AssociativeGraphId<S>,
+ S::NodeId: AssociativeGraphId<S>,
E: GraphCost<S>,
E::Value: DijkstraMeasure,
{
@@ -318,7 +318,7 @@
fn distance_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph <S as GraphStorage>::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>>, Self::Error> {
let iter = DijkstraIter::new(
graph,
diff --git a/crates/algorithms/src/shortest_paths/floyd_warshall/impl.rs b/crates/algorithms/src/shortest_paths/floyd_warshall/impl.rs
index 3deb5a9..72082d3 100644
--- a/crates/algorithms/src/shortest_paths/floyd_warshall/impl.rs
+++ b/crates/algorithms/src/shortest_paths/floyd_warshall/impl.rs
@@ -19,8 +19,8 @@
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,
+ u: S::NodeId,
+ v: S::NodeId,
value: Option<Moo<'this, E::Value>>,
) where
S: GraphStorage,
@@ -33,8 +33,8 @@
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,
+ u: S::NodeId,
+ v: S::NodeId,
value: Option<Moo<'this, E::Value>>,
) where
S: GraphStorage,
@@ -49,10 +49,10 @@
}
}
-pub(super) fn init_directed_edge_predecessor<'graph, S>(
- matrix: &mut SlotMatrix<'graph, S, &'graph S::NodeId>,
- u: &'graph S::NodeId,
- v: &'graph S::NodeId,
+pub(super) fn init_directed_edge_predecessor<S>(
+ matrix: &mut SlotMatrix<S, S::NodeId>,
+ u: S::NodeId,
+ v: S::NodeId,
) where
S: GraphStorage,
S::NodeId: LinearGraphId<S> + Clone,
@@ -60,10 +60,10 @@
matrix.set(u, v, Some(u));
}
-pub(super) fn init_undirected_edge_predecessor<'graph, S>(
- matrix: &mut SlotMatrix<'graph, S, &'graph S::NodeId>,
- u: &'graph S::NodeId,
- v: &'graph S::NodeId,
+pub(super) fn init_undirected_edge_predecessor<S>(
+ matrix: &mut SlotMatrix<S, S::NodeId>,
+ u: S::NodeId,
+ v: S::NodeId,
) where
S: GraphStorage,
S::NodeId: LinearGraphId<S> + Clone,
@@ -72,11 +72,11 @@
matrix.set(v, u, Some(v));
}
-fn reconstruct_path<'a, S>(
- matrix: &SlotMatrix<'_, S, &'a S::NodeId>,
- source: &S::NodeId,
- target: &'a S::NodeId,
-) -> Vec<&'a S::NodeId>
+fn reconstruct_path<S>(
+ matrix: &SlotMatrix<'_, S, S::NodeId>,
+ source: S::NodeId,
+ target: S::NodeId,
+) -> Vec<S::NodeId>
where
S: GraphStorage,
S::NodeId: LinearGraphId<S> + Clone,
@@ -113,15 +113,15 @@
}
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,
+ <S as GraphStorage>::NodeId,
+ <S as GraphStorage>::NodeId,
Option<Moo<'this, <E as GraphCost<S>>::Value>>,
);
type InitEdgePredecessorFn<'graph, S> = fn(
- &mut SlotMatrix<'graph, S, &'graph <S as GraphStorage>::NodeId>,
- &'graph <S as GraphStorage>::NodeId,
- &'graph <S as GraphStorage>::NodeId,
+ &mut SlotMatrix<'graph, S, <S as GraphStorage>::NodeId>,
+ <S as GraphStorage>::NodeId,
+ <S as GraphStorage>::NodeId,
);
pub(super) struct FloydWarshallImpl<'graph: 'parent, 'parent, S, E>
@@ -139,7 +139,7 @@
init_edge_predecessor: InitEdgePredecessorFn<'graph, S>,
distances: SlotMatrix<'graph, S, Moo<'parent, E::Value>>,
- predecessors: SlotMatrix<'graph, S, &'graph S::NodeId>,
+ predecessors: SlotMatrix<'graph, S, S::NodeId>,
}
// TODO: relax `NodeId` requirements or make `Send + Sync + 'static` across the board
@@ -264,7 +264,7 @@
let mut result: Result<(), FloydWarshallError> = Ok(());
for index in negative_cycles {
- let Some(node) = self.distances.resolve(index).map(Moo::into_owned) else {
+ let Some(node) = self.distances.resolve(index) else {
continue;
};
@@ -318,8 +318,8 @@
pub(super) fn pick(
self,
- source: &S::NodeId,
- target: &S::NodeId,
+ source: S::NodeId,
+ target: S::NodeId,
) -> Option<Route<'graph, S, E::Value>> {
let Self {
graph,
diff --git a/crates/algorithms/src/shortest_paths/floyd_warshall/matrix.rs b/crates/algorithms/src/shortest_paths/floyd_warshall/matrix.rs
index 83e86e7..5915c2e 100644
--- a/crates/algorithms/src/shortest_paths/floyd_warshall/matrix.rs
+++ b/crates/algorithms/src/shortest_paths/floyd_warshall/matrix.rs
@@ -23,14 +23,14 @@
}
}
- fn get(&self, from: &T) -> Option<usize> {
+ fn get(&self, from: T) -> Option<usize> {
match self {
Self::Store(mapper) => mapper.get(from),
Self::Discard => None,
}
}
- fn reverse(&self, to: usize) -> Option<Moo<T>> {
+ fn reverse(&self, to: usize) -> Option<T> {
match self {
Self::Store(mapper) => mapper.reverse(to),
Self::Discard => None,
@@ -81,7 +81,7 @@
}
}
- pub(crate) fn set(&mut self, source: &S::NodeId, target: &S::NodeId, value: Option<T>) {
+ pub(crate) fn set(&mut self, source: S::NodeId, target: S::NodeId, value: Option<T>) {
if matches!(self.mapper, MatrixIndexMapper::Discard) {
// this should never happen, even if it does, we don't want to panic here (map call)
// so we simply return.
@@ -106,14 +106,14 @@
///
/// See the contract described on the [`IndexMapper`] for more information about the
/// `map/lookup` contract.
- pub(crate) fn get(&self, source: &S::NodeId, target: &S::NodeId) -> Option<&T> {
+ pub(crate) fn get(&self, source: S::NodeId, target: S::NodeId) -> Option<&T> {
let source = self.mapper.get(source)?;
let target = self.mapper.get(target)?;
self.matrix[source * self.length + target].as_ref()
}
- pub(crate) fn resolve(&self, index: usize) -> Option<Moo<S::NodeId>> {
+ pub(crate) fn resolve(&self, index: usize) -> Option<S::NodeId> {
self.mapper.reverse(index)
}
}
diff --git a/crates/algorithms/src/shortest_paths/floyd_warshall/mod.rs b/crates/algorithms/src/shortest_paths/floyd_warshall/mod.rs
index 36f662e..2049e2b 100644
--- a/crates/algorithms/src/shortest_paths/floyd_warshall/mod.rs
+++ b/crates/algorithms/src/shortest_paths/floyd_warshall/mod.rs
@@ -186,7 +186,7 @@
fn path_to<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- target: &'graph S::NodeId,
+ target: S::NodeId,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
FloydWarshallImpl::new(
graph,
@@ -201,7 +201,7 @@
fn path_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
FloydWarshallImpl::new(
graph,
@@ -216,8 +216,8 @@
fn path_between<'graph>(
&self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ source: S::NodeId,
+ target: S::NodeId,
) -> Option<Route<'graph, S, Self::Cost>> {
let r#impl = FloydWarshallImpl::new(
graph,
@@ -259,7 +259,7 @@
fn distance_to<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- target: &'graph S::NodeId,
+ target: S::NodeId,
) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
let iter = FloydWarshallImpl::new(
graph,
@@ -277,7 +277,7 @@
fn distance_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
let iter = FloydWarshallImpl::new(
graph,
@@ -292,11 +292,11 @@
.map(From::from))
}
- fn distance_between<'graph>(
+ fn distance_between(
&self,
- graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ graph: &Graph<S>,
+ source: S::NodeId,
+ target: S::NodeId,
) -> Option<Cost<Self::Cost>> {
let iter = FloydWarshallImpl::new(
graph,
@@ -339,7 +339,7 @@
fn path_to<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- target: &'graph S::NodeId,
+ target: S::NodeId,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
FloydWarshallImpl::new(
graph,
@@ -354,7 +354,7 @@
fn path_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
FloydWarshallImpl::new(
graph,
@@ -370,8 +370,8 @@
fn path_between<'graph>(
&self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ source: S::NodeId,
+ target: S::NodeId,
) -> Option<Route<'graph, S, Self::Cost>> {
let r#impl = FloydWarshallImpl::new(
graph,
@@ -413,7 +413,7 @@
fn distance_to<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- target: &'graph S::NodeId,
+ target: S::NodeId,
) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
let iter = FloydWarshallImpl::new(
graph,
@@ -431,7 +431,7 @@
fn distance_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
let iter = FloydWarshallImpl::new(
graph,
@@ -446,11 +446,11 @@
.map(From::from))
}
- fn distance_between<'graph>(
+ fn distance_between(
&self,
- graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ graph: &Graph<S>,
+ source: S::NodeId,
+ target: S::NodeId,
) -> Option<Cost<Self::Cost>> {
let iter = FloydWarshallImpl::new(
graph,
diff --git a/crates/algorithms/src/shortest_paths/mod.rs b/crates/algorithms/src/shortest_paths/mod.rs
index 8e7f26d..5f8f095 100644
--- a/crates/algorithms/src/shortest_paths/mod.rs
+++ b/crates/algorithms/src/shortest_paths/mod.rs
@@ -128,7 +128,7 @@
fn path_to<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- target: &'graph S::NodeId,
+ target: S::NodeId,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
let iter = self.every_path(graph)?;
@@ -143,7 +143,7 @@
fn path_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = Route<'graph, S, Self::Cost>> + 'this, Self::Error> {
let iter = self.every_path(graph)?;
@@ -156,8 +156,8 @@
fn path_between<'graph>(
&self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ source: S::NodeId,
+ target: S::NodeId,
) -> Option<Route<'graph, S, Self::Cost>> {
self.path_from(graph, source)
.ok()?
@@ -207,7 +207,7 @@
fn distance_to<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- target: &'graph S::NodeId,
+ target: S::NodeId,
) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
let iter = self.every_distance(graph)?;
@@ -223,7 +223,7 @@
fn distance_from<'graph: 'this, 'this>(
&'this self,
graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
+ source: S::NodeId,
) -> Result<impl Iterator<Item = DirectRoute<'graph, S, Self::Cost>> + 'this, Self::Error> {
let iter = self.every_distance(graph)?;
@@ -233,11 +233,11 @@
/// 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>(
+ fn distance_between(
&self,
- graph: &'graph Graph<S>,
- source: &'graph S::NodeId,
- target: &'graph S::NodeId,
+ graph: &Graph<S>,
+ source: S::NodeId,
+ target: S::NodeId,
) -> Option<Cost<Self::Cost>> {
self.every_distance(graph)
.ok()?
