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()?