weavatrix_graph/working/
core.rs

1use super::{StableEdgeKey, StableNodeKey};
2use crate::graph::validate::{validate_edge, validate_node};
3use crate::{Edge, EdgeEndpoints, GraphError, Node, NodeId, Result};
4use crate::{ToString, Vec};
5#[cfg(not(feature = "std"))]
6use alloc::collections::BTreeMap as NodeMap;
7#[cfg(feature = "std")]
8use std::collections::HashMap as NodeMap;
9
10pub(super) struct WorkingEdge {
11    pub(super) value: Edge,
12    pub(super) source: StableNodeKey,
13    pub(super) target: StableNodeKey,
14}
15
16pub(super) struct NodeSlot {
17    pub(super) generation: u32,
18    pub(super) value: Option<Node>,
19    pub(super) outgoing: Vec<StableEdgeKey>,
20    pub(super) incoming: Vec<StableEdgeKey>,
21}
22
23pub(super) struct EdgeSlot {
24    pub(super) generation: u32,
25    pub(super) value: Option<WorkingEdge>,
26}
27
28#[derive(Default)]
29pub struct WorkingGraph {
30    pub(super) nodes: Vec<NodeSlot>,
31    pub(super) edges: Vec<EdgeSlot>,
32    pub(super) node_by_id: NodeMap<NodeId, StableNodeKey>,
33    pub(super) free_nodes: Vec<u32>,
34    pub(super) free_edges: Vec<u32>,
35    pub(super) node_count: usize,
36    pub(super) edge_count: usize,
37}
38
39impl WorkingGraph {
40    #[must_use]
41    pub fn new() -> Self {
42        Self::default()
43    }
44
45    #[must_use]
46    pub fn with_capacity(nodes: usize, edges: usize) -> Self {
47        Self {
48            nodes: Vec::with_capacity(nodes),
49            edges: Vec::with_capacity(edges),
50            node_by_id: node_map_with_capacity(nodes),
51            free_nodes: Vec::new(),
52            free_edges: Vec::new(),
53            node_count: 0,
54            edge_count: 0,
55        }
56    }
57
58    /// Inserts a node idempotently and returns its generation-stable key.
59    ///
60    /// # Errors
61    ///
62    /// Returns an error for invalid nodes or conflicting definitions.
63    pub fn insert_node(&mut self, node: Node) -> Result<StableNodeKey> {
64        validate_node(&node)?;
65        if let Some(&key) = self.node_by_id.get(&node.id) {
66            if self.node(key) == Some(&node) {
67                return Ok(key);
68            }
69            return Err(GraphError::ConflictingNode {
70                id: node.id.to_string(),
71            });
72        }
73        let id = node.id.clone();
74        let key = self.allocate_node(node)?;
75        self.node_by_id.insert(id, key);
76        self.node_count += 1;
77        Ok(key)
78    }
79
80    /// Inserts an edge after resolving its endpoint ids.
81    ///
82    /// # Errors
83    ///
84    /// Returns an error for invalid evidence or missing endpoints.
85    pub fn insert_edge(&mut self, edge: Edge) -> Result<StableEdgeKey> {
86        validate_edge(&edge)?;
87        let source = self.node_by_id.get(&edge.source).copied().ok_or_else(|| {
88            GraphError::MissingEdgeSource {
89                id: edge.source.to_string(),
90            }
91        })?;
92        let target = self.node_by_id.get(&edge.target).copied().ok_or_else(|| {
93            GraphError::MissingEdgeTarget {
94                id: edge.target.to_string(),
95            }
96        })?;
97        if self.node_slot(source).is_none() {
98            return Err(GraphError::MissingEdgeSource {
99                id: edge.source.to_string(),
100            });
101        }
102        if self.node_slot(target).is_none() {
103            return Err(GraphError::MissingEdgeTarget {
104                id: edge.target.to_string(),
105            });
106        }
107        let key = self.allocate_edge(WorkingEdge {
108            value: edge,
109            source,
110            target,
111        })?;
112        if let Some(slot) = self.node_slot_mut(source) {
113            slot.outgoing.push(key);
114        }
115        if let Some(slot) = self.node_slot_mut(target) {
116            slot.incoming.push(key);
117        }
118        self.edge_count += 1;
119        Ok(key)
120    }
121
122    #[must_use]
123    pub fn node(&self, key: StableNodeKey) -> Option<&Node> {
124        self.node_slot(key)?.value.as_ref()
125    }
126
127    #[must_use]
128    pub fn edge(&self, key: StableEdgeKey) -> Option<&Edge> {
129        Some(&self.edge_slot(key)?.value.as_ref()?.value)
130    }
131
132    #[must_use]
133    pub fn node_key(&self, id: &str) -> Option<StableNodeKey> {
134        self.node_by_id.get(id).copied()
135    }
136
137    #[must_use]
138    pub fn edge_endpoints(&self, key: StableEdgeKey) -> Option<EdgeEndpoints<StableNodeKey>> {
139        let edge = self.edge_slot(key)?.value.as_ref()?;
140        Some(EdgeEndpoints::new(edge.source, edge.target))
141    }
142
143    pub fn nodes(&self) -> impl Iterator<Item = (StableNodeKey, &Node)> {
144        self.nodes.iter().enumerate().filter_map(|(slot, entry)| {
145            let node = entry.value.as_ref()?;
146            Some((
147                StableNodeKey::new(u32::try_from(slot).ok()?, entry.generation),
148                node,
149            ))
150        })
151    }
152
153    pub fn edges(&self) -> impl Iterator<Item = (StableEdgeKey, &Edge)> {
154        self.edges.iter().enumerate().filter_map(|(slot, entry)| {
155            let edge = entry.value.as_ref()?;
156            Some((
157                StableEdgeKey::new(u32::try_from(slot).ok()?, entry.generation),
158                &edge.value,
159            ))
160        })
161    }
162
163    #[must_use]
164    pub fn outgoing_edges(
165        &self,
166        node: StableNodeKey,
167    ) -> impl DoubleEndedIterator<Item = StableEdgeKey> + ExactSizeIterator + '_ {
168        self.node_slot(node)
169            .map_or(&[][..], |slot| slot.outgoing.as_slice())
170            .iter()
171            .copied()
172    }
173
174    #[must_use]
175    pub fn incoming_edges(
176        &self,
177        node: StableNodeKey,
178    ) -> impl DoubleEndedIterator<Item = StableEdgeKey> + ExactSizeIterator + '_ {
179        self.node_slot(node)
180            .map_or(&[][..], |slot| slot.incoming.as_slice())
181            .iter()
182            .copied()
183    }
184
185    #[must_use]
186    pub const fn node_count(&self) -> usize {
187        self.node_count
188    }
189
190    #[must_use]
191    pub const fn edge_count(&self) -> usize {
192        self.edge_count
193    }
194
195    #[must_use]
196    pub const fn is_empty(&self) -> bool {
197        self.node_count == 0 && self.edge_count == 0
198    }
199
200    pub(super) fn node_slot(&self, key: StableNodeKey) -> Option<&NodeSlot> {
201        let slot = self.nodes.get(key.index())?;
202        (slot.generation == key.generation() && slot.value.is_some()).then_some(slot)
203    }
204
205    pub(super) fn node_slot_mut(&mut self, key: StableNodeKey) -> Option<&mut NodeSlot> {
206        let slot = self.nodes.get_mut(key.index())?;
207        (slot.generation == key.generation() && slot.value.is_some()).then_some(slot)
208    }
209
210    pub(super) fn edge_slot(&self, key: StableEdgeKey) -> Option<&EdgeSlot> {
211        let slot = self.edges.get(key.index())?;
212        (slot.generation == key.generation() && slot.value.is_some()).then_some(slot)
213    }
214
215    pub(super) fn edge_slot_mut(&mut self, key: StableEdgeKey) -> Option<&mut EdgeSlot> {
216        let slot = self.edges.get_mut(key.index())?;
217        (slot.generation == key.generation() && slot.value.is_some()).then_some(slot)
218    }
219
220    fn allocate_node(&mut self, node: Node) -> Result<StableNodeKey> {
221        if let Some(slot) = self.free_nodes.pop() {
222            let entry = &mut self.nodes[slot as usize];
223            entry.value = Some(node);
224            entry.outgoing.clear();
225            entry.incoming.clear();
226            return Ok(StableNodeKey::new(slot, entry.generation));
227        }
228        let slot =
229            u32::try_from(self.nodes.len()).map_err(|_| GraphError::IndexCapacityExceeded {
230                category: "working nodes",
231                count: self.nodes.len(),
232            })?;
233        self.nodes.push(NodeSlot {
234            generation: 0,
235            value: Some(node),
236            outgoing: Vec::new(),
237            incoming: Vec::new(),
238        });
239        Ok(StableNodeKey::new(slot, 0))
240    }
241
242    fn allocate_edge(&mut self, edge: WorkingEdge) -> Result<StableEdgeKey> {
243        if let Some(slot) = self.free_edges.pop() {
244            let entry = &mut self.edges[slot as usize];
245            entry.value = Some(edge);
246            return Ok(StableEdgeKey::new(slot, entry.generation));
247        }
248        let slot =
249            u32::try_from(self.edges.len()).map_err(|_| GraphError::IndexCapacityExceeded {
250                category: "working edges",
251                count: self.edges.len(),
252            })?;
253        self.edges.push(EdgeSlot {
254            generation: 0,
255            value: Some(edge),
256        });
257        Ok(StableEdgeKey::new(slot, 0))
258    }
259}
260
261#[cfg(feature = "std")]
262fn node_map_with_capacity(capacity: usize) -> NodeMap<NodeId, StableNodeKey> {
263    NodeMap::with_capacity(capacity)
264}
265
266#[cfg(not(feature = "std"))]
267fn node_map_with_capacity(_: usize) -> NodeMap<NodeId, StableNodeKey> {
268    NodeMap::new()
269}
weavatrix_graph/working/core.rs

weavatrix_graph/working/
core.rs
