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

weavatrix_graph/working/
core.rs
