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

weavatrix_graph/payload/stable_undirected/
mutate.rs
