Merge remote-tracking branch 'origin/bm/algorithms-shortest-path' into bm/dino-closure
# Conflicts:
# .gitignore
# crates/algorithms/src/shortest_paths/astar/impl.rs
# crates/algorithms/src/shortest_paths/common/path.rs
# crates/algorithms/src/shortest_paths/common/transit.rs
# crates/algorithms/src/shortest_paths/dijkstra/iter.rs
# crates/algorithms/src/shortest_paths/dijkstra/mod.rs
# crates/algorithms/src/shortest_paths/mod.rs
diff --git a/.gitignore b/.gitignore
index f2694a9..f4602b6 100644
--- a/.gitignore
+++ b/.gitignore
@@ -3,3 +3,4 @@
Cargo.lock
/crates/algorithms/tests/cases/problems
venv
+crates/algorithms/benches/input
diff --git a/crates/algorithms/Cargo.toml b/crates/algorithms/Cargo.toml
index 21bf91d..8e9dec9 100644
--- a/crates/algorithms/Cargo.toml
+++ b/crates/algorithms/Cargo.toml
@@ -19,6 +19,7 @@
error-stack.workspace = true
hashbrown = { workspace = true, features = ['ahash'] }
either = "1.9.0"
+dary_heap = "0.3.6"
[build-dependencies]
rustc_version = "0.4.0"
@@ -51,6 +52,9 @@
remove-me-only-intended-for-move-graph = []
remove-me-only-intended-for-move-adjacency-matrix = []
+[profile.release]
+lto = "fat"
+
[[bench]]
name = "shortest_paths"
harness = false
diff --git a/crates/algorithms/benches/shortest_paths/large.rs b/crates/algorithms/benches/shortest_paths/large.rs
index d21a814..5f11794 100644
--- a/crates/algorithms/benches/shortest_paths/large.rs
+++ b/crates/algorithms/benches/shortest_paths/large.rs
@@ -133,7 +133,7 @@
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"),
@@ -179,21 +179,16 @@
}
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| {
- let (source, graph) = build_graph(filename);
- let dijkstra = Dijkstra::directed();
+ let (source, graph) = build_graph("USA-road-d.FLA");
+ let dijkstra = Dijkstra::directed();
- bench.iter(|| {
- for distances in dijkstra.distance_from(&graph, &source).unwrap() {
- black_box(distances);
- }
- });
- },
- );
+ criterion.bench_function("dimacs9/florida/dijkstra", |bench| {
+ bench.iter_with_large_drop(|| {
+ let scores: Vec<_> = dijkstra.distance_from(&graph, &source).unwrap().collect();
+
+ scores
+ });
+ });
}
criterion_group!(benches, dijkstra);
diff --git a/crates/algorithms/src/shortest_paths/astar/impl.rs b/crates/algorithms/src/shortest_paths/astar/impl.rs
index 33c5e13..263d1a8 100644
--- a/crates/algorithms/src/shortest_paths/astar/impl.rs
+++ b/crates/algorithms/src/shortest_paths/astar/impl.rs
@@ -23,6 +23,7 @@
pub(super) struct AStarImpl<'graph: 'parent, 'parent, S, E, H, C>
where
S: GraphStorage,
+ S::NodeId: FlaggableGraphId<S>,
E: GraphCost<S>,
E::Value: Ord,
{
@@ -44,7 +45,7 @@
impl<'graph: 'parent, 'parent, S, E, H, C> AStarImpl<'graph, 'parent, S, E, H, C>
where
S: GraphStorage,
- S::NodeId: Eq + Hash,
+ S::NodeId: FlaggableGraphId<S> + Eq + Hash,
E: GraphCost<S>,
E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
@@ -102,7 +103,7 @@
}
pub(super) fn find(mut self) -> Option<Route<'graph, S, E::Value>> {
- while let Some(node) = self.queue.pop_min() {
+ while let Some(QueueItem { node, .. }) = self.queue.pop_min() {
if node.id() == self.target.id() {
let transit = if self.predecessor_mode == PredecessorMode::Record {
reconstruct_path_to(&self.predecessors, node.id())
diff --git a/crates/algorithms/src/shortest_paths/astar/mod.rs b/crates/algorithms/src/shortest_paths/astar/mod.rs
index a15e300..fa9935d 100644
--- a/crates/algorithms/src/shortest_paths/astar/mod.rs
+++ b/crates/algorithms/src/shortest_paths/astar/mod.rs
@@ -12,6 +12,9 @@
use error_stack::Result;
use petgraph_core::{
edge::marker::{Directed, Undirected},
+ Direction,
+ },
+ id::FlaggableGraphId,
DirectedGraphStorage, Graph, GraphDirectionality, GraphStorage, Node,
};
@@ -149,7 +152,7 @@
) -> Result<AStarImpl<'graph, 'this, S, E, H, impl Connections<'graph, S> + 'this>, AStarError>
where
S: DirectedGraphStorage,
- S::NodeId: Eq + Hash,
+ S::NodeId: FlaggableGraphId<S> + Eq + Hash,
E: GraphCost<S>,
E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
@@ -176,7 +179,7 @@
) -> Result<AStarImpl<'graph, 'this, S, E, H, impl Connections<'graph, S> + 'this>, AStarError>
where
S: GraphStorage,
- S::NodeId: Eq + Hash,
+ S::NodeId: FlaggableGraphId<S> + Eq + Hash,
E: GraphCost<S>,
E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
@@ -199,7 +202,7 @@
impl<S, E, H> ShortestPath<S> for AStar<Undirected, E, H>
where
S: GraphStorage,
- S::NodeId: Eq + Hash,
+ S::NodeId: FlaggableGraphId<S> + Eq + Hash,
E: GraphCost<S>,
E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
@@ -268,7 +271,7 @@
impl<S, E, H> ShortestDistance<S> for AStar<Undirected, E, H>
where
S: GraphStorage,
- S::NodeId: Eq + Hash,
+ S::NodeId: FlaggableGraphId<S> + Eq + Hash,
E: GraphCost<S>,
E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
@@ -338,7 +341,7 @@
impl<S, E, H> ShortestPath<S> for AStar<Directed, E, H>
where
S: DirectedGraphStorage,
- S::NodeId: Eq + Hash,
+ S::NodeId: FlaggableGraphId<S> + Eq + Hash,
E: GraphCost<S>,
E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::Value>,
@@ -407,7 +410,7 @@
impl<S, E, H> ShortestDistance<S> for AStar<Directed, E, H>
where
S: DirectedGraphStorage,
- S::NodeId: Eq + Hash,
+ S::NodeId: FlaggableGraphId<S> + Eq + Hash,
E: GraphCost<S>,
E::Value: AStarMeasure,
H: GraphHeuristic<S, Value = E::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..494738b 100644
--- a/crates/algorithms/src/shortest_paths/common/queue/priority.rs
+++ b/crates/algorithms/src/shortest_paths/common/queue/priority.rs
@@ -4,17 +4,18 @@
cmp::{Ordering, Reverse},
};
-use petgraph_core::{GraphStorage, Node};
+use petgraph_core::{
+ id::{FlagStorage, FlaggableGraphId},
+ GraphStorage, Node,
+};
struct PriorityQueueItem<'a, S, T>
where
S: GraphStorage,
{
- node: Node<'a, S>,
+ pub(in crate::shortest_paths) node: Node<'a, S>,
- priority: T,
-
- skip: Cell<bool>,
+ pub(in crate::shortest_paths) priority: T,
}
impl<S, T> PartialEq for PriorityQueueItem<'_, S, T>
@@ -23,7 +24,7 @@
T: PartialEq,
{
fn eq(&self, other: &Self) -> bool {
- self.priority.eq(&other.priority)
+ other.priority.eq(&self.priority)
}
}
@@ -40,71 +41,78 @@
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<S, T> Ord for QueueItem<'_, S, 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::NodeId: FlaggableGraphId<S>,
T: Ord,
{
- heap: BinaryHeap<Reverse<PriorityQueueItem<'a, S, T>>>,
+ heap: BinaryHeap<PriorityQueueItem<'a, S, T>>,
+
+ flags: <S::NodeId as FlaggableGraphId<S>>::Store<'a>,
}
impl<'a, S, T> PriorityQueue<'a, S, T>
where
S: GraphStorage,
+ S::NodeId: FlaggableGraphId<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(),
+ flags: <S::NodeId as FlaggableGraphId<S>>::flag_store(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),
- }));
+ self.heap.push(PriorityQueueItem { node, priority });
}
+ pub(in crate::shortest_paths) fn visit(&mut self, id: &'a S::NodeId) {
+ self.flags.set(id, true);
+ }
+
+ #[inline]
+ pub(in crate::shortest_paths) fn has_been_visited(&self, id: &'a S::NodeId) -> bool {
+ self.flags.index(id)
+ }
+
+ #[inline]
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;
- }
+ if self.has_been_visited(node.id()) {
+ return;
}
- self.heap.push(Reverse(PriorityQueueItem {
- node,
- priority,
-
- skip: Cell::new(false),
- }));
+ self.heap.push(PriorityQueueItem { node, priority });
}
- 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);
- }
- }
+ #[inline]
+ pub(in crate::shortest_paths) fn pop_min(&mut self) -> Option<QueueItem<'a, S, T>> {
+ loop {
+ let item = self.heap.pop()?;
- None
+ if self.has_been_visited(item.node.id()) {
+ continue;
+ }
+
+ self.visit(item.node.id());
+ return Some(item);
+ }
}
}
diff --git a/crates/algorithms/src/shortest_paths/common/transit.rs b/crates/algorithms/src/shortest_paths/common/transit.rs
index 2e05130..8921358 100644
--- a/crates/algorithms/src/shortest_paths/common/transit.rs
+++ b/crates/algorithms/src/shortest_paths/common/transit.rs
@@ -1,8 +1,4 @@
-use alloc::{vec, vec::Vec};
-use core::{
- hash::{BuildHasher, Hash},
- iter,
-};
+
use hashbrown::{HashMap, HashSet};
use petgraph_core::{GraphStorage, Node};
@@ -13,33 +9,32 @@
Record,
}
-pub(in crate::shortest_paths) fn reconstruct_path_to<'a, S, H>(
- predecessors: &HashMap<&'a S::NodeId, Option<Node<'a, S>>, H>,
+pub(in crate::shortest_paths) fn reconstruct_path_to<'a, S>(
+ predecessors: &<S::NodeId as AttributeGraphId<S>>::Store<'a, Option<Node<'a, S>>>,
target: &'a S::NodeId,
) -> Vec<Node<'a, S>>
where
S: GraphStorage,
- S::NodeId: Eq + Hash,
- H: BuildHasher,
+ S::NodeId: AttributeGraphId<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.id()).is_none() {
// we have reached the source node
break;
}
- path.push(node);
+ path.push(*node);
current = node.id();
}
diff --git a/crates/algorithms/src/shortest_paths/dijkstra/iter.rs b/crates/algorithms/src/shortest_paths/dijkstra/iter.rs
index 471ef22..c998f95 100644
--- a/crates/algorithms/src/shortest_paths/dijkstra/iter.rs
+++ b/crates/algorithms/src/shortest_paths/dijkstra/iter.rs
@@ -1,11 +1,15 @@
use alloc::vec::Vec;
use core::hash::Hash;
+use std::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::{AttributeGraphId, AttributeStorage, FlaggableGraphId},
+ Graph, GraphStorage, Node,
+};
use crate::shortest_paths::{
common::{
@@ -22,9 +26,11 @@
pub(super) struct DijkstraIter<'graph: 'parent, 'parent, S, E, G>
where
S: GraphStorage,
+ S::NodeId: FlaggableGraphId<S> + AttributeGraphId<S>,
E: GraphCost<S>,
E::Value: DijkstraMeasure,
{
+ graph: &'graph Graph<S>,
queue: PriorityQueue<'graph, S, E::Value>,
edge_cost: &'parent E,
@@ -35,18 +41,18 @@
num_nodes: usize,
init: bool,
- next: Option<Node<'graph, S>>,
+ next: Option<QueueItem<'graph, S, 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 AttributeGraphId<S>>::Store<'graph, E::Value>,
+ predecessors: <S::NodeId as AttributeGraphId<S>>::Store<'graph, Option<Node<'graph, S>>>,
}
impl<'graph: 'parent, 'parent, S, E, G> DijkstraIter<'graph, 'parent, S, E, G>
where
S: GraphStorage,
- S::NodeId: Eq + Hash,
+ S::NodeId: FlaggableGraphId<S> + AttributeGraphId<S>,
E: GraphCost<S>,
E::Value: DijkstraMeasure,
G: Connections<'graph, S>,
@@ -59,7 +65,7 @@
source: &'graph S::NodeId,
- intermediates: PredecessorMode,
+ predecessor_mode: PredecessorMode,
) -> Result<Self, DijkstraError> {
let source_node = graph
.node(source)
@@ -67,15 +73,16 @@
let queue = PriorityQueue::new();
- let mut distances = HashMap::with_hasher(FxBuildHasher::default());
- distances.insert(source, E::Value::zero());
+ let mut distances = <S::NodeId as AttributeGraphId<S>>::attribute_store(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 AttributeGraphId<S>>::attribute_store(graph.storage());
+ if predecessor_mode == PredecessorMode::Record {
+ predecessors.set(source, None);
}
Ok(Self {
+ graph,
queue,
edge_cost,
connections,
@@ -83,7 +90,7 @@
num_nodes: graph.num_nodes(),
init: true,
next: None,
- predecessor_mode: intermediates,
+ predecessor_mode,
distances,
predecessors,
})
@@ -93,7 +100,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: FlaggableGraphId<S> + AttributeGraphId<S>,
E: GraphCost<S>,
E::Value: DijkstraMeasure,
G: Connections<'graph, S>,
@@ -105,7 +112,11 @@
// and then begin with the actual iteration loop.
if self.init {
self.init = false;
- self.next = Some(self.source);
+ self.next = Some(QueueItem {
+ node: self.source,
+ priority: E::Value::zero(),
+ });
+ self.queue.visit(self.source.id());
return Some(Route::new(
Path::new(self.source, Vec::new(), self.source),
@@ -115,30 +126,43 @@
// Process the neighbours from the node we determined in the last iteration.
// Reasoning behind this see below.
- let node = self.next?;
+ let QueueItem {
+ 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.id() { 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 + 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));
}
- self.queue.decrease_priority(target, alternative);
+ 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 +180,28 @@
// 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())
};
- let path = Path::new(self.source, transit, 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..69732e4 100644
--- a/crates/algorithms/src/shortest_paths/dijkstra/mod.rs
+++ b/crates/algorithms/src/shortest_paths/dijkstra/mod.rs
@@ -11,6 +11,9 @@
use error_stack::Result;
use petgraph_core::{
edge::marker::{Directed, Undirected},
+ Direction,
+ },
+ id::FlaggableGraphId,
DirectedGraphStorage, Graph, GraphDirectionality, GraphStorage, Node,
};
@@ -174,7 +177,7 @@
impl<S, E> ShortestPath<S> for Dijkstra<Undirected, E>
where
S: GraphStorage,
- S::NodeId: Eq + Hash,
+ S::NodeId: FlaggableGraphId<S> + AttributeGraphId<S>,
E: GraphCost<S>,
E::Value: DijkstraMeasure,
{
@@ -258,7 +261,7 @@
impl<S, E> ShortestDistance<S> for Dijkstra<Undirected, E>
where
S: GraphStorage,
- S::NodeId: Eq + Hash,
+ S::NodeId: FlaggableGraphId<S> + AttributeGraphId<S>,
E: GraphCost<S>,
E::Value: DijkstraMeasure,
{
@@ -307,7 +310,7 @@
impl<S, E> ShortestDistance<S> for Dijkstra<Directed, E>
where
S: DirectedGraphStorage,
- S::NodeId: Eq + Hash,
+ S::NodeId: FlaggableGraphId<S> + AttributeGraphId<S>,
E: GraphCost<S>,
E::Value: DijkstraMeasure,
{
diff --git a/crates/algorithms/src/shortest_paths/mod.rs b/crates/algorithms/src/shortest_paths/mod.rs
index 8e7f26d..fb51d08 100644
--- a/crates/algorithms/src/shortest_paths/mod.rs
+++ b/crates/algorithms/src/shortest_paths/mod.rs
@@ -60,7 +60,7 @@
use petgraph_core::{Graph, GraphStorage};
pub use self::{
- astar::AStar,
+ // astar::AStar,
bellman_ford::BellmanFord,
common::{
cost::{Cost, GraphCost},
diff --git a/crates/core/src/error.rs b/crates/core/src/error.rs
index 5cd81db..ec86092 100644
--- a/crates/core/src/error.rs
+++ b/crates/core/src/error.rs
@@ -1,5 +1,7 @@
use core::fmt::{Display, Formatter};
+use error_stack::Context;
+
/// General error type for `petgraph-core`.
///
/// This error is used in [`Graph`] as a context from the returned result of fallible
diff --git a/crates/core/src/id/attributes.rs b/crates/core/src/id/attributes.rs
new file mode 100644
index 0000000..adb91be
--- /dev/null
+++ b/crates/core/src/id/attributes.rs
@@ -0,0 +1,36 @@
+use crate::{base::MaybeOwned, GraphStorage};
+
+// TODO: Entry API
+
+pub trait AttributeStorage<K, V> {
+ 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).unwrap()
+ }
+ fn index_mut(&mut self, id: &K) -> &mut V {
+ self.get_mut(id).unwrap()
+ }
+
+ fn set(&mut self, id: &K, value: V) -> Option<V>;
+ fn remove(&mut self, id: &K) -> Option<V>;
+
+ type Iter<'a>: Iterator<Item = (MaybeOwned<'a, K>, &'a V)>
+ where
+ K: 'a,
+ V: 'a,
+ Self: 'a;
+
+ fn iter(&self) -> Self::Iter<'_>;
+}
+
+pub trait AttributeGraphId<S>: Sized
+where
+ S: GraphStorage,
+{
+ type Store<'a, V>: AttributeStorage<Self, V>
+ where
+ S: 'a;
+
+ fn attribute_store<V>(storage: &S) -> Self::Store<'_, V>;
+}
diff --git a/crates/core/src/id/flag.rs b/crates/core/src/id/flag.rs
new file mode 100644
index 0000000..4cad073
--- /dev/null
+++ b/crates/core/src/id/flag.rs
@@ -0,0 +1,23 @@
+use crate::GraphStorage;
+// TODO: naming
+
+pub trait FlagStorage<Id> {
+ fn get(&self, id: &Id) -> Option<bool>;
+ #[inline]
+ fn index(&self, id: &Id) -> bool {
+ self.get(id).unwrap_or(false)
+ }
+
+ fn set(&mut self, id: &Id, flag: bool) -> Option<bool>;
+}
+
+pub trait FlaggableGraphId<S>: Sized
+where
+ S: GraphStorage,
+{
+ type Store<'a>: FlagStorage<Self>
+ where
+ S: 'a;
+
+ fn flag_store(storage: &S) -> Self::Store<'_>;
+}
diff --git a/crates/core/src/id/mod.rs b/crates/core/src/id/mod.rs
index f5eb4be..f298d14 100644
--- a/crates/core/src/id/mod.rs
+++ b/crates/core/src/id/mod.rs
@@ -7,9 +7,15 @@
//! 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 attributes;
+mod flag;
mod linear;
-pub use self::linear::{IndexMapper, LinearGraphId};
+pub use self::{
+ attributes::{AttributeGraphId, AttributeStorage},
+ flag::{FlagStorage, FlaggableGraphId},
+ linear::{IndexMapper, LinearGraphId},
+};
use crate::attributes::NoValue;
// The `PartialEq` bound is required for the default implementation, we could in theory remove it,
diff --git a/crates/dino/Cargo.toml b/crates/dino/Cargo.toml
index 0c0e715..758ab55 100644
--- a/crates/dino/Cargo.toml
+++ b/crates/dino/Cargo.toml
@@ -11,8 +11,10 @@
error-stack.workspace = true
either = "1.9.0" # TODO: potentially remove
+bitvec = "1.0.1"
# Closures
roaring = "0.10.2"
+croaring = "1.0.1"
fnv = { version = "1.0.7", default-features = false }
hashbrown = { workspace = true, features = ['ahash'] }
diff --git a/crates/dino/src/closure/mod.rs b/crates/dino/src/closure/mod.rs
index 5495d96..6ab397d 100644
--- a/crates/dino/src/closure/mod.rs
+++ b/crates/dino/src/closure/mod.rs
@@ -1,29 +1,20 @@
mod union;
+use croaring::Bitmap as RoaringBitmap;
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::union::UnionIterator;
use crate::{
- closure::union::UnionIntoIterator,
- edge::Edge,
- node::Node,
+ edge::{Edge, EdgeSlab},
+ node::{Node, NodeSlab},
slab::{EntryId, Key as _, Slab},
EdgeId, NodeId,
};
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
enum Key {
- SourceToTargets(NodeId),
- TargetToSources(NodeId),
-
- SourceToEdges(NodeId),
- TargetsToEdges(NodeId),
-
EndpointsToEdges(NodeId, NodeId),
}
@@ -41,138 +32,118 @@
}
}
- fn create_edge<T>(&mut self, edge: &Edge<T>) {
+ fn create_edge<T, U>(&mut self, edge: &Edge<T>, nodes: &mut NodeSlab<U>) {
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());
+ if let Some(source) = nodes.get_mut(source) {
+ source.closures.outgoing_nodes.push(target);
+ source.closures.outgoing_edges.push(edge.id);
+ }
- 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);
+ if let Some(target) = nodes.get_mut(target) {
+ target.closures.incoming_nodes.push(source);
+ target.closures.incoming_edges.push(edge.id);
+ }
self.inner
.entry(Key::EndpointsToEdges(source, target))
.or_default()
- .insert(raw_index);
+ .add(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 remove_edge<T, U>(&mut self, edge: &Edge<T>, nodes: &mut NodeSlab<U>) {
+ todo!()
+ // 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.cardinality() > 1);
+ //
+ // if let Some(source) = nodes.get_mut(source) {
+ // if !is_multi {
+ // source
+ // .closures
+ // .outgoing_nodes
+ // .remove(target.into_id().raw());
+ // }
+ //
+ // source.closures.outgoing_edges.remove(raw_index);
+ // }
+ //
+ // if let Some(target) = nodes.get_mut(target) {
+ // if !is_multi {
+ // target
+ // .closures
+ // .incoming_nodes
+ // .remove(source.into_id().raw());
+ // }
+ //
+ // target.closures.incoming_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>, nodes: &mut NodeSlab<T>) -> (NodeId, T) {
+ todo!()
+ // let raw_index = node.id.into_id().raw();
+ //
+ // let targets = node.closures.outgoing_nodes;
+ // for target in targets.iter() {
+ // let target_id = NodeId::from_id(EntryId::new_unchecked(target));
+ //
+ // let Some(target) = nodes.get_mut(target_id) else {
+ // continue;
+ // };
+ //
+ // target.closures.incoming_nodes.remove(raw_index);
+ //
+ // self.inner
+ // .remove(&Key::EndpointsToEdges(node.id, target_id));
+ // }
+ //
+ // let sources = node.closures.incoming_nodes;
+ // for source in sources.iter() {
+ // let source_id = NodeId::from_id(EntryId::new_unchecked(source));
+ //
+ // let Some(source) = nodes.get_mut(source_id) else {
+ // continue;
+ // };
+ //
+ // source.closures.outgoing_nodes.remove(raw_index);
+ // self.inner
+ // .remove(&Key::EndpointsToEdges(source_id, node.id));
+ // }
+ //
+ // (node.id, node.weight)
}
- 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) {
+ fn clear<N>(&mut self, nodes: &mut NodeSlab<N>) {
self.inner.clear();
+
+ for node in nodes.iter_mut() {
+ node.closures.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);
- }
+ fn refresh<N, E>(&mut self, nodes: &mut NodeSlab<N>, edges: &EdgeSlab<E>) {
+ self.clear(nodes);
for edge in edges.iter() {
- self.create_edge(edge);
+ self.create_edge(edge, nodes);
}
}
@@ -185,122 +156,6 @@
}
}
-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,
}
@@ -374,54 +229,20 @@
}
}
- pub(crate) const fn nodes(&self) -> NodeClosure<'_> {
- NodeClosure::new(&self.storage)
- }
-
- 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) fn remove_node<T>(&mut self, node: Node<T>, nodes: &mut NodeSlab<T>) -> (NodeId, T) {
+ self.storage.remove_node(node, nodes)
}
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 create_edge<T, U>(&mut self, edge: &Edge<T>, nodes: &mut NodeSlab<U>) {
+ self.storage.create_edge(edge, nodes);
}
- 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)))
- }
- };
-
- iter.map(|id| EdgeId::from_id(EntryId::new_unchecked(id)))
+ pub(crate) fn remove_edge<T, U>(&mut self, edge: &Edge<T>, nodes: &mut NodeSlab<U>) {
+ self.storage.remove_edge(edge, nodes);
}
pub(crate) fn reserve(&mut self, additional: usize) {
@@ -434,28 +255,30 @@
pub(crate) fn refresh<N, E>(
&mut self,
- nodes: &Slab<NodeId, Node<N>>,
+ nodes: &mut Slab<NodeId, Node<N>>,
edges: &Slab<EdgeId, Edge<E>>,
) {
self.storage.refresh(nodes, edges);
}
- pub(crate) fn clear(&mut self) {
- self.storage.clear();
+ pub(crate) fn clear<N>(&mut self, nodes: &mut NodeSlab<N>) {
+ self.storage.clear(nodes);
}
}
#[cfg(test)]
mod tests {
+ use alloc::vec::Vec;
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};
+ use roaring::RoaringBitmap;
use crate::{
- closure::{Closures, Key},
+ closure::Key,
slab::{EntryId, Key as _},
- DinoGraph, EdgeId, NodeId,
+ DinoGraph, DinoStorage, EdgeId, NodeId,
};
#[derive(Debug, Clone, PartialEq, Eq)]
@@ -472,19 +295,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.outgoing_neighbours().collect(),
+ incoming_neighbours: node.incoming_neighbours().collect(),
- neighbours: lookup.neighbours(id).collect(),
+ neighbours: node.neighbours().collect(),
- outgoing_edges: lookup.outgoing_edges(id).collect(),
- incoming_edges: lookup.incoming_edges(id).collect(),
+ outgoing_edges: node.outgoing_edges().collect(),
+ incoming_edges: node.incoming_edges().collect(),
- edges: lookup.edges(id).collect(),
+ edges: node.edges().collect(),
}
}
}
@@ -501,71 +324,40 @@
}
impl EvaluatedEdgeClosures {
- fn new(closures: &Closures) -> Self {
+ fn new<N, E>(storage: &DinoStorage<N, E>) -> Self {
+ fn node_id_set(bitmap: &[NodeId]) -> HashSet<NodeId> {
+ bitmap.iter().copied().collect()
+ }
+
+ fn edge_id_set(bitmap: &[EdgeId]) -> HashSet<EdgeId> {
+ bitmap.iter().copied().collect()
+ }
+
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_id_set(&node.closures.outgoing_nodes)))
.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_id_set(&node.closures.incoming_nodes)))
.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, edge_id_set(&node.closures.outgoing_edges)))
.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, edge_id_set(&node.closures.incoming_edges)))
.collect(),
- endpoints_to_edges: closures
+ endpoints_to_edges: storage
+ .closures
.storage
.inner
.iter()
@@ -599,16 +391,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();
@@ -618,14 +400,10 @@
let closures = &graph.storage().closures;
- assert_storage_size(closures, 1, 0);
- assert_eq!(
- closures.nodes().externals().collect::<HashSet<_>>(),
- once(id).collect()
- );
+ assert_eq!(externals(&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 +415,7 @@
);
assert_eq!(
- EvaluatedEdgeClosures::new(closures),
+ EvaluatedEdgeClosures::new(graph.storage()),
EvaluatedEdgeClosures {
source_to_targets: map! {
id => HashSet::new(),
@@ -656,6 +434,18 @@
);
}
+ fn externals<N, E, D>(graph: &DinoGraph<N, E, D>) -> HashSet<NodeId>
+ where
+ D: GraphDirectionality,
+ {
+ graph
+ .storage()
+ .nodes
+ .entries()
+ .filter_map(|(id, node)| node.is_isolated().then_some(id))
+ .collect()
+ }
+
#[test]
fn multiple_nodes() {
let mut graph = DinoGraph::<u8, u8, Directed>::new();
@@ -666,16 +456,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!(externals(&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 +471,7 @@
);
assert_eq!(
- EvaluatedNodeClosure::new(closures, b),
+ EvaluatedNodeClosure::new(graph.storage(), b),
EvaluatedNodeClosure {
outgoing_neighbours: HashSet::new(),
incoming_neighbours: HashSet::new(),
@@ -699,7 +483,7 @@
);
assert_eq!(
- EvaluatedEdgeClosures::new(closures),
+ EvaluatedEdgeClosures::new(graph.storage()),
EvaluatedEdgeClosures {
source_to_targets: map! {
a => HashSet::new(),
@@ -735,13 +519,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!(externals(&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 +534,7 @@
);
assert_eq!(
- EvaluatedNodeClosure::new(closures, b),
+ EvaluatedNodeClosure::new(graph.storage(), b),
EvaluatedNodeClosure {
outgoing_neighbours: HashSet::new(),
incoming_neighbours: once(a).collect(),
@@ -765,7 +546,7 @@
);
assert_eq!(
- EvaluatedEdgeClosures::new(closures),
+ EvaluatedEdgeClosures::new(graph.storage()),
EvaluatedEdgeClosures {
source_to_targets: map! {
a => once(b).collect(),
@@ -800,13 +581,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!(externals(&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 +596,7 @@
);
assert_eq!(
- EvaluatedEdgeClosures::new(closures),
+ EvaluatedEdgeClosures::new(graph.storage()),
EvaluatedEdgeClosures {
source_to_targets: map! {
a => once(a).collect(),
@@ -897,13 +675,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!(externals(&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 +690,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 +702,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 +714,7 @@
);
assert_eq!(
- EvaluatedEdgeClosures::new(closures),
+ EvaluatedEdgeClosures::new(graph.storage()),
EvaluatedEdgeClosures {
source_to_targets: map! {
a => once(b).collect(),
@@ -993,13 +768,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!(externals(&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 +783,7 @@
);
assert_eq!(
- EvaluatedNodeClosure::new(closures, b),
+ EvaluatedNodeClosure::new(graph.storage(), b),
EvaluatedNodeClosure {
outgoing_neighbours: HashSet::new(),
incoming_neighbours: once(a).collect(),
@@ -1023,7 +795,7 @@
);
assert_eq!(
- EvaluatedEdgeClosures::new(closures),
+ EvaluatedEdgeClosures::new(graph.storage()),
EvaluatedEdgeClosures {
source_to_targets: map! {
a => once(b).collect(),
@@ -1064,13 +836,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!(externals(&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 +851,7 @@
);
assert_eq!(
- EvaluatedNodeClosure::new(closures, c),
+ EvaluatedNodeClosure::new(graph.storage(), c),
EvaluatedNodeClosure {
outgoing_neighbours: once(a).collect(),
incoming_neighbours: HashSet::new(),
@@ -1094,7 +863,7 @@
);
assert_eq!(
- EvaluatedEdgeClosures::new(closures),
+ EvaluatedEdgeClosures::new(graph.storage()),
EvaluatedEdgeClosures {
source_to_targets: map! {
a => HashSet::new(),
@@ -1136,13 +905,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!(externals(&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 +920,7 @@
);
assert_eq!(
- EvaluatedNodeClosure::new(closures, b),
+ EvaluatedNodeClosure::new(graph.storage(), b),
EvaluatedNodeClosure {
outgoing_neighbours: HashSet::new(),
incoming_neighbours: once(a).collect(),
@@ -1166,7 +932,7 @@
);
assert_eq!(
- EvaluatedNodeClosure::new(closures, c),
+ EvaluatedNodeClosure::new(graph.storage(), c),
EvaluatedNodeClosure {
outgoing_neighbours: once(a).collect(),
incoming_neighbours: HashSet::new(),
@@ -1178,7 +944,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
index 24c6a0f..60e74de 100644
--- a/crates/dino/src/closure/union.rs
+++ b/crates/dino/src/closure/union.rs
@@ -1,4 +1,4 @@
-use roaring::RoaringBitmap;
+use croaring::Bitmap as RoaringBitmap;
#[derive(Default)]
struct IteratorState {
@@ -83,35 +83,9 @@
}
}
-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>,
+ left: croaring::bitmap::BitmapIterator<'a>,
+ right: croaring::bitmap::BitmapIterator<'a>,
state: IteratorState,
}
@@ -142,9 +116,9 @@
mod tests {
use alloc::vec::Vec;
- use roaring::RoaringBitmap;
+ use croaring::Bitmap as RoaringBitmap;
- use crate::closure::union::{UnionIntoIterator, UnionIterator};
+ use crate::closure::union::UnionIterator;
#[test]
fn empty() {
@@ -153,51 +127,39 @@
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 a = RoaringBitmap::from_iter(0..10);
+ let b = RoaringBitmap::from_iter(10..20);
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 a = RoaringBitmap::from_iter(0..10);
+ let b = RoaringBitmap::from_iter(5..15);
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();
+ let mut a = RoaringBitmap::from_iter(0..10);
+ let mut b = RoaringBitmap::from_iter(5..15);
- a.insert_range(20..30);
- b.insert_range(25..35);
+ a.add_range(20..30);
+ b.add_range(25..35);
- a.insert_range(40..50);
- b.insert_range(15..21);
- b.insert_range(29..42);
+ a.add_range(40..50);
+ b.add_range(15..21);
+ b.add_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/directed.rs b/crates/dino/src/directed.rs
index 9e774aa..37ed7b6 100644
--- a/crates/dino/src/directed.rs
+++ b/crates/dino/src/directed.rs
@@ -5,7 +5,9 @@
storage::{DirectedGraphStorage, GraphStorage},
};
-use crate::{DinoStorage, Directed};
+use crate::{
+ iter::directed::NodeDirectedConnectionsIter, node::NodeClosures, DinoStorage, Directed,
+};
impl<N, E> DirectedGraphStorage for DinoStorage<N, E, Directed> {
fn directed_edges_between<'a: 'b, 'b>(
@@ -40,13 +42,13 @@
id: &'b 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)),
+ 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>(
@@ -54,19 +56,18 @@
id: &'b Self::NodeId,
direction: Direction,
) -> impl Iterator<Item = EdgeMut<'a, Self>> + 'b {
- let Self {
- closures, edges, ..
- } = 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 => Either::Left(node.incoming_edges()),
+ Direction::Outgoing => Either::Right(node.outgoing_edges()),
+ });
edges
- .filter_mut(available)
+ .filter_mut(allow)
.map(|edge| EdgeMut::new(&edge.id, &mut edge.weight, &edge.source, &edge.target))
}
@@ -75,13 +76,14 @@
id: &'b 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))
+ self.nodes
+ .get(*id)
+ .into_iter()
+ .flat_map(move |node| match direction {
+ Direction::Incoming => Either::Left(node.incoming_neighbours()),
+ Direction::Outgoing => Either::Right(node.outgoing_neighbours()),
+ })
+ .filter_map(move |id| self.node(&id))
}
fn node_directed_neighbours_mut<'a: 'b, 'b>(
@@ -89,19 +91,22 @@
id: &'b 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)),
+ 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 { &*(&node.closures as *const _) };
+ let neighbours = match direction {
+ Direction::Incoming => Either::Left(closure.incoming_neighbours()),
+ Direction::Outgoing => Either::Right(closure.outgoing_neighbours()),
+ };
+
+ 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..595d101 100644
--- a/crates/dino/src/edge.rs
+++ b/crates/dino/src/edge.rs
@@ -71,6 +71,8 @@
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..d50c642
--- /dev/null
+++ b/crates/dino/src/iter/closure.rs
@@ -0,0 +1,4 @@
+use crate::{EdgeId, NodeId};
+
+pub type NodeIdClosureIter<'a> = core::iter::Copied<core::slice::Iter<'a, NodeId>>;
+pub type EdgeIdClosureIter<'a> = core::iter::Copied<core::slice::Iter<'a, EdgeId>>;
diff --git a/crates/dino/src/iter/directed.rs b/crates/dino/src/iter/directed.rs
new file mode 100644
index 0000000..4acccf7
--- /dev/null
+++ b/crates/dino/src/iter/directed.rs
@@ -0,0 +1,43 @@
+use petgraph_core::{edge::Direction, Edge, GraphDirectionality, GraphStorage};
+
+use crate::{iter::closure::NodeIdClosureIter, node::Node, slab::Key, DinoStorage, EdgeId, NodeId};
+
+pub 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 id = iter.next()?;
+
+ 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..0d12dfa 100644
--- a/crates/dino/src/lib.rs
+++ b/crates/dino/src/lib.rs
@@ -109,6 +109,7 @@
mod edge;
mod node;
+pub(crate) mod iter;
mod retain;
pub(crate) mod slab;
#[cfg(test)]
@@ -119,6 +120,7 @@
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 +134,12 @@
Graph,
};
-use crate::{closure::Closures, edge::Edge, node::Node, slab::Slab};
+use crate::{
+ closure::Closures,
+ edge::Edge,
+ node::{Node, NodeClosures},
+ slab::Slab,
+};
/// Alias for a [`Graph`] that uses [`DinoStorage`] as its backing storage.
///
@@ -433,7 +440,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))
@@ -456,7 +463,7 @@
// 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,
@@ -520,11 +527,9 @@
.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))
}
@@ -572,7 +577,7 @@
// 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);
+ self.closures.create_edge(edge, &mut self.nodes);
Ok(EdgeMut::new(
&edge.id,
@@ -586,16 +591,17 @@
&mut self,
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.edges() {
if let Some(edge) = self.edges.remove(edge) {
- self.closures.remove_edge(&edge);
+ self.closures.remove_edge(&edge, &mut self.nodes);
}
}
- let node = self.nodes.remove(*id)?;
- self.closures.remove_node(&node);
+ let (id, weight) = self.closures.remove_node(node, &mut self.nodes);
- Some(DetachedNode::new(node.id, node.weight))
+ Some(DetachedNode::new(id, weight))
}
fn remove_edge(
@@ -603,7 +609,7 @@
id: &Self::EdgeId,
) -> Option<DetachedEdge<Self::EdgeId, Self::NodeId, Self::EdgeWeight>> {
let edge = self.edges.remove(*id)?;
- self.closures.remove_edge(&edge);
+ self.closures.remove_edge(&edge, &mut self.nodes);
Some(DetachedEdge::new(
edge.id,
@@ -616,7 +622,7 @@
fn clear(&mut self) {
self.nodes.clear();
self.edges.clear();
- self.closures.clear();
+ self.closures.clear(&mut self.nodes);
}
fn node(&self, id: &Self::NodeId) -> Option<petgraph_core::node::Node<Self>> {
@@ -683,22 +689,26 @@
&'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))
+ self.nodes
+ .get(*id)
+ .into_iter()
+ .flat_map(move |node| node.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;
+ let Self { nodes, edges, .. } = self;
+
+ let allow = nodes
+ .get(*id)
+ .into_iter()
+ .flat_map(move |node| node.edges());
edges
- .filter_mut(closures.nodes().edges(*id))
+ .filter_mut(allow)
.map(move |edge| EdgeMut::new(&edge.id, &mut edge.weight, &edge.source, &edge.target))
}
@@ -706,9 +716,10 @@
&'a self,
id: &'b Self::NodeId,
) -> impl Iterator<Item = petgraph_core::node::Node<'a, Self>> + 'b {
- self.closures
- .nodes()
- .neighbours(*id)
+ self.nodes
+ .get(*id)
+ .into_iter()
+ .flat_map(move |node| node.neighbours())
.filter_map(move |node| self.node(&node))
}
@@ -716,29 +727,33 @@
&'a mut self,
id: &'b Self::NodeId,
) -> impl Iterator<Item = NodeMut<'a, Self>> + 'b {
- let Self {
- closures, nodes, ..
- } = 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 { &*(&node.closures as *const _) };
+ 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.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())
+ self.nodes
+ .iter_mut()
+ .filter(move |node| node.is_isolated())
.map(move |node| NodeMut::new(&node.id, &mut node.weight))
}
diff --git a/crates/dino/src/node.rs b/crates/dino/src/node.rs
index c4c2e54..f3a9187 100644
--- a/crates/dino/src/node.rs
+++ b/crates/dino/src/node.rs
@@ -1,14 +1,25 @@
-use core::fmt::{Display, Formatter};
+use alloc::vec::Vec;
+use core::{
+ fmt::{Display, Formatter},
+ iter::Enumerate,
+};
+use bitvec::{boxed::BitBox, vec::BitVec};
use petgraph_core::{
attributes::NoValue,
+ base::MaybeOwned,
edge::marker::GraphDirectionality,
- id::{GraphId, LinearGraphId, ManagedGraphId},
+ id::{
+ AttributeGraphId, AttributeStorage, FlagStorage, FlaggableGraphId, GraphId, IndexMapper,
+ LinearGraphId, ManagedGraphId,
+ },
+ GraphStorage,
};
use crate::{
- slab::{EntryId, Key, SlabIndexMapper},
- DinoStorage,
+ iter::closure::{EdgeIdClosureIter, NodeIdClosureIter},
+ slab::{EntryId, Generation, Key, SlabIndexMapper},
+ DinoStorage, EdgeId,
};
/// Identifier for a node in [`DinoStorage`].
@@ -45,6 +56,7 @@
Self(id)
}
+ #[inline]
fn into_id(self) -> EntryId {
self.0
}
@@ -65,16 +77,278 @@
}
}
+// TODO: potential matter to reduce memory usage
+pub struct FlagStore {
+ vector: BitBox,
+}
+
+impl FlagStorage<NodeId> for FlagStore {
+ #[inline]
+ fn get(&self, id: &NodeId) -> Option<bool> {
+ self.vector.get(id.into_id().index()).map(|flag| *flag)
+ }
+
+ #[inline]
+
+ fn index(&self, id: &NodeId) -> bool {
+ self.vector[id.into_id().index()]
+ }
+
+ fn set(&mut self, id: &NodeId, flag: bool) -> Option<bool> {
+ let old = self.vector.replace(id.into_id().index(), flag);
+
+ Some(old)
+ }
+}
+
+impl<N, E, D> FlaggableGraphId<DinoStorage<N, E, D>> for NodeId
+where
+ D: GraphDirectionality,
+{
+ type Store<'a> = FlagStore where
+ DinoStorage<N, E, D>: 'a;
+
+ fn flag_store(storage: &DinoStorage<N, E, D>) -> Self::Store<'_> {
+ let vector = BitVec::repeat(false, storage.num_nodes()).into_boxed_bitslice();
+
+ Self::Store { vector }
+ }
+}
+
+pub struct AttributeStoreIter<'a, T> {
+ iter: Enumerate<core::slice::Iter<'a, Option<(Generation, T)>>>,
+}
+
+impl<'a, T> Iterator for AttributeStoreIter<'a, T> {
+ type Item = (MaybeOwned<'a, NodeId>, &'a T);
+
+ fn next(&mut self) -> Option<Self::Item> {
+ loop {
+ let (index, item) = self.iter.next()?;
+
+ if let Some((generation, item)) = item {
+ let id = EntryId::new(*generation, index)?;
+ let id = NodeId::from_id(id);
+
+ return Some((MaybeOwned::Owned(id), item));
+ }
+ }
+ }
+}
+
+pub struct AttributeStore<T> {
+ items: Vec<Option<(Generation, T)>>,
+}
+
+impl<T> AttributeStorage<NodeId, T> for AttributeStore<T> {
+ type Iter<'a> = AttributeStoreIter<'a, T> where NodeId: 'a, T: 'a, Self: 'a;
+
+ fn get(&self, id: &NodeId) -> Option<&T> {
+ if id.into_id().index() >= self.items.len() {
+ return None;
+ }
+
+ self.items[id.into_id().index()]
+ .as_ref()
+ .map(|(_, item)| item)
+ }
+
+ fn get_mut(&mut self, id: &NodeId) -> Option<&mut T> {
+ if id.into_id().index() >= self.items.len() {
+ return None;
+ }
+
+ self.items[id.into_id().index()]
+ .as_mut()
+ .map(|(_, item)| item)
+ }
+
+ fn index(&self, id: &NodeId) -> &T {
+ self.items[id.into_id().index()]
+ .as_ref()
+ .map(|(_, item)| item)
+ .expect("index called on empty node")
+ }
+
+ fn index_mut(&mut self, id: &NodeId) -> &mut T {
+ self.items[id.into_id().index()]
+ .as_mut()
+ .map(|(_, item)| item)
+ .expect("index_mut called on empty node")
+ }
+
+ fn set(&mut self, id: &NodeId, value: T) -> Option<T> {
+ let index = id.into_id().index();
+ let generation = id.into_id().generation();
+
+ if index >= self.items.len() {
+ return None;
+ }
+
+ core::mem::replace(&mut self.items[index], Some((generation, value))).map(|(_, item)| item)
+ }
+
+ fn remove(&mut self, id: &NodeId) -> Option<T> {
+ let index = id.into_id().index();
+
+ if index >= self.items.len() {
+ return None;
+ }
+
+ self.items[index].take().map(|(_, item)| item)
+ }
+
+ fn iter(&self) -> Self::Iter<'_> {
+ Self::Iter {
+ iter: self.items.iter().enumerate(),
+ }
+ }
+}
+
+impl<N, E, D> AttributeGraphId<DinoStorage<N, E, D>> for NodeId
+where
+ D: GraphDirectionality,
+{
+ type Store<'a, T> = AttributeStore<T> where DinoStorage<N, E, D>: 'a;
+
+ fn attribute_store<T>(storage: &DinoStorage<N, E, D>) -> Self::Store<'_, T> {
+ let mut items = Vec::with_capacity(storage.nodes.total_len());
+ items.resize_with(storage.nodes.total_len(), || None);
+
+ Self::Store { items }
+ }
+}
+
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 {
+ pub(crate) outgoing_nodes: Vec<NodeId>,
+ pub(crate) incoming_nodes: Vec<NodeId>,
+
+ pub(crate) outgoing_edges: Vec<EdgeId>,
+ pub(crate) incoming_edges: Vec<EdgeId>,
+}
+
+impl NodeClosures {
+ fn new() -> Self {
+ Self {
+ outgoing_nodes: Vec::new(),
+ incoming_nodes: Vec::new(),
+
+ outgoing_edges: Vec::new(),
+ incoming_edges: Vec::new(),
+ }
+ }
+
+ pub(crate) fn outgoing_neighbours(&self) -> NodeIdClosureIter {
+ self.outgoing_nodes.iter().copied()
+ }
+
+ pub(crate) fn incoming_neighbours(&self) -> NodeIdClosureIter {
+ self.incoming_nodes.iter().copied()
+ }
+
+ pub(crate) fn neighbours(&self) -> impl Iterator<Item = NodeId> + '_ {
+ todo!();
+ core::iter::empty()
+ }
+
+ 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) -> impl Iterator<Item = EdgeId> + '_ {
+ todo!();
+ core::iter::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 }
+ pub(crate) fn new(id: NodeId, weight: T) -> Self {
+ Self {
+ id,
+ weight,
+ closures: NodeClosures::new(),
+ }
+ }
+
+ pub(crate) fn outgoing_neighbours(&self) -> impl Iterator<Item = NodeId> + '_ {
+ self.closures.outgoing_neighbours()
+ }
+
+ pub(crate) fn incoming_neighbours(&self) -> impl Iterator<Item = NodeId> + '_ {
+ self.closures.incoming_neighbours()
+ }
+
+ pub(crate) fn neighbours(&self) -> impl Iterator<Item = NodeId> + '_ {
+ self.closures.neighbours()
+ }
+
+ pub(crate) fn outgoing_edges(&self) -> impl Iterator<Item = EdgeId> + '_ {
+ self.closures.outgoing_edges()
+ }
+
+ pub(crate) fn incoming_edges(&self) -> impl Iterator<Item = EdgeId> + '_ {
+ self.closures.incoming_edges()
+ }
+
+ pub(crate) fn edges(&self) -> impl Iterator<Item = EdgeId> + '_ {
+ self.closures.edges()
+ }
+
+ pub(crate) fn is_isolated(&self) -> bool {
+ self.closures.outgoing_nodes.is_empty() && self.closures.incoming_nodes.is_empty()
+ }
+}
+
+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..48661e9 100644
--- a/crates/dino/src/retain.rs
+++ b/crates/dino/src/retain.rs
@@ -42,7 +42,7 @@
edges(edge)
});
- self.closures.refresh(&self.nodes, &self.edges);
+ self.closures.refresh(&mut self.nodes, &self.edges);
}
fn retain_nodes(&mut self, mut f: impl FnMut(NodeMut<'_, Self>) -> bool) {
@@ -65,7 +65,7 @@
&& !removed.contains(value.target.into_id().raw())
});
- self.closures.refresh(&self.nodes, &self.edges);
+ self.closures.refresh(&mut self.nodes, &self.edges);
}
fn retain_edges(&mut self, mut f: impl FnMut(EdgeMut<'_, Self>) -> bool) {
@@ -75,6 +75,6 @@
f(edge)
});
- self.closures.refresh(&self.nodes, &self.edges);
+ self.closures.refresh(&mut self.nodes, &self.edges);
}
}
diff --git a/crates/dino/src/slab/mod.rs b/crates/dino/src/slab/mod.rs
index 8a8a811..6321d35 100644
--- a/crates/dino/src/slab/mod.rs
+++ b/crates/dino/src/slab/mod.rs
@@ -145,6 +145,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 +362,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>
