Improve overall speed. (#603)

diff --git a/.gitattributes b/.gitattributes
index d02eb85..8e44e96 100644
--- a/.gitattributes
+++ b/.gitattributes
@@ -57,3 +57,5 @@
 crates/algorithms/tests/cases/shortest_path/grid_swirl_00.out filter=lfs diff=lfs merge=lfs -text
 crates/algorithms/tests/cases/shortest_path/max_dense_zero_00.out filter=lfs diff=lfs merge=lfs -text
 crates/algorithms/tests/cases/shortest_path/wrong_dijkstra_killer_00.in filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/benches/cases/shortest_path/USA-road-d.FLA.co filter=lfs diff=lfs merge=lfs -text
+crates/algorithms/benches/cases/shortest_path/USA-road-d.FLA.gr filter=lfs diff=lfs merge=lfs -text
diff --git a/crates/algorithms/benches/cases/shortest_path/USA-road-d.FLA.co b/crates/algorithms/benches/cases/shortest_path/USA-road-d.FLA.co
new file mode 100644
index 0000000..fe22d72
--- /dev/null
+++ b/crates/algorithms/benches/cases/shortest_path/USA-road-d.FLA.co
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:e9ef8ff417f2e0b19faf51918b87f7e77d99269fa95726d105fdf47cd893e90d
+size 29930001
diff --git a/crates/algorithms/benches/cases/shortest_path/USA-road-d.FLA.gr b/crates/algorithms/benches/cases/shortest_path/USA-road-d.FLA.gr
new file mode 100644
index 0000000..00d2764
--- /dev/null
+++ b/crates/algorithms/benches/cases/shortest_path/USA-road-d.FLA.gr
@@ -0,0 +1,3 @@
+version https://git-lfs.github.com/spec/v1
+oid sha256:47a3e851dea2bf27d6c939542e569fa9b5e6f2c8f11e8af3187d87c28435a85d
+size 55645328
diff --git a/crates/algorithms/benches/shortest_paths/large.rs b/crates/algorithms/benches/shortest_paths/large.rs
index d21a814..18a31ef 100644
--- a/crates/algorithms/benches/shortest_paths/large.rs
+++ b/crates/algorithms/benches/shortest_paths/large.rs
@@ -15,46 +15,53 @@
     static WORKSPACES: Mutex<BTreeMap<String, Arc<Path>>> = Mutex::new(BTreeMap::new());
 
     let manifest_dir = env!("CARGO_MANIFEST_DIR");
-    let mut workspaces = WORKSPACES.lock().unwrap();
+    let mut workspaces = WORKSPACES.lock().expect("lock workspaces");
 
     if let Some(path) = workspaces.get(manifest_dir) {
         return Arc::clone(path);
     }
 
-    let output = process::Command::new(
-        env::var("CARGO")
-            .ok()
-            .unwrap_or_else(|| "cargo".to_string()),
-    )
-    .arg("metadata")
-    .arg("--format-version=1")
-    .arg("--no-deps")
-    .current_dir(manifest_dir)
-    .output()
-    .unwrap();
+    let output =
+        process::Command::new(env::var("CARGO").ok().unwrap_or_else(|| "cargo".to_owned()))
+            .arg("metadata")
+            .arg("--format-version=1")
+            .arg("--no-deps")
+            .current_dir(manifest_dir)
+            .output()
+            .expect("execute `cargo metadata`");
 
-    let manifest = serde_json::from_slice::<serde_json::Value>(&output.stdout).unwrap();
+    let manifest = serde_json::from_slice::<serde_json::Value>(&output.stdout).expect("parse json");
 
-    let root = PathBuf::from(manifest["workspace_root"].as_str().unwrap());
+    let root = PathBuf::from(manifest["workspace_root"].as_str().expect("workspace root"));
     let root = Arc::from(root);
 
-    workspaces.insert(manifest_dir.to_string(), Arc::clone(&root));
+    workspaces.insert(manifest_dir.to_owned(), Arc::clone(&root));
     root
 }
 
 fn input(file: &str) -> Arc<Path> {
     let workspace = get_cargo_workspace();
-    let path = workspace.join("crates/algorithms/benches/input").join(file);
+    let path = workspace
+        .join("crates/algorithms/benches/cases/shortest_path")
+        .join(file);
 
-    if !path.exists() {
-        panic!("{} does not exist", path.display());
-    }
+    assert!(path.exists(), "{} does not exist", path.display());
 
     Arc::from(path)
 }
 
+macro_rules! next {
+    ($iter:ident as $ty:ty) => {
+        $iter
+            .next()
+            .expect("expected token")
+            .parse::<$ty>()
+            .expect(concat!("is ", stringify!($ty)))
+    };
+}
+
 fn parse_coordinate_file(path: &Path) -> Vec<(usize, i128, i128)> {
-    let contents = fs::read_to_string(path).unwrap();
+    let contents = fs::read_to_string(path).expect("able to read file");
 
     let mut output = vec![];
     let mut amount_of_lines = None;
@@ -71,7 +78,7 @@
                 assert_eq!(iter.next(), Some("sp"));
                 assert_eq!(iter.next(), Some("co"));
 
-                amount_of_lines = Some(iter.next().unwrap().parse::<usize>().unwrap());
+                amount_of_lines = Some(next!(iter as usize));
 
                 assert_eq!(iter.next(), None);
             }
@@ -79,16 +86,16 @@
             b'v' if amount_of_lines.is_some() => {
                 let mut iter = line.split_whitespace();
                 assert_eq!(iter.next(), Some("v"));
-                let id = iter.next().unwrap().parse::<usize>().unwrap();
-                let x = iter.next().unwrap().parse::<i128>().unwrap();
-                let y = iter.next().unwrap().parse::<i128>().unwrap();
+                let id = next!(iter as usize);
+                let x = next!(iter as i128);
+                let y = next!(iter as i128);
 
                 assert_eq!(iter.next(), None);
 
                 output.push((id, x, y));
 
                 if let Some(amount_of_lines) = &mut amount_of_lines {
-                    *amount_of_lines = amount_of_lines.checked_sub(1).expect("too many lines")
+                    *amount_of_lines = amount_of_lines.checked_sub(1).expect("too many lines");
                 }
             }
             b'v' => panic!("vertex lines before problem statement"),
@@ -100,7 +107,7 @@
 }
 
 fn parse_graph_file(path: &Path) -> Vec<(usize, usize, u128)> {
-    let mut contents = fs::read_to_string(path).unwrap();
+    let contents = fs::read_to_string(path).expect("able to read file");
 
     let mut output = vec![];
     let mut amount_of_lines = None;
@@ -114,8 +121,8 @@
                 let mut iter = line.split_whitespace();
                 assert_eq!(iter.next(), Some("p"));
                 assert_eq!(iter.next(), Some("sp"));
-                let _number_of_nodes = iter.next().unwrap().parse::<usize>().unwrap();
-                let number_of_edges = iter.next().unwrap().parse::<usize>().unwrap();
+                let _number_of_nodes = next!(iter as usize);
+                let number_of_edges = next!(iter as usize);
                 amount_of_lines = Some(number_of_edges);
 
                 assert_eq!(iter.next(), None);
@@ -124,16 +131,16 @@
             b'a' if amount_of_lines.is_some() => {
                 let mut iter = line.split_whitespace();
                 assert_eq!(iter.next(), Some("a"));
-                let source = iter.next().unwrap().parse::<usize>().unwrap();
-                let target = iter.next().unwrap().parse::<usize>().unwrap();
-                let weight = iter.next().unwrap().parse::<u128>().unwrap();
+                let source = next!(iter as usize);
+                let target = next!(iter as usize);
+                let weight = next!(iter as u128);
 
                 assert_eq!(iter.next(), None);
 
                 output.push((source, target, weight));
 
                 if let Some(amount_of_lines) = &mut amount_of_lines {
-                    *amount_of_lines = amount_of_lines.checked_sub(1).expect("too many lines")
+                    *amount_of_lines = amount_of_lines.checked_sub(1).expect("too many lines");
                 }
             }
             b'a' => panic!("edge lines before problem statement"),
@@ -160,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() {
@@ -172,15 +179,14 @@
         let source = lookup[&source];
         let target = lookup[&target];
 
-        graph.insert_edge(weight, &source, &target);
+        graph.insert_edge(weight, source, target);
     }
 
-    (source.unwrap(), graph)
+    (source.expect("source available"), graph)
 }
 
 fn dijkstra(criterion: &mut Criterion) {
     criterion.bench_with_input(
-        // BenchmarkId::from_parameter("dimacs9/florida"),
         BenchmarkId::new("dimacs9/florida", "dijkstra"),
         &"USA-road-d.FLA",
         |bench, &filename| {
@@ -188,7 +194,10 @@
             let dijkstra = Dijkstra::directed();
 
             bench.iter(|| {
-                for distances in dijkstra.distance_from(&graph, &source).unwrap() {
+                for distances in dijkstra
+                    .distance_from(&graph, source)
+                    .expect("route available")
+                {
                     black_box(distances);
                 }
             });
diff --git a/crates/algorithms/src/polyfill.rs b/crates/algorithms/src/polyfill.rs
index 2000f5a..4bacb86 100644
--- a/crates/algorithms/src/polyfill.rs
+++ b/crates/algorithms/src/polyfill.rs
@@ -1,6 +1,8 @@
 //! Implementation of traits that are not yet available in error-stack and friends, but are
 //! tremendously useful.
 
+use alloc::vec::Vec;
+
 use error_stack::Result;
 
 pub(crate) trait Container<T> {
@@ -12,11 +14,11 @@
 
 impl<T> Container<T> for Vec<T> {
     fn new() -> Self {
-        Vec::new()
+        Self::new()
     }
 
     fn with_capacity(capacity: usize) -> Self {
-        Vec::with_capacity(capacity)
+        Self::with_capacity(capacity)
     }
 
     fn extend_one(&mut self, item: T) {
@@ -46,11 +48,7 @@
     {
         let (_, max) = self.size_hint();
 
-        let state = if let Some(max) = max {
-            F::with_capacity(max)
-        } else {
-            F::new()
-        };
+        let state = max.map_or_else(F::new, |max| F::with_capacity(max));
 
         let mut state: Result<F, Self::Context> = Ok(state);
 
diff --git a/crates/algorithms/src/shortest_paths/astar/impl.rs b/crates/algorithms/src/shortest_paths/astar/impl.rs
index 33c5e13..a8d1869 100644
--- a/crates/algorithms/src/shortest_paths/astar/impl.rs
+++ b/crates/algorithms/src/shortest_paths/astar/impl.rs
@@ -1,31 +1,32 @@
 use alloc::vec::Vec;
-use core::hash::Hash;
 
 use error_stack::{Report, Result};
-use fxhash::FxBuildHasher;
-use hashbrown::HashMap;
 use numi::num::{identity::Zero, ops::AddRef};
-use petgraph_core::{Graph, GraphStorage, Node};
+use petgraph_core::{
+    id::{AssociativeGraphId, AttributeMapper},
+    Graph, GraphStorage, Node,
+};
 
 use crate::shortest_paths::{
     astar::{error::AStarError, heuristic::GraphHeuristic, AStarMeasure},
     common::{
         connections::Connections,
         cost::{Cost, GraphCost},
-        queue::priority::PriorityQueue,
+        queue::priority::{PriorityQueue, PriorityQueueItem},
         route::{DirectRoute, Route},
         transit::{reconstruct_path_to, PredecessorMode},
     },
     Path,
 };
 
-// The graph must outlive the A* instance
 pub(super) struct AStarImpl<'graph: 'parent, 'parent, S, E, H, C>
 where
     S: GraphStorage,
+    S::NodeId: AssociativeGraphId<S>,
     E: GraphCost<S>,
     E::Value: Ord,
 {
+    graph: &'graph Graph<S>,
     queue: PriorityQueue<'graph, S, E::Value>,
 
     edge_cost: &'parent E,
@@ -37,14 +38,15 @@
 
     predecessor_mode: PredecessorMode,
 
-    distances: HashMap<&'graph S::NodeId, E::Value, FxBuildHasher>,
-    predecessors: HashMap<&'graph S::NodeId, Option<Node<'graph, S>>, FxBuildHasher>,
+    distances: <S::NodeId as AssociativeGraphId<S>>::AttributeMapper<'graph, E::Value>,
+    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>
 where
     S: GraphStorage,
-    S::NodeId: Eq + Hash,
+    S::NodeId: AssociativeGraphId<S>,
     E: GraphCost<S>,
     E::Value: AStarMeasure,
     H: GraphHeuristic<S, Value = E::Value>,
@@ -57,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> {
@@ -70,21 +72,26 @@
             .node(target)
             .ok_or_else(|| Report::new(AStarError::NodeNotFound))?;
 
-        let mut queue = PriorityQueue::new();
-        queue.push(
-            source_node,
-            heuristic.estimate(source_node, target_node).into_owned(),
-        );
+        let estimate = heuristic.estimate(source_node, target_node);
 
-        let mut distances = HashMap::with_hasher(FxBuildHasher::default());
-        distances.insert(source, E::Value::zero());
+        let mut queue = PriorityQueue::new(graph.storage());
+        queue.check_admissibility = false;
 
-        let mut predecessors = HashMap::with_hasher(FxBuildHasher::default());
+        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 {
-            predecessors.insert(source, None);
+            predecessors.set(source, None);
         }
 
         Ok(Self {
+            graph,
             queue,
 
             edge_cost,
@@ -97,34 +104,52 @@
             predecessor_mode,
 
             distances,
+            estimates,
             predecessors,
         })
     }
 
     pub(super) fn find(mut self) -> Option<Route<'graph, S, E::Value>> {
-        while let Some(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[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 alternative =
-                    self.distances[node.id()].add_ref(self.edge_cost.cost(edge).as_ref());
+                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 {
@@ -134,13 +159,13 @@
 
                 let guess =
                     alternative.add_ref(self.heuristic.estimate(neighbour, self.target).as_ref());
-                self.distances.insert(neighbour.id(), alternative);
+                self.distances.set(neighbour.id(), alternative);
 
                 if self.predecessor_mode == PredecessorMode::Record {
-                    self.predecessors.insert(neighbour.id(), Some(node));
+                    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 a15e300..4109c44 100644
--- a/crates/algorithms/src/shortest_paths/astar/mod.rs
+++ b/crates/algorithms/src/shortest_paths/astar/mod.rs
@@ -7,11 +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,
     DirectedGraphStorage, Graph, GraphDirectionality, GraphStorage, Node,
 };
 
@@ -19,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.
 ///
@@ -143,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: Eq + Hash,
+        S::NodeId: AssociativeGraphId<S>,
         E: GraphCost<S>,
         E::Value: AStarMeasure,
         H: GraphHeuristic<S, Value = E::Value>,
@@ -158,7 +159,7 @@
             graph,
             &self.edge_cost,
             &self.heuristic,
-            outgoing_connections as fn(&Node<'graph, S>) -> _,
+            NodeConnections::directed(graph.storage()),
             source,
             target,
             intermediates,
@@ -170,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: Eq + Hash,
+        S::NodeId: AssociativeGraphId<S>,
         E: GraphCost<S>,
         E::Value: AStarMeasure,
         H: GraphHeuristic<S, Value = E::Value>,
@@ -185,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,
@@ -199,7 +200,7 @@
 impl<S, E, H> ShortestPath<S> for AStar<Undirected, E, H>
 where
     S: GraphStorage,
-    S::NodeId: Eq + Hash,
+    S::NodeId: AssociativeGraphId<S>,
     E: GraphCost<S>,
     E::Value: AStarMeasure,
     H: GraphHeuristic<S, Value = E::Value>,
@@ -210,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());
 
@@ -224,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());
 
@@ -238,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()?
@@ -268,7 +269,7 @@
 impl<S, E, H> ShortestDistance<S> for AStar<Undirected, E, H>
 where
     S: GraphStorage,
-    S::NodeId: Eq + Hash,
+    S::NodeId: AssociativeGraphId<S>,
     E: GraphCost<S>,
     E::Value: AStarMeasure,
     H: GraphHeuristic<S, Value = E::Value>,
@@ -279,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());
 
@@ -293,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());
 
@@ -304,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()?
@@ -338,7 +339,7 @@
 impl<S, E, H> ShortestPath<S> for AStar<Directed, E, H>
 where
     S: DirectedGraphStorage,
-    S::NodeId: Eq + Hash,
+    S::NodeId: AssociativeGraphId<S>,
     E: GraphCost<S>,
     E::Value: AStarMeasure,
     H: GraphHeuristic<S, Value = E::Value>,
@@ -349,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());
 
@@ -363,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());
 
@@ -377,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()?
@@ -407,7 +408,7 @@
 impl<S, E, H> ShortestDistance<S> for AStar<Directed, E, H>
 where
     S: DirectedGraphStorage,
-    S::NodeId: Eq + Hash,
+    S::NodeId: AssociativeGraphId<S>,
     E: GraphCost<S>,
     E::Value: AStarMeasure,
     H: GraphHeuristic<S, Value = E::Value>,
@@ -418,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());
 
@@ -432,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());
 
@@ -443,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/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 9e44259..f0b9963 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,16 +239,16 @@
             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;
                 }
             }
 
-            let edges = self.connections.connections(&source);
+            let edges = self.connections.connections(source.id());
 
             for edge in edges {
                 let (u, v) = edge.endpoints();
@@ -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..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,
@@ -292,7 +293,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,12 +303,12 @@
     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,
             &self.edge_cost,
-            Node::<'graph, S>::connections as fn(&Node<'graph, S>) -> _,
+            NodeConnections::undirected(graph.storage()),
             source,
             PredecessorMode::Record,
             self.candidate_order,
@@ -319,13 +320,13 @@
     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,
             &self.edge_cost,
-            Node::<'graph, S>::connections as fn(&Node<'graph, S>) -> _,
+            NodeConnections::undirected(graph.storage()),
             source,
             PredecessorMode::Record,
             self.candidate_order,
@@ -361,7 +362,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,12 +372,12 @@
     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,
             &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>,
-        source: &'graph S::NodeId,
-        target: &'graph S::NodeId,
+        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,
@@ -432,12 +433,12 @@
     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,
             &self.edge_cost,
-            outgoing_connections as fn(&Node<'graph, S>) -> _,
+            NodeConnections::directed(graph.storage()),
             source,
             PredecessorMode::Record,
             self.candidate_order,
@@ -449,13 +450,13 @@
     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,
             &self.edge_cost,
-            outgoing_connections as fn(&Node<'graph, S>) -> _,
+            NodeConnections::directed(graph.storage()),
             source,
             PredecessorMode::Record,
             self.candidate_order,
@@ -491,12 +492,12 @@
     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,
             &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>,
-        source: &'graph S::NodeId,
-        target: &'graph S::NodeId,
+        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/connections.rs b/crates/algorithms/src/shortest_paths/common/connections.rs
index 0a5b0ad..ad1006a 100644
--- a/crates/algorithms/src/shortest_paths/common/connections.rs
+++ b/crates/algorithms/src/shortest_paths/common/connections.rs
@@ -1,27 +1,68 @@
-use petgraph_core::{edge::Direction, DirectedGraphStorage, Edge, GraphStorage, Node};
+use core::marker::PhantomData;
 
-pub(in crate::shortest_paths) fn outgoing_connections<'a, S>(
-    node: &Node<'a, S>,
-) -> impl Iterator<Item = Edge<'a, S>> + 'a
+use petgraph_core::{
+    edge::{
+        marker::{Directed, Undirected},
+        Direction,
+    },
+    DirectedGraphStorage, Edge, GraphDirectionality, GraphStorage,
+};
+
+pub(in crate::shortest_paths) struct NodeConnections<'graph, S, D>
 where
-    S: DirectedGraphStorage,
+    S: GraphStorage,
+    D: GraphDirectionality,
 {
-    node.directed_connections(Direction::Outgoing)
+    storage: &'graph S,
+    _marker: PhantomData<fn() -> *const D>,
+}
+
+impl<'graph, S> NodeConnections<'graph, S, Directed>
+where
+    S: GraphStorage,
+{
+    pub(in crate::shortest_paths) fn directed(storage: &'graph S) -> Self {
+        Self {
+            storage,
+            _marker: PhantomData,
+        }
+    }
+}
+
+impl<'graph, S> NodeConnections<'graph, S, Undirected>
+where
+    S: GraphStorage,
+{
+    pub(in crate::shortest_paths) fn undirected(storage: &'graph S) -> Self {
+        Self {
+            storage,
+            _marker: PhantomData,
+        }
+    }
 }
 
 pub(in crate::shortest_paths) trait Connections<'a, S>
 where
-    S: GraphStorage,
+    S: GraphStorage + 'a,
 {
-    fn connections(&self, node: &Node<'a, S>) -> impl Iterator<Item = Edge<'a, S>> + 'a;
+    fn connections(&self, node: S::NodeId) -> impl Iterator<Item = Edge<'a, S>> + 'a;
 }
 
-impl<'a, S, I> Connections<'a, S> for fn(&Node<'a, S>) -> I
+impl<'graph, S> Connections<'graph, S> for NodeConnections<'graph, S, Directed>
+where
+    S: DirectedGraphStorage,
+{
+    fn connections(&self, node: S::NodeId) -> impl Iterator<Item = Edge<'graph, S>> + 'graph {
+        self.storage
+            .node_directed_connections(node, Direction::Outgoing)
+    }
+}
+
+impl<'graph, S> Connections<'graph, S> for NodeConnections<'graph, S, Undirected>
 where
     S: GraphStorage,
-    I: Iterator<Item = Edge<'a, S>> + 'a,
 {
-    fn connections(&self, node: &Node<'a, S>) -> impl Iterator<Item = Edge<'a, S>> + 'a {
-        (*self)(node)
+    fn connections(&self, node: S::NodeId) -> impl Iterator<Item = Edge<'graph, S>> + 'graph {
+        self.storage.node_connections(node)
     }
 }
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 bcbc6d9..24de078 100644
--- a/crates/algorithms/src/shortest_paths/common/queue/priority.rs
+++ b/crates/algorithms/src/shortest_paths/common/queue/priority.rs
@@ -1,110 +1,106 @@
 use alloc::collections::BinaryHeap;
-use core::{
-    cell::Cell,
-    cmp::{Ordering, Reverse},
+use core::cmp::Ordering;
+
+use petgraph_core::{
+    id::{AssociativeGraphId, BooleanMapper},
+    GraphStorage,
 };
 
-use petgraph_core::{GraphStorage, Node};
+pub(in crate::shortest_paths) struct PriorityQueueItem<I, T> {
+    pub(in crate::shortest_paths) node: I,
 
-struct PriorityQueueItem<'a, S, T>
-where
-    S: GraphStorage,
-{
-    node: Node<'a, S>,
-
-    priority: T,
-
-    skip: Cell<bool>,
+    pub(in crate::shortest_paths) priority: T,
 }
 
-impl<S, T> PartialEq for PriorityQueueItem<'_, S, T>
+impl<I, T> PartialEq for PriorityQueueItem<I, T>
 where
-    S: GraphStorage,
     T: PartialEq,
 {
     fn eq(&self, other: &Self) -> bool {
-        self.priority.eq(&other.priority)
+        other.priority.eq(&self.priority)
     }
 }
 
-impl<S, T> Eq for PriorityQueueItem<'_, S, T>
-where
-    S: GraphStorage,
-    T: Eq,
-{
-}
+impl<I, T> Eq for PriorityQueueItem<I, T> where T: Eq {}
 
-impl<S, T> PartialOrd for PriorityQueueItem<'_, S, T>
+impl<I, T> PartialOrd for PriorityQueueItem<I, T>
 where
-    S: GraphStorage,
     T: PartialOrd,
 {
     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
-        self.priority.partial_cmp(&other.priority)
+        other.priority.partial_cmp(&self.priority)
     }
 }
 
-impl<S, T> Ord for PriorityQueueItem<'_, S, T>
+impl<I, T> Ord for PriorityQueueItem<I, T>
 where
-    S: GraphStorage,
     T: Ord,
 {
     fn cmp(&self, other: &Self) -> Ordering {
-        self.priority.cmp(&other.priority)
+        other.priority.cmp(&self.priority)
     }
 }
 
 pub(in crate::shortest_paths) struct PriorityQueue<'a, S, T>
 where
-    S: GraphStorage,
+    S: GraphStorage + 'a,
+    S::NodeId: AssociativeGraphId<S>,
     T: Ord,
 {
-    heap: BinaryHeap<Reverse<PriorityQueueItem<'a, S, T>>>,
+    heap: BinaryHeap<PriorityQueueItem<S::NodeId, T>>,
+    pub(crate) check_admissibility: bool,
+
+    flags: <S::NodeId as AssociativeGraphId<S>>::BooleanMapper<'a>,
 }
 
 impl<'a, S, T> PriorityQueue<'a, S, T>
 where
     S: GraphStorage,
+    S::NodeId: AssociativeGraphId<S>,
     T: Ord,
 {
-    pub(in crate::shortest_paths) fn new() -> Self {
+    #[inline]
+    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),
         }
     }
 
-    pub(in crate::shortest_paths) fn push(&mut self, node: Node<'a, S>, priority: T) {
-        self.heap.push(Reverse(PriorityQueueItem {
-            node,
-            priority,
-
-            skip: Cell::new(false),
-        }));
+    pub(in crate::shortest_paths) fn push(&mut self, node: S::NodeId, priority: T) {
+        self.heap.push(PriorityQueueItem { node, priority });
     }
 
-    pub(in crate::shortest_paths) fn decrease_priority(&mut self, node: Node<'a, S>, priority: T) {
-        for Reverse(item) in &self.heap {
-            if item.node.id() == node.id() {
-                item.skip.set(true);
-                break;
+    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: S::NodeId) -> bool {
+        self.flags.index(id)
+    }
+
+    #[inline]
+    pub(in crate::shortest_paths) fn decrease_priority(&mut self, node: S::NodeId, priority: T) {
+        if self.check_admissibility && self.has_been_visited(node) {
+            return;
+        }
+
+        self.heap.push(PriorityQueueItem { node, priority });
+    }
+
+    #[inline]
+    pub(in crate::shortest_paths) fn pop_min(&mut self) -> Option<PriorityQueueItem<S::NodeId, T>> {
+        loop {
+            let item = self.heap.pop()?;
+
+            if self.check_admissibility && self.has_been_visited(item.node) {
+                continue;
             }
+
+            self.visit(item.node);
+            return Some(item);
         }
-
-        self.heap.push(Reverse(PriorityQueueItem {
-            node,
-            priority,
-
-            skip: Cell::new(false),
-        }));
-    }
-
-    pub(in crate::shortest_paths) fn pop_min(&mut self) -> Option<Node<'a, S>> {
-        while let Some(Reverse(item)) = self.heap.pop() {
-            if !item.skip.get() {
-                return Some(item.node);
-            }
-        }
-
-        None
     }
 }
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 2e05130..cd7f47e 100644
--- a/crates/algorithms/src/shortest_paths/common/transit.rs
+++ b/crates/algorithms/src/shortest_paths/common/transit.rs
@@ -5,7 +5,10 @@
 };
 
 use hashbrown::{HashMap, HashSet};
-use petgraph_core::{GraphStorage, Node};
+use petgraph_core::{
+    id::{AssociativeGraphId, AttributeMapper},
+    GraphStorage, Node,
+};
 
 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
 pub(in crate::shortest_paths) enum PredecessorMode {
@@ -13,34 +16,33 @@
     Record,
 }
 
-pub(in crate::shortest_paths) fn reconstruct_path_to<'a, S, H>(
-    predecessors: &HashMap<&'a S::NodeId, Option<Node<'a, S>>, H>,
-    target: &'a S::NodeId,
-) -> Vec<Node<'a, S>>
+pub(in crate::shortest_paths) fn reconstruct_path_to<S>(
+    predecessors: &<S::NodeId as AssociativeGraphId<S>>::AttributeMapper<'_, Option<S::NodeId>>,
+    target: S::NodeId,
+) -> Vec<S::NodeId>
 where
     S: GraphStorage,
-    S::NodeId: Eq + Hash,
-    H: BuildHasher,
+    S::NodeId: AssociativeGraphId<S>,
 {
     let mut current = target;
 
     let mut path = Vec::new();
 
     loop {
-        let Some(node) = predecessors[current] else {
+        let &Some(node) = predecessors.index(current) else {
             // this case should in theory _never_ happen, as the next statement
             // terminates if the next node is `None` (we're at a source node)
             // we do it this way, so that we don't need to push and then pop immediately.
             break;
         };
 
-        if predecessors[node.id()].is_none() {
+        if predecessors.index(node).is_none() {
             // we have reached the source node
             break;
         }
 
         path.push(node);
-        current = node.id();
+        current = node;
     }
 
     path.reverse();
@@ -52,8 +54,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
@@ -90,9 +92,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;
@@ -108,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 471ef22..f2972f3 100644
--- a/crates/algorithms/src/shortest_paths/dijkstra/iter.rs
+++ b/crates/algorithms/src/shortest_paths/dijkstra/iter.rs
@@ -1,18 +1,19 @@
 use alloc::vec::Vec;
-use core::hash::Hash;
+use core::mem;
 
 use error_stack::{Report, Result};
-use fxhash::FxBuildHasher;
-use hashbrown::HashMap;
 use numi::num::{identity::Zero, ops::AddRef};
-use petgraph_core::{Graph, GraphStorage, Node};
+use petgraph_core::{
+    id::{AssociativeGraphId, AttributeMapper},
+    Graph, GraphStorage, Node,
+};
 
 use crate::shortest_paths::{
     common::{
         connections::Connections,
         cost::{Cost, GraphCost},
         path::Path,
-        queue::priority::PriorityQueue,
+        queue::priority::{PriorityQueue, PriorityQueueItem},
         route::Route,
         transit::{reconstruct_path_to, PredecessorMode},
     },
@@ -22,9 +23,11 @@
 pub(super) struct DijkstraIter<'graph: 'parent, 'parent, S, E, G>
 where
     S: GraphStorage,
+    S::NodeId: AssociativeGraphId<S>,
     E: GraphCost<S>,
     E::Value: DijkstraMeasure,
 {
+    graph: &'graph Graph<S>,
     queue: PriorityQueue<'graph, S, E::Value>,
 
     edge_cost: &'parent E,
@@ -35,18 +38,18 @@
     num_nodes: usize,
 
     init: bool,
-    next: Option<Node<'graph, S>>,
+    next: Option<PriorityQueueItem<S::NodeId, E::Value>>,
 
     predecessor_mode: PredecessorMode,
 
-    distances: HashMap<&'graph S::NodeId, E::Value, FxBuildHasher>,
-    predecessors: HashMap<&'graph S::NodeId, Option<Node<'graph, S>>, FxBuildHasher>,
+    distances: <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, G> DijkstraIter<'graph, 'parent, S, E, G>
 where
     S: GraphStorage,
-    S::NodeId: Eq + Hash,
+    S::NodeId: AssociativeGraphId<S>,
     E: GraphCost<S>,
     E::Value: DijkstraMeasure,
     G: Connections<'graph, S>,
@@ -57,25 +60,27 @@
         edge_cost: &'parent E,
         connections: G,
 
-        source: &'graph S::NodeId,
+        source: S::NodeId,
 
-        intermediates: PredecessorMode,
+        predecessor_mode: PredecessorMode,
     ) -> Result<Self, DijkstraError> {
         let source_node = graph
             .node(source)
             .ok_or_else(|| Report::new(DijkstraError::NodeNotFound))?;
 
-        let queue = PriorityQueue::new();
+        let queue = PriorityQueue::new(graph.storage());
 
-        let mut distances = HashMap::with_hasher(FxBuildHasher::default());
-        distances.insert(source, E::Value::zero());
+        let mut distances = <S::NodeId as AssociativeGraphId<S>>::attribute_mapper(graph.storage());
+        distances.set(source, E::Value::zero());
 
-        let mut predecessors = HashMap::with_hasher(FxBuildHasher::default());
-        if intermediates == PredecessorMode::Record {
-            predecessors.insert(source, None);
+        let mut predecessors =
+            <S::NodeId as AssociativeGraphId<S>>::attribute_mapper(graph.storage());
+        if predecessor_mode == PredecessorMode::Record {
+            predecessors.set(source, None);
         }
 
         Ok(Self {
+            graph,
             queue,
             edge_cost,
             connections,
@@ -83,7 +88,7 @@
             num_nodes: graph.num_nodes(),
             init: true,
             next: None,
-            predecessor_mode: intermediates,
+            predecessor_mode,
             distances,
             predecessors,
         })
@@ -93,7 +98,7 @@
 impl<'graph: 'parent, 'parent, S, E, G> Iterator for DijkstraIter<'graph, 'parent, S, E, G>
 where
     S: GraphStorage,
-    S::NodeId: Eq + Hash,
+    S::NodeId: AssociativeGraphId<S>,
     E: GraphCost<S>,
     E::Value: DijkstraMeasure,
     G: Connections<'graph, S>,
@@ -105,7 +110,11 @@
         // and then begin with the actual iteration loop.
         if self.init {
             self.init = false;
-            self.next = Some(self.source);
+            self.next = Some(PriorityQueueItem {
+                node: self.source.id(),
+                priority: E::Value::zero(),
+            });
+            self.queue.visit(self.source.id());
 
             return Some(Route::new(
                 Path::new(self.source, Vec::new(), self.source),
@@ -115,30 +124,43 @@
 
         // Process the neighbours from the node we determined in the last iteration.
         // Reasoning behind this see below.
-        let node = self.next?;
-        let connections = self.connections.connections(&node);
+        let PriorityQueueItem {
+            node,
+            priority: cost,
+        } = mem::take(&mut self.next)?;
 
+        let connections = self.connections.connections(node);
         for edge in connections {
-            let (u, v) = edge.endpoints();
-            let target = if v.id() == node.id() { u } else { v };
+            let (u, v) = edge.endpoint_ids();
+            let target = if u == node { v } else { u };
 
-            let alternative = self.distances[node.id()].add_ref(self.edge_cost.cost(edge).as_ref());
+            // do not pursue edges that have already been processed.
+            if self.queue.has_been_visited(target) {
+                continue;
+            }
 
-            if let Some(distance) = self.distances.get(target.id()) {
-                // do not insert the updated distance if it is not strictly better than the current
-                // one
-                if alternative >= *distance {
+            let alternative = cost.add_ref(self.edge_cost.cost(edge).as_ref());
+
+            // TODO: Entry API
+            if let Some(distance) = self.distances.get_mut(target) {
+                // do not insert the updated distance if it is not strictly better than the
+                // current one
+                if *distance <= alternative {
                     continue;
                 }
-            }
 
-            self.distances.insert(target.id(), alternative.clone());
+                *distance = alternative.clone();
+            } else {
+                self.distances.set(target, alternative.clone());
+            }
 
             if self.predecessor_mode == PredecessorMode::Record {
-                self.predecessors.insert(target.id(), Some(node));
+                self.predecessors.set(target, Some(node));
             }
 
+            // if let Some(target) = self.graph.node(target) {
             self.queue.decrease_priority(target, alternative);
+            // }
         }
 
         // this is what makes this special: instead of getting the next node as the start of next
@@ -156,25 +178,34 @@
         // for neighbour in get_neighbours() { ... }
         // ```
         // Only difference is that we do not have generators in stable Rust (yet).
-        let Some(node) = self.queue.pop_min() else {
-            self.next = None;
+        let Some(item) = self.queue.pop_min() else {
+            // next is already `None`
             return None;
         };
 
-        self.next = Some(node);
+        let node = item.node;
+        let cost = item.priority.clone();
+        self.next = Some(item);
 
         // we're currently visiting the node that has the shortest distance, therefore we know
         // that the distance is the shortest possible
-        let distance = self.distances[node.id()].clone();
+        let distance = cost;
         let transit = if self.predecessor_mode == PredecessorMode::Discard {
             Vec::new()
         } else {
-            reconstruct_path_to(&self.predecessors, node.id())
+            // TODO: cache via dedicated structure
+            reconstruct_path_to::<S>(&self.predecessors, node)
+                .into_iter()
+                .filter_map(|id| self.graph.node(id))
+                .collect()
         };
 
-        let path = Path::new(self.source, transit, node);
+        let node = self.graph.node(node)?;
 
-        Some(Route::new(path, Cost::new(distance)))
+        Some(Route::new(
+            Path::new(self.source, transit, node),
+            Cost::new(distance),
+        ))
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
diff --git a/crates/algorithms/src/shortest_paths/dijkstra/mod.rs b/crates/algorithms/src/shortest_paths/dijkstra/mod.rs
index b8e5c77..9dec7ba 100644
--- a/crates/algorithms/src/shortest_paths/dijkstra/mod.rs
+++ b/crates/algorithms/src/shortest_paths/dijkstra/mod.rs
@@ -6,11 +6,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,
     DirectedGraphStorage, Graph, GraphDirectionality, GraphStorage, Node,
 };
 
@@ -18,14 +19,13 @@
 pub use self::{error::DijkstraError, measure::DijkstraMeasure};
 use super::{
     common::{
-        connections::outgoing_connections,
         cost::{DefaultCost, GraphCost},
         route::{DirectRoute, Route},
         transit::PredecessorMode,
     },
     ShortestDistance, ShortestPath,
 };
-use crate::polyfill::IteratorExt;
+use crate::{polyfill::IteratorExt, shortest_paths::common::connections::NodeConnections};
 
 /// An implementation of Dijkstra's shortest path algorithm.
 ///
@@ -174,7 +174,7 @@
 impl<S, E> ShortestPath<S> for Dijkstra<Undirected, E>
 where
     S: GraphStorage,
-    S::NodeId: Eq + Hash,
+    S::NodeId: AssociativeGraphId<S>,
     E: GraphCost<S>,
     E::Value: DijkstraMeasure,
 {
@@ -184,7 +184,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)?;
 
@@ -194,12 +194,12 @@
     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,
             &self.edge_cost,
-            Node::<'graph, S>::connections as fn(&Node<'graph, S>) -> _,
+            NodeConnections::undirected(graph.storage()),
             source,
             PredecessorMode::Record,
         )
@@ -221,7 +221,7 @@
 impl<S, E> ShortestPath<S> for Dijkstra<Directed, E>
 where
     S: DirectedGraphStorage,
-    S::NodeId: Eq + Hash,
+    S::NodeId: AssociativeGraphId<S>,
     E: GraphCost<S>,
     E::Value: DijkstraMeasure,
 {
@@ -231,12 +231,12 @@
     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,
             &self.edge_cost,
-            outgoing_connections as fn(&Node<'graph, S>) -> _,
+            NodeConnections::directed(graph.storage()),
             source,
             PredecessorMode::Record,
         )
@@ -258,7 +258,7 @@
 impl<S, E> ShortestDistance<S> for Dijkstra<Undirected, E>
 where
     S: GraphStorage,
-    S::NodeId: Eq + Hash,
+    S::NodeId: AssociativeGraphId<S>,
     E: GraphCost<S>,
     E::Value: DijkstraMeasure,
 {
@@ -268,7 +268,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)?;
 
@@ -278,12 +278,12 @@
     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,
             &self.edge_cost,
-            Node::<'graph, S>::connections as fn(&Node<'graph, S>) -> _,
+            NodeConnections::undirected(graph.storage()),
             source,
             PredecessorMode::Discard,
         )?;
@@ -307,7 +307,7 @@
 impl<S, E> ShortestDistance<S> for Dijkstra<Directed, E>
 where
     S: DirectedGraphStorage,
-    S::NodeId: Eq + Hash,
+    S::NodeId: AssociativeGraphId<S>,
     E: GraphCost<S>,
     E::Value: DijkstraMeasure,
 {
@@ -317,12 +317,12 @@
     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,
             &self.edge_cost,
-            outgoing_connections as fn(&Node<'graph, S>) -> _,
+            NodeConnections::directed(graph.storage()),
             source,
             PredecessorMode::Discard,
         )?;
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/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/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 8e7f26d..c199eaf 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,16 +233,16 @@
     /// 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()?
             .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/core/src/attributes.rs b/crates/core/src/attributes.rs
index 95b3918..07b75c9 100644
--- a/crates/core/src/attributes.rs
+++ b/crates/core/src/attributes.rs
@@ -129,14 +129,14 @@
 
 #[cfg(test)]
 mod tests {
-    use core::marker::PhantomData;
+    use core::{fmt::Debug, marker::PhantomData};
 
     use crate::{
         attributes::{Attributes, NoValue},
         ArbitraryGraphId, GraphId, ManagedGraphId,
     };
 
-    #[derive(PartialEq)]
+    #[derive(Debug, Copy, Clone, PartialEq)]
     struct Managed(usize);
 
     impl GraphId for Managed {
@@ -145,17 +145,17 @@
 
     impl ManagedGraphId for Managed {}
 
-    #[derive(PartialEq)]
+    #[derive(Debug, Copy, Clone, PartialEq)]
     struct Arbitrary<V>(V);
 
     impl<V> GraphId for Arbitrary<V>
     where
-        V: PartialEq,
+        V: Debug + Copy + Clone + PartialEq,
     {
         type AttributeIndex = Self;
     }
 
-    impl<V> ArbitraryGraphId for Arbitrary<V> where V: PartialEq {}
+    impl<V> ArbitraryGraphId for Arbitrary<V> where V: Debug + Copy + Clone + PartialEq {}
 
     impl<T> From<T> for Arbitrary<T> {
         fn from(value: T) -> Self {
diff --git a/crates/core/src/edge/mod.rs b/crates/core/src/edge/mod.rs
index f75f831..5ca357b 100644
--- a/crates/core/src/edge/mod.rs
+++ b/crates/core/src/edge/mod.rs
@@ -64,10 +64,10 @@
 {
     storage: &'a S,
 
-    id: &'a S::EdgeId,
+    id: S::EdgeId,
 
-    u: &'a S::NodeId,
-    v: &'a S::NodeId,
+    u: S::NodeId,
+    v: S::NodeId,
 
     weight: &'a S::EdgeWeight,
 }
@@ -86,8 +86,6 @@
 impl<S> Debug for Edge<'_, S>
 where
     S: GraphStorage,
-    S::EdgeId: Debug,
-    S::NodeId: Debug,
     S::EdgeWeight: Debug,
 {
     fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
@@ -153,11 +151,11 @@
     pub fn new(
         storage: &'a S,
 
-        id: &'a S::EdgeId,
+        id: S::EdgeId,
         weight: &'a S::EdgeWeight,
 
-        u: &'a S::NodeId,
-        v: &'a S::NodeId,
+        u: S::NodeId,
+        v: S::NodeId,
     ) -> Self {
         debug_assert!(storage.contains_node(u));
         debug_assert!(storage.contains_node(v));
@@ -197,7 +195,7 @@
     /// assert_eq!(edge.id(), &aa);
     /// ```
     #[must_use]
-    pub const fn id(&self) -> &'a S::EdgeId {
+    pub const fn id(&self) -> S::EdgeId {
         self.id
     }
 
@@ -232,7 +230,7 @@
     /// assert!((u, v) == (&a, &b) || (u, v) == (&b, &a));
     /// ```
     #[must_use]
-    pub const fn endpoint_ids(&self) -> (&'a S::NodeId, &'a S::NodeId) {
+    pub const fn endpoint_ids(&self) -> (S::NodeId, S::NodeId) {
         (self.u, self.v)
     }
 
@@ -338,7 +336,7 @@
     /// assert_eq!(edge.source_id(), &a);
     /// ```
     #[must_use]
-    pub const fn source_id(&self) -> &'a S::NodeId {
+    pub const fn source_id(&self) -> S::NodeId {
         self.u
     }
 
@@ -403,7 +401,7 @@
     /// let edge = graph.edge(&ab).unwrap();
     /// assert_eq!(edge.target_id(), &b);
     /// ```
-    pub const fn target_id(&self) -> &'a S::NodeId {
+    pub const fn target_id(&self) -> S::NodeId {
         self.v
     }
 
@@ -451,8 +449,6 @@
 impl<S> Edge<'_, S>
 where
     S: GraphStorage,
-    S::NodeId: Clone,
-    S::EdgeId: Clone,
     S::EdgeWeight: Clone,
 {
     /// Detach this edge from the graph.
@@ -490,12 +486,7 @@
     /// [`Graph::from_parts`]: crate::graph::Graph::from_parts
     #[must_use]
     pub fn detach(self) -> DetachedStorageEdge<S> {
-        DetachedEdge::new(
-            self.id.clone(),
-            self.weight.clone(),
-            self.u.clone(),
-            self.v.clone(),
-        )
+        DetachedEdge::new(self.id, self.weight.clone(), self.u, self.v)
     }
 }
 
@@ -527,12 +518,12 @@
 where
     S: GraphStorage,
 {
-    id: &'a S::EdgeId,
+    id: S::EdgeId,
 
     weight: &'a mut S::EdgeWeight,
 
-    u: &'a S::NodeId,
-    v: &'a S::NodeId,
+    u: S::NodeId,
+    v: S::NodeId,
 }
 
 impl<'a, S> EdgeMut<'a, S>
@@ -556,13 +547,7 @@
     ///
     /// [`Graph::edge_mut`]: crate::graph::Graph::edge_mut
     /// [`Graph::insert_edge`]: crate::graph::Graph::insert_edge
-    pub fn new(
-        id: &'a S::EdgeId,
-        weight: &'a mut S::EdgeWeight,
-
-        u: &'a S::NodeId,
-        v: &'a S::NodeId,
-    ) -> Self {
+    pub fn new(id: S::EdgeId, weight: &'a mut S::EdgeWeight, u: S::NodeId, v: S::NodeId) -> Self {
         Self { id, weight, u, v }
     }
 
@@ -587,7 +572,7 @@
     /// assert_eq!(edge.id(), &ab);
     /// ```
     #[must_use]
-    pub const fn id(&self) -> &'a S::EdgeId {
+    pub const fn id(&self) -> S::EdgeId {
         self.id
     }
 
@@ -620,7 +605,7 @@
     /// assert!((u, v) == (&a, &b) || (u, v) == (&b, &a));
     /// ```
     #[must_use]
-    pub const fn endpoint_ids(&self) -> (&'a S::NodeId, &'a S::NodeId) {
+    pub const fn endpoint_ids(&self) -> (S::NodeId, S::NodeId) {
         (self.u, self.v)
     }
 
@@ -690,7 +675,7 @@
     /// assert_eq!(edge.source_id(), &a);
     /// ```
     #[must_use]
-    pub const fn source_id(&self) -> &'a S::NodeId {
+    pub const fn source_id(&self) -> S::NodeId {
         self.u
     }
 
@@ -712,7 +697,7 @@
     /// assert_eq!(edge.target_id(), &b);
     /// ```
     #[must_use]
-    pub const fn target_id(&self) -> &'a S::NodeId {
+    pub const fn target_id(&self) -> S::NodeId {
         self.v
     }
 }
@@ -720,8 +705,6 @@
 impl<S> EdgeMut<'_, S>
 where
     S: GraphStorage,
-    S::NodeId: Clone,
-    S::EdgeId: Clone,
     S::EdgeWeight: Clone,
 {
     /// Detaches the edge from the graph.
@@ -756,12 +739,7 @@
     /// [`Graph::from_parts`]: crate::graph::Graph::from_parts
     #[must_use]
     pub fn detach(self) -> DetachedStorageEdge<S> {
-        DetachedEdge::new(
-            self.id.clone(),
-            self.weight.clone(),
-            self.u.clone(),
-            self.v.clone(),
-        )
+        DetachedEdge::new(self.id, self.weight.clone(), self.u, self.v)
     }
 }
 
diff --git a/crates/core/src/graph/compat.rs b/crates/core/src/graph/compat.rs
index 123f573..b5f997e 100644
--- a/crates/core/src/graph/compat.rs
+++ b/crates/core/src/graph/compat.rs
@@ -57,14 +57,13 @@
     }
 
     fn to_index(&self, a: Self::NodeId) -> usize {
-        S::NodeId::index_mapper(&self.storage).index(&a)
+        S::NodeId::index_mapper(&self.storage).index(a)
     }
 
     fn from_index(&self, i: usize) -> Self::NodeId {
         S::NodeId::index_mapper(&self.storage)
             .reverse(i)
             .expect("unable to determine index")
-            .into_owned()
     }
 }
 
@@ -98,14 +97,13 @@
     }
 
     fn to_index(&self, a: Self::EdgeId) -> usize {
-        S::EdgeId::index_mapper(&self.storage).index(&a)
+        S::EdgeId::index_mapper(&self.storage).index(a)
     }
 
     fn from_index(&self, i: usize) -> Self::EdgeId {
         S::EdgeId::index_mapper(&self.storage)
             .reverse(i)
             .expect("unable to determine index")
-            .into_owned()
     }
 }
 
@@ -128,7 +126,7 @@
     type NodeIdentifiers = impl Iterator<Item = Self::NodeId>;
 
     fn node_identifiers(self) -> Self::NodeIdentifiers {
-        self.nodes().map(|node| *node.id())
+        self.nodes().map(|node| node.id())
     }
 }
 
@@ -176,8 +174,8 @@
         // We make use of `&n` in the trait and the iterator is bound to it, which means that we
         // need to collect to avoid having a lifetime we created in this code.
         // we _could_ in theory also use `Cow` here, but that's a bit overkill.
-        self.neighbours(&n)
-            .map(|node| *node.id())
+        self.neighbours(n)
+            .map(|node| node.id())
             .collect::<Vec<_>>()
             .into_iter()
     }
@@ -194,8 +192,8 @@
 
     fn neighbors_directed(self, n: Self::NodeId, d: Direction) -> Self::NeighborsDirected {
         // see comment in `IntoNeighbors` for why we need to collect here.
-        self.neighbours_directed(&n, d)
-            .map(|node| *node.id())
+        self.neighbours_directed(n, d)
+            .map(|node| node.id())
             .collect::<Vec<_>>()
             .into_iter()
     }
@@ -212,7 +210,7 @@
 
     fn edges(self, a: Self::NodeId) -> Self::Edges {
         // see comment in `IntoNeighbors` for why we need to collect here.
-        self.connections(&a).collect::<Vec<_>>().into_iter()
+        self.connections(a).collect::<Vec<_>>().into_iter()
     }
 }
 
@@ -227,7 +225,7 @@
 
     fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected {
         // see comment in `IntoNeighbors` for why we need to collect here.
-        self.connections_directed(&a, dir)
+        self.connections_directed(a, dir)
             .collect::<Vec<_>>()
             .into_iter()
     }
@@ -261,7 +259,7 @@
     T: LinearGraphId<S> + Clone,
 {
     fn visit(&mut self, a: T) -> bool {
-        let Some(index) = self.mapper.get(&a) else {
+        let Some(index) = self.mapper.get(a) else {
             return false;
         };
 
@@ -269,7 +267,7 @@
     }
 
     fn is_visited(&self, a: &T) -> bool {
-        let Some(index) = self.mapper.get(a) else {
+        let Some(index) = self.mapper.get(*a) else {
             return false;
         };
 
@@ -330,7 +328,7 @@
     fn adjacency_matrix(&self) -> Self::AdjMatrix {}
 
     fn is_adjacent(&self, _: &Self::AdjMatrix, a: Self::NodeId, b: Self::NodeId) -> bool {
-        self.edges_between(&a, &b).next().is_some()
+        self.edges_between(a, b).next().is_some()
     }
 }
 
@@ -342,11 +340,11 @@
     S::EdgeId: Copy,
 {
     fn node_weight(&self, id: Self::NodeId) -> Option<&Self::NodeWeight> {
-        self.node(&id).map(|node| node.weight())
+        self.node(id).map(|node| node.weight())
     }
 
     fn edge_weight(&self, id: Self::EdgeId) -> Option<&Self::EdgeWeight> {
-        self.edge(&id).map(|edge| edge.weight())
+        self.edge(id).map(|edge| edge.weight())
     }
 }
 
@@ -358,7 +356,7 @@
     S::EdgeId: ManagedGraphId + Copy,
 {
     fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId {
-        *self.insert_node(weight).id()
+        self.insert_node(weight).id()
     }
 
     fn update_edge(
@@ -367,7 +365,7 @@
         b: Self::NodeId,
         weight: Self::EdgeWeight,
     ) -> Self::EdgeId {
-        *self.insert_edge(weight, &a, &b).id()
+        self.insert_edge(weight, a, b).id()
     }
 }
 
diff --git a/crates/core/src/graph/directed.rs b/crates/core/src/graph/directed.rs
index 9b6baa3..7e8122d 100644
--- a/crates/core/src/graph/directed.rs
+++ b/crates/core/src/graph/directed.rs
@@ -44,11 +44,11 @@
     ///     [(ba, u8::MAX - 1)].into_iter().collect::<HashSet<_>>()
     /// );
     /// ```
-    pub fn directed_edges_between<'a: 'b, 'b>(
-        &'a self,
-        source: &'b S::NodeId,
-        target: &'b S::NodeId,
-    ) -> impl Iterator<Item = Edge<'a, S>> + 'b {
+    pub fn directed_edges_between(
+        &self,
+        source: S::NodeId,
+        target: S::NodeId,
+    ) -> impl Iterator<Item = Edge<'_, S>> {
         self.storage.directed_edges_between(source, target)
     }
 
@@ -87,11 +87,11 @@
     ///         .collect::<HashSet<_>>()
     /// );
     /// ```
-    pub fn directed_edges_between_mut<'a: 'b, 'b>(
-        &'a mut self,
-        source: &'b S::NodeId,
-        target: &'b S::NodeId,
-    ) -> impl Iterator<Item = EdgeMut<'a, S>> + 'b {
+    pub fn directed_edges_between_mut(
+        &mut self,
+        source: S::NodeId,
+        target: S::NodeId,
+    ) -> impl Iterator<Item = EdgeMut<'_, S>> {
         self.storage.directed_edges_between_mut(source, target)
     }
 
@@ -106,11 +106,11 @@
     /// This is an alias for [`Self::neighbours_directed`], due to spelling differences between
     /// American and British English.
     #[inline]
-    pub fn neighbors_directed<'a: 'b, 'b>(
-        &'a self,
-        id: &'b S::NodeId,
+    pub fn neighbors_directed(
+        &self,
+        id: S::NodeId,
         direction: Direction,
-    ) -> impl Iterator<Item = Node<'a, S>> + 'b {
+    ) -> impl Iterator<Item = Node<'_, S>> {
         self.neighbours_directed(id, direction)
     }
 
@@ -154,11 +154,11 @@
     ///     [a].into_iter().collect::<HashSet<_>>()
     /// );
     /// ```
-    pub fn neighbours_directed<'a: 'b, 'b>(
-        &'a self,
-        id: &'b S::NodeId,
+    pub fn neighbours_directed(
+        &self,
+        id: S::NodeId,
         direction: Direction,
-    ) -> impl Iterator<Item = Node<'a, S>> + 'b {
+    ) -> impl Iterator<Item = Node<'_, S>> {
         self.storage.node_directed_neighbours(id, direction)
     }
 
@@ -174,11 +174,11 @@
     /// This is an alias for [`Self::neighbours_directed_mut`], due to spelling differences between
     /// American and British English.
     #[inline]
-    pub fn neighbors_directed_mut<'a: 'b, 'b>(
-        &'a mut self,
-        id: &'b S::NodeId,
+    pub fn neighbors_directed_mut(
+        &mut self,
+        id: S::NodeId,
         direction: Direction,
-    ) -> impl Iterator<Item = NodeMut<'a, S>> + 'b {
+    ) -> impl Iterator<Item = NodeMut<'_, S>> {
         self.neighbours_directed_mut(id, direction)
     }
 
@@ -219,11 +219,11 @@
     ///     [(a, 1), (b, 1), (c, 3)].into_iter().collect::<HashSet<_>>()
     /// );
     /// ```
-    pub fn neighbours_directed_mut<'a: 'b, 'b>(
-        &'a mut self,
-        id: &'b S::NodeId,
+    pub fn neighbours_directed_mut(
+        &mut self,
+        id: S::NodeId,
         direction: Direction,
-    ) -> impl Iterator<Item = NodeMut<'a, S>> + 'b {
+    ) -> impl Iterator<Item = NodeMut<'_, S>> {
         self.storage.node_directed_neighbours_mut(id, direction)
     }
 
@@ -261,11 +261,11 @@
     ///         .collect::<HashSet<_>>()
     /// );
     /// ```
-    pub fn connections_directed<'a: 'b, 'b>(
-        &'a self,
-        id: &'b S::NodeId,
+    pub fn connections_directed(
+        &self,
+        id: S::NodeId,
         direction: Direction,
-    ) -> impl Iterator<Item = Edge<'a, S>> + 'b {
+    ) -> impl Iterator<Item = Edge<'_, S>> {
         self.storage.node_directed_connections(id, direction)
     }
 
@@ -308,11 +308,11 @@
     ///         .collect::<HashSet<_>>()
     /// );
     /// ```
-    pub fn connections_directed_mut<'a: 'b, 'b>(
-        &'a mut self,
-        id: &'b S::NodeId,
+    pub fn connections_directed_mut(
+        &mut self,
+        id: S::NodeId,
         direction: Direction,
-    ) -> impl Iterator<Item = EdgeMut<'a, S>> + 'b {
+    ) -> impl Iterator<Item = EdgeMut<'_, S>> {
         self.storage.node_directed_connections_mut(id, direction)
     }
 
diff --git a/crates/core/src/graph/insert.rs b/crates/core/src/graph/insert.rs
index 592d82b..48ce252 100644
--- a/crates/core/src/graph/insert.rs
+++ b/crates/core/src/graph/insert.rs
@@ -138,10 +138,10 @@
     /// Refer to the documentation of the underlying storage for more information.
     pub fn try_insert_node_with(
         &mut self,
-        weight: impl FnOnce(&S::NodeId) -> S::NodeWeight,
+        weight: impl FnOnce(S::NodeId) -> S::NodeWeight,
     ) -> Result<NodeMut<S>, Error> {
         let id = self.storage.next_node_id(NoValue::new());
-        let weight = weight(&id);
+        let weight = weight(id);
 
         self.storage.insert_node(id, weight).change_context(Error)
     }
@@ -180,7 +180,7 @@
     /// Refer to the documentation of the underlying storage for more information.
     pub fn insert_node_with(
         &mut self,
-        weight: impl FnOnce(&S::NodeId) -> S::NodeWeight,
+        weight: impl FnOnce(S::NodeId) -> S::NodeWeight,
     ) -> NodeMut<S> {
         self.try_insert_node_with(weight)
             .expect("Constraint violation. Try using `try_insert_node_with` instead.")
@@ -213,10 +213,10 @@
         weight: S::NodeWeight,
     ) -> Result<NodeMut<S>, Error> {
         // we cannot use `if let` here due to limitations of the borrow checker
-        if self.storage.contains_node(&id) {
+        if self.storage.contains_node(id) {
             let mut node = self
                 .storage
-                .node_mut(&id)
+                .node_mut(id)
                 .expect("inconsistent storage, node must exist");
 
             *node.weight_mut() = weight;
@@ -272,8 +272,8 @@
     pub fn try_insert_edge(
         &mut self,
         attributes: impl Into<Attributes<<S::EdgeId as GraphId>::AttributeIndex, S::EdgeWeight>>,
-        source: &S::NodeId,
-        target: &S::NodeId,
+        source: S::NodeId,
+        target: S::NodeId,
     ) -> Result<EdgeMut<S>, Error> {
         let Attributes { id, weight } = attributes.into();
 
@@ -312,8 +312,8 @@
     pub fn insert_edge(
         &mut self,
         attributes: impl Into<Attributes<<S::EdgeId as GraphId>::AttributeIndex, S::EdgeWeight>>,
-        source: &S::NodeId,
-        target: &S::NodeId,
+        source: S::NodeId,
+        target: S::NodeId,
     ) -> EdgeMut<S> {
         self.try_insert_edge(attributes, source, target)
             .expect("Constraint violation. Try using `try_insert_edge` instead.")
@@ -361,12 +361,12 @@
     /// The same errors as [`Self::try_insert_edge`] may occur.
     pub fn try_insert_edge_with(
         &mut self,
-        weight: impl FnOnce(&S::EdgeId) -> S::EdgeWeight,
-        source: &S::NodeId,
-        target: &S::NodeId,
+        weight: impl FnOnce(S::EdgeId) -> S::EdgeWeight,
+        source: S::NodeId,
+        target: S::NodeId,
     ) -> Result<EdgeMut<S>, Error> {
         let id = self.storage.next_edge_id(NoValue::new());
-        let weight = weight(&id);
+        let weight = weight(id);
 
         self.storage
             .insert_edge(id, weight, source, target)
@@ -406,9 +406,9 @@
     /// The same panics as [`Self::insert_edge`] may occur.
     pub fn insert_edge_with(
         &mut self,
-        weight: impl FnOnce(&S::EdgeId) -> S::EdgeWeight,
-        source: &S::NodeId,
-        target: &S::NodeId,
+        weight: impl FnOnce(S::EdgeId) -> S::EdgeWeight,
+        source: S::NodeId,
+        target: S::NodeId,
     ) -> EdgeMut<S> {
         self.try_insert_edge_with(weight, source, target)
             .expect("Constraint violation. Try using `try_insert_edge_with` instead.")
@@ -441,13 +441,13 @@
         id: S::EdgeId,
         weight: S::EdgeWeight,
 
-        source: &S::NodeId,
-        target: &S::NodeId,
+        source: S::NodeId,
+        target: S::NodeId,
     ) -> Result<EdgeMut<S>, Error> {
-        if self.storage.contains_edge(&id) {
+        if self.storage.contains_edge(id) {
             let mut edge = self
                 .storage
-                .edge_mut(&id)
+                .edge_mut(id)
                 .expect("inconsistent storage, edge must exist");
 
             *edge.weight_mut() = weight;
@@ -473,8 +473,8 @@
         id: S::EdgeId,
         weight: S::EdgeWeight,
 
-        source: &S::NodeId,
-        target: &S::NodeId,
+        source: S::NodeId,
+        target: S::NodeId,
     ) -> EdgeMut<S> {
         self.try_upsert_edge(id, weight, source, target)
             .expect("Constraint violation. Try using `try_upsert_edge` instead.")
diff --git a/crates/core/src/graph/mod.rs b/crates/core/src/graph/mod.rs
index e38fb88..8937b61 100644
--- a/crates/core/src/graph/mod.rs
+++ b/crates/core/src/graph/mod.rs
@@ -472,7 +472,7 @@
     ///     None
     /// );
     /// ```
-    pub fn node(&self, id: &S::NodeId) -> Option<Node<S>> {
+    pub fn node(&self, id: S::NodeId) -> Option<Node<S>> {
         self.storage.node(id)
     }
 
@@ -502,7 +502,7 @@
     ///
     /// assert!(graph.node_mut(&b).is_none());
     /// ```
-    pub fn node_mut(&mut self, id: &S::NodeId) -> Option<NodeMut<S>> {
+    pub fn node_mut(&mut self, id: S::NodeId) -> Option<NodeMut<S>> {
         self.storage.node_mut(id)
     }
 
@@ -526,7 +526,7 @@
     /// assert!(graph.contains_node(&a));
     /// assert!(!graph.contains_node(&b));
     /// ```
-    pub fn contains_node(&self, id: &S::NodeId) -> bool {
+    pub fn contains_node(&self, id: S::NodeId) -> bool {
         self.storage.contains_node(id)
     }
 
@@ -555,10 +555,7 @@
     /// assert_eq!(graph.remove_node(&a), None);
     /// assert_eq!(graph.remove_node(&b), None);
     /// ```
-    pub fn remove_node(
-        &mut self,
-        id: &S::NodeId,
-    ) -> Option<DetachedNode<S::NodeId, S::NodeWeight>> {
+    pub fn remove_node(&mut self, id: S::NodeId) -> Option<DetachedNode<S::NodeId, S::NodeWeight>> {
         self.storage.remove_node(id)
     }
 
@@ -589,7 +586,7 @@
     /// );
     /// assert!(graph.edge(&bc).is_none());
     /// ```
-    pub fn edge(&self, id: &S::EdgeId) -> Option<Edge<S>> {
+    pub fn edge(&self, id: S::EdgeId) -> Option<Edge<S>> {
         self.storage.edge(id)
     }
 
@@ -621,7 +618,7 @@
     /// );
     /// assert!(graph.edge_mut(&bc).is_none());
     /// ```
-    pub fn edge_mut(&mut self, id: &S::EdgeId) -> Option<EdgeMut<S>> {
+    pub fn edge_mut(&mut self, id: S::EdgeId) -> Option<EdgeMut<S>> {
         self.storage.edge_mut(id)
     }
 
@@ -646,7 +643,7 @@
     /// assert!(graph.contains_edge(&ab));
     /// assert!(!graph.contains_edge(&bc));
     /// ```
-    pub fn contains_edge(&self, id: &S::EdgeId) -> bool {
+    pub fn contains_edge(&self, id: S::EdgeId) -> bool {
         self.storage.contains_edge(id)
     }
 
@@ -683,7 +680,7 @@
     /// ```
     pub fn remove_edge(
         &mut self,
-        id: &S::EdgeId,
+        id: S::EdgeId,
     ) -> Option<DetachedEdge<S::EdgeId, S::NodeId, S::EdgeWeight>> {
         self.storage.remove_edge(id)
     }
@@ -693,10 +690,7 @@
     /// This is an alias for [`Self::neighbours`], as there's a spelling difference between the
     /// American and British English.
     #[inline]
-    pub fn neighbors<'a: 'b, 'b>(
-        &'a self,
-        id: &'b S::NodeId,
-    ) -> impl Iterator<Item = Node<'a, S>> + 'b {
+    pub fn neighbors(&self, id: S::NodeId) -> impl Iterator<Item = Node<'_, S>> {
         self.neighbours(id)
     }
 
@@ -742,10 +736,7 @@
     ///     [a, c].into_iter().collect::<HashSet<_>>()
     /// );
     /// ```
-    pub fn neighbours<'a: 'b, 'b>(
-        &'a self,
-        id: &'b S::NodeId,
-    ) -> impl Iterator<Item = Node<S>> + 'b {
+    pub fn neighbours(&self, id: S::NodeId) -> impl Iterator<Item = Node<'_, S>> {
         self.storage.node_neighbours(id)
     }
 
@@ -754,10 +745,7 @@
     /// This is an alias for [`Self::neighbours_mut`], as there's a spelling difference between
     /// American and British English.
     #[inline]
-    pub fn neighbors_mut<'a: 'b, 'b>(
-        &'a mut self,
-        id: &'b S::NodeId,
-    ) -> impl Iterator<Item = NodeMut<'a, S>> + 'b {
+    pub fn neighbors_mut(&mut self, id: S::NodeId) -> impl Iterator<Item = NodeMut<'_, S>> {
         self.neighbours_mut(id)
     }
 
@@ -805,10 +793,7 @@
     ///     Some((d, 3))
     /// );
     /// ```
-    pub fn neighbours_mut<'a: 'b, 'b>(
-        &'a mut self,
-        id: &'b S::NodeId,
-    ) -> impl Iterator<Item = NodeMut<'a, S>> + 'b {
+    pub fn neighbours_mut(&mut self, id: S::NodeId) -> impl Iterator<Item = NodeMut<'_, S>> {
         self.storage.node_neighbours_mut(id)
     }
 
@@ -843,10 +828,7 @@
     ///     [ab, ca, aa].into_iter().collect::<HashSet<_>>()
     /// );
     /// ```
-    pub fn connections<'a: 'b, 'b>(
-        &'a self,
-        id: &'b S::NodeId,
-    ) -> impl Iterator<Item = Edge<'a, S>> + 'b {
+    pub fn connections(&self, id: S::NodeId) -> impl Iterator<Item = Edge<'_, S>> {
         self.storage.node_connections(id)
     }
 
@@ -892,10 +874,7 @@
     ///     Some((bc, u8::MAX - 1))
     /// );
     /// ```
-    pub fn connections_mut<'a: 'b, 'b>(
-        &'a mut self,
-        id: &'b S::NodeId,
-    ) -> impl Iterator<Item = EdgeMut<'a, S>> + 'b {
+    pub fn connections_mut(&mut self, id: S::NodeId) -> impl Iterator<Item = EdgeMut<'_, S>> {
         self.storage.node_connections_mut(id)
     }
 
@@ -926,7 +905,7 @@
     /// assert_eq!(graph.degree(&c), 2);
     /// assert_eq!(graph.degree(&d), 0);
     /// ```
-    pub fn degree(&self, id: &S::NodeId) -> usize {
+    pub fn degree(&self, id: S::NodeId) -> usize {
         self.storage.node_degree(id)
     }
 
@@ -960,11 +939,7 @@
     ///     [ab, ba].into_iter().collect::<HashSet<_>>()
     /// );
     /// ```
-    pub fn edges_between<'a: 'b, 'b>(
-        &'a self,
-        u: &'b S::NodeId,
-        v: &'b S::NodeId,
-    ) -> impl Iterator<Item = Edge<'a, S>> + 'b {
+    pub fn edges_between(&self, u: S::NodeId, v: S::NodeId) -> impl Iterator<Item = Edge<'_, S>> {
         self.storage.edges_between(u, v)
     }
 
@@ -1002,11 +977,11 @@
     ///         .collect::<HashSet<_>>()
     /// );
     /// ```
-    pub fn edges_between_mut<'a: 'b, 'b>(
-        &'a mut self,
-        u: &'b S::NodeId,
-        v: &'b S::NodeId,
-    ) -> impl Iterator<Item = EdgeMut<'a, S>> + 'b {
+    pub fn edges_between_mut(
+        &mut self,
+        u: S::NodeId,
+        v: S::NodeId,
+    ) -> impl Iterator<Item = EdgeMut<'_, S>> {
         self.storage.edges_between_mut(u, v)
     }
 
diff --git a/crates/core/src/id/associative.rs b/crates/core/src/id/associative.rs
new file mode 100644
index 0000000..ed4a95b
--- /dev/null
+++ b/crates/core/src/id/associative.rs
@@ -0,0 +1,51 @@
+use crate::{GraphId, GraphStorage};
+
+// TODO: Entry API
+
+pub trait AttributeMapper<K, V> {
+    type Iter<'a>: Iterator<Item = (K, &'a V)>
+    where
+        V: 'a,
+        Self: 'a;
+
+    fn get(&self, id: K) -> Option<&V>;
+    fn get_mut(&mut self, id: K) -> Option<&mut V>;
+    fn index(&self, id: K) -> &V {
+        self.get(id).expect("item")
+    }
+    fn index_mut(&mut self, id: K) -> &mut V {
+        self.get_mut(id).expect("item")
+    }
+
+    fn set(&mut self, id: K, value: V) -> Option<V>;
+    fn remove(&mut self, id: K) -> Option<V>;
+
+    fn iter(&self) -> Self::Iter<'_>;
+}
+
+pub trait BooleanMapper<K> {
+    fn get(&self, id: K) -> Option<bool>;
+    #[inline]
+    fn index(&self, id: K) -> bool {
+        self.get(id).unwrap_or(false)
+    }
+
+    fn set(&mut self, id: K, flag: bool) -> Option<bool>;
+}
+
+pub trait AssociativeGraphId<S>: GraphId + Sized
+where
+    S: GraphStorage,
+{
+    type AttributeMapper<'a, V>: AttributeMapper<Self, V>
+    where
+        S: 'a;
+
+    type BooleanMapper<'a>: BooleanMapper<Self>
+    where
+        S: 'a;
+
+    fn attribute_mapper<V>(storage: &S) -> Self::AttributeMapper<'_, V>;
+
+    fn boolean_mapper(storage: &S) -> Self::BooleanMapper<'_>;
+}
diff --git a/crates/core/src/id/linear.rs b/crates/core/src/id/linear.rs
index d5c2f55..f36e349 100644
--- a/crates/core/src/id/linear.rs
+++ b/crates/core/src/id/linear.rs
@@ -62,7 +62,7 @@
     /// // The order for which node maps to which value is not guaranteed.
     /// assert_ne!(mapper.get(&a), mapper.get(&b));
     /// ```
-    fn get(&self, from: &Id) -> Option<usize>;
+    fn get(&self, from: Id) -> Option<usize>;
 
     /// Lookup a value from `To` to [`usize`].
     ///
@@ -92,7 +92,7 @@
     ///
     /// Panics if the provided id is not valid, meaning it is not part of the graph (e.g. id from
     /// another instance)
-    fn index(&self, from: &Id) -> usize {
+    fn index(&self, from: Id) -> usize {
         self.get(from).expect("invalid id provided")
     }
 
@@ -119,7 +119,7 @@
     /// let mapped = mapper.index(&a);
     /// assert_eq!(mapper.reverse(mapped), Some(Moo::Borrowed(&a)));
     /// ```
-    fn reverse(&self, to: usize) -> Option<Moo<Id>>;
+    fn reverse(&self, to: usize) -> Option<Id>;
 }
 
 /// Linear graph identifier.
diff --git a/crates/core/src/id/mod.rs b/crates/core/src/id/mod.rs
index f5eb4be..3cb1299 100644
--- a/crates/core/src/id/mod.rs
+++ b/crates/core/src/id/mod.rs
@@ -7,9 +7,16 @@
 //! exclusive and define if a node or edge id will be automatically assigned by the graph (are
 //! managed) and a user has no control over their value or are arbitrary, allowing the user to use
 //! _any_ value.
+mod associative;
+
 mod linear;
 
-pub use self::linear::{IndexMapper, LinearGraphId};
+use core::fmt::Debug;
+
+pub use self::{
+    associative::{AssociativeGraphId, AttributeMapper, BooleanMapper},
+    linear::{IndexMapper, LinearGraphId},
+};
 use crate::attributes::NoValue;
 
 // The `PartialEq` bound is required for the default implementation, we could in theory remove it,
@@ -22,7 +29,7 @@
 /// This trait is implemented for all types that are used as node or edge identifiers in the graph.
 /// A type should never only implement this trait, but also [`ManagedGraphId`] or
 /// [`ArbitraryGraphId`].
-pub trait GraphId: PartialEq {
+pub trait GraphId: Debug + Copy + Clone + PartialEq {
     /// The type of value used to index attributes.
     ///
     /// Used to differentiate between [`ManagedGraphId`] and [`ArbitraryGraphId`] and to allow for
diff --git a/crates/core/src/node/mod.rs b/crates/core/src/node/mod.rs
index b4f01ad..716f6f3 100644
--- a/crates/core/src/node/mod.rs
+++ b/crates/core/src/node/mod.rs
@@ -53,7 +53,7 @@
 {
     storage: &'a S,
 
-    id: &'a S::NodeId,
+    id: S::NodeId,
     weight: &'a S::NodeWeight,
 }
 
@@ -123,7 +123,6 @@
 impl<S> Debug for Node<'_, S>
 where
     S: GraphStorage,
-    S::NodeId: Debug,
     S::NodeWeight: Debug,
 {
     fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
@@ -169,7 +168,7 @@
     /// ```
     ///
     /// [`Graph::node`]: crate::graph::Graph::node
-    pub const fn new(storage: &'a S, id: &'a S::NodeId, weight: &'a S::NodeWeight) -> Self {
+    pub const fn new(storage: &'a S, id: S::NodeId, weight: &'a S::NodeWeight) -> Self {
         Self {
             storage,
             id,
@@ -198,7 +197,7 @@
     /// assert_eq!(node.id(), &a);
     /// ```
     #[must_use]
-    pub const fn id(&self) -> &'a S::NodeId {
+    pub const fn id(&self) -> S::NodeId {
         self.id
     }
 
@@ -411,7 +410,6 @@
 impl<S> Node<'_, S>
 where
     S: GraphStorage,
-    S::NodeId: Clone,
     S::NodeWeight: Clone,
 {
     /// Detaches the node from the graph.
@@ -445,7 +443,7 @@
     /// [`Graph::from_parts`]: crate::graph::Graph::from_parts
     #[must_use]
     pub fn detach(self) -> DetachedNode<S::NodeId, S::NodeWeight> {
-        DetachedNode::new(self.id.clone(), self.weight.clone())
+        DetachedNode::new(self.id, self.weight.clone())
     }
 }
 
@@ -476,7 +474,7 @@
 where
     S: GraphStorage,
 {
-    id: &'a S::NodeId,
+    id: S::NodeId,
 
     weight: &'a mut S::NodeWeight,
 }
@@ -500,7 +498,7 @@
     ///
     /// [`Graph::node_mut`]: crate::graph::Graph::node_mut
     /// [`Graph::insert_node`]: crate::graph::Graph::insert_node
-    pub fn new(id: &'a S::NodeId, weight: &'a mut S::NodeWeight) -> Self {
+    pub fn new(id: S::NodeId, weight: &'a mut S::NodeWeight) -> Self {
         Self { id, weight }
     }
 
@@ -525,7 +523,7 @@
     /// assert_eq!(node.id(), &a);
     /// ```
     #[must_use]
-    pub const fn id(&self) -> &'a S::NodeId {
+    pub const fn id(&self) -> S::NodeId {
         self.id
     }
 
@@ -576,7 +574,6 @@
 impl<S> NodeMut<'_, S>
 where
     S: GraphStorage,
-    S::NodeId: Clone,
     S::NodeWeight: Clone,
 {
     /// Detaches the node from the graph.
@@ -611,7 +608,7 @@
     /// [`Graph::from_parts`]: crate::graph::Graph::from_parts
     #[must_use]
     pub fn detach(&self) -> DetachedNode<S::NodeId, S::NodeWeight> {
-        DetachedNode::new(self.id.clone(), self.weight.clone())
+        DetachedNode::new(self.id, self.weight.clone())
     }
 }
 
diff --git a/crates/core/src/storage/directed.rs b/crates/core/src/storage/directed.rs
index 1656351..8837fb6 100644
--- a/crates/core/src/storage/directed.rs
+++ b/crates/core/src/storage/directed.rs
@@ -73,11 +73,11 @@
     /// This method is implemented by calling [`Self::node_directed_connections`] and filtering the
     /// edges by their target.
     /// Most implementations should be able to provide a more efficient implementation.
-    fn directed_edges_between<'a: 'b, 'b>(
-        &'a self,
-        source: &'b Self::NodeId,
-        target: &'b Self::NodeId,
-    ) -> impl Iterator<Item = Edge<'a, Self>> + 'b {
+    fn directed_edges_between(
+        &self,
+        source: Self::NodeId,
+        target: Self::NodeId,
+    ) -> impl Iterator<Item = Edge<'_, Self>> {
         self.node_directed_connections(source, Direction::Outgoing)
             .filter(move |edge| edge.target_id() == target)
     }
@@ -128,11 +128,11 @@
     /// This method is implemented by calling [`Self::node_directed_connections_mut`] and filtering
     /// the edges by their target.
     /// Most implementations should be able to provide a more efficient implementation.
-    fn directed_edges_between_mut<'a: 'b, 'b>(
-        &'a mut self,
-        source: &'b Self::NodeId,
-        target: &'b Self::NodeId,
-    ) -> impl Iterator<Item = EdgeMut<'a, Self>> + 'b {
+    fn directed_edges_between_mut(
+        &mut self,
+        source: Self::NodeId,
+        target: Self::NodeId,
+    ) -> impl Iterator<Item = EdgeMut<'_, Self>> {
         self.node_directed_connections_mut(source, Direction::Outgoing)
             .filter(move |edge| edge.target_id() == target)
     }
@@ -189,11 +189,11 @@
     ///     [ca]
     /// );
     /// ```
-    fn node_directed_connections<'a: 'b, 'b>(
-        &'a self,
-        id: &'b Self::NodeId,
+    fn node_directed_connections(
+        &self,
+        id: Self::NodeId,
         direction: Direction,
-    ) -> impl Iterator<Item = Edge<'a, Self>> + 'b;
+    ) -> impl Iterator<Item = Edge<'_, Self>>;
 
     /// Returns an iterator over all directed edges that are connected to the given node, by the
     /// given direction with mutable weights.
@@ -243,11 +243,11 @@
     ///     [5, 5]
     /// );
     /// ```
-    fn node_directed_connections_mut<'a: 'b, 'b>(
-        &'a mut self,
-        id: &'b Self::NodeId,
+    fn node_directed_connections_mut(
+        &mut self,
+        id: Self::NodeId,
         direction: Direction,
-    ) -> impl Iterator<Item = EdgeMut<'a, Self>> + 'b;
+    ) -> impl Iterator<Item = EdgeMut<'_, Self>>;
 
     /// Returns the number of directed edges that are connected to the given node, by the given
     /// direction.
@@ -280,7 +280,7 @@
     /// assert_eq!(storage.node_directed_degree(&a, Direction::Outgoing), 1);
     /// assert_eq!(storage.node_directed_degree(&a, Direction::Incoming), 1);
     /// ```
-    fn node_directed_degree(&self, id: &Self::NodeId, direction: Direction) -> usize {
+    fn node_directed_degree(&self, id: Self::NodeId, direction: Direction) -> usize {
         self.node_directed_connections(id, direction).count()
     }
 
@@ -343,11 +343,11 @@
     ///
     /// Implementations should try to provide a more efficient implementation than the default one,
     /// and must uphold the contract that the returned iterator does not contain duplicates.
-    fn node_directed_neighbours<'a: 'b, 'b>(
-        &'a self,
-        id: &'b Self::NodeId,
+    fn node_directed_neighbours(
+        &self,
+        id: Self::NodeId,
         direction: Direction,
-    ) -> impl Iterator<Item = Node<'a, Self>> + 'b {
+    ) -> impl Iterator<Item = Node<'_, Self>> {
         self.node_directed_connections(id, direction)
             .map(move |edge| match direction {
                 Direction::Outgoing => edge.target(),
@@ -412,9 +412,9 @@
     /// No default implementation is provided, as a mutable iterator based on
     /// [`Self::node_directed_connections_mut`] could potentially lead to a double mutable borrow.
     // I'd love to provide a default implementation for this, but I just can't get it to work.
-    fn node_directed_neighbours_mut<'a: 'b, 'b>(
-        &'a mut self,
-        id: &'b Self::NodeId,
+    fn node_directed_neighbours_mut(
+        &mut self,
+        id: Self::NodeId,
         direction: Direction,
-    ) -> impl Iterator<Item = NodeMut<'a, Self>> + 'b;
+    ) -> impl Iterator<Item = NodeMut<'_, Self>>;
 }
diff --git a/crates/core/src/storage/mod.rs b/crates/core/src/storage/mod.rs
index d090c4e..c7ce1cc 100644
--- a/crates/core/src/storage/mod.rs
+++ b/crates/core/src/storage/mod.rs
@@ -326,7 +326,7 @@
         let mut result: Result<(), Self::Error> = Ok(());
 
         for edge in edges {
-            if let Err(error) = graph.insert_edge(edge.id, edge.weight, &edge.u, &edge.v) {
+            if let Err(error) = graph.insert_edge(edge.id, edge.weight, edge.u, edge.v) {
                 match &mut result {
                     Err(errors) => errors.extend_one(error),
                     result => *result = Err(error),
@@ -614,8 +614,8 @@
         id: Self::EdgeId,
         weight: Self::EdgeWeight,
 
-        u: &Self::NodeId,
-        v: &Self::NodeId,
+        u: Self::NodeId,
+        v: Self::NodeId,
     ) -> Result<EdgeMut<Self>, Self::Error>;
 
     /// Removes the node with the given identifier from the graph.
@@ -682,7 +682,7 @@
     /// ```
     fn remove_node(
         &mut self,
-        id: &Self::NodeId,
+        id: Self::NodeId,
     ) -> Option<DetachedNode<Self::NodeId, Self::NodeWeight>>;
 
     /// Removes the edge with the given identifier from the graph.
@@ -716,7 +716,7 @@
     /// ```
     fn remove_edge(
         &mut self,
-        id: &Self::EdgeId,
+        id: Self::EdgeId,
     ) -> Option<DetachedEdge<Self::EdgeId, Self::NodeId, Self::EdgeWeight>>;
 
     /// Clears the graph, removing all nodes and edges.
@@ -773,7 +773,7 @@
     /// // This will access the underlying storage, and is equivalent to `storage.neighbours(&a)`.
     /// assert_eq!(node.neighbours().count(), 0);
     /// ```
-    fn node(&self, id: &Self::NodeId) -> Option<Node<Self>>;
+    fn node(&self, id: Self::NodeId) -> Option<Node<Self>>;
 
     /// Returns the node, with a mutable weight, with the given identifier.
     ///
@@ -797,7 +797,7 @@
     /// assert_eq!(node.id(), &a);
     /// assert_eq!(node.weight(), &mut 1);
     /// ```
-    fn node_mut(&mut self, id: &Self::NodeId) -> Option<NodeMut<Self>>;
+    fn node_mut(&mut self, id: Self::NodeId) -> Option<NodeMut<Self>>;
 
     /// Checks if the node with the given identifier exists.
     ///
@@ -825,7 +825,7 @@
     /// The default implementation simply checks if [`Self::node`] returns [`Some`], but if
     /// possible, custom implementations that are able to do this more efficiently should override
     /// this.
-    fn contains_node(&self, id: &Self::NodeId) -> bool {
+    fn contains_node(&self, id: Self::NodeId) -> bool {
         self.node(id).is_some()
     }
 
@@ -872,7 +872,7 @@
     /// assert_eq!(edge.target().id(), &b);
     /// assert_eq!(edge.target().weight(), &2);
     /// ```
-    fn edge(&self, id: &Self::EdgeId) -> Option<Edge<Self>>;
+    fn edge(&self, id: Self::EdgeId) -> Option<Edge<Self>>;
 
     /// Returns the edge, with a mutable weight, with the given identifier, if it exists.
     ///
@@ -905,7 +905,7 @@
     ///
     /// assert_eq!(storage.edge(&ab).unwrap().weight(), &4);
     /// ```
-    fn edge_mut(&mut self, id: &Self::EdgeId) -> Option<EdgeMut<Self>>;
+    fn edge_mut(&mut self, id: Self::EdgeId) -> Option<EdgeMut<Self>>;
 
     /// Checks if the edge with the given identifier exists.
     ///
@@ -938,7 +938,7 @@
     /// The default implementation simply checks if [`Self::edge`] returns [`Some`], but if
     /// possible, custom implementations that are able to do this more efficiently should override
     /// this.
-    fn contains_edge(&self, id: &Self::EdgeId) -> bool {
+    fn contains_edge(&self, id: Self::EdgeId) -> bool {
         self.edge(id).is_some()
     }
 
@@ -981,11 +981,11 @@
     /// The default implementation simply calls [`Self::node_connections`] on both nodes and then
     /// chains those, after filtering for the respective end. Most implementations should be able to
     /// provide a more efficient implementation.
-    fn edges_between<'a: 'b, 'b>(
-        &'a self,
-        u: &'b Self::NodeId,
-        v: &'b Self::NodeId,
-    ) -> impl Iterator<Item = Edge<'a, Self>> + 'b {
+    fn edges_between(
+        &self,
+        u: Self::NodeId,
+        v: Self::NodeId,
+    ) -> impl Iterator<Item = Edge<'_, Self>> {
         // How does this work with a default implementation?
         let from_source = self.node_connections(u).filter(move |edge| {
             let (edge_u, edge_v) = edge.endpoint_ids();
@@ -1050,11 +1050,11 @@
     /// [`Self::node_connections_mut`] for `source` and `target` would lead to a double mutable
     /// borrow.
     // I'd love to provide a default implementation for this, but I just can't get it to work.
-    fn edges_between_mut<'a: 'b, 'b>(
-        &'a mut self,
-        u: &'b Self::NodeId,
-        v: &'b Self::NodeId,
-    ) -> impl Iterator<Item = EdgeMut<'a, Self>> + 'b;
+    fn edges_between_mut(
+        &mut self,
+        u: Self::NodeId,
+        v: Self::NodeId,
+    ) -> impl Iterator<Item = EdgeMut<'_, Self>>;
 
     /// Returns an iterator over all edges that are connected to the given node.
     ///
@@ -1094,10 +1094,7 @@
     ///     [ab, ca]
     /// );
     /// ```
-    fn node_connections<'a: 'b, 'b>(
-        &'a self,
-        id: &'b Self::NodeId,
-    ) -> impl Iterator<Item = Edge<'a, Self>> + 'b;
+    fn node_connections(&self, id: Self::NodeId) -> impl Iterator<Item = Edge<'_, Self>>;
 
     /// Returns an iterator over all edges that are connected to the given node, with mutable
     /// weights.
@@ -1142,10 +1139,8 @@
     ///     [5, 6]
     /// );
     /// ```
-    fn node_connections_mut<'a: 'b, 'b>(
-        &'a mut self,
-        id: &'b Self::NodeId,
-    ) -> impl Iterator<Item = EdgeMut<'a, Self>> + 'b;
+    fn node_connections_mut(&mut self, id: Self::NodeId)
+    -> impl Iterator<Item = EdgeMut<'_, Self>>;
 
     /// Returns the number of edges that are connected to the given node.
     ///
@@ -1181,7 +1176,7 @@
     /// edges.
     /// This is unlikely to be the most efficient implementation, so custom implementations should
     /// override this.
-    fn node_degree(&self, id: &Self::NodeId) -> usize {
+    fn node_degree(&self, id: Self::NodeId) -> usize {
         self.node_connections(id).count()
     }
 
@@ -1239,10 +1234,7 @@
     ///
     /// Changing the requirement from **SHOULD NOT** to **MUST NOT** may occur in the future, and is
     /// to be considered a breaking change.
-    fn node_neighbours<'a: 'b, 'b>(
-        &'a self,
-        id: &'b Self::NodeId,
-    ) -> impl Iterator<Item = Node<'a, Self>> + 'b {
+    fn node_neighbours(&self, id: Self::NodeId) -> impl Iterator<Item = Node<'_, Self>> {
         self.node_connections(id)
             .filter_map(move |edge: Edge<Self>| {
                 let (u, v) = edge.endpoint_ids();
@@ -1303,10 +1295,7 @@
     ///
     /// No default implementation is provided, as a mutable iterator based on
     /// [`Self::node_connections_mut`] could potentially lead to a double mutable borrow.
-    fn node_neighbours_mut<'a: 'b, 'b>(
-        &'a mut self,
-        id: &'b Self::NodeId,
-    ) -> impl Iterator<Item = NodeMut<'a, Self>> + 'b;
+    fn node_neighbours_mut(&mut self, id: Self::NodeId) -> impl Iterator<Item = NodeMut<'_, Self>>;
 
     /// Returns an iterator over all nodes that do not have any edges connected to them.
     ///
diff --git a/crates/core/tests/test_deprecated/visit_filter.rs b/crates/core/tests/test_deprecated/visit_filter.rs
index 2abe8a4..930ef99 100644
--- a/crates/core/tests/test_deprecated/visit_filter.rs
+++ b/crates/core/tests/test_deprecated/visit_filter.rs
@@ -22,20 +22,20 @@
 fn edge_filtered_edges_directed() {
     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();
 
-    let ab = *graph.insert_edge("A → B", &a, &b).id();
-    let ac = *graph.insert_edge("A → C", &a, &c).id();
-    let ad = *graph.insert_edge("A → D", &a, &d).id();
+    let ab = graph.insert_edge("A → B", a, b).id();
+    let ac = graph.insert_edge("A → C", a, c).id();
+    let ad = graph.insert_edge("A → D", a, d).id();
 
-    let filtered = EdgeFiltered::from_fn(&graph, |edge| *edge.id() != ab);
+    let filtered = EdgeFiltered::from_fn(&graph, |edge| edge.id() != ab);
 
     let received = filtered
         .edges_directed(a, Direction::Outgoing)
-        .map(|edge| *edge.id())
+        .map(|edge| edge.id())
         .collect::<Vec<_>>();
     let expected = vec![ac, ad];
 
@@ -43,7 +43,7 @@
 
     let received = filtered
         .edges_directed(b, Direction::Incoming)
-        .map(|edge| *edge.id())
+        .map(|edge| edge.id())
         .collect::<Vec<_>>();
     let expected = vec![];
 
@@ -54,10 +54,10 @@
 fn edge_filtered_edges_directed_reverse() {
     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();
 
-    let ab = *graph.insert_edge("A → B", &a, &b).id();
+    let ab = graph.insert_edge("A → B", a, b).id();
 
     // do not filter anything, we just want to test the reverse direction
     let filtered = EdgeFiltered::from_fn(&graph, |_| true);
@@ -66,7 +66,7 @@
     assert_eq!(
         graph
             .edges_directed(a, Direction::Outgoing)
-            .map(|edge| *edge.id())
+            .map(|edge| edge.id())
             .collect::<Vec<_>>(),
         [ab]
     );
@@ -81,7 +81,7 @@
     assert_eq!(
         graph
             .edges_directed(a, Direction::Incoming)
-            .map(|edge| *edge.id())
+            .map(|edge| edge.id())
             .collect::<Vec<_>>(),
         []
     );
@@ -98,12 +98,12 @@
 fn edge_filtered_undirected_filter_by_weight() {
     let mut graph = UnDinoGraph::new();
 
-    let a = *graph.insert_node("A").id();
-    let b = *graph.insert_node("B").id();
-    let c = *graph.insert_node("C").id();
+    let a = graph.insert_node("A").id();
+    let b = graph.insert_node("B").id();
+    let c = graph.insert_node("C").id();
 
     for (source, target, weight) in [(a, b, 0), (a, c, 1), (b, c, -1)] {
-        graph.insert_edge(weight, &source, &target);
+        graph.insert_edge(weight, source, target);
     }
 
     let filtered = EdgeFiltered::from_fn(&graph, |edge| *edge.weight() >= 0);
@@ -123,20 +123,20 @@
 fn node_filtered_edges_directed() {
     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();
 
-    let ab = *graph.insert_edge("A → B", &a, &b).id();
-    let ac = *graph.insert_edge("A → C", &a, &c).id();
-    let ad = *graph.insert_edge("A → D", &a, &d).id();
+    let ab = graph.insert_edge("A → B", a, b).id();
+    let ac = graph.insert_edge("A → C", a, c).id();
+    let ad = graph.insert_edge("A → D", a, d).id();
 
     let filtered = NodeFiltered::from_fn(&graph, |node| node != b);
 
     let received = filtered
         .edges_directed(a, Direction::Outgoing)
-        .map(|edge| *edge.id())
+        .map(|edge| edge.id())
         .collect::<Vec<_>>();
     let expected = vec![ac, ad];
 
@@ -144,7 +144,7 @@
 
     let received = filtered
         .edges_directed(b, Direction::Incoming)
-        .map(|edge| *edge.id())
+        .map(|edge| edge.id())
         .collect::<Vec<_>>();
     let expected = vec![];
 
@@ -155,10 +155,10 @@
 fn node_filtered_node_identifiers() {
     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();
 
     let filtered = NodeFiltered::from_fn(&graph, |node| node != b);
 
@@ -172,9 +172,9 @@
 fn node_filtered_by_fixed_bit_set() {
     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 a = graph.insert_node("A").id();
+    let b = graph.insert_node("B").id();
+    let c = graph.insert_node("C").id();
 
     let mut map = (&graph).visit_map();
     map.visit(a);
diff --git a/crates/core/tests/test_deprecated/visit_traversal_bfs.rs b/crates/core/tests/test_deprecated/visit_traversal_bfs.rs
index dba324e..1b264e9 100644
--- a/crates/core/tests/test_deprecated/visit_traversal_bfs.rs
+++ b/crates/core/tests/test_deprecated/visit_traversal_bfs.rs
@@ -22,14 +22,14 @@
 fn simple() {
     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("A → B", &a, &b);
-    graph.insert_edge("B → C", &b, &c);
-    graph.insert_edge("B → D", &b, &d);
+    graph.insert_edge("A → B", a, b);
+    graph.insert_edge("B → C", b, c);
+    graph.insert_edge("B → D", b, d);
 
     let dfs = Bfs::new(&graph, a);
 
@@ -51,12 +51,12 @@
 fn unreachable() {
     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 a = graph.insert_node("A").id();
+    let b = graph.insert_node("B").id();
+    let c = graph.insert_node("C").id();
 
-    graph.insert_edge("A → B", &a, &b);
-    graph.insert_edge("B → C", &b, &c);
+    graph.insert_edge("A → B", a, b);
+    graph.insert_edge("B → C", b, c);
 
     let dfs = Bfs::new(&graph, b);
 
@@ -80,11 +80,11 @@
 fn disconnected() {
     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 a = graph.insert_node("A").id();
+    let b = graph.insert_node("B").id();
+    let c = graph.insert_node("C").id();
 
-    graph.insert_edge("A → B", &a, &b);
+    graph.insert_edge("A → B", a, b);
 
     let dfs = Bfs::new(&graph, a);
 
@@ -119,12 +119,12 @@
 fn order() {
     let mut graph = DiDinoGraph::new();
 
-    let b = *graph.insert_node("B").id();
-    let c = *graph.insert_node("C").id();
-    let d = *graph.insert_node("D").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("B → C", &b, &c);
-    graph.insert_edge("B → D", &b, &d);
+    graph.insert_edge("B → C", b, c);
+    graph.insert_edge("B → D", b, d);
 
     let dfs = Bfs::new(&graph, b);
 
@@ -149,20 +149,20 @@
 fn order_deep() {
     let mut graph = DiDinoGraph::new();
 
-    let b = *graph.insert_node("B").id();
-    let c = *graph.insert_node("C").id();
-    let d = *graph.insert_node("D").id();
-    let e = *graph.insert_node("E").id();
-    let f = *graph.insert_node("F").id();
-    let g = *graph.insert_node("G").id();
-    let h = *graph.insert_node("H").id();
+    let b = graph.insert_node("B").id();
+    let c = graph.insert_node("C").id();
+    let d = graph.insert_node("D").id();
+    let e = graph.insert_node("E").id();
+    let f = graph.insert_node("F").id();
+    let g = graph.insert_node("G").id();
+    let h = graph.insert_node("H").id();
 
-    graph.insert_edge("B → C", &b, &c);
-    graph.insert_edge("B → D", &b, &d);
-    graph.insert_edge("C → G", &c, &g);
-    graph.insert_edge("C → H", &c, &h);
-    graph.insert_edge("D → E", &d, &e);
-    graph.insert_edge("D → F", &d, &f);
+    graph.insert_edge("B → C", b, c);
+    graph.insert_edge("B → D", b, d);
+    graph.insert_edge("C → G", c, g);
+    graph.insert_edge("C → H", c, h);
+    graph.insert_edge("D → E", d, e);
+    graph.insert_edge("D → F", d, f);
 
     let dfs = Bfs::new(&graph, b);
 
diff --git a/crates/core/tests/test_deprecated/visit_traversal_dfs.rs b/crates/core/tests/test_deprecated/visit_traversal_dfs.rs
index 82b14e8..8502c9d 100644
--- a/crates/core/tests/test_deprecated/visit_traversal_dfs.rs
+++ b/crates/core/tests/test_deprecated/visit_traversal_dfs.rs
@@ -24,14 +24,14 @@
 fn simple() {
     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("A → B", &a, &b);
-    graph.insert_edge("B → C", &b, &c);
-    graph.insert_edge("B → D", &b, &d);
+    graph.insert_edge("A → B", a, b);
+    graph.insert_edge("B → C", b, c);
+    graph.insert_edge("B → D", b, d);
 
     let dfs = Dfs::new(&graph, a);
 
@@ -53,12 +53,12 @@
 fn unreachable() {
     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 a = graph.insert_node("A").id();
+    let b = graph.insert_node("B").id();
+    let c = graph.insert_node("C").id();
 
-    graph.insert_edge("A → B", &a, &b);
-    graph.insert_edge("B → C", &b, &c);
+    graph.insert_edge("A → B", a, b);
+    graph.insert_edge("B → C", b, c);
 
     let dfs = Dfs::new(&graph, b);
 
@@ -82,11 +82,11 @@
 fn disconnected() {
     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 a = graph.insert_node("A").id();
+    let b = graph.insert_node("B").id();
+    let c = graph.insert_node("C").id();
 
-    graph.insert_edge("A → B", &a, &b);
+    graph.insert_edge("A → B", a, b);
 
     let dfs = Dfs::new(&graph, a);
 
@@ -120,12 +120,12 @@
 fn order() {
     let mut graph = DiDinoGraph::new();
 
-    let b = *graph.insert_node("B").id();
-    let c = *graph.insert_node("C").id();
-    let d = *graph.insert_node("D").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("B → C", &b, &c);
-    graph.insert_edge("B → D", &b, &d);
+    graph.insert_edge("B → C", b, c);
+    graph.insert_edge("B → D", b, d);
 
     let dfs = Dfs::new(&graph, b);
 
@@ -150,20 +150,20 @@
 fn order_deep() {
     let mut graph = DiDinoGraph::new();
 
-    let b = *graph.insert_node("B").id();
-    let c = *graph.insert_node("C").id();
-    let d = *graph.insert_node("D").id();
-    let e = *graph.insert_node("E").id();
-    let f = *graph.insert_node("F").id();
-    let g = *graph.insert_node("G").id();
-    let h = *graph.insert_node("H").id();
+    let b = graph.insert_node("B").id();
+    let c = graph.insert_node("C").id();
+    let d = graph.insert_node("D").id();
+    let e = graph.insert_node("E").id();
+    let f = graph.insert_node("F").id();
+    let g = graph.insert_node("G").id();
+    let h = graph.insert_node("H").id();
 
-    graph.insert_edge("B → C", &b, &c);
-    graph.insert_edge("B → D", &b, &d);
-    graph.insert_edge("C → G", &c, &g);
-    graph.insert_edge("C → H", &c, &h);
-    graph.insert_edge("H → E", &d, &e);
-    graph.insert_edge("D → F", &d, &f);
+    graph.insert_edge("B → C", b, c);
+    graph.insert_edge("B → D", b, d);
+    graph.insert_edge("C → G", c, g);
+    graph.insert_edge("C → H", c, h);
+    graph.insert_edge("H → E", d, e);
+    graph.insert_edge("D → F", d, f);
 
     let dfs = Dfs::new(&graph, b);
 
diff --git a/crates/core/tests/test_deprecated/visit_traversal_dfs_visit.rs b/crates/core/tests/test_deprecated/visit_traversal_dfs_visit.rs
index b22ff56..d596ffc 100644
--- a/crates/core/tests/test_deprecated/visit_traversal_dfs_visit.rs
+++ b/crates/core/tests/test_deprecated/visit_traversal_dfs_visit.rs
@@ -10,13 +10,13 @@
 fn simple() {
     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 a = graph.insert_node("A").id();
+    let b = graph.insert_node("B").id();
+    let c = graph.insert_node("C").id();
 
-    graph.insert_edge("A → B", &a, &b);
-    graph.insert_edge("B → C", &b, &c);
-    graph.insert_edge("C → A", &c, &a);
+    graph.insert_edge("A → B", a, b);
+    graph.insert_edge("B → C", b, c);
+    graph.insert_edge("C → A", c, a);
 
     // TODO: think about moving this to an iterator instead
     depth_first_search(&graph, Some(a), |event| match event {
@@ -57,20 +57,20 @@
 fn terminate_early() {
     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 a = graph.insert_node("A").id();
+    let b = graph.insert_node("B").id();
+    let c = graph.insert_node("C").id();
 
-    graph.insert_edge("A → B", &a, &b);
-    graph.insert_edge("B → C", &b, &c);
-    graph.insert_edge("C → A", &c, &a);
+    graph.insert_edge("A → B", a, b);
+    graph.insert_edge("B → C", b, c);
+    graph.insert_edge("C → A", c, a);
 
     let mut mapper = NodeId::index_mapper(graph.storage());
 
     let mut predecessor = vec![None; graph.num_nodes()];
     let control = depth_first_search(&graph, once(a), |event| {
         if let DfsEvent::TreeEdge(start, end) = event {
-            predecessor[mapper.get(&end)] = Some(start);
+            predecessor[mapper.index(end)] = Some(start);
             if end == b {
                 return Control::Break(start);
             }
@@ -87,13 +87,13 @@
 fn cross_forward_edge() {
     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 a = graph.insert_node("A").id();
+    let b = graph.insert_node("B").id();
+    let c = graph.insert_node("C").id();
 
-    graph.insert_edge("A → B", &a, &b);
-    graph.insert_edge("B → C", &b, &c);
-    graph.insert_edge("A → C", &a, &c);
+    graph.insert_edge("A → B", a, b);
+    graph.insert_edge("B → C", b, c);
+    graph.insert_edge("A → C", a, c);
 
     depth_first_search(&graph, once(a), |event| {
         if let DfsEvent::CrossForwardEdge(start, end) = event {
@@ -109,12 +109,12 @@
 fn prune() {
     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 a = graph.insert_node("A").id();
+    let b = graph.insert_node("B").id();
+    let c = graph.insert_node("C").id();
 
-    graph.insert_edge("A → B", &a, &b);
-    graph.insert_edge("B → C", &b, &c);
+    graph.insert_edge("A → B", a, b);
+    graph.insert_edge("B → C", b, c);
 
     depth_first_search(&graph, once(a), |event| {
         if let DfsEvent::Discover(node, _) = event {
@@ -124,7 +124,7 @@
         }
 
         if let DfsEvent::TreeEdge(start, end) = event {
-            assert!(end != c, "Unexpected edge: {start:?} → {end:?}");
+            assert_ne!(end, c, "Unexpected edge: {start:?} → {end:?}");
         }
 
         Control::Continue
diff --git a/crates/core/tests/test_deprecated/visit_traversal_topo.rs b/crates/core/tests/test_deprecated/visit_traversal_topo.rs
index 6beba28..8ee82ef 100644
--- a/crates/core/tests/test_deprecated/visit_traversal_topo.rs
+++ b/crates/core/tests/test_deprecated/visit_traversal_topo.rs
@@ -14,12 +14,12 @@
 
         let source_index = order
             .iter()
-            .position(|x| x == source)
+            .position(|x| *x == source)
             .expect("Source node not found");
 
         let target_index = order
             .iter()
-            .position(|x| x == target)
+            .position(|x| *x == target)
             .expect("Target node not found");
 
         assert!(
@@ -44,14 +44,14 @@
 fn setup() -> DiDinoGraph<&'static str, &'static str> {
     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 e = *graph.insert_node("E").id();
-    let f = *graph.insert_node("F").id();
-    let g = *graph.insert_node("G").id();
-    let h = *graph.insert_node("H").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();
+    let e = graph.insert_node("E").id();
+    let f = graph.insert_node("F").id();
+    let g = graph.insert_node("G").id();
+    let h = graph.insert_node("H").id();
 
     for (source, target, weight) in [
         (b, e, "B → E"), //
@@ -64,7 +64,7 @@
         (h, f, "H → F"),
         (h, g, "H → G"),
     ] {
-        graph.insert_edge(weight, &source, &target);
+        graph.insert_edge(weight, source, target);
     }
 
     graph
@@ -88,13 +88,13 @@
 fn disjoint() {
     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("A → B", &a, &b);
-    graph.insert_edge("C → D", &c, &d);
+    graph.insert_edge("A → B", a, b);
+    graph.insert_edge("C → D", c, d);
 
     let mut topo = Topo::new(&graph);
     let mut order = vec![];
@@ -111,10 +111,10 @@
 fn path() {
     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("A → B", &a, &b);
+    graph.insert_edge("A → B", a, b);
 
     let mut topo = Topo::new(&graph);
     let mut order = vec![];
@@ -130,11 +130,11 @@
 fn error_on_cycle() {
     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("A → B", &a, &b);
-    graph.insert_edge("B → A", &b, &a);
+    graph.insert_edge("A → B", a, b);
+    graph.insert_edge("B → A", b, a);
 
     let mut topo = Topo::new(&graph);
     // toposort silently ignores cycles, therefore `Topo` will output `None`, instead of returning a
diff --git a/crates/dino/Cargo.toml b/crates/dino/Cargo.toml
index 0c0e715..95c7608 100644
--- a/crates/dino/Cargo.toml
+++ b/crates/dino/Cargo.toml
@@ -10,9 +10,8 @@
 petgraph-core = { workspace = true, features = ['alloc'] }
 error-stack.workspace = true
 
+bitvec = "1.0.1"
 either = "1.9.0" # TODO: potentially remove
 
-# Closures
-roaring = "0.10.2"
-fnv = { version = "1.0.7", default-features = false }
+[dev-dependencies]
 hashbrown = { workspace = true, features = ['ahash'] }
diff --git a/crates/dino/src/closure/mod.rs b/crates/dino/src/closure/mod.rs
index 5495d96..fa2f55a 100644
--- a/crates/dino/src/closure/mod.rs
+++ b/crates/dino/src/closure/mod.rs
@@ -1,447 +1,112 @@
-mod union;
+mod unique_vec;
 
-use either::Either;
-use fnv::FnvBuildHasher;
-// The closure tables have quite a bit of allocations (due to the nested nature of the data
-// structure). Question is can we avoid them?
-use hashbrown::HashMap;
-use roaring::RoaringBitmap;
-
-use self::union::UnionIterator;
+pub(crate) use self::unique_vec::UniqueVec;
 use crate::{
-    closure::union::UnionIntoIterator,
-    edge::Edge,
-    node::Node,
-    slab::{EntryId, Key as _, Slab},
+    edge::{Edge, EdgeSlab},
+    node::{Node, NodeSlab},
     EdgeId, NodeId,
 };
 
-#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
-enum Key {
-    SourceToTargets(NodeId),
-    TargetToSources(NodeId),
-
-    SourceToEdges(NodeId),
-    TargetsToEdges(NodeId),
-
-    EndpointsToEdges(NodeId, NodeId),
-}
-
-#[derive(Debug, Clone, PartialEq)]
-struct ClosureStorage {
-    inner: HashMap<Key, RoaringBitmap, FnvBuildHasher>,
-    nodes: RoaringBitmap,
-}
-
-impl ClosureStorage {
-    fn new() -> Self {
-        Self {
-            inner: HashMap::with_hasher(FnvBuildHasher::default()),
-            nodes: RoaringBitmap::new(),
-        }
-    }
-
-    fn create_edge<T>(&mut self, edge: &Edge<T>) {
-        let raw_index = edge.id.into_id().raw();
-
-        let source = edge.source;
-        let target = edge.target;
-
-        self.inner
-            .entry(Key::SourceToTargets(source))
-            .or_default()
-            .insert(target.into_id().raw());
-
-        self.inner
-            .entry(Key::TargetToSources(target))
-            .or_default()
-            .insert(source.into_id().raw());
-
-        self.inner
-            .entry(Key::SourceToEdges(source))
-            .or_default()
-            .insert(raw_index);
-
-        self.inner
-            .entry(Key::TargetsToEdges(target))
-            .or_default()
-            .insert(raw_index);
-
-        self.inner
-            .entry(Key::EndpointsToEdges(source, target))
-            .or_default()
-            .insert(raw_index);
-    }
-
-    fn remove_edge<T>(&mut self, edge: &Edge<T>) {
-        let raw_index = edge.id.into_id().raw();
-
-        let source = edge.source;
-        let target = edge.target;
-
-        let is_multi = self
-            .inner
-            .get(&Key::EndpointsToEdges(edge.source, edge.target))
-            .map_or(false, |bitmap| bitmap.len() > 1);
-
-        if !is_multi {
-            if let Some(targets) = self.inner.get_mut(&Key::SourceToTargets(source)) {
-                targets.remove(edge.target.into_id().raw());
-            }
-
-            if let Some(sources) = self.inner.get_mut(&Key::TargetToSources(target)) {
-                sources.remove(edge.source.into_id().raw());
-            }
-        }
-
-        if let Some(edges) = self.inner.get_mut(&Key::SourceToEdges(source)) {
-            edges.remove(raw_index);
-        }
-
-        if let Some(edges) = self.inner.get_mut(&Key::TargetsToEdges(target)) {
-            edges.remove(raw_index);
-        }
-
-        if let Some(edges) = self.inner.get_mut(&Key::EndpointsToEdges(source, target)) {
-            edges.remove(raw_index);
-
-            if edges.is_empty() {
-                self.inner.remove(&Key::EndpointsToEdges(source, target));
-            }
-        }
-    }
-
-    fn create_node<T>(&mut self, node: &Node<T>) {
-        self.inner
-            .insert(Key::SourceToTargets(node.id), RoaringBitmap::new());
-        self.inner
-            .insert(Key::TargetToSources(node.id), RoaringBitmap::new());
-
-        self.inner
-            .insert(Key::SourceToEdges(node.id), RoaringBitmap::new());
-        self.inner
-            .insert(Key::TargetsToEdges(node.id), RoaringBitmap::new());
-
-        self.nodes.insert(node.id.into_id().raw());
-    }
-
-    fn remove_node<T>(&mut self, node: &Node<T>) {
-        let raw_index = node.id.into_id().raw();
-
-        let targets = self.inner.remove(&Key::SourceToTargets(node.id));
-
-        if let Some(targets) = targets {
-            for target in targets {
-                let target = NodeId::from_id(EntryId::new_unchecked(target));
-                if let Some(sources) = self.inner.get_mut(&Key::TargetToSources(target)) {
-                    sources.remove(raw_index);
-                }
-
-                self.inner.remove(&Key::EndpointsToEdges(node.id, target));
-            }
-        }
-
-        let sources = self.inner.remove(&Key::TargetToSources(node.id));
-
-        if let Some(sources) = sources {
-            for source in sources {
-                let source = NodeId::from_id(EntryId::new_unchecked(source));
-                if let Some(targets) = self.inner.get_mut(&Key::SourceToTargets(source)) {
-                    targets.remove(raw_index);
-                }
-
-                self.inner.remove(&Key::EndpointsToEdges(source, node.id));
-            }
-        }
-
-        self.inner.remove(&Key::SourceToEdges(node.id));
-        self.inner.remove(&Key::TargetsToEdges(node.id));
-
-        self.nodes.remove(raw_index);
-    }
-
-    fn clear(&mut self) {
-        self.inner.clear();
-    }
-
-    fn refresh<N, E>(&mut self, nodes: &Slab<NodeId, Node<N>>, edges: &Slab<EdgeId, Edge<E>>) {
-        self.clear();
-
-        for node in nodes.iter() {
-            self.create_node(node);
-        }
-
-        for edge in edges.iter() {
-            self.create_edge(edge);
-        }
-    }
-
-    fn reserve(&mut self, additional: usize) {
-        self.inner.reserve(additional);
-    }
-
-    fn shrink_to_fit(&mut self) {
-        self.inner.shrink_to_fit();
-    }
-}
-
-pub(crate) struct NodeClosure<'a> {
-    storage: &'a ClosureStorage,
-}
-
-impl<'a> NodeClosure<'a> {
-    const fn new(storage: &'a ClosureStorage) -> Self {
-        Self { storage }
-    }
-
-    pub(crate) fn outgoing_neighbours(&self, id: NodeId) -> impl Iterator<Item = NodeId> + 'a {
-        let Some(bitmap) = self.storage.inner.get(&Key::SourceToTargets(id)) else {
-            return Either::Left(core::iter::empty());
-        };
-
-        Either::Right(
-            bitmap
-                .iter()
-                .map(|value| NodeId::from_id(EntryId::new_unchecked(value))),
-        )
-    }
-
-    pub(crate) fn incoming_neighbours(&self, id: NodeId) -> impl Iterator<Item = NodeId> + 'a {
-        let Some(bitmap) = self.storage.inner.get(&Key::TargetToSources(id)) else {
-            return Either::Left(core::iter::empty());
-        };
-
-        Either::Right(
-            bitmap
-                .iter()
-                .map(|value| NodeId::from_id(EntryId::new_unchecked(value))),
-        )
-    }
-
-    pub(crate) fn neighbours(&self, id: NodeId) -> impl Iterator<Item = NodeId> + 'a {
-        let Some(left) = self.storage.inner.get(&Key::SourceToTargets(id)) else {
-            return Either::Left(core::iter::empty());
-        };
-
-        let Some(right) = self.storage.inner.get(&Key::TargetToSources(id)) else {
-            return Either::Right(Either::Left(
-                left.iter()
-                    .map(|value| NodeId::from_id(EntryId::new_unchecked(value))),
-            ));
-        };
-
-        Either::Right(Either::Right(
-            UnionIterator::new(left, right)
-                .map(|value| NodeId::from_id(EntryId::new_unchecked(value))),
-        ))
-    }
-
-    pub(crate) fn outgoing_edges(&self, id: NodeId) -> impl Iterator<Item = EdgeId> + 'a {
-        let Some(bitmap) = self.storage.inner.get(&Key::SourceToEdges(id)) else {
-            return Either::Left(core::iter::empty());
-        };
-
-        Either::Right(
-            bitmap
-                .iter()
-                .map(|value| EdgeId::from_id(EntryId::new_unchecked(value))),
-        )
-    }
-
-    pub(crate) fn incoming_edges(&self, id: NodeId) -> impl Iterator<Item = EdgeId> + 'a {
-        let Some(bitmap) = self.storage.inner.get(&Key::TargetsToEdges(id)) else {
-            return Either::Left(core::iter::empty());
-        };
-
-        Either::Right(
-            bitmap
-                .iter()
-                .map(|value| EdgeId::from_id(EntryId::new_unchecked(value))),
-        )
-    }
-
-    pub(crate) fn edges(&self, id: NodeId) -> impl Iterator<Item = EdgeId> + 'a {
-        let Some(left) = self.storage.inner.get(&Key::SourceToEdges(id)) else {
-            return Either::Left(core::iter::empty());
-        };
-
-        let Some(right) = self.storage.inner.get(&Key::TargetsToEdges(id)) else {
-            return Either::Right(Either::Left(
-                left.iter()
-                    .map(|value| EdgeId::from_id(EntryId::new_unchecked(value))),
-            ));
-        };
-
-        Either::Right(Either::Right(
-            UnionIterator::new(left, right)
-                .map(|value| EdgeId::from_id(EntryId::new_unchecked(value))),
-        ))
-    }
-
-    pub(crate) fn externals(&self) -> impl Iterator<Item = NodeId> + 'a {
-        self.storage.nodes.iter().filter_map(|index| {
-            let id = NodeId::from_id(EntryId::new_unchecked(index));
-
-            let has_source_to_targets = self
-                .storage
-                .inner
-                .get(&Key::SourceToTargets(id))
-                .map_or(false, |bitmap| !bitmap.is_empty());
-
-            let has_target_to_sources = self
-                .storage
-                .inner
-                .get(&Key::TargetToSources(id))
-                .map_or(false, |bitmap| !bitmap.is_empty());
-
-            let is_external = !has_source_to_targets && !has_target_to_sources;
-
-            is_external.then_some(id)
-        })
-    }
-}
-
-pub(crate) struct EdgeClosure<'a> {
-    storage: &'a ClosureStorage,
-}
-
-impl<'a> EdgeClosure<'a> {
-    const fn new(storage: &'a ClosureStorage) -> Self {
-        Self { storage }
-    }
-
-    pub(crate) fn endpoints_to_edges(
-        &self,
-        source: NodeId,
-        target: NodeId,
-    ) -> impl Iterator<Item = EdgeId> + 'a {
-        let Some(bitmap) = self
-            .storage
-            .inner
-            .get(&Key::EndpointsToEdges(source, target))
-        else {
-            return Either::Left(core::iter::empty());
-        };
-
-        Either::Right(
-            bitmap
-                .iter()
-                .map(|value| EdgeId::from_id(EntryId::new_unchecked(value))),
-        )
-    }
-
-    pub(crate) fn undirected_endpoints_to_edges(
-        &self,
-        source: NodeId,
-        target: NodeId,
-    ) -> impl Iterator<Item = EdgeId> + 'a {
-        let Some(source_to_targets) = self
-            .storage
-            .inner
-            .get(&Key::EndpointsToEdges(source, target))
-        else {
-            return Either::Left(core::iter::empty());
-        };
-
-        let Some(target_to_sources) = self
-            .storage
-            .inner
-            .get(&Key::EndpointsToEdges(target, source))
-        else {
-            return Either::Right(Either::Right(
-                source_to_targets
-                    .iter()
-                    .map(|value| EdgeId::from_id(EntryId::new_unchecked(value))),
-            ));
-        };
-
-        Either::Right(Either::Left(
-            UnionIterator::new(source_to_targets, target_to_sources)
-                .map(|value| EdgeId::from_id(EntryId::new_unchecked(value))),
-        ))
-    }
-}
-
-#[derive(Debug, Clone, PartialEq)]
-pub(crate) struct Closures {
-    storage: ClosureStorage,
-}
+#[derive(Debug, Copy, Clone, PartialEq)]
+pub(crate) struct Closures;
 
 impl Closures {
-    pub(crate) fn new() -> Self {
-        Self {
-            storage: ClosureStorage::new(),
+    pub(crate) fn create_edge<T, U>(edge: &Edge<T>, nodes: &mut NodeSlab<U>) {
+        let source = edge.source;
+        let target = edge.target;
+
+        if let Some(source) = nodes.get_mut(source) {
+            source.closures.insert_outgoing_node(target);
+            source.closures.insert_outgoing_edge(edge.id);
+        }
+
+        if let Some(target) = nodes.get_mut(target) {
+            target.closures.insert_incoming_node(source);
+            target.closures.insert_incoming_edge(edge.id);
         }
     }
 
-    pub(crate) const fn nodes(&self) -> NodeClosure<'_> {
-        NodeClosure::new(&self.storage)
-    }
+    fn has_multiple_edges<T, U>(edge: &Edge<T>, nodes: &NodeSlab<U>) -> bool {
+        let source = edge.source;
+        let target = edge.target;
 
-    pub(crate) fn create_node<T>(&mut self, node: &Node<T>) {
-        self.storage.create_node(node);
-    }
-
-    pub(crate) fn remove_node<T>(&mut self, node: &Node<T>) {
-        self.storage.remove_node(node);
-    }
-
-    pub(crate) const fn edges(&self) -> EdgeClosure<'_> {
-        EdgeClosure::new(&self.storage)
-    }
-
-    pub(crate) fn create_edge<T>(&mut self, edge: &Edge<T>) {
-        self.storage.create_edge(edge);
-    }
-
-    pub(crate) fn remove_edge<T>(&mut self, edge: &Edge<T>) {
-        self.storage.remove_edge(edge);
-    }
-
-    /// Drain the `SourceToTargets` and `TargetToSources` entries for the given node
-    ///
-    /// Returns an iterator of all edges and ensures that there are no duplicates.
-    ///
-    /// # Note
-    ///
-    /// To completely remove the edge you also need to call `remove_edge`.
-    /// This leaves the closure table in an incomplete (although recoverable) state, use
-    /// `remove_node` to completely remove a node, or call `refresh` to rebuild the closure
-    /// table.
-    pub(crate) fn drain_edges(&mut self, node: NodeId) -> impl Iterator<Item = EdgeId> {
-        let left = self.storage.inner.remove(&Key::SourceToEdges(node));
-        let right = self.storage.inner.remove(&Key::TargetsToEdges(node));
-
-        let iter = match (left, right) {
-            (None, None) => Either::Left(core::iter::empty()),
-            (Some(left), None) => Either::Right(Either::Left(left.into_iter())),
-            (None, Some(right)) => Either::Right(Either::Left(right.into_iter())),
-            (Some(left), Some(right)) => {
-                Either::Right(Either::Right(UnionIntoIterator::new(left, right)))
-            }
+        let Some(source) = nodes.get(source) else {
+            return false;
+        };
+        let Some(target) = nodes.get(target) else {
+            return false;
         };
 
-        iter.map(|id| EdgeId::from_id(EntryId::new_unchecked(id)))
+        // multi means more than one
+        let mut iter = source.closures.edges_between_directed(&target.closures);
+
+        // advance twice, instead of `.count()` this will be faster
+        if iter.next().is_some() {
+            iter.next().is_some()
+        } else {
+            false
+        }
     }
 
-    pub(crate) fn reserve(&mut self, additional: usize) {
-        self.storage.reserve(additional);
+    pub(crate) fn remove_edge<T, U>(edge: &Edge<T>, nodes: &mut NodeSlab<U>) {
+        let has_multiple = Self::has_multiple_edges(edge, nodes);
+
+        if let Some(source) = nodes.get_mut(edge.source) {
+            source.closures.remove_outgoing_edge(edge.id);
+
+            if !has_multiple {
+                source.closures.remove_outgoing_node(edge.target);
+            }
+        }
+
+        if let Some(target) = nodes.get_mut(edge.target) {
+            target.closures.remove_incoming_edge(edge.id);
+
+            if !has_multiple {
+                target.closures.remove_incoming_node(edge.source);
+            }
+        }
     }
 
-    pub(crate) fn shrink_to_fit(&mut self) {
-        self.storage.shrink_to_fit();
+    /// Removes the node from the graph.
+    ///
+    /// You must ensure that the node is not connected to any other node.
+    ///
+    /// (meaning you must call `remove_edge` for all edges connected to this node)
+    pub(crate) fn remove_node<T>(node: Node<T>, nodes: &mut NodeSlab<T>) -> (NodeId, T) {
+        let targets = node.closures.outgoing_nodes();
+        for target in targets {
+            let Some(target) = nodes.get_mut(target) else {
+                continue;
+            };
+
+            target.closures.remove_incoming_node(node.id);
+        }
+
+        let sources = node.closures.incoming_nodes();
+        for source in sources {
+            let Some(source) = nodes.get_mut(source) else {
+                continue;
+            };
+
+            source.closures.remove_outgoing_node(node.id);
+        }
+
+        (node.id, node.weight)
     }
 
-    pub(crate) fn refresh<N, E>(
-        &mut self,
-        nodes: &Slab<NodeId, Node<N>>,
-        edges: &Slab<EdgeId, Edge<E>>,
-    ) {
-        self.storage.refresh(nodes, edges);
+    pub(crate) fn clear<N>(nodes: &mut NodeSlab<N>) {
+        for node in nodes.iter_mut() {
+            node.closures.clear();
+        }
     }
 
-    pub(crate) fn clear(&mut self) {
-        self.storage.clear();
+    pub(crate) fn refresh<N, E>(nodes: &mut NodeSlab<N>, edges: &EdgeSlab<E>) {
+        Self::clear(nodes);
+
+        for edge in edges.iter() {
+            Self::create_edge(edge, nodes);
+        }
     }
 }
 
@@ -450,12 +115,13 @@
     use core::iter::once;
 
     use hashbrown::{HashMap, HashSet};
-    use petgraph_core::{attributes::Attributes, edge::marker::Directed};
+    use petgraph_core::{
+        attributes::Attributes, edge::marker::Directed, GraphDirectionality, GraphStorage,
+    };
 
     use crate::{
-        closure::{Closures, Key},
         slab::{EntryId, Key as _},
-        DinoGraph, EdgeId, NodeId,
+        DinoGraph, DinoStorage, EdgeId, NodeId,
     };
 
     #[derive(Debug, Clone, PartialEq, Eq)]
@@ -472,19 +138,19 @@
     }
 
     impl EvaluatedNodeClosure {
-        fn new(closures: &Closures, id: NodeId) -> Self {
-            let lookup = closures.nodes();
+        fn new<N, E>(storage: &DinoStorage<N, E>, id: NodeId) -> Self {
+            let node = storage.nodes.get(id).expect("node not found");
 
             Self {
-                outgoing_neighbours: lookup.outgoing_neighbours(id).collect(),
-                incoming_neighbours: lookup.incoming_neighbours(id).collect(),
+                outgoing_neighbours: node.closures.outgoing_nodes().collect(),
+                incoming_neighbours: node.closures.incoming_nodes().collect(),
 
-                neighbours: lookup.neighbours(id).collect(),
+                neighbours: node.closures.neighbours().collect(),
 
-                outgoing_edges: lookup.outgoing_edges(id).collect(),
-                incoming_edges: lookup.incoming_edges(id).collect(),
+                outgoing_edges: node.closures.outgoing_edges().collect(),
+                incoming_edges: node.closures.incoming_edges().collect(),
 
-                edges: lookup.edges(id).collect(),
+                edges: node.closures.edges().collect(),
             }
         }
     }
@@ -501,83 +167,46 @@
     }
 
     impl EvaluatedEdgeClosures {
-        fn new(closures: &Closures) -> Self {
+        fn new<N, E>(storage: &DinoStorage<N, E>) -> Self {
             Self {
-                source_to_targets: closures
-                    .storage
-                    .inner
-                    .iter()
-                    .filter_map(|(key, bitmap)| match key {
-                        Key::SourceToTargets(id) => Some((
-                            *id,
-                            bitmap
-                                .iter()
-                                .map(|id| NodeId::from_id(EntryId::new_unchecked(id)))
-                                .collect::<HashSet<_>>(),
-                        )),
-                        _ => None,
-                    })
+                source_to_targets: storage
+                    .nodes
+                    .entries()
+                    .map(|(id, node)| (id, node.closures.outgoing_nodes().collect()))
                     .collect(),
-                target_to_sources: closures
-                    .storage
-                    .inner
-                    .iter()
-                    .filter_map(|(key, bitmap)| match key {
-                        Key::TargetToSources(id) => Some((
-                            *id,
-                            bitmap
-                                .iter()
-                                .map(|id| NodeId::from_id(EntryId::new_unchecked(id)))
-                                .collect::<HashSet<_>>(),
-                        )),
-                        _ => None,
-                    })
+                target_to_sources: storage
+                    .nodes
+                    .entries()
+                    .map(|(id, node)| (id, node.closures.incoming_nodes().collect()))
                     .collect(),
 
-                source_to_edges: closures
-                    .storage
-                    .inner
-                    .iter()
-                    .filter_map(|(key, bitmap)| match key {
-                        Key::SourceToEdges(id) => Some((
-                            *id,
-                            bitmap
-                                .iter()
-                                .map(|id| EdgeId::from_id(EntryId::new_unchecked(id)))
-                                .collect::<HashSet<_>>(),
-                        )),
-                        _ => None,
-                    })
+                source_to_edges: storage
+                    .nodes
+                    .entries()
+                    .map(|(id, node)| (id, node.closures.outgoing_edges().collect()))
                     .collect(),
-                targets_to_edges: closures
-                    .storage
-                    .inner
-                    .iter()
-                    .filter_map(|(key, bitmap)| match key {
-                        Key::TargetsToEdges(id) => Some((
-                            *id,
-                            bitmap
-                                .iter()
-                                .map(|id| EdgeId::from_id(EntryId::new_unchecked(id)))
-                                .collect::<HashSet<_>>(),
-                        )),
-                        _ => None,
-                    })
+                targets_to_edges: storage
+                    .nodes
+                    .entries()
+                    .map(|(id, node)| (id, node.closures.incoming_edges().collect()))
                     .collect(),
 
-                endpoints_to_edges: closures
-                    .storage
-                    .inner
+                endpoints_to_edges: storage
+                    .nodes
                     .iter()
-                    .filter_map(|(key, bitmap)| match key {
-                        Key::EndpointsToEdges(source, target) => Some((
-                            (*source, *target),
-                            bitmap
-                                .iter()
-                                .map(|id| EdgeId::from_id(EntryId::new_unchecked(id)))
+                    .flat_map(|source| {
+                        source.closures.outgoing_nodes().map(move |target| {
+                            (source, storage.nodes.get(target).expect("node available"))
+                        })
+                    })
+                    .map(|(source, target)| {
+                        (
+                            (source.id, target.id),
+                            source
+                                .closures
+                                .edges_between_directed(&target.closures)
                                 .collect::<HashSet<_>>(),
-                        )),
-                        _ => None,
+                        )
                     })
                     .collect(),
             }
@@ -599,16 +228,6 @@
         }};
     }
 
-    fn assert_storage_size(closure: &Closures, expected_nodes: usize, expected_endpoints: usize) {
-        // expected_nodes * (SourceToTargets + TargetToSources + SourceToEdges + TargetToEdges)
-        // + expected_endpoints * EndpointsToEdges
-
-        assert_eq!(
-            closure.storage.inner.len(),
-            4 * expected_nodes + expected_endpoints
-        );
-    }
-
     #[test]
     fn single_node() {
         let mut graph = DinoGraph::<u8, u8, Directed>::new();
@@ -616,16 +235,10 @@
         let node = graph.try_insert_node(1).unwrap();
         let id = *node.id();
 
-        let closures = &graph.storage().closures;
-
-        assert_storage_size(closures, 1, 0);
-        assert_eq!(
-            closures.nodes().externals().collect::<HashSet<_>>(),
-            once(id).collect()
-        );
+        assert_eq!(isolated(&graph), once(id).collect());
 
         assert_eq!(
-            EvaluatedNodeClosure::new(closures, id),
+            EvaluatedNodeClosure::new(graph.storage(), id),
             EvaluatedNodeClosure {
                 outgoing_neighbours: HashSet::new(),
                 incoming_neighbours: HashSet::new(),
@@ -637,7 +250,7 @@
         );
 
         assert_eq!(
-            EvaluatedEdgeClosures::new(closures),
+            EvaluatedEdgeClosures::new(graph.storage()),
             EvaluatedEdgeClosures {
                 source_to_targets: map! {
                     id => HashSet::new(),
@@ -656,6 +269,18 @@
         );
     }
 
+    fn isolated<N, E, D>(graph: &DinoGraph<N, E, D>) -> HashSet<NodeId>
+    where
+        D: GraphDirectionality,
+    {
+        graph
+            .storage()
+            .nodes
+            .entries()
+            .filter_map(|(id, node)| node.closures.is_isolated().then_some(id))
+            .collect()
+    }
+
     #[test]
     fn multiple_nodes() {
         let mut graph = DinoGraph::<u8, u8, Directed>::new();
@@ -666,16 +291,10 @@
         let b = graph.try_insert_node(Attributes::new(2)).unwrap();
         let b = *b.id();
 
-        let closures = &graph.storage().closures;
-
-        assert_storage_size(closures, 2, 0);
-        assert_eq!(
-            closures.nodes().externals().collect::<HashSet<_>>(),
-            [a, b].into_iter().collect()
-        );
+        assert_eq!(isolated(&graph), [a, b].into_iter().collect());
 
         assert_eq!(
-            EvaluatedNodeClosure::new(closures, a),
+            EvaluatedNodeClosure::new(graph.storage(), a),
             EvaluatedNodeClosure {
                 outgoing_neighbours: HashSet::new(),
                 incoming_neighbours: HashSet::new(),
@@ -687,7 +306,7 @@
         );
 
         assert_eq!(
-            EvaluatedNodeClosure::new(closures, b),
+            EvaluatedNodeClosure::new(graph.storage(), b),
             EvaluatedNodeClosure {
                 outgoing_neighbours: HashSet::new(),
                 incoming_neighbours: HashSet::new(),
@@ -699,7 +318,7 @@
         );
 
         assert_eq!(
-            EvaluatedEdgeClosures::new(closures),
+            EvaluatedEdgeClosures::new(graph.storage()),
             EvaluatedEdgeClosures {
                 source_to_targets: map! {
                     a => HashSet::new(),
@@ -735,13 +354,10 @@
         let edge = graph.try_insert_edge(1u8, &a, &b).unwrap();
         let edge = *edge.id();
 
-        let closures = &graph.storage().closures;
-
-        assert_storage_size(closures, 2, 1);
-        assert_eq!(closures.nodes().externals().count(), 0);
+        assert!(isolated(&graph).is_empty());
 
         assert_eq!(
-            EvaluatedNodeClosure::new(closures, a),
+            EvaluatedNodeClosure::new(graph.storage(), a),
             EvaluatedNodeClosure {
                 outgoing_neighbours: once(b).collect(),
                 incoming_neighbours: HashSet::new(),
@@ -753,7 +369,7 @@
         );
 
         assert_eq!(
-            EvaluatedNodeClosure::new(closures, b),
+            EvaluatedNodeClosure::new(graph.storage(), b),
             EvaluatedNodeClosure {
                 outgoing_neighbours: HashSet::new(),
                 incoming_neighbours: once(a).collect(),
@@ -765,7 +381,7 @@
         );
 
         assert_eq!(
-            EvaluatedEdgeClosures::new(closures),
+            EvaluatedEdgeClosures::new(graph.storage()),
             EvaluatedEdgeClosures {
                 source_to_targets: map! {
                     a => once(b).collect(),
@@ -800,13 +416,10 @@
         let edge = graph.try_insert_edge(1u8, &a, &a).unwrap();
         let edge = *edge.id();
 
-        let closures = &graph.storage().closures;
-
-        assert_storage_size(closures, 1, 1);
-        assert_eq!(closures.nodes().externals().count(), 0);
+        assert!(isolated(&graph).is_empty());
 
         assert_eq!(
-            EvaluatedNodeClosure::new(closures, a),
+            EvaluatedNodeClosure::new(graph.storage(), a),
             EvaluatedNodeClosure {
                 outgoing_neighbours: once(a).collect(),
                 incoming_neighbours: once(a).collect(),
@@ -818,7 +431,7 @@
         );
 
         assert_eq!(
-            EvaluatedEdgeClosures::new(closures),
+            EvaluatedEdgeClosures::new(graph.storage()),
             EvaluatedEdgeClosures {
                 source_to_targets: map! {
                     a => once(a).collect(),
@@ -897,13 +510,10 @@
 
             let (a, b, c, ab, bc, ca) = (*a, *b, *c, *ab, *bc, *ca);
 
-            let closures = &graph.storage().closures;
-
-            assert_storage_size(closures, 3, 3);
-            assert_eq!(closures.nodes().externals().count(), 0);
+            assert!(isolated(&graph).is_empty());
 
             assert_eq!(
-                EvaluatedNodeClosure::new(closures, a),
+                EvaluatedNodeClosure::new(graph.storage(), a),
                 EvaluatedNodeClosure {
                     outgoing_neighbours: once(b).collect(),
                     incoming_neighbours: once(c).collect(),
@@ -915,7 +525,7 @@
             );
 
             assert_eq!(
-                EvaluatedNodeClosure::new(closures, b),
+                EvaluatedNodeClosure::new(graph.storage(), b),
                 EvaluatedNodeClosure {
                     outgoing_neighbours: once(c).collect(),
                     incoming_neighbours: once(a).collect(),
@@ -927,7 +537,7 @@
             );
 
             assert_eq!(
-                EvaluatedNodeClosure::new(closures, c),
+                EvaluatedNodeClosure::new(graph.storage(), c),
                 EvaluatedNodeClosure {
                     outgoing_neighbours: once(a).collect(),
                     incoming_neighbours: once(b).collect(),
@@ -939,7 +549,7 @@
             );
 
             assert_eq!(
-                EvaluatedEdgeClosures::new(closures),
+                EvaluatedEdgeClosures::new(graph.storage()),
                 EvaluatedEdgeClosures {
                     source_to_targets: map! {
                         a => once(b).collect(),
@@ -993,13 +603,10 @@
         let ab2 = graph.try_insert_edge(1u8, &a, &b).unwrap();
         let ab2 = *ab2.id();
 
-        let closures = &graph.storage().closures;
-
-        assert_storage_size(closures, 2, 1);
-        assert_eq!(closures.nodes().externals().count(), 0);
+        assert!(isolated(&graph).is_empty());
 
         assert_eq!(
-            EvaluatedNodeClosure::new(closures, a),
+            EvaluatedNodeClosure::new(graph.storage(), a),
             EvaluatedNodeClosure {
                 outgoing_neighbours: once(b).collect(),
                 incoming_neighbours: HashSet::new(),
@@ -1011,7 +618,7 @@
         );
 
         assert_eq!(
-            EvaluatedNodeClosure::new(closures, b),
+            EvaluatedNodeClosure::new(graph.storage(), b),
             EvaluatedNodeClosure {
                 outgoing_neighbours: HashSet::new(),
                 incoming_neighbours: once(a).collect(),
@@ -1023,7 +630,7 @@
         );
 
         assert_eq!(
-            EvaluatedEdgeClosures::new(closures),
+            EvaluatedEdgeClosures::new(graph.storage()),
             EvaluatedEdgeClosures {
                 source_to_targets: map! {
                     a => once(b).collect(),
@@ -1064,13 +671,10 @@
 
         graph.remove_node(&b).unwrap();
 
-        let closures = &graph.storage().closures;
-
-        assert_storage_size(closures, 2, 1);
-        assert_eq!(closures.nodes().externals().count(), 0);
+        assert!(isolated(&graph).is_empty());
 
         assert_eq!(
-            EvaluatedNodeClosure::new(closures, a),
+            EvaluatedNodeClosure::new(graph.storage(), a),
             EvaluatedNodeClosure {
                 outgoing_neighbours: HashSet::new(),
                 incoming_neighbours: once(c).collect(),
@@ -1082,7 +686,7 @@
         );
 
         assert_eq!(
-            EvaluatedNodeClosure::new(closures, c),
+            EvaluatedNodeClosure::new(graph.storage(), c),
             EvaluatedNodeClosure {
                 outgoing_neighbours: once(a).collect(),
                 incoming_neighbours: HashSet::new(),
@@ -1094,7 +698,7 @@
         );
 
         assert_eq!(
-            EvaluatedEdgeClosures::new(closures),
+            EvaluatedEdgeClosures::new(graph.storage()),
             EvaluatedEdgeClosures {
                 source_to_targets: map! {
                     a => HashSet::new(),
@@ -1136,13 +740,10 @@
 
         graph.remove_edge(&bc).unwrap();
 
-        let closures = &graph.storage().closures;
-
-        assert_storage_size(closures, 3, 2);
-        assert_eq!(closures.nodes().externals().count(), 0);
+        assert!(isolated(&graph).is_empty());
 
         assert_eq!(
-            EvaluatedNodeClosure::new(closures, a),
+            EvaluatedNodeClosure::new(graph.storage(), a),
             EvaluatedNodeClosure {
                 outgoing_neighbours: once(b).collect(),
                 incoming_neighbours: once(c).collect(),
@@ -1154,7 +755,7 @@
         );
 
         assert_eq!(
-            EvaluatedNodeClosure::new(closures, b),
+            EvaluatedNodeClosure::new(graph.storage(), b),
             EvaluatedNodeClosure {
                 outgoing_neighbours: HashSet::new(),
                 incoming_neighbours: once(a).collect(),
@@ -1166,7 +767,7 @@
         );
 
         assert_eq!(
-            EvaluatedNodeClosure::new(closures, c),
+            EvaluatedNodeClosure::new(graph.storage(), c),
             EvaluatedNodeClosure {
                 outgoing_neighbours: once(a).collect(),
                 incoming_neighbours: HashSet::new(),
@@ -1178,7 +779,7 @@
         );
 
         assert_eq!(
-            EvaluatedEdgeClosures::new(closures),
+            EvaluatedEdgeClosures::new(graph.storage()),
             EvaluatedEdgeClosures {
                 source_to_targets: map! {
                     a => once(b).collect(),
diff --git a/crates/dino/src/closure/union.rs b/crates/dino/src/closure/union.rs
deleted file mode 100644
index 24c6a0f..0000000
--- a/crates/dino/src/closure/union.rs
+++ /dev/null
@@ -1,203 +0,0 @@
-use roaring::RoaringBitmap;
-
-#[derive(Default)]
-struct IteratorState {
-    left_next: Option<u32>,
-    right_next: Option<u32>,
-
-    last: Option<u32>,
-}
-
-impl IteratorState {
-    fn next(
-        &mut self,
-        left: &mut impl Iterator<Item = u32>,
-        right: &mut impl Iterator<Item = u32>,
-    ) -> Option<u32> {
-        // a and b originate from `RoaringBitmap::iter`, which is guaranteed to be sorted, this
-        // simplifies the logic needed here a lot.
-        // We only want to return all unique elements from both iterators.
-
-        // The algorithm is pretty simple.
-        // 1) get the last element from each iterator, but only if it is larger than the last
-        //    element we returned
-        // 2) return the smaller of the two elements
-        // 3) set the last element to the element we just returned
-        const fn is_greater_than_or_equal(left: Option<u32>, right: Option<u32>) -> bool {
-            match (left, right) {
-                (Some(last), Some(next)) => last >= next,
-                // `None` can occur if the last iteration chose the value of the right side,
-                // therefore we continue.
-                // `None` on the left side means, meaning we
-                // can stop and take the value.
-                (_, None) => true,
-                (None, _) => false,
-            }
-        }
-
-        let last = self.last.take();
-
-        let mut left_next = self.left_next.take();
-        let mut right_next = self.right_next.take();
-
-        // Find a value that is larger than the last value we returned.
-        // `last >= left_next`
-        while is_greater_than_or_equal(last, left_next) {
-            let Some(next) = left.next() else {
-                left_next = None;
-                break;
-            };
-
-            left_next = Some(next);
-        }
-
-        // Find a value that is larger than the last value we returned.
-        // `last >= right_next`
-        while is_greater_than_or_equal(last, right_next) {
-            let Some(next) = right.next() else {
-                right_next = None;
-                break;
-            };
-
-            right_next = Some(next);
-        }
-
-        let next = match (left_next, right_next) {
-            (Some(a), Some(b)) => {
-                if a < b {
-                    self.right_next = Some(b);
-                    Some(a)
-                } else {
-                    self.left_next = Some(a);
-                    Some(b)
-                }
-            }
-            (Some(a), None) => Some(a),
-            (None, Some(b)) => Some(b),
-            (None, None) => None,
-        };
-
-        self.last = next;
-
-        next
-    }
-}
-
-pub(crate) struct UnionIntoIterator {
-    left: roaring::bitmap::IntoIter,
-    right: roaring::bitmap::IntoIter,
-
-    state: IteratorState,
-}
-
-impl UnionIntoIterator {
-    pub(crate) fn new(left: RoaringBitmap, right: RoaringBitmap) -> Self {
-        Self {
-            left: left.into_iter(),
-            right: right.into_iter(),
-
-            state: IteratorState::default(),
-        }
-    }
-}
-
-impl Iterator for UnionIntoIterator {
-    type Item = u32;
-
-    fn next(&mut self) -> Option<Self::Item> {
-        self.state.next(&mut self.left, &mut self.right)
-    }
-}
-
-pub(crate) struct UnionIterator<'a> {
-    left: roaring::bitmap::Iter<'a>,
-    right: roaring::bitmap::Iter<'a>,
-
-    state: IteratorState,
-}
-
-impl<'a> UnionIterator<'a> {
-    pub(crate) fn new(left: &'a RoaringBitmap, right: &'a RoaringBitmap) -> Self {
-        let left = left.iter();
-        let right = right.iter();
-
-        Self {
-            left,
-            right,
-
-            state: IteratorState::default(),
-        }
-    }
-}
-
-impl Iterator for UnionIterator<'_> {
-    type Item = u32;
-
-    fn next(&mut self) -> Option<Self::Item> {
-        self.state.next(&mut self.left, &mut self.right)
-    }
-}
-
-#[cfg(test)]
-mod tests {
-    use alloc::vec::Vec;
-
-    use roaring::RoaringBitmap;
-
-    use crate::closure::union::{UnionIntoIterator, UnionIterator};
-
-    #[test]
-    fn empty() {
-        let a = RoaringBitmap::new();
-        let b = RoaringBitmap::new();
-
-        let iterator = UnionIterator::new(&a, &b);
-        assert_eq!(iterator.count(), 0);
-
-        let iterator = UnionIntoIterator::new(a, b);
-        assert_eq!(iterator.count(), 0);
-    }
-
-    #[test]
-    fn non_overlapping() {
-        let a = RoaringBitmap::from_sorted_iter(0..10).unwrap();
-        let b = RoaringBitmap::from_sorted_iter(10..20).unwrap();
-
-        let iterator = UnionIterator::new(&a, &b);
-        assert_eq!(iterator.collect::<Vec<_>>(), (0..20).collect::<Vec<_>>());
-
-        let iterator = UnionIntoIterator::new(a, b);
-        assert_eq!(iterator.collect::<Vec<_>>(), (0..20).collect::<Vec<_>>());
-    }
-
-    #[test]
-    fn overlapping() {
-        let a = RoaringBitmap::from_sorted_iter(0..10).unwrap();
-        let b = RoaringBitmap::from_sorted_iter(5..15).unwrap();
-
-        let iterator = UnionIterator::new(&a, &b);
-        assert_eq!(iterator.collect::<Vec<_>>(), (0..15).collect::<Vec<_>>());
-
-        let iterator = UnionIntoIterator::new(a, b);
-        assert_eq!(iterator.collect::<Vec<_>>(), (0..15).collect::<Vec<_>>());
-    }
-
-    #[test]
-    fn multiple_overlapping_regions() {
-        let mut a = RoaringBitmap::from_sorted_iter(0..10).unwrap();
-        let mut b = RoaringBitmap::from_sorted_iter(5..15).unwrap();
-
-        a.insert_range(20..30);
-        b.insert_range(25..35);
-
-        a.insert_range(40..50);
-        b.insert_range(15..21);
-        b.insert_range(29..42);
-
-        let iterator = UnionIterator::new(&a, &b);
-        assert_eq!(iterator.collect::<Vec<_>>(), (0..50).collect::<Vec<_>>());
-
-        let iterator = UnionIntoIterator::new(a, b);
-        assert_eq!(iterator.collect::<Vec<_>>(), (0..50).collect::<Vec<_>>());
-    }
-}
diff --git a/crates/dino/src/closure/unique_vec.rs b/crates/dino/src/closure/unique_vec.rs
new file mode 100644
index 0000000..a2a8e0e
--- /dev/null
+++ b/crates/dino/src/closure/unique_vec.rs
@@ -0,0 +1,95 @@
+use alloc::vec::Vec;
+use core::slice;
+
+#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
+pub(crate) struct UniqueVec<T>(Vec<T>);
+
+impl<T> UniqueVec<T>
+where
+    T: Ord,
+{
+    pub(crate) const fn new() -> Self {
+        Self(Vec::new())
+    }
+
+    pub(crate) fn insert(&mut self, node: T) {
+        let Err(index) = self.0.binary_search(&node) else {
+            return;
+        };
+
+        self.0.insert(index, node);
+    }
+
+    pub(crate) fn remove(&mut self, node: &T) {
+        let Ok(index) = self.0.binary_search(node) else {
+            return;
+        };
+
+        self.0.remove(index);
+    }
+
+    pub(crate) fn clear(&mut self) {
+        self.0.clear();
+    }
+
+    pub(crate) fn iter(&self) -> slice::Iter<'_, T> {
+        self.0.iter()
+    }
+
+    pub(crate) fn is_empty(&self) -> bool {
+        self.0.is_empty()
+    }
+}
+
+impl<T> IntoIterator for UniqueVec<T> {
+    type IntoIter = alloc::vec::IntoIter<T>;
+    type Item = T;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.0.into_iter()
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use alloc::vec;
+
+    #[test]
+    fn insert_sorted() {
+        let mut vec = super::UniqueVec::new();
+
+        vec.insert(1);
+        vec.insert(2);
+        vec.insert(3);
+        vec.insert(4);
+        vec.insert(5);
+
+        assert_eq!(vec.0, vec![1, 2, 3, 4, 5]);
+    }
+
+    #[test]
+    fn insert_unsorted() {
+        let mut vec = super::UniqueVec::new();
+
+        vec.insert(5);
+        vec.insert(4);
+        vec.insert(3);
+        vec.insert(2);
+        vec.insert(1);
+
+        assert_eq!(vec.0, vec![1, 2, 3, 4, 5]);
+    }
+
+    #[test]
+    fn insert_duplicates() {
+        let mut vec = super::UniqueVec::new();
+
+        vec.insert(1);
+        vec.insert(1);
+        vec.insert(1);
+        vec.insert(1);
+        vec.insert(1);
+
+        assert_eq!(vec.0, vec![1]);
+    }
+}
diff --git a/crates/dino/src/directed.rs b/crates/dino/src/directed.rs
index 9e774aa..7ae82ac 100644
--- a/crates/dino/src/directed.rs
+++ b/crates/dino/src/directed.rs
@@ -5,103 +5,119 @@
     storage::{DirectedGraphStorage, GraphStorage},
 };
 
-use crate::{DinoStorage, Directed};
+use crate::{
+    iter::directed::NodeDirectedConnectionsIter,
+    node::{NodeClosures, NodeSlab},
+    DinoStorage, Directed, EdgeId, NodeId,
+};
+
+fn directed_edges_between<N>(
+    nodes: &NodeSlab<N>,
+    source: NodeId,
+    target: NodeId,
+) -> impl Iterator<Item = EdgeId> + '_ {
+    let source = nodes.get(source);
+    let target = nodes.get(target);
+
+    source
+        .and_then(|source| target.map(|target| (source, target)))
+        .into_iter()
+        .flat_map(|(source, target)| source.closures.edges_between_directed(&target.closures))
+}
 
 impl<N, E> DirectedGraphStorage for DinoStorage<N, E, Directed> {
-    fn directed_edges_between<'a: 'b, 'b>(
-        &'a self,
-        source: &'b Self::NodeId,
-        target: &'b Self::NodeId,
-    ) -> impl Iterator<Item = Edge<'a, Self>> + 'b {
-        self.closures
-            .edges()
-            .endpoints_to_edges(*source, *target)
-            .filter_map(|id| self.edge(&id))
+    fn directed_edges_between(
+        &self,
+        source: Self::NodeId,
+        target: Self::NodeId,
+    ) -> impl Iterator<Item = Edge<Self>> {
+        directed_edges_between(&self.nodes, source, target).filter_map(move |id| self.edge(id))
     }
 
-    fn directed_edges_between_mut<'a: 'b, 'b>(
-        &'a mut self,
-        source: &'b Self::NodeId,
-        target: &'b Self::NodeId,
-    ) -> impl Iterator<Item = EdgeMut<'a, Self>> + 'b {
-        let Self {
-            closures, edges, ..
-        } = self;
+    fn directed_edges_between_mut(
+        &mut self,
+        source: Self::NodeId,
+        target: Self::NodeId,
+    ) -> impl Iterator<Item = EdgeMut<Self>> {
+        let Self { edges, nodes, .. } = self;
 
-        let available = closures.edges().endpoints_to_edges(*source, *target);
+        let available = directed_edges_between(nodes, source, target);
 
         edges
             .filter_mut(available)
-            .map(|edge| EdgeMut::new(&edge.id, &mut edge.weight, &edge.source, &edge.target))
+            .map(|edge| EdgeMut::new(edge.id, &mut edge.weight, edge.source, edge.target))
     }
 
-    fn node_directed_connections<'a: 'b, 'b>(
-        &'a self,
-        id: &'b Self::NodeId,
+    fn node_directed_connections(
+        &self,
+        id: Self::NodeId,
         direction: Direction,
-    ) -> impl Iterator<Item = Edge<'a, Self>> + 'b {
-        let closure = self.closures.nodes();
-
-        match direction {
-            Direction::Incoming => Either::Left(closure.incoming_edges(*id)),
-            Direction::Outgoing => Either::Right(closure.outgoing_edges(*id)),
+    ) -> impl Iterator<Item = Edge<Self>> {
+        NodeDirectedConnectionsIter {
+            storage: self,
+            iter: self.nodes.get(id).map(|node| match direction {
+                Direction::Incoming => node.closures.incoming_edges(),
+                Direction::Outgoing => node.closures.outgoing_edges(),
+            }),
         }
-        .filter_map(move |id| self.edge(&id))
     }
 
-    fn node_directed_connections_mut<'a: 'b, 'b>(
-        &'a mut self,
-        id: &'b Self::NodeId,
+    fn node_directed_connections_mut(
+        &mut self,
+        id: Self::NodeId,
         direction: Direction,
-    ) -> impl Iterator<Item = EdgeMut<'a, Self>> + 'b {
-        let Self {
-            closures, edges, ..
-        } = self;
+    ) -> impl Iterator<Item = EdgeMut<Self>> {
+        let Self { nodes, edges, .. } = self;
 
-        let closure = closures.nodes();
-
-        let available = match direction {
-            Direction::Incoming => Either::Left(closure.incoming_edges(*id)),
-            Direction::Outgoing => Either::Right(closure.outgoing_edges(*id)),
-        };
+        let allow = nodes
+            .get(id)
+            .into_iter()
+            .flat_map(move |node| match direction {
+                Direction::Incoming => node.closures.incoming_edges(),
+                Direction::Outgoing => node.closures.outgoing_edges(),
+            });
 
         edges
-            .filter_mut(available)
-            .map(|edge| EdgeMut::new(&edge.id, &mut edge.weight, &edge.source, &edge.target))
+            .filter_mut(allow)
+            .map(|edge| EdgeMut::new(edge.id, &mut edge.weight, edge.source, edge.target))
     }
 
-    fn node_directed_neighbours<'a: 'b, 'b>(
-        &'a self,
-        id: &'b Self::NodeId,
+    fn node_directed_neighbours(
+        &self,
+        id: Self::NodeId,
         direction: Direction,
-    ) -> impl Iterator<Item = Node<'a, Self>> + 'b {
-        let closure = self.closures.nodes();
-
-        match direction {
-            Direction::Incoming => Either::Left(closure.incoming_neighbours(*id)),
-            Direction::Outgoing => Either::Right(closure.outgoing_neighbours(*id)),
-        }
-        .filter_map(move |id| self.node(&id))
+    ) -> impl Iterator<Item = Node<Self>> {
+        self.nodes
+            .get(id)
+            .into_iter()
+            .flat_map(move |node| match direction {
+                Direction::Incoming => node.closures.incoming_nodes(),
+                Direction::Outgoing => node.closures.outgoing_nodes(),
+            })
+            .filter_map(move |id| self.node(id))
     }
 
-    fn node_directed_neighbours_mut<'a: 'b, 'b>(
-        &'a mut self,
-        id: &'b Self::NodeId,
+    fn node_directed_neighbours_mut(
+        &mut self,
+        id: Self::NodeId,
         direction: Direction,
-    ) -> impl Iterator<Item = NodeMut<'a, Self>> + 'b {
-        let Self {
-            closures, nodes, ..
-        } = self;
-
-        let closure = closures.nodes();
-
-        let available = match direction {
-            Direction::Incoming => Either::Left(closure.incoming_neighbours(*id)),
-            Direction::Outgoing => Either::Right(closure.outgoing_neighbours(*id)),
+    ) -> impl Iterator<Item = NodeMut<Self>> {
+        let Some(node) = self.nodes.get(id) else {
+            return Either::Right(core::iter::empty());
         };
 
-        nodes
-            .filter_mut(available)
-            .map(|node| NodeMut::new(&node.id, &mut node.weight))
+        // SAFETY: we never access the closure argument mutably, only the weight.
+        // Therefore it is safe for us to access both at the same time.
+        let closure: &NodeClosures = unsafe { &*core::ptr::addr_of!(node.closures) };
+        let neighbours = match direction {
+            Direction::Incoming => closure.incoming_nodes(),
+            Direction::Outgoing => closure.outgoing_nodes(),
+        };
+
+        Either::Left(
+            self.nodes
+                .filter_mut(neighbours)
+                .map(move |node| NodeMut::new(node.id, &mut node.weight)),
+        )
     }
 }
diff --git a/crates/dino/src/edge.rs b/crates/dino/src/edge.rs
index 022e305..3442d2c 100644
--- a/crates/dino/src/edge.rs
+++ b/crates/dino/src/edge.rs
@@ -3,12 +3,15 @@
 use petgraph_core::{
     attributes::NoValue,
     edge::marker::GraphDirectionality,
-    id::{GraphId, LinearGraphId, ManagedGraphId},
+    id::{AssociativeGraphId, GraphId, LinearGraphId, ManagedGraphId},
 };
 
 use crate::{
     node::NodeId,
-    slab::{EntryId, Key, SlabIndexMapper},
+    slab::{
+        secondary::{SlabAttributeMapper, SlabBooleanMapper},
+        EntryId, Key, SlabIndexMapper,
+    },
     DinoStorage,
 };
 
@@ -45,10 +48,12 @@
 }
 
 impl Key for EdgeId {
+    #[inline]
     fn from_id(id: EntryId) -> Self {
         Self(id)
     }
 
+    #[inline]
     fn into_id(self) -> EntryId {
         self.0
     }
@@ -69,8 +74,26 @@
     }
 }
 
+impl<N, E, D> AssociativeGraphId<DinoStorage<N, E, D>> for EdgeId
+where
+    D: GraphDirectionality,
+{
+    type AttributeMapper<'a, V> = SlabAttributeMapper<'a, Self, V> where DinoStorage<N, E, D>: 'a;
+    type BooleanMapper<'a> = SlabBooleanMapper<'a> where DinoStorage<N, E, D>: 'a;
+
+    fn attribute_mapper<V>(storage: &DinoStorage<N, E, D>) -> Self::AttributeMapper<'_, V> {
+        SlabAttributeMapper::new(&storage.edges)
+    }
+
+    fn boolean_mapper(storage: &DinoStorage<N, E, D>) -> Self::BooleanMapper<'_> {
+        SlabBooleanMapper::new(&storage.edges)
+    }
+}
+
 impl ManagedGraphId for EdgeId {}
 
+pub(crate) type EdgeSlab<T> = crate::slab::Slab<EdgeId, Edge<T>>;
+
 #[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
 pub(crate) struct Edge<T> {
     pub(crate) id: EdgeId,
diff --git a/crates/dino/src/iter/closure.rs b/crates/dino/src/iter/closure.rs
new file mode 100644
index 0000000..b601da7
--- /dev/null
+++ b/crates/dino/src/iter/closure.rs
@@ -0,0 +1,311 @@
+use core::{cmp::Ordering, iter::Peekable};
+
+use crate::{node::NodeClosures, EdgeId, NodeId};
+
+pub(crate) type NodeIdClosureIter<'a> = core::iter::Copied<core::slice::Iter<'a, NodeId>>;
+pub(crate) type EdgeIdClosureIter<'a> = core::iter::Copied<core::slice::Iter<'a, EdgeId>>;
+
+/// Computes the union of two sorted iterators with unique elements.
+///
+/// The resulting iterator will contain all elements from both iterators, removing duplicates.
+struct UnionIterator<I, J>
+where
+    I: Iterator,
+    I::Item: Ord,
+    J: Iterator<Item = I::Item>,
+{
+    left: Peekable<I>,
+    right: Peekable<J>,
+}
+
+impl<I, J> UnionIterator<I, J>
+where
+    I: Iterator,
+    I::Item: Ord,
+    J: Iterator<Item = I::Item>,
+{
+    fn new(left: I, right: J) -> Self {
+        Self {
+            left: left.peekable(),
+            right: right.peekable(),
+        }
+    }
+}
+
+impl<I, J> Iterator for UnionIterator<I, J>
+where
+    I: Iterator,
+    I::Item: Ord,
+    J: Iterator<Item = I::Item>,
+{
+    type Item = I::Item;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let next_left = self.left.peek();
+        let next_right = self.right.peek();
+
+        match (next_left, next_right) {
+            (Some(a), Some(b)) => {
+                match a.cmp(b) {
+                    Ordering::Less => self.left.next(),
+                    Ordering::Greater => self.right.next(),
+                    Ordering::Equal => {
+                        // remove duplicates
+                        self.left.next();
+                        self.right.next()
+                    }
+                }
+            }
+            (Some(_), None) => self.left.next(),
+            (None, Some(_)) => self.right.next(),
+            (None, None) => None,
+        }
+    }
+}
+
+/// Computes the intersection of two sorted iterators with unique elements.
+///
+/// The resulting iterator will contain all elements that are present in both iterators.
+struct IntersectionIterator<I, J>
+where
+    I: Iterator,
+    I::Item: Ord,
+    J: Iterator<Item = I::Item>,
+{
+    left: Peekable<I>,
+    right: Peekable<J>,
+}
+
+impl<I, J> IntersectionIterator<I, J>
+where
+    I: Iterator,
+    I::Item: Ord,
+    J: Iterator<Item = I::Item>,
+{
+    fn new(left: I, right: J) -> Self {
+        Self {
+            left: left.peekable(),
+            right: right.peekable(),
+        }
+    }
+}
+
+impl<I, J> Iterator for IntersectionIterator<I, J>
+where
+    I: Iterator,
+    I::Item: Ord,
+    J: Iterator<Item = I::Item>,
+{
+    type Item = I::Item;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        loop {
+            // if either of them are exhausted the intersection is empty
+            let Some(next_left) = self.left.peek() else {
+                return None;
+            };
+            let Some(next_right) = self.right.peek() else {
+                return None;
+            };
+
+            match next_left.cmp(next_right) {
+                Ordering::Less => {
+                    // left is behind, advance it
+                    self.left.next();
+                }
+                Ordering::Greater => {
+                    // right is behind, advance it
+                    self.right.next();
+                }
+                Ordering::Equal => {
+                    // both are equal, advance both
+                    self.left.next();
+                    return self.right.next();
+                }
+            }
+        }
+    }
+}
+
+pub(crate) struct NeighbourIterator<'a>(
+    UnionIterator<NodeIdClosureIter<'a>, NodeIdClosureIter<'a>>,
+);
+
+impl<'a> NeighbourIterator<'a> {
+    pub(crate) fn new(
+        incoming_nodes: NodeIdClosureIter<'a>,
+        outgoing_nodes: NodeIdClosureIter<'a>,
+    ) -> Self {
+        Self(UnionIterator::new(incoming_nodes, outgoing_nodes))
+    }
+}
+
+impl<'a> Iterator for NeighbourIterator<'a> {
+    type Item = NodeId;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next()
+    }
+}
+
+pub(crate) struct EdgeIterator<'a>(UnionIterator<EdgeIdClosureIter<'a>, EdgeIdClosureIter<'a>>);
+
+impl<'a> EdgeIterator<'a> {
+    pub(crate) fn new(
+        incoming_edges: EdgeIdClosureIter<'a>,
+        outgoing_edges: EdgeIdClosureIter<'a>,
+    ) -> Self {
+        Self(UnionIterator::new(incoming_edges, outgoing_edges))
+    }
+}
+
+impl<'a> Iterator for EdgeIterator<'a> {
+    type Item = EdgeId;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next()
+    }
+}
+
+pub(crate) struct EdgeIntersectionIterator<'a>(
+    IntersectionIterator<EdgeIdClosureIter<'a>, EdgeIdClosureIter<'a>>,
+);
+
+impl<'a> EdgeIntersectionIterator<'a> {
+    pub(crate) fn new(
+        incoming_edges: EdgeIdClosureIter<'a>,
+        outgoing_edges: EdgeIdClosureIter<'a>,
+    ) -> Self {
+        Self(IntersectionIterator::new(incoming_edges, outgoing_edges))
+    }
+}
+
+impl<'a> Iterator for EdgeIntersectionIterator<'a> {
+    type Item = EdgeId;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next()
+    }
+}
+
+pub(crate) struct EdgeBetweenIterator<'a>(
+    UnionIterator<EdgeIntersectionIterator<'a>, EdgeIntersectionIterator<'a>>,
+);
+
+impl<'a> EdgeBetweenIterator<'a> {
+    pub(crate) fn new(this: &'a NodeClosures, other: &'a NodeClosures) -> Self {
+        Self(UnionIterator::new(
+            EdgeIntersectionIterator::new(this.outgoing_edges(), other.incoming_edges()),
+            EdgeIntersectionIterator::new(this.incoming_edges(), other.outgoing_edges()),
+        ))
+    }
+}
+
+impl<'a> Iterator for EdgeBetweenIterator<'a> {
+    type Item = EdgeId;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.0.next()
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use alloc::vec::Vec;
+
+    use super::*;
+    use crate::slab::{EntryId, Generation, Key};
+
+    fn nid(id: usize) -> NodeId {
+        NodeId::from_id(EntryId::new(Generation::first(), id).expect("valid id"))
+    }
+
+    fn eid(id: usize) -> EdgeId {
+        EdgeId::from_id(EntryId::new(Generation::first(), id).expect("valid id"))
+    }
+
+    #[test]
+    fn union_iterator() {
+        let left = [1, 2, 3, 4, 5];
+        let right = [2, 4, 6, 8, 10];
+
+        let iter = UnionIterator::new(left.iter().copied(), right.iter().copied());
+
+        assert_eq!(iter.collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6, 8, 10]);
+    }
+
+    #[test]
+    fn intersection_iterator() {
+        let left = [1, 2, 3, 4, 5];
+        let right = [2, 4, 6, 8, 10];
+
+        let iter = IntersectionIterator::new(left.iter().copied(), right.iter().copied());
+
+        assert_eq!(iter.collect::<Vec<_>>(), [2, 4]);
+    }
+
+    #[test]
+    fn intersection_iterator_empty() {
+        let left = [1, 2, 3, 4, 5];
+        let right = [6, 7, 8, 9, 10];
+
+        let iter = IntersectionIterator::new(left.iter().copied(), right.iter().copied());
+
+        assert_eq!(iter.collect::<Vec<_>>(), []);
+    }
+
+    #[test]
+    fn neighbour_iterator() {
+        let incoming = [nid(1), nid(2), nid(3), nid(4), nid(5)];
+        let outgoing = [nid(2), nid(4), nid(6), nid(8), nid(10)];
+
+        let iter = NeighbourIterator::new(incoming.iter().copied(), outgoing.iter().copied());
+
+        assert_eq!(
+            iter.collect::<Vec<_>>(),
+            [
+                nid(1),
+                nid(2),
+                nid(3),
+                nid(4),
+                nid(5),
+                nid(6),
+                nid(8),
+                nid(10)
+            ]
+        );
+    }
+
+    #[test]
+    fn edge_iterator() {
+        let incoming = [eid(1), eid(2), eid(3), eid(4), eid(5)];
+        let outgoing = [eid(2), eid(4), eid(6), eid(8), eid(10)];
+
+        let iter = EdgeIterator::new(incoming.iter().copied(), outgoing.iter().copied());
+
+        assert_eq!(
+            iter.collect::<Vec<_>>(),
+            [
+                eid(1),
+                eid(2),
+                eid(3),
+                eid(4),
+                eid(5),
+                eid(6),
+                eid(8),
+                eid(10)
+            ]
+        );
+    }
+
+    #[test]
+    fn edge_intersection_iterator() {
+        let incoming = [eid(1), eid(2), eid(3), eid(4), eid(5)];
+        let outgoing = [eid(2), eid(4), eid(6), eid(8), eid(10)];
+
+        let iter =
+            EdgeIntersectionIterator::new(incoming.iter().copied(), outgoing.iter().copied());
+
+        assert_eq!(iter.collect::<Vec<_>>(), [eid(2), eid(4)]);
+    }
+}
diff --git a/crates/dino/src/iter/directed.rs b/crates/dino/src/iter/directed.rs
new file mode 100644
index 0000000..a6a28e8
--- /dev/null
+++ b/crates/dino/src/iter/directed.rs
@@ -0,0 +1,46 @@
+use petgraph_core::{Edge, GraphDirectionality};
+
+use crate::{DinoStorage, EdgeId};
+
+pub(crate) struct NodeDirectedConnectionsIter<'storage, N, E, D, I>
+where
+    D: GraphDirectionality,
+{
+    pub(crate) storage: &'storage DinoStorage<N, E, D>,
+    pub(crate) iter: Option<I>,
+}
+
+impl<'storage, N, E, D, I> Iterator for NodeDirectedConnectionsIter<'storage, N, E, D, I>
+where
+    D: GraphDirectionality,
+    I: Iterator<Item = EdgeId>,
+{
+    type Item = Edge<'storage, DinoStorage<N, E, D>>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let iter = self.iter.as_mut()?;
+
+        loop {
+            let Some(id) = iter.next() else {
+                self.iter = None;
+                return None;
+            };
+
+            let Some(edge) = self.storage.edges.get_unchecked(id) else {
+                continue;
+            };
+
+            return Some(Edge::new(
+                self.storage,
+                edge.id,
+                &edge.weight,
+                edge.source,
+                edge.target,
+            ));
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.as_ref().map_or((0, Some(0)), Iterator::size_hint)
+    }
+}
diff --git a/crates/dino/src/iter/mod.rs b/crates/dino/src/iter/mod.rs
new file mode 100644
index 0000000..b329399
--- /dev/null
+++ b/crates/dino/src/iter/mod.rs
@@ -0,0 +1,2 @@
+pub(crate) mod closure;
+pub(crate) mod directed;
diff --git a/crates/dino/src/lib.rs b/crates/dino/src/lib.rs
index a889383..54e3b30 100644
--- a/crates/dino/src/lib.rs
+++ b/crates/dino/src/lib.rs
@@ -104,21 +104,27 @@
 #![warn(missing_docs)]
 #![no_std]
 
+// TODO: benchmark a linked-list based implementation (mirroring current `Graph` implementation)
+//  & overhead
+// Using such an approach would allow us to reduce heap allocations in favor of slower iteration
+// speed.
+
+extern crate alloc;
+
 pub(crate) mod closure;
 mod directed;
 mod edge;
+mod iter;
 mod node;
-
 mod retain;
 pub(crate) mod slab;
 #[cfg(test)]
 mod tests;
 
-extern crate alloc;
-
 use core::fmt::{Debug, Display};
 
 pub use edge::EdgeId;
+use either::Either;
 use error_stack::{Context, Report, Result};
 pub use node::NodeId;
 use petgraph_core::{
@@ -132,7 +138,12 @@
     Graph,
 };
 
-use crate::{closure::Closures, edge::Edge, node::Node, slab::Slab};
+use crate::{
+    closure::Closures,
+    edge::Edge,
+    node::{Node, NodeClosures, NodeSlab},
+    slab::Slab,
+};
 
 /// Alias for a [`Graph`] that uses [`DinoStorage`] as its backing storage.
 ///
@@ -331,8 +342,6 @@
     nodes: Slab<NodeId, Node<N>>,
     edges: Slab<EdgeId, Edge<E>>,
 
-    closures: Closures,
-
     _marker: core::marker::PhantomData<fn() -> *const D>,
 }
 
@@ -408,6 +417,20 @@
 
 impl Context for Error {}
 
+fn edges_between_undirected<N>(
+    nodes: &NodeSlab<N>,
+    source: NodeId,
+    target: NodeId,
+) -> impl Iterator<Item = EdgeId> + '_ {
+    let source = nodes.get(source);
+    let target = nodes.get(target);
+
+    source
+        .and_then(|source| target.map(|target| (source, target)))
+        .into_iter()
+        .flat_map(|(source, target)| source.closures.edges_between_undirected(&target.closures))
+}
+
 impl<N, E, D> GraphStorage for DinoStorage<N, E, D>
 where
     D: GraphDirectionality,
@@ -423,8 +446,6 @@
             nodes: Slab::with_capacity(node_capacity),
             edges: Slab::with_capacity(edge_capacity),
 
-            closures: Closures::new(),
-
             _marker: core::marker::PhantomData,
         }
     }
@@ -433,7 +454,7 @@
         nodes: impl IntoIterator<Item = DetachedNode<Self::NodeId, Self::NodeWeight>>,
         edges: impl IntoIterator<Item = DetachedEdge<Self::EdgeId, Self::NodeId, Self::EdgeWeight>>,
     ) -> Result<Self, Self::Error> {
-        let nodes: Slab<_, _> = nodes
+        let mut nodes: Slab<_, _> = nodes
             .into_iter()
             .map(|node: DetachedNode<Self::NodeId, Self::NodeWeight>| {
                 (node.id, Node::new(node.id, node.weight))
@@ -455,13 +476,11 @@
         // TODO: what about nodes that are added or edges?
         //      We don't know their ID yet (need a way to get those -> PartialNode/Edge)
 
-        let mut closures = Closures::new();
-        closures.refresh(&nodes, &edges);
+        Closures::refresh(&mut nodes, &edges);
 
         Ok(Self {
             nodes,
             edges,
-            closures,
 
             _marker: core::marker::PhantomData,
         })
@@ -520,12 +539,10 @@
             .nodes
             .get_mut(id)
             .ok_or_else(|| Report::new(Error::NodeNotFound))?;
+
         // we do not need to set the node's id, since the assertion above guarantees that the id is
         // correct
-
-        self.closures.create_node(node);
-
-        Ok(NodeMut::new(&node.id, &mut node.weight))
+        Ok(NodeMut::new(node.id, &mut node.weight))
     }
 
     fn next_edge_id(&self, _: <Self::EdgeId as GraphId>::AttributeIndex) -> Self::EdgeId {
@@ -537,19 +554,19 @@
         id: Self::EdgeId,
         weight: Self::EdgeWeight,
 
-        source: &Self::NodeId,
-        target: &Self::NodeId,
+        source: Self::NodeId,
+        target: Self::NodeId,
     ) -> Result<EdgeMut<Self>, Self::Error> {
         // TODO: option to disallow self-loops and parallel edges
 
         // undirected edges in the graph are stored in a canonical form, where the source node id is
         // always smaller than the target node id
         let (source, target) = if D::is_directed() {
-            (*source, *target)
+            (source, target)
         } else if source > target {
-            (*target, *source)
+            (target, source)
         } else {
-            (*source, *target)
+            (source, target)
         };
 
         let expected = id;
@@ -572,38 +589,39 @@
         // we do not need to set the node's id, since the assertion above guarantees that the id is
         // correct
 
-        self.closures.create_edge(edge);
+        Closures::create_edge(edge, &mut self.nodes);
 
         Ok(EdgeMut::new(
-            &edge.id,
+            edge.id,
             &mut edge.weight,
-            &edge.source,
-            &edge.target,
+            edge.source,
+            edge.target,
         ))
     }
 
     fn remove_node(
         &mut self,
-        id: &Self::NodeId,
+        id: Self::NodeId,
     ) -> Option<DetachedNode<Self::NodeId, Self::NodeWeight>> {
-        for edge in self.closures.drain_edges(*id) {
+        let node = self.nodes.remove(id)?;
+
+        for edge in node.closures.edges() {
             if let Some(edge) = self.edges.remove(edge) {
-                self.closures.remove_edge(&edge);
+                Closures::remove_edge(&edge, &mut self.nodes);
             }
         }
 
-        let node = self.nodes.remove(*id)?;
-        self.closures.remove_node(&node);
+        let (id, weight) = Closures::remove_node(node, &mut self.nodes);
 
-        Some(DetachedNode::new(node.id, node.weight))
+        Some(DetachedNode::new(id, weight))
     }
 
     fn remove_edge(
         &mut self,
-        id: &Self::EdgeId,
+        id: Self::EdgeId,
     ) -> Option<DetachedEdge<Self::EdgeId, Self::NodeId, Self::EdgeWeight>> {
-        let edge = self.edges.remove(*id)?;
-        self.closures.remove_edge(&edge);
+        let edge = self.edges.remove(id)?;
+        Closures::remove_edge(&edge, &mut self.nodes);
 
         Some(DetachedEdge::new(
             edge.id,
@@ -616,173 +634,165 @@
     fn clear(&mut self) {
         self.nodes.clear();
         self.edges.clear();
-        self.closures.clear();
+        Closures::clear(&mut self.nodes);
     }
 
-    fn node(&self, id: &Self::NodeId) -> Option<petgraph_core::node::Node<Self>> {
+    fn node(&self, id: Self::NodeId) -> Option<petgraph_core::node::Node<Self>> {
         self.nodes
-            .get(*id)
-            .map(|node| petgraph_core::node::Node::new(self, &node.id, &node.weight))
+            .get(id)
+            .map(|node| petgraph_core::node::Node::new(self, node.id, &node.weight))
     }
 
-    fn node_mut(&mut self, id: &Self::NodeId) -> Option<NodeMut<Self>> {
+    fn node_mut(&mut self, id: Self::NodeId) -> Option<NodeMut<Self>> {
         self.nodes
-            .get_mut(*id)
-            .map(|node| NodeMut::new(&node.id, &mut node.weight))
+            .get_mut(id)
+            .map(|node| NodeMut::new(node.id, &mut node.weight))
     }
 
-    fn contains_node(&self, id: &Self::NodeId) -> bool {
-        self.nodes.contains_key(*id)
+    fn contains_node(&self, id: Self::NodeId) -> bool {
+        self.nodes.contains_key(id)
     }
 
-    fn edge(&self, id: &Self::EdgeId) -> Option<petgraph_core::edge::Edge<Self>> {
-        self.edges.get(*id).map(|edge| {
-            petgraph_core::edge::Edge::new(self, &edge.id, &edge.weight, &edge.source, &edge.target)
+    fn edge(&self, id: Self::EdgeId) -> Option<petgraph_core::edge::Edge<Self>> {
+        self.edges.get(id).map(|edge| {
+            petgraph_core::edge::Edge::new(self, edge.id, &edge.weight, edge.source, edge.target)
         })
     }
 
-    fn edge_mut(&mut self, id: &Self::EdgeId) -> Option<EdgeMut<Self>> {
+    fn edge_mut(&mut self, id: Self::EdgeId) -> Option<EdgeMut<Self>> {
         self.edges
-            .get_mut(*id)
-            .map(|edge| EdgeMut::new(&edge.id, &mut edge.weight, &edge.source, &edge.target))
+            .get_mut(id)
+            .map(|edge| EdgeMut::new(edge.id, &mut edge.weight, edge.source, edge.target))
     }
 
-    fn contains_edge(&self, id: &Self::EdgeId) -> bool {
-        self.edges.contains_key(*id)
+    fn contains_edge(&self, id: Self::EdgeId) -> bool {
+        self.edges.contains_key(id)
     }
 
-    fn edges_between<'a: 'b, 'b>(
-        &'a self,
-        source: &'b Self::NodeId,
-        target: &'b Self::NodeId,
-    ) -> impl Iterator<Item = petgraph_core::edge::Edge<'a, Self>> + 'b {
-        let edges = self
-            .closures
-            .edges()
-            .undirected_endpoints_to_edges(*source, *target);
-
-        edges.filter_map(move |edge| self.edge(&edge))
+    fn edges_between(
+        &self,
+        source: Self::NodeId,
+        target: Self::NodeId,
+    ) -> impl Iterator<Item = petgraph_core::edge::Edge<Self>> {
+        edges_between_undirected(&self.nodes, source, target)
+            .filter_map(move |edge| self.edge(edge))
     }
 
-    fn edges_between_mut<'a: 'b, 'b>(
-        &'a mut self,
-        source: &'b Self::NodeId,
-        target: &'b Self::NodeId,
-    ) -> impl Iterator<Item = EdgeMut<'a, Self>> + 'b {
-        let edges = self
-            .closures
-            .edges()
-            .undirected_endpoints_to_edges(*source, *target);
+    fn edges_between_mut(
+        &mut self,
+        source: Self::NodeId,
+        target: Self::NodeId,
+    ) -> impl Iterator<Item = EdgeMut<Self>> {
+        let available = edges_between_undirected(&self.nodes, source, target);
 
         self.edges
-            .filter_mut(edges)
-            .map(move |edge| EdgeMut::new(&edge.id, &mut edge.weight, &edge.source, &edge.target))
+            .filter_mut(available)
+            .map(move |edge| EdgeMut::new(edge.id, &mut edge.weight, edge.source, edge.target))
     }
 
-    fn node_connections<'a: 'b, 'b>(
-        &'a self,
-        id: &'b Self::NodeId,
-    ) -> impl Iterator<Item = petgraph_core::edge::Edge<'a, Self>> + 'b {
-        self.closures
-            .nodes()
-            .edges(*id)
-            .filter_map(|edge| self.edge(&edge))
+    fn node_connections(
+        &self,
+        id: Self::NodeId,
+    ) -> impl Iterator<Item = petgraph_core::edge::Edge<Self>> {
+        self.nodes
+            .get(id)
+            .into_iter()
+            .flat_map(move |node| node.closures.edges())
+            .filter_map(move |edge| self.edge(edge))
     }
 
-    fn node_connections_mut<'a: 'b, 'b>(
-        &'a mut self,
-        id: &'b Self::NodeId,
-    ) -> impl Iterator<Item = EdgeMut<'a, Self>> + 'b {
-        let Self {
-            closures, edges, ..
-        } = self;
+    fn node_connections_mut(&mut self, id: Self::NodeId) -> impl Iterator<Item = EdgeMut<Self>> {
+        let Self { nodes, edges, .. } = self;
+
+        let available = nodes
+            .get(id)
+            .into_iter()
+            .flat_map(move |node| node.closures.edges());
 
         edges
-            .filter_mut(closures.nodes().edges(*id))
-            .map(move |edge| EdgeMut::new(&edge.id, &mut edge.weight, &edge.source, &edge.target))
+            .filter_mut(available)
+            .map(move |edge| EdgeMut::new(edge.id, &mut edge.weight, edge.source, edge.target))
     }
 
-    fn node_neighbours<'a: 'b, 'b>(
-        &'a self,
-        id: &'b Self::NodeId,
-    ) -> impl Iterator<Item = petgraph_core::node::Node<'a, Self>> + 'b {
-        self.closures
-            .nodes()
-            .neighbours(*id)
-            .filter_map(move |node| self.node(&node))
+    fn node_neighbours(
+        &self,
+        id: Self::NodeId,
+    ) -> impl Iterator<Item = petgraph_core::node::Node<Self>> {
+        self.nodes
+            .get(id)
+            .into_iter()
+            .flat_map(move |node| node.closures.neighbours())
+            .filter_map(move |node| self.node(node))
     }
 
-    fn node_neighbours_mut<'a: 'b, 'b>(
-        &'a mut self,
-        id: &'b Self::NodeId,
-    ) -> impl Iterator<Item = NodeMut<'a, Self>> + 'b {
-        let Self {
-            closures, nodes, ..
-        } = self;
+    fn node_neighbours_mut(&mut self, id: Self::NodeId) -> impl Iterator<Item = NodeMut<Self>> {
+        let Some(node) = self.nodes.get(id) else {
+            return Either::Right(core::iter::empty());
+        };
 
-        nodes
-            .filter_mut(closures.nodes().neighbours(*id))
-            .map(move |node| NodeMut::new(&node.id, &mut node.weight))
+        // SAFETY: we never access the closure argument mutably, only the weight.
+        // Therefore it is safe for us to access both at the same time.
+        let closure: &NodeClosures = unsafe { &*core::ptr::addr_of!(node.closures) };
+        let neighbours = closure.neighbours();
+
+        Either::Left(
+            self.nodes
+                .filter_mut(neighbours)
+                .map(move |node| NodeMut::new(node.id, &mut node.weight)),
+        )
     }
 
     fn isolated_nodes(&self) -> impl Iterator<Item = petgraph_core::node::Node<Self>> {
-        self.closures
-            .nodes()
-            .externals()
-            .filter_map(move |node| self.node(&node))
+        self.nodes
+            .iter()
+            .filter(|node| node.closures.is_isolated())
+            .map(move |node| petgraph_core::node::Node::new(self, node.id, &node.weight))
     }
 
     fn isolated_nodes_mut(&mut self) -> impl Iterator<Item = NodeMut<Self>> {
-        let Self {
-            nodes, closures, ..
-        } = self;
-
-        nodes
-            .filter_mut(closures.nodes().externals())
-            .map(move |node| NodeMut::new(&node.id, &mut node.weight))
+        self.nodes
+            .iter_mut()
+            .filter(move |node| node.closures.is_isolated())
+            .map(move |node| NodeMut::new(node.id, &mut node.weight))
     }
 
     fn nodes(&self) -> impl Iterator<Item = petgraph_core::node::Node<Self>> {
         self.nodes
             .iter()
-            .map(move |node| petgraph_core::node::Node::new(self, &node.id, &node.weight))
+            .map(move |node| petgraph_core::node::Node::new(self, node.id, &node.weight))
     }
 
     fn nodes_mut(&mut self) -> impl Iterator<Item = NodeMut<Self>> {
         self.nodes
             .iter_mut()
-            .map(move |node| NodeMut::new(&node.id, &mut node.weight))
+            .map(move |node| NodeMut::new(node.id, &mut node.weight))
     }
 
     fn edges(&self) -> impl Iterator<Item = petgraph_core::edge::Edge<Self>> {
         self.edges.iter().map(move |edge| {
-            petgraph_core::edge::Edge::new(self, &edge.id, &edge.weight, &edge.source, &edge.target)
+            petgraph_core::edge::Edge::new(self, edge.id, &edge.weight, edge.source, edge.target)
         })
     }
 
     fn edges_mut(&mut self) -> impl Iterator<Item = EdgeMut<Self>> {
         self.edges
             .iter_mut()
-            .map(move |edge| EdgeMut::new(&edge.id, &mut edge.weight, &edge.source, &edge.target))
+            .map(move |edge| EdgeMut::new(edge.id, &mut edge.weight, edge.source, edge.target))
     }
 
     fn reserve_nodes(&mut self, additional: usize) {
         self.nodes.reserve(additional);
-        self.closures.reserve(additional);
     }
 
     fn reserve_edges(&mut self, additional: usize) {
         self.edges.reserve(additional);
-        self.closures.reserve(additional);
     }
 
     fn shrink_to_fit_nodes(&mut self) {
         self.nodes.shrink_to_fit();
-        self.closures.shrink_to_fit();
     }
 
     fn shrink_to_fit_edges(&mut self) {
         self.edges.shrink_to_fit();
-        self.closures.shrink_to_fit();
     }
 }
diff --git a/crates/dino/src/node.rs b/crates/dino/src/node.rs
index c4c2e54..88818da 100644
--- a/crates/dino/src/node.rs
+++ b/crates/dino/src/node.rs
@@ -3,12 +3,20 @@
 use petgraph_core::{
     attributes::NoValue,
     edge::marker::GraphDirectionality,
-    id::{GraphId, LinearGraphId, ManagedGraphId},
+    id::{AssociativeGraphId, GraphId, LinearGraphId, ManagedGraphId},
 };
 
 use crate::{
-    slab::{EntryId, Key, SlabIndexMapper},
-    DinoStorage,
+    closure::UniqueVec,
+    iter::closure::{
+        EdgeBetweenIterator, EdgeIdClosureIter, EdgeIntersectionIterator, EdgeIterator,
+        NeighbourIterator, NodeIdClosureIter,
+    },
+    slab::{
+        secondary::{SlabAttributeMapper, SlabBooleanMapper},
+        EntryId, Key, SlabIndexMapper,
+    },
+    DinoStorage, EdgeId,
 };
 
 /// Identifier for a node in [`DinoStorage`].
@@ -41,10 +49,12 @@
 }
 
 impl Key for NodeId {
+    #[inline]
     fn from_id(id: EntryId) -> Self {
         Self(id)
     }
 
+    #[inline]
     fn into_id(self) -> EntryId {
         self.0
     }
@@ -65,16 +75,182 @@
     }
 }
 
+impl<N, E, D> AssociativeGraphId<DinoStorage<N, E, D>> for NodeId
+where
+    D: GraphDirectionality,
+{
+    type AttributeMapper<'a, V> = SlabAttributeMapper<'a, Self, V> where DinoStorage<N, E, D>: 'a;
+    type BooleanMapper<'a> = SlabBooleanMapper<'a> where DinoStorage<N, E, D>: 'a;
+
+    fn attribute_mapper<V>(storage: &DinoStorage<N, E, D>) -> Self::AttributeMapper<'_, V> {
+        SlabAttributeMapper::new(&storage.nodes)
+    }
+
+    fn boolean_mapper(storage: &DinoStorage<N, E, D>) -> Self::BooleanMapper<'_> {
+        SlabBooleanMapper::new(&storage.nodes)
+    }
+}
+
 impl ManagedGraphId for NodeId {}
 
-#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
+pub(crate) type NodeSlab<T> = crate::slab::Slab<NodeId, Node<T>>;
+
+#[derive(Debug, Clone)]
+pub(crate) struct NodeClosures {
+    outgoing_nodes: UniqueVec<NodeId>,
+    incoming_nodes: UniqueVec<NodeId>,
+
+    outgoing_edges: UniqueVec<EdgeId>,
+    incoming_edges: UniqueVec<EdgeId>,
+}
+
+impl NodeClosures {
+    const fn new() -> Self {
+        Self {
+            outgoing_nodes: UniqueVec::new(),
+            incoming_nodes: UniqueVec::new(),
+
+            outgoing_edges: UniqueVec::new(),
+            incoming_edges: UniqueVec::new(),
+        }
+    }
+
+    pub(crate) fn insert_outgoing_node(&mut self, node: NodeId) {
+        self.outgoing_nodes.insert(node);
+    }
+
+    pub(crate) fn remove_outgoing_node(&mut self, node: NodeId) {
+        self.outgoing_nodes.remove(&node);
+    }
+
+    pub(crate) fn insert_incoming_node(&mut self, node: NodeId) {
+        self.incoming_nodes.insert(node);
+    }
+
+    pub(crate) fn remove_incoming_node(&mut self, node: NodeId) {
+        self.incoming_nodes.remove(&node);
+    }
+
+    pub(crate) fn insert_outgoing_edge(&mut self, edge: EdgeId) {
+        self.outgoing_edges.insert(edge);
+    }
+
+    pub(crate) fn remove_outgoing_edge(&mut self, edge: EdgeId) {
+        self.outgoing_edges.remove(&edge);
+    }
+
+    pub(crate) fn insert_incoming_edge(&mut self, edge: EdgeId) {
+        self.incoming_edges.insert(edge);
+    }
+
+    pub(crate) fn remove_incoming_edge(&mut self, edge: EdgeId) {
+        self.incoming_edges.remove(&edge);
+    }
+
+    pub(crate) fn outgoing_nodes(&self) -> NodeIdClosureIter {
+        self.outgoing_nodes.iter().copied()
+    }
+
+    pub(crate) fn incoming_nodes(&self) -> NodeIdClosureIter {
+        self.incoming_nodes.iter().copied()
+    }
+
+    pub(crate) fn neighbours(&self) -> NeighbourIterator {
+        NeighbourIterator::new(
+            self.outgoing_nodes.iter().copied(),
+            self.incoming_nodes.iter().copied(),
+        )
+    }
+
+    pub(crate) fn outgoing_edges(&self) -> EdgeIdClosureIter {
+        self.outgoing_edges.iter().copied()
+    }
+
+    pub(crate) fn incoming_edges(&self) -> EdgeIdClosureIter {
+        self.incoming_edges.iter().copied()
+    }
+
+    pub(crate) fn edges(&self) -> EdgeIterator {
+        EdgeIterator::new(
+            self.outgoing_edges.iter().copied(),
+            self.incoming_edges.iter().copied(),
+        )
+    }
+
+    pub(crate) fn edges_between_undirected<'a>(
+        &'a self,
+        other: &'a Self,
+    ) -> EdgeBetweenIterator<'a> {
+        EdgeBetweenIterator::new(self, other)
+    }
+
+    pub(crate) fn edges_between_directed<'a>(
+        &'a self,
+        other: &'a Self,
+    ) -> EdgeIntersectionIterator<'a> {
+        EdgeIntersectionIterator::new(
+            self.outgoing_edges.iter().copied(),
+            other.incoming_edges.iter().copied(),
+        )
+    }
+
+    pub(crate) fn is_isolated(&self) -> bool {
+        self.outgoing_nodes.is_empty() && self.incoming_nodes.is_empty()
+    }
+
+    pub(crate) fn clear(&mut self) {
+        self.outgoing_nodes.clear();
+        self.incoming_nodes.clear();
+
+        self.outgoing_edges.clear();
+        self.incoming_edges.clear();
+    }
+}
+
+#[derive(Debug, Clone)]
 pub(crate) struct Node<T> {
     pub(crate) id: NodeId,
     pub(crate) weight: T,
+
+    pub(crate) closures: NodeClosures,
 }
 
 impl<T> Node<T> {
     pub(crate) const fn new(id: NodeId, weight: T) -> Self {
-        Self { id, weight }
+        Self {
+            id,
+            weight,
+
+            closures: NodeClosures::new(),
+        }
+    }
+}
+
+impl<T> PartialEq for Node<T>
+where
+    T: PartialEq,
+{
+    fn eq(&self, other: &Self) -> bool {
+        (self.id, &self.weight) == (other.id, &other.weight)
+    }
+}
+
+impl<T> Eq for Node<T> where T: Eq {}
+
+impl<T> PartialOrd for Node<T>
+where
+    T: PartialOrd,
+{
+    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
+        (self.id, &self.weight).partial_cmp(&(other.id, &other.weight))
+    }
+}
+
+impl<T> Ord for Node<T>
+where
+    T: Ord,
+{
+    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
+        (self.id, &self.weight).cmp(&(other.id, &other.weight))
     }
 }
diff --git a/crates/dino/src/retain.rs b/crates/dino/src/retain.rs
index 6c9bc77..2da701f 100644
--- a/crates/dino/src/retain.rs
+++ b/crates/dino/src/retain.rs
@@ -1,11 +1,12 @@
+use alloc::collections::BTreeSet;
+
 use petgraph_core::{
     edge::{marker::GraphDirectionality, EdgeMut},
     node::NodeMut,
     storage::RetainableGraphStorage,
 };
-use roaring::RoaringBitmap;
 
-use crate::{slab::Key, DinoStorage};
+use crate::{closure::Closures, DinoStorage};
 
 impl<N, E, D> RetainableGraphStorage for DinoStorage<N, E, D>
 where
@@ -16,65 +17,62 @@
         mut nodes: impl FnMut(NodeMut<'_, Self>) -> bool,
         mut edges: impl FnMut(EdgeMut<'_, Self>) -> bool,
     ) {
-        let mut removed = RoaringBitmap::new();
+        let mut removed = BTreeSet::new();
 
         self.nodes.retain(|_, value| {
-            let node = NodeMut::new(&value.id, &mut value.weight);
+            let node = NodeMut::new(value.id, &mut value.weight);
 
             let retain = nodes(node);
 
             if !retain {
-                removed.insert(value.id.into_id().raw());
+                removed.insert(value.id);
             }
 
             retain
         });
 
         self.edges.retain(|_, value| {
-            if removed.contains(value.source.into_id().raw())
-                || removed.contains(value.target.into_id().raw())
-            {
+            if removed.contains(&value.source) || removed.contains(&value.target) {
                 return false;
             }
 
-            let edge = EdgeMut::new(&value.id, &mut value.weight, &value.source, &value.target);
+            let edge = EdgeMut::new(value.id, &mut value.weight, value.source, value.target);
 
             edges(edge)
         });
 
-        self.closures.refresh(&self.nodes, &self.edges);
+        Closures::refresh(&mut self.nodes, &self.edges);
     }
 
     fn retain_nodes(&mut self, mut f: impl FnMut(NodeMut<'_, Self>) -> bool) {
-        let mut removed = RoaringBitmap::new();
+        let mut removed = BTreeSet::new();
 
         self.nodes.retain(|_, value| {
-            let node = NodeMut::new(&value.id, &mut value.weight);
+            let node = NodeMut::new(value.id, &mut value.weight);
 
             let retain = f(node);
 
             if !retain {
-                removed.insert(value.id.into_id().raw());
+                removed.insert(value.id);
             }
 
             retain
         });
 
         self.edges.retain(|_, value| {
-            !removed.contains(value.source.into_id().raw())
-                && !removed.contains(value.target.into_id().raw())
+            !removed.contains(&value.source) && !removed.contains(&value.target)
         });
 
-        self.closures.refresh(&self.nodes, &self.edges);
+        Closures::refresh(&mut self.nodes, &self.edges);
     }
 
     fn retain_edges(&mut self, mut f: impl FnMut(EdgeMut<'_, Self>) -> bool) {
         self.edges.retain(|_, value| {
-            let edge = EdgeMut::new(&value.id, &mut value.weight, &value.source, &value.target);
+            let edge = EdgeMut::new(value.id, &mut value.weight, value.source, value.target);
 
             f(edge)
         });
 
-        self.closures.refresh(&self.nodes, &self.edges);
+        Closures::refresh(&mut self.nodes, &self.edges);
     }
 }
diff --git a/crates/dino/src/slab/key.rs b/crates/dino/src/slab/key.rs
index 7d9a9e3..287551c 100644
--- a/crates/dino/src/slab/key.rs
+++ b/crates/dino/src/slab/key.rs
@@ -4,5 +4,6 @@
 
 pub trait Key: Debug + Copy + Clone + PartialEq + Eq + PartialOrd + Ord + Hash {
     fn from_id(id: EntryId) -> Self;
+
     fn into_id(self) -> EntryId;
 }
diff --git a/crates/dino/src/slab/mod.rs b/crates/dino/src/slab/mod.rs
index 8a8a811..44eee1d 100644
--- a/crates/dino/src/slab/mod.rs
+++ b/crates/dino/src/slab/mod.rs
@@ -3,6 +3,7 @@
 mod generation;
 mod id;
 mod key;
+pub(crate) mod secondary;
 
 use alloc::{vec, vec::Vec};
 use core::{fmt::Debug, hash::Hash, marker::PhantomData, ptr};
@@ -145,6 +146,16 @@
         entry.get()
     }
 
+    pub(crate) fn get_unchecked(&self, key: K) -> Option<&V> {
+        let id = key.into_id();
+
+        let index = id.index();
+
+        let entry = self.entries.get(index)?;
+
+        entry.get()
+    }
+
     pub(crate) fn get_mut(&mut self, key: K) -> Option<&mut V> {
         let id = key.into_id();
 
@@ -352,6 +363,10 @@
     pub(crate) fn len(&self) -> usize {
         self.entries.len() - self.free.len()
     }
+
+    pub(crate) fn total_len(&self) -> usize {
+        self.entries.len()
+    }
 }
 
 impl<K, V> FromIterator<(K, V)> for Slab<K, V>
@@ -421,16 +436,16 @@
         self.reverse.len()
     }
 
-    fn get(&self, from: &K) -> Option<usize> {
+    fn get(&self, from: K) -> Option<usize> {
         self.lookup.get(from.into_id().index()).copied().flatten()
     }
 
-    fn index(&self, from: &K) -> usize {
+    fn index(&self, from: K) -> usize {
         self.lookup[from.into_id().index()].expect("tried to access vacant entry")
     }
 
-    fn reverse(&self, to: usize) -> Option<Moo<K>> {
-        self.reverse.get(to).copied().flatten().map(Moo::from)
+    fn reverse(&self, to: usize) -> Option<K> {
+        self.reverse.get(to).copied().flatten()
     }
 }
 
diff --git a/crates/dino/src/slab/secondary.rs b/crates/dino/src/slab/secondary.rs
new file mode 100644
index 0000000..23d4e86
--- /dev/null
+++ b/crates/dino/src/slab/secondary.rs
@@ -0,0 +1,158 @@
+use alloc::vec::Vec;
+use core::iter;
+
+use bitvec::{boxed::BitBox, prelude::BitVec};
+use numi::borrow::Moo;
+use petgraph_core::id::{AttributeMapper, BooleanMapper};
+
+use crate::slab::{EntryId, Generation, Key, Slab};
+
+pub struct SlabBooleanMapper<'a> {
+    flags: BitBox,
+    _marker: core::marker::PhantomData<&'a ()>,
+}
+
+impl<'a> SlabBooleanMapper<'a> {
+    pub(crate) fn new<K, V>(slab: &'a Slab<K, V>) -> Self
+    where
+        K: Key,
+    {
+        let length = slab.total_len();
+
+        Self {
+            flags: BitVec::repeat(false, length).into_boxed_bitslice(),
+            _marker: core::marker::PhantomData,
+        }
+    }
+}
+
+impl<Id> BooleanMapper<Id> for SlabBooleanMapper<'_>
+where
+    Id: Key,
+{
+    #[inline]
+    fn get(&self, id: Id) -> Option<bool> {
+        let index = id.into_id().index();
+
+        self.flags.get(index).map(|bit| *bit)
+    }
+
+    #[inline]
+    fn index(&self, id: Id) -> bool {
+        let index = id.into_id().index();
+
+        self.flags[index]
+    }
+
+    #[inline]
+    fn set(&mut self, id: Id, flag: bool) -> Option<bool> {
+        let index = id.into_id().index();
+
+        let value = self.flags.replace(index, flag);
+
+        Some(value)
+    }
+}
+
+pub struct SlabAttributeStorageIter<'a, K, T> {
+    iter: iter::Enumerate<core::slice::Iter<'a, Option<(Generation, T)>>>,
+    _marker: core::marker::PhantomData<&'a K>,
+}
+
+impl<'a, K, T> Iterator for SlabAttributeStorageIter<'a, K, T>
+where
+    K: Key,
+{
+    type Item = (K, &'a T);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        loop {
+            let (index, item) = self.iter.next()?;
+
+            if let Some((generation, value)) = item.as_ref() {
+                let id = EntryId::new(*generation, index)?;
+                let id = K::from_id(id);
+
+                return Some((id, value));
+            }
+        }
+    }
+}
+
+pub struct SlabAttributeMapper<'a, K, T> {
+    // generation is needed for iter
+    items: Vec<Option<(Generation, T)>>,
+
+    _slab: core::marker::PhantomData<&'a ()>,
+    _key: core::marker::PhantomData<fn() -> *const K>,
+}
+
+impl<'a, K, T> SlabAttributeMapper<'a, K, T> {
+    pub(crate) fn new<V>(slab: &'a Slab<K, V>) -> Self
+    where
+        K: Key,
+    {
+        let length = slab.total_len();
+
+        Self {
+            items: iter::repeat_with(|| None).take(length).collect::<Vec<_>>(),
+
+            _slab: core::marker::PhantomData,
+            _key: core::marker::PhantomData,
+        }
+    }
+}
+
+impl<K, T> AttributeMapper<K, T> for SlabAttributeMapper<'_, K, T>
+where
+    K: Key,
+{
+    type Iter<'a> = SlabAttributeStorageIter<'a, K, T> where
+        K: 'a,
+        T: 'a,
+        Self: 'a,;
+
+    fn get(&self, id: K) -> Option<&T> {
+        let index = id.into_id().index();
+
+        self.items
+            .get(index)
+            .and_then(|item| item.as_ref())
+            .map(|(_, value)| value)
+    }
+
+    fn get_mut(&mut self, id: K) -> Option<&mut T> {
+        let index = id.into_id().index();
+
+        self.items
+            .get_mut(index)
+            .and_then(|item| item.as_mut())
+            .map(|(_, value)| value)
+    }
+
+    fn set(&mut self, id: K, value: T) -> Option<T> {
+        let index = id.into_id().index();
+        let generation = id.into_id().generation();
+
+        self.items
+            .get_mut(index)
+            .and_then(|item| item.replace((generation, value)))
+            .map(|(_, value)| value)
+    }
+
+    fn remove(&mut self, id: K) -> Option<T> {
+        let index = id.into_id().index();
+
+        self.items
+            .get_mut(index)
+            .and_then(Option::take)
+            .map(|(_, value)| value)
+    }
+
+    fn iter(&self) -> Self::Iter<'_> {
+        SlabAttributeStorageIter {
+            iter: self.items.iter().enumerate(),
+            _marker: core::marker::PhantomData,
+        }
+    }
+}
diff --git a/crates/dino/src/tests.rs b/crates/dino/src/tests.rs
index 2215dae..b042474 100644
--- a/crates/dino/src/tests.rs
+++ b/crates/dino/src/tests.rs
@@ -10,6 +10,8 @@
 
 use crate::{DinoGraph, DinoStorage, EdgeId, NodeId};
 
+// TODO: rework tests to be more encompassing and use test utils!
+
 #[test]
 fn empty() {
     let graph = DinoGraph::<(), (), Directed>::new();
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()
     }};
 
     (
diff --git a/justfile b/justfile
index 5be2e82..80af3cb 100644
--- a/justfile
+++ b/justfile
@@ -156,3 +156,14 @@
     @just generate-problem graph shortest_path
 
 
+download-benchmarks:
+    # create output directory if it does not exist
+    mkdir -p crates/algorithms/benches/cases/shortest_path
+
+    wget http://www.diag.uniroma1.it/challenge9/data/USA-road-d/USA-road-d.FLA.gr.gz -O crates/algorithms/benches/cases/shortest_path/USA-road-d.FLA.gr.gz
+    wget http://www.diag.uniroma1.it/challenge9/data/USA-road-d/USA-road-d.FLA.co.gz -O crates/algorithms/benches/cases/shortest_path/USA-road-d.FLA.co.gz
+
+    # uncompress the files
+    gunzip crates/algorithms/benches/cases/shortest_path/USA-road-d.FLA.gr.gz
+    gunzip crates/algorithms/benches/cases/shortest_path/USA-road-d.FLA.co.gz
+