weavatrix_graph/payload/stable/
mutate.rs

1use super::StablePayloadGraph;
2use super::adjacency::NONE_SLOT;
3use crate::{GraphError, Result, StableEdgeKey, StableNodeKey};
4
5impl<NodePayload, EdgePayload> StablePayloadGraph<NodePayload, EdgePayload> {
6    pub fn remove_edge(&mut self, key: StableEdgeKey) -> Option<EdgePayload> {
7        let endpoints = self.edge_endpoints(key)?;
8        self.unlink_outgoing(endpoints.source(), key);
9        self.unlink_incoming(endpoints.target(), key);
10        let payload = self.edge_slot_mut(key)?.value.take()?;
11        self.edge_count -= 1;
12        self.retire_edge(key);
13        Some(payload)
14    }
15
16    pub fn remove_node(&mut self, key: StableNodeKey) -> Option<NodePayload> {
17        self.node_slot(key)?;
18        let mut incident = self.outgoing_edges(key).collect::<crate::Vec<_>>();
19        incident.extend(self.incoming_edges(key));
20        incident.sort_unstable();
21        incident.dedup();
22        for edge in incident {
23            self.remove_edge(edge);
24        }
25        let payload = self.node_slot_mut(key)?.value.take()?;
26        self.node_count -= 1;
27        self.retire_node(key);
28        Some(payload)
29    }
30
31    /// Moves a live edge without changing its stable key or payload.
32    ///
33    /// # Errors
34    ///
35    /// Returns an error when either new endpoint key is stale.
36    pub fn set_edge_endpoints(
37        &mut self,
38        key: StableEdgeKey,
39        source: StableNodeKey,
40        target: StableNodeKey,
41    ) -> Result<bool> {
42        self.require_node(source)?;
43        self.require_node(target)?;
44        let Some(previous) = self.edge_endpoints(key) else {
45            return Ok(false);
46        };
47        if previous.source() == source && previous.target() == target {
48            return Ok(true);
49        }
50        self.unlink_outgoing(previous.source(), key);
51        self.unlink_incoming(previous.target(), key);
52        let edge = self
53            .edge_slot_mut(key)
54            .ok_or(GraphError::InvalidStableKey {
55                category: "edge",
56                slot: key.slot(),
57                generation: key.generation(),
58            })?;
59        edge.source = source.slot();
60        edge.target = target.slot();
61        self.link_outgoing(source, key);
62        self.link_incoming(target, key);
63        Ok(true)
64    }
65
66    pub(super) fn link_outgoing(&mut self, node: StableNodeKey, key: StableEdgeKey) {
67        self.edges[key.index()].next_outgoing = self.nodes[node.index()].outgoing;
68        self.nodes[node.index()].outgoing = key.slot();
69    }
70
71    pub(super) fn link_incoming(&mut self, node: StableNodeKey, key: StableEdgeKey) {
72        self.edges[key.index()].next_incoming = self.nodes[node.index()].incoming;
73        self.nodes[node.index()].incoming = key.slot();
74    }
75
76    fn unlink_outgoing(&mut self, node: StableNodeKey, key: StableEdgeKey) {
77        let next = self.edges[key.index()].next_outgoing;
78        if self.nodes[node.index()].outgoing == key.slot() {
79            self.nodes[node.index()].outgoing = next;
80            return;
81        }
82        let mut cursor = self.nodes[node.index()].outgoing;
83        while cursor != NONE_SLOT {
84            if self.edges[cursor as usize].next_outgoing == key.slot() {
85                self.edges[cursor as usize].next_outgoing = next;
86                return;
87            }
88            cursor = self.edges[cursor as usize].next_outgoing;
89        }
90    }
91
92    fn unlink_incoming(&mut self, node: StableNodeKey, key: StableEdgeKey) {
93        let next = self.edges[key.index()].next_incoming;
94        if self.nodes[node.index()].incoming == key.slot() {
95            self.nodes[node.index()].incoming = next;
96            return;
97        }
98        let mut cursor = self.nodes[node.index()].incoming;
99        while cursor != NONE_SLOT {
100            if self.edges[cursor as usize].next_incoming == key.slot() {
101                self.edges[cursor as usize].next_incoming = next;
102                return;
103            }
104            cursor = self.edges[cursor as usize].next_incoming;
105        }
106    }
107
108    fn retire_node(&mut self, key: StableNodeKey) {
109        let slot = &mut self.nodes[key.index()];
110        slot.outgoing = NONE_SLOT;
111        slot.incoming = NONE_SLOT;
112        if let Some(generation) = slot.generation.checked_add(1) {
113            slot.generation = generation;
114            self.free_nodes.push(key.slot());
115        }
116    }
117
118    fn retire_edge(&mut self, key: StableEdgeKey) {
119        let slot = &mut self.edges[key.index()];
120        slot.next_outgoing = NONE_SLOT;
121        slot.next_incoming = NONE_SLOT;
122        if let Some(generation) = slot.generation.checked_add(1) {
123            slot.generation = generation;
124            self.free_edges.push(key.slot());
125        }
126    }
127}
weavatrix_graph/payload/stable/mutate.rs

weavatrix_graph/payload/stable/
mutate.rs
