weavatrix_graph/payload/stable_undirected/
mutate.rs

1use super::core::StableUndirectedPayloadGraph;
2use super::incidence::NONE_SLOT;
3use crate::{GraphError, Result, StableEdgeKey, StableNodeKey};
4
5impl<NodePayload, EdgePayload> StableUndirectedPayloadGraph<NodePayload, EdgePayload> {
6    pub fn remove_edge(&mut self, key: StableEdgeKey) -> Option<EdgePayload> {
7        let endpoints = self.edge_endpoints(key)?;
8        self.validate_unlink(endpoints.source(), key).ok()?;
9        if endpoints.source() != endpoints.target() {
10            self.validate_unlink(endpoints.target(), key).ok()?;
11        }
12        self.unlink(endpoints.source(), key).ok()?;
13        if endpoints.source() != endpoints.target() {
14            self.unlink(endpoints.target(), key).ok()?;
15        }
16        let payload = self.edge_slot_mut(key)?.value.take()?;
17        self.edge_count -= 1;
18        self.retire_edge(key);
19        Some(payload)
20    }
21
22    pub fn remove_node(&mut self, key: StableNodeKey) -> Option<NodePayload> {
23        let incident = self.incident_edges(key).collect::<crate::Vec<_>>();
24        for edge in incident {
25            self.remove_edge(edge);
26        }
27        let payload = self.node_slot_mut(key)?.value.take()?;
28        self.node_count -= 1;
29        self.retire_node(key);
30        Some(payload)
31    }
32
33    /// Moves an edge without changing its stable key or payload.
34    ///
35    /// # Errors
36    ///
37    /// Returns an error when either new endpoint is stale.
38    pub fn set_edge_endpoints(
39        &mut self,
40        key: StableEdgeKey,
41        source: StableNodeKey,
42        target: StableNodeKey,
43    ) -> Result<bool> {
44        self.require_node(source)?;
45        self.require_node(target)?;
46        let Some(previous) = self.edge_endpoints(key) else {
47            return Ok(false);
48        };
49        if previous.source() == source && previous.target() == target {
50            return Ok(true);
51        }
52        self.validate_unlink(previous.source(), key)?;
53        if previous.source() != previous.target() {
54            self.validate_unlink(previous.target(), key)?;
55        }
56        self.unlink(previous.source(), key)?;
57        if previous.source() != previous.target() {
58            self.unlink(previous.target(), key)?;
59        }
60        let edge = self
61            .edge_slot_mut(key)
62            .ok_or(GraphError::InvalidStableKey {
63                category: "undirected edge",
64                slot: key.slot(),
65                generation: key.generation(),
66            })?;
67        edge.source = source.slot();
68        edge.target = target.slot();
69        edge.source_previous = NONE_SLOT;
70        edge.source_next = NONE_SLOT;
71        edge.target_previous = NONE_SLOT;
72        edge.target_next = NONE_SLOT;
73        self.link(source, key);
74        if source != target {
75            self.link(target, key);
76        }
77        Ok(true)
78    }
79
80    fn unlink(&mut self, node: StableNodeKey, edge: StableEdgeKey) -> Result<()> {
81        self.validate_unlink(node, edge)?;
82        let (previous, next) = {
83            let Some(slot) = self.edge_slot(edge) else {
84                return Err(invalid_incidence(edge));
85            };
86            (slot.previous(node.slot()), slot.next(node.slot()))
87        };
88        if previous == NONE_SLOT {
89            self.nodes[node.index()].first_edge = next;
90        } else {
91            self.edges[previous as usize].set_next(node.slot(), next);
92        }
93        if next == NONE_SLOT {
94            self.nodes[node.index()].last_edge = previous;
95        } else {
96            self.edges[next as usize].set_previous(node.slot(), previous);
97        }
98        self.nodes[node.index()].degree -= 1;
99        Ok(())
100    }
101
102    fn validate_unlink(&self, node: StableNodeKey, edge: StableEdgeKey) -> Result<()> {
103        let node_slot = self.node_slot(node).ok_or(GraphError::InvalidStableKey {
104            category: "undirected node",
105            slot: node.slot(),
106            generation: node.generation(),
107        })?;
108        let edge_slot = self
109            .edge_slot(edge)
110            .ok_or_else(|| invalid_incidence(edge))?;
111        if node_slot.degree == 0
112            || (edge_slot.source != node.slot() && edge_slot.target != node.slot())
113            || !self.live_incidence(edge_slot.previous(node.slot()), node.slot())
114            || !self.live_incidence(edge_slot.next(node.slot()), node.slot())
115        {
116            return Err(invalid_incidence(edge));
117        }
118        Ok(())
119    }
120
121    fn live_incidence(&self, edge: u32, node: u32) -> bool {
122        edge == NONE_SLOT
123            || self.edges.get(edge as usize).is_some_and(|slot| {
124                slot.value.is_some() && (slot.source == node || slot.target == node)
125            })
126    }
127
128    fn retire_node(&mut self, key: StableNodeKey) {
129        let slot = &mut self.nodes[key.index()];
130        slot.first_edge = NONE_SLOT;
131        slot.last_edge = NONE_SLOT;
132        slot.degree = 0;
133        if let Some(generation) = slot.generation.checked_add(1) {
134            slot.generation = generation;
135            self.free_nodes.push(key.slot());
136        }
137    }
138
139    fn retire_edge(&mut self, key: StableEdgeKey) {
140        let slot = &mut self.edges[key.index()];
141        slot.source_previous = NONE_SLOT;
142        slot.source_next = NONE_SLOT;
143        slot.target_previous = NONE_SLOT;
144        slot.target_next = NONE_SLOT;
145        if let Some(generation) = slot.generation.checked_add(1) {
146            slot.generation = generation;
147            self.free_edges.push(key.slot());
148        }
149    }
150
151    pub(super) fn link(&mut self, node: StableNodeKey, edge: StableEdgeKey) {
152        let previous = self.nodes[node.index()].last_edge;
153        self.edges[edge.index()].set_previous(node.slot(), previous);
154        self.edges[edge.index()].set_next(node.slot(), NONE_SLOT);
155        if previous == NONE_SLOT {
156            self.nodes[node.index()].first_edge = edge.slot();
157        } else {
158            self.edges[previous as usize].set_next(node.slot(), edge.slot());
159        }
160        self.nodes[node.index()].last_edge = edge.slot();
161        self.nodes[node.index()].degree += 1;
162    }
163}
164
165fn invalid_incidence(edge: StableEdgeKey) -> GraphError {
166    GraphError::InvalidStableKey {
167        category: "undirected incidence edge",
168        slot: edge.slot(),
169        generation: edge.generation(),
170    }
171}
weavatrix_graph/payload/stable_undirected/mutate.rs

weavatrix_graph/payload/stable_undirected/
mutate.rs
