weavatrix_graph/payload/stable_undirected/
core.rs

1use super::incidence::{IncidentEdges, NONE_SLOT};
2use crate::Vec;
3use crate::payload::stable::core::next_slot;
4use crate::{EdgeEndpoints, GraphError, Result, StableEdgeKey, StableNodeKey};
5
6#[derive(Debug, Clone)]
7pub(super) struct NodeSlot<NodePayload> {
8    pub(super) generation: u32,
9    pub(super) value: Option<NodePayload>,
10    pub(super) first_edge: u32,
11    pub(super) last_edge: u32,
12    pub(super) degree: usize,
13}
14
15#[derive(Debug, Clone)]
16pub(super) struct EdgeSlot<EdgePayload> {
17    pub(super) generation: u32,
18    pub(super) value: Option<EdgePayload>,
19    pub(super) source: u32,
20    pub(super) target: u32,
21    pub(super) source_previous: u32,
22    pub(super) source_next: u32,
23    pub(super) target_previous: u32,
24    pub(super) target_next: u32,
25}
26
27/// A mutable undirected payload graph with generation-checked stable keys.
28#[derive(Debug, Clone)]
29pub struct StableUndirectedPayloadGraph<NodePayload, EdgePayload> {
30    pub(super) nodes: Vec<NodeSlot<NodePayload>>,
31    pub(super) edges: Vec<EdgeSlot<EdgePayload>>,
32    pub(super) free_nodes: Vec<u32>,
33    pub(super) free_edges: Vec<u32>,
34    pub(super) node_count: usize,
35    pub(super) edge_count: usize,
36}
37
38impl<NodePayload, EdgePayload> Default for StableUndirectedPayloadGraph<NodePayload, EdgePayload> {
39    fn default() -> Self {
40        Self::new()
41    }
42}
43
44impl<NodePayload, EdgePayload> StableUndirectedPayloadGraph<NodePayload, EdgePayload> {
45    #[must_use]
46    pub const fn new() -> Self {
47        Self {
48            nodes: Vec::new(),
49            edges: Vec::new(),
50            free_nodes: Vec::new(),
51            free_edges: Vec::new(),
52            node_count: 0,
53            edge_count: 0,
54        }
55    }
56
57    #[must_use]
58    pub fn with_capacity(nodes: usize, edges: usize) -> Self {
59        Self {
60            nodes: Vec::with_capacity(nodes),
61            edges: Vec::with_capacity(edges),
62            free_nodes: Vec::new(),
63            free_edges: Vec::new(),
64            node_count: 0,
65            edge_count: 0,
66        }
67    }
68
69    /// Adds a node payload and returns a generation-stable key.
70    ///
71    /// # Errors
72    ///
73    /// Returns an error when the stable index space is exhausted.
74    pub fn add_node(&mut self, payload: NodePayload) -> Result<StableNodeKey> {
75        let key = if let Some(slot) = self.free_nodes.pop() {
76            let entry = &mut self.nodes[slot as usize];
77            entry.value = Some(payload);
78            entry.first_edge = NONE_SLOT;
79            entry.last_edge = NONE_SLOT;
80            entry.degree = 0;
81            StableNodeKey::new(slot, entry.generation)
82        } else {
83            let slot = next_slot(self.nodes.len(), "stable undirected nodes")?;
84            self.nodes.push(NodeSlot {
85                generation: 0,
86                value: Some(payload),
87                first_edge: NONE_SLOT,
88                last_edge: NONE_SLOT,
89                degree: 0,
90            });
91            StableNodeKey::new(slot, 0)
92        };
93        self.node_count += 1;
94        Ok(key)
95    }
96
97    /// Adds one undirected edge. A self-loop occupies one incidence entry.
98    ///
99    /// # Errors
100    ///
101    /// Returns an error for stale endpoints or exhausted edge indices.
102    pub fn add_edge(
103        &mut self,
104        source: StableNodeKey,
105        target: StableNodeKey,
106        payload: EdgePayload,
107    ) -> Result<StableEdgeKey> {
108        self.require_node(source)?;
109        self.require_node(target)?;
110        let key = self.allocate_edge(source, target, payload)?;
111        self.link(source, key);
112        if source != target {
113            self.link(target, key);
114        }
115        self.edge_count += 1;
116        Ok(key)
117    }
118
119    #[must_use]
120    pub fn node(&self, key: StableNodeKey) -> Option<&NodePayload> {
121        self.node_slot(key)?.value.as_ref()
122    }
123
124    #[must_use]
125    pub fn node_mut(&mut self, key: StableNodeKey) -> Option<&mut NodePayload> {
126        self.node_slot_mut(key)?.value.as_mut()
127    }
128
129    #[must_use]
130    pub fn edge(&self, key: StableEdgeKey) -> Option<&EdgePayload> {
131        self.edge_slot(key)?.value.as_ref()
132    }
133
134    #[must_use]
135    pub fn edge_mut(&mut self, key: StableEdgeKey) -> Option<&mut EdgePayload> {
136        self.edge_slot_mut(key)?.value.as_mut()
137    }
138
139    #[must_use]
140    pub fn edge_endpoints(&self, key: StableEdgeKey) -> Option<EdgeEndpoints<StableNodeKey>> {
141        let edge = self.edge_slot(key)?;
142        Some(EdgeEndpoints::new(
143            self.node_key_at(edge.source)?,
144            self.node_key_at(edge.target)?,
145        ))
146    }
147
148    pub fn nodes(&self) -> impl Iterator<Item = (StableNodeKey, &NodePayload)> {
149        self.nodes.iter().enumerate().filter_map(|(slot, entry)| {
150            Some((
151                StableNodeKey::new(u32::try_from(slot).ok()?, entry.generation),
152                entry.value.as_ref()?,
153            ))
154        })
155    }
156
157    pub fn edges(&self) -> impl Iterator<Item = (StableEdgeKey, &EdgePayload)> {
158        self.edges.iter().enumerate().filter_map(|(slot, entry)| {
159            Some((
160                StableEdgeKey::new(u32::try_from(slot).ok()?, entry.generation),
161                entry.value.as_ref()?,
162            ))
163        })
164    }
165
166    #[must_use]
167    pub fn incident_edges(
168        &self,
169        node: StableNodeKey,
170    ) -> impl DoubleEndedIterator<Item = StableEdgeKey> + ExactSizeIterator + '_ {
171        IncidentEdges::new(self, node)
172    }
173
174    #[must_use]
175    pub const fn node_count(&self) -> usize {
176        self.node_count
177    }
178
179    #[must_use]
180    pub const fn edge_count(&self) -> usize {
181        self.edge_count
182    }
183
184    #[must_use]
185    pub const fn is_empty(&self) -> bool {
186        self.node_count == 0 && self.edge_count == 0
187    }
188
189    pub(super) fn node_slot(&self, key: StableNodeKey) -> Option<&NodeSlot<NodePayload>> {
190        let slot = self.nodes.get(key.index())?;
191        (slot.generation == key.generation() && slot.value.is_some()).then_some(slot)
192    }
193
194    pub(super) fn node_slot_mut(
195        &mut self,
196        key: StableNodeKey,
197    ) -> Option<&mut NodeSlot<NodePayload>> {
198        let slot = self.nodes.get_mut(key.index())?;
199        (slot.generation == key.generation() && slot.value.is_some()).then_some(slot)
200    }
201
202    pub(super) fn edge_slot(&self, key: StableEdgeKey) -> Option<&EdgeSlot<EdgePayload>> {
203        let slot = self.edges.get(key.index())?;
204        (slot.generation == key.generation() && slot.value.is_some()).then_some(slot)
205    }
206
207    pub(super) fn edge_slot_mut(
208        &mut self,
209        key: StableEdgeKey,
210    ) -> Option<&mut EdgeSlot<EdgePayload>> {
211        let slot = self.edges.get_mut(key.index())?;
212        (slot.generation == key.generation() && slot.value.is_some()).then_some(slot)
213    }
214
215    pub(super) fn require_node(&self, key: StableNodeKey) -> Result<()> {
216        self.node_slot(key)
217            .map(|_| ())
218            .ok_or(GraphError::InvalidStableKey {
219                category: "undirected node",
220                slot: key.slot(),
221                generation: key.generation(),
222            })
223    }
224
225    fn allocate_edge(
226        &mut self,
227        source: StableNodeKey,
228        target: StableNodeKey,
229        payload: EdgePayload,
230    ) -> Result<StableEdgeKey> {
231        if let Some(slot) = self.free_edges.pop() {
232            let entry = &mut self.edges[slot as usize];
233            entry.value = Some(payload);
234            entry.source = source.slot();
235            entry.target = target.slot();
236            entry.source_previous = NONE_SLOT;
237            entry.source_next = NONE_SLOT;
238            entry.target_previous = NONE_SLOT;
239            entry.target_next = NONE_SLOT;
240            return Ok(StableEdgeKey::new(slot, entry.generation));
241        }
242        let slot = next_slot(self.edges.len(), "stable undirected edges")?;
243        self.edges.push(EdgeSlot {
244            generation: 0,
245            value: Some(payload),
246            source: source.slot(),
247            target: target.slot(),
248            source_previous: NONE_SLOT,
249            source_next: NONE_SLOT,
250            target_previous: NONE_SLOT,
251            target_next: NONE_SLOT,
252        });
253        Ok(StableEdgeKey::new(slot, 0))
254    }
255
256    pub(super) fn node_key_at(&self, slot: u32) -> Option<StableNodeKey> {
257        let entry = self.nodes.get(slot as usize)?;
258        entry
259            .value
260            .as_ref()
261            .map(|_| StableNodeKey::new(slot, entry.generation))
262    }
263}
weavatrix_graph/payload/stable_undirected/core.rs

weavatrix_graph/payload/stable_undirected/
core.rs
