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 pub(crate) adjacency_list: BTreeSet<Adjacency>,
18 pub(crate) weight: Vertex,
20}
21
22#[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 if let Some(vertex) = self.vertices.get(vertex_id as usize) {
153 let label = vertex.weight.label();
154 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 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 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 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 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 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}