graph_api_simplegraph/graph/
label.rs

1use crate::index::VertexIndexStorage;
2use crate::tombstone_vec::TombstoneVec;
3use crate::{EdgeId, VertexId};
4use graph_api_lib::{Direction, Element, Index, Label};
5use std::collections::BTreeSet;
6use std::marker::PhantomData;
7use std::ops::RangeInclusive;
8
9#[derive(Default)]
10pub(crate) struct LabelledVertices<Vertex, Edge> {
11    vertices: TombstoneVec<VertexStorage<Vertex>>,
12    _phantom: PhantomData<Edge>,
13}
14
15pub(crate) struct VertexStorage<Vertex> {
16    // Maps vertex ID to list of outgoing edge IDs
17    pub(crate) adjacency_list: BTreeSet<Adjacency>,
18    // The vertex itself
19    pub(crate) weight: Vertex,
20}
21
22/// An adjacency represents a unidirectional edge.
23/// The fields are range to minimize the number of distinct ranges that
24/// need to be covered for the most common traversal.
25/// To do this direction is first as it has the lowest cardinality.
26/// Then edge label, as users will likely only have a single edge type that they want to traverse.
27/// Lastly the adjacent vertex label.
28#[derive(Ord, PartialOrd, Eq, PartialEq, Clone, Debug)]
29pub(crate) struct Adjacency {
30    pub(crate) direction: Direction,
31    pub(crate) edge_label: u16,
32    pub(crate) vertex_label: u16,
33    pub(crate) edge_id: u32,
34    pub(crate) vertex_id: u32,
35}
36
37impl Adjacency {}
38
39impl Adjacency {
40    pub(crate) fn reversed(&self, vertex: VertexId) -> Adjacency {
41        Adjacency {
42            direction: self.direction.reverse(),
43            edge_label: self.edge_label,
44            vertex_label: vertex.label(),
45            edge_id: self.edge_id,
46            vertex_id: vertex.vertex(),
47        }
48    }
49
50    pub(crate) fn outgoing(edge: &EdgeId) -> Adjacency {
51        Adjacency {
52            direction: Direction::Outgoing,
53            edge_label: edge.label(),
54            vertex_label: edge.head().label(),
55            edge_id: edge.edge(),
56            vertex_id: edge.head().vertex(),
57        }
58    }
59
60    pub(crate) fn incoming(edge: &EdgeId) -> Adjacency {
61        Adjacency {
62            direction: Direction::Incoming,
63            edge_label: edge.label(),
64            vertex_label: edge.tail().label(),
65            edge_id: edge.edge(),
66            vertex_id: edge.tail().vertex(),
67        }
68    }
69
70    pub(crate) fn range(
71        direction: Option<Direction>,
72        edge_label: Option<u16>,
73        vertex_label: Option<u16>,
74    ) -> RangeInclusive<Adjacency> {
75        Adjacency {
76            direction: direction.unwrap_or(Direction::Outgoing),
77            edge_label: edge_label.unwrap_or(0),
78            vertex_label: vertex_label.unwrap_or(0),
79            edge_id: 0,
80            vertex_id: 0,
81        }..=Adjacency {
82            direction: direction.unwrap_or(Direction::Incoming),
83            edge_label: edge_label.unwrap_or(u16::MAX),
84            vertex_label: vertex_label.unwrap_or(u16::MAX),
85            edge_id: u32::MAX,
86            vertex_id: u32::MAX,
87        }
88    }
89}
90
91impl<Vertex> VertexStorage<Vertex> {
92    pub(crate) fn new(weight: Vertex) -> Self {
93        Self {
94            adjacency_list: BTreeSet::new(),
95            weight,
96        }
97    }
98}
99
100impl<Vertex, Edge> LabelledVertices<Vertex, Edge>
101where
102    Vertex: Element,
103    Edge: Element,
104{
105    pub(crate) fn new() -> Self {
106        Self {
107            vertices: TombstoneVec::new(),
108            _phantom: Default::default(),
109        }
110    }
111
112    pub(crate) fn get(&self, vertex_id: u32) -> Option<&Vertex> {
113        self.vertices.get(vertex_id as usize).map(|v| &v.weight)
114    }
115
116    pub(crate) fn get_mut(&mut self, vertex_id: u32) -> Option<&mut Vertex> {
117        self.vertices
118            .get_mut(vertex_id as usize)
119            .map(|v| &mut v.weight)
120    }
121
122    pub(crate) fn add(&mut self, vertex: Vertex, indexes: &mut [VertexIndexStorage]) -> u32 {
123        let label = vertex.label();
124        let vertex_id = self.vertices.push(VertexStorage::new(vertex)) as u32;
125        let storage = self
126            .vertices
127            .get(vertex_id as usize)
128            .expect("we just inserted the vertex, qed");
129        let weight = &storage.weight;
130
131        for index in label.indexes() {
132            if let Some(value) = weight.value(index) {
133                let index_storage = &mut indexes[index.ordinal()];
134                index_storage.insert(value, vertex_id, index);
135            }
136        }
137        vertex_id
138    }
139
140    pub(crate) fn add_adjacency(&mut self, vertex_id: u32, adjacency: Adjacency) {
141        if let Some(vertex) = self.vertices.get_mut(vertex_id as usize) {
142            vertex.adjacency_list.insert(adjacency);
143        }
144    }
145
146    pub(crate) fn remove(
147        &mut self,
148        vertex_id: u32,
149        indexes: &mut [VertexIndexStorage],
150    ) -> Option<VertexStorage<Vertex>> {
151        // Get the vertex before removing it so we can clean up indexes
152        if let Some(vertex) = self.vertices.get(vertex_id as usize) {
153            let label = vertex.weight.label();
154            // Remove from all indexes first
155            for index in label.indexes() {
156                if let Some(value) = vertex.weight.value(index) {
157                    let index_storage = &mut indexes[index.ordinal()];
158                    index_storage.remove(&value, vertex_id, index);
159                }
160            }
161            // Then remove the vertex itself
162            self.vertices.remove(vertex_id as usize)
163        } else {
164            None
165        }
166    }
167
168    pub(crate) fn remove_adjacency(&mut self, vertex_id: u32, adjacency: &Adjacency) {
169        if let Some(vertex) = self.vertices.get_mut(vertex_id as usize) {
170            vertex.adjacency_list.remove(adjacency);
171        }
172    }
173
174    pub(crate) fn iter(&self) -> impl Iterator<Item = u32> + '_ {
175        self.vertices.index_iter().map(|idx| idx as u32)
176    }
177
178    pub(crate) fn clear(&mut self) {
179        self.vertices.clear();
180    }
181}
182
183impl<Vertex, Edge> std::ops::Index<u32> for LabelledVertices<Vertex, Edge> {
184    type Output = VertexStorage<Vertex>;
185
186    fn index(&self, index: u32) -> &Self::Output {
187        &self.vertices[index as usize]
188    }
189}
190
191impl<Vertex, Edge> std::ops::IndexMut<u32> for LabelledVertices<Vertex, Edge> {
192    fn index_mut(&mut self, index: u32) -> &mut Self::Output {
193        &mut self.vertices[index as usize]
194    }
195}
196
197#[derive(Default)]
198pub(crate) struct LabelledEdges<Edge> {
199    // Stores edge data for this label
200    pub(crate) edges: TombstoneVec<Edge>,
201}
202
203impl<Edge> LabelledEdges<Edge>
204where
205    Edge: Element,
206{
207    pub fn new() -> Self {
208        Self {
209            edges: TombstoneVec::new(),
210        }
211    }
212
213    pub(crate) fn add(&mut self, edge: Edge) -> u32 {
214        self.edges.push(edge) as u32
215    }
216
217    pub(crate) fn remove(&mut self, edge_id: u32) -> Option<Edge> {
218        self.edges.remove(edge_id as usize)
219    }
220
221    pub(crate) fn clear(&mut self) {
222        self.edges.clear();
223    }
224
225    pub(crate) fn get(&self, edge_id: u32) -> Option<&Edge> {
226        self.edges.get(edge_id as usize)
227    }
228
229    pub(crate) fn get_mut(&mut self, edge_id: u32) -> Option<&mut Edge> {
230        self.edges.get_mut(edge_id as usize)
231    }
232}
233#[cfg(test)]
234mod tests {
235    use super::*;
236    use std::collections::BTreeSet;
237
238    #[test]
239    fn test_insert_and_retrieve_adjacencies() {
240        let mut adjacencies = BTreeSet::new();
241
242        let adj1 = Adjacency {
243            direction: Direction::Outgoing,
244            edge_label: 1,
245            vertex_label: 1,
246            edge_id: 1,
247            vertex_id: 1,
248        };
249
250        let adj2 = Adjacency {
251            direction: Direction::Outgoing,
252            edge_label: 2,
253            vertex_label: 2,
254            edge_id: 2,
255            vertex_id: 2,
256        };
257
258        let adj3 = Adjacency {
259            direction: Direction::Incoming,
260            edge_label: 3,
261            vertex_label: 3,
262            edge_id: 3,
263            vertex_id: 3,
264        };
265
266        adjacencies.insert(adj1.clone());
267        adjacencies.insert(adj2.clone());
268        adjacencies.insert(adj3.clone());
269
270        let range = Adjacency::range(Some(Direction::Outgoing), None, None);
271        let retrieved: Vec<_> = adjacencies.range(range).cloned().collect();
272
273        assert_eq!(retrieved, vec![adj1, adj2]);
274    }
275
276    #[test]
277    fn test_empty_range() {
278        let adjacencies: BTreeSet<Adjacency> = BTreeSet::new();
279        let range = Adjacency::range(Some(Direction::Outgoing), None, None);
280        let retrieved: Vec<_> = adjacencies.range(range).cloned().collect();
281
282        assert!(retrieved.is_empty());
283    }
284
285    #[test]
286    fn test_retrieve_specific_edge_label() {
287        let mut adjacencies = BTreeSet::new();
288
289        let adj1 = Adjacency {
290            direction: Direction::Outgoing,
291            edge_label: 1,
292            vertex_label: 1,
293            edge_id: 1,
294            vertex_id: 1,
295        };
296
297        let adj2 = Adjacency {
298            direction: Direction::Outgoing,
299            edge_label: 2,
300            vertex_label: 2,
301            edge_id: 2,
302            vertex_id: 2,
303        };
304
305        let adj3 = Adjacency {
306            direction: Direction::Incoming,
307            edge_label: 3,
308            vertex_label: 3,
309            edge_id: 3,
310            vertex_id: 3,
311        };
312
313        adjacencies.insert(adj1.clone());
314        adjacencies.insert(adj2.clone());
315        adjacencies.insert(adj3.clone());
316
317        let range = Adjacency::range(Some(Direction::Outgoing), None, None);
318        let retrieved: Vec<_> = adjacencies.range(range).cloned().collect();
319        assert_eq!(retrieved, vec![adj1.clone(), adj2.clone()]);
320
321        // Test range with specific edge label
322        let range = Adjacency::range(Some(Direction::Outgoing), Some(2), None);
323        let retrieved: Vec<_> = adjacencies.range(range).cloned().collect();
324        assert_eq!(retrieved, vec![adj2.clone()]);
325
326        // Test range with specific edge and vertex label
327        let range = Adjacency::range(Some(Direction::Outgoing), Some(2), Some(2));
328        let retrieved: Vec<_> = adjacencies.range(range).cloned().collect();
329        assert_eq!(retrieved, vec![adj2.clone()]);
330
331        // Test full range
332        let range = Adjacency::range(None, None, None);
333        let retrieved: Vec<_> = adjacencies.range(range).cloned().collect();
334        assert_eq!(retrieved, vec![adj1.clone(), adj2.clone(), adj3.clone()]);
335    }
336}