1use super::{
10 BTreeMap, BTreeSet, Direction, Edge, GraphEntityFilter, GraphEntityKind, GraphLabelRegistry,
11 GraphStore, GraphStoreError, GraphStoreResult, LabelKind, PersistentGraphStore, Vertex,
12};
13
14impl GraphStore for PersistentGraphStore {
15 fn vertex_id_page(
16 &self,
17 graph: &str,
18 after: Option<u64>,
19 limit: usize,
20 ) -> GraphStoreResult<Vec<u64>> {
21 self.require_graph(graph)?;
22 let filter = GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph));
23 self.observe_selection(filter, after)?;
24 self.storage.ids(filter, after, limit)
25 }
26 fn edge_id_page(
27 &self,
28 graph: &str,
29 after: Option<u64>,
30 limit: usize,
31 ) -> GraphStoreResult<Vec<u64>> {
32 self.require_graph(graph)?;
33 let filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
34 self.observe_selection(filter, after)?;
35 self.storage.ids(filter, after, limit)
36 }
37 fn transaction<T>(
38 &mut self,
39 operation: impl FnOnce(&mut Self) -> GraphStoreResult<T>,
40 ) -> GraphStoreResult<T> {
41 self.transaction_mapped(operation, std::convert::identity)
42 }
43
44 fn create_graph(&mut self, name: &str) -> GraphStoreResult<()> {
45 self.transaction(|store| {
46 if !store.has_graph(name)? {
47 store.storage.create_graph(name)?;
48 let registry = GraphLabelRegistry {
49 allocation_id: if store.storage.identifiers()?.is_some() {
50 uqa_storage::catalog::new_nonzero_catalog_identity("graph", "allocation")?
51 } else {
52 [0; 16]
53 },
54 ..GraphLabelRegistry::default()
55 };
56 store.save_registry(name, ®istry)?;
57 }
58 Ok(())
59 })
60 }
61 fn drop_graph(&mut self, name: &str) -> GraphStoreResult<()> {
62 self.transaction(|store| {
63 if !store.has_graph(name)? {
64 return Ok(());
65 }
66 for kind in [GraphEntityKind::Edge, GraphEntityKind::Vertex] {
67 store.for_each_selected_id(GraphEntityFilter::new(kind, Some(name)), |id| {
68 store.detach_entity(kind, id, name)
69 })?;
70 }
71 store.storage.delete_graph(name)
72 })
73 }
74 fn graph_names(&self) -> GraphStoreResult<Vec<String>> {
75 self.observe_definition(
76 uqa_storage::catalog::graph_observations::GraphDefinitionKind::NamedGraph,
77 None,
78 )?;
79 self.storage.graph_names()
80 }
81 fn has_graph(&self, name: &str) -> GraphStoreResult<bool> {
82 self.observe_definition(
83 uqa_storage::catalog::graph_observations::GraphDefinitionKind::NamedGraph,
84 Some(name),
85 )?;
86 self.storage.has_graph(name)
87 }
88 fn union_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()> {
89 self.algebra(g1, Some(g2), target, |_| true, true)
90 }
91 fn intersect_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()> {
92 self.algebra(g1, Some(g2), target, |common| common, false)
93 }
94 fn difference_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()> {
95 self.algebra(g1, Some(g2), target, |common| !common, false)
96 }
97 fn copy_graph(&mut self, source: &str, target: &str) -> GraphStoreResult<()> {
98 self.algebra(source, None, target, |_| true, false)
99 }
100
101 fn add_vertex(&mut self, vertex: Vertex, graph: &str) -> GraphStoreResult<()> {
102 self.transaction(|store| {
103 store.require_graph(graph)?;
104 store.storage.guard_definition(Some(graph))?;
105 store.reserve_id(GraphEntityKind::Vertex, vertex.vertex_id)?;
106 store.storage.save_vertex(&vertex)?;
107 store
108 .storage
109 .attach(GraphEntityKind::Vertex, vertex.vertex_id, graph)?;
110 for owner in store
111 .storage
112 .memberships(GraphEntityKind::Vertex, vertex.vertex_id)?
113 {
114 store.storage.guard_definition(Some(&owner))?;
115 let mut registry = store.restored_registry(&owner)?;
116 if registry.observe(&vertex.label, vertex.vertex_id, LabelKind::Vertex) {
117 store.save_registry(&owner, ®istry)?;
118 }
119 }
120 Ok(())
121 })
122 }
123 fn add_edge(&mut self, edge: Edge, graph: &str) -> GraphStoreResult<()> {
124 self.transaction(|store| {
125 store.require_graph(graph)?;
126 let mut owners = store
127 .storage
128 .memberships(GraphEntityKind::Edge, edge.edge_id)?;
129 if !owners.iter().any(|owner| owner == graph) {
130 owners.push(graph.to_owned());
131 }
132 for owner in &owners {
133 store.storage.guard_definition(Some(owner))?;
134 for id in [edge.source_id, edge.target_id] {
135 if !store
136 .storage
137 .has_membership(GraphEntityKind::Vertex, id, owner)?
138 {
139 return Err(GraphStoreError::InvalidMutation(format!(
140 "edge {} references endpoint outside graph {owner:?}: {} -> {}",
141 edge.edge_id, edge.source_id, edge.target_id
142 )));
143 }
144 store.require_vertex(id)?;
145 }
146 }
147 store.reserve_id(GraphEntityKind::Edge, edge.edge_id)?;
148 store.storage.save_edge(&edge)?;
149 store
150 .storage
151 .attach(GraphEntityKind::Edge, edge.edge_id, graph)?;
152 for owner in owners {
153 let mut registry = store.restored_registry(&owner)?;
154 if registry.observe(&edge.label, edge.edge_id, LabelKind::Edge) {
155 store.save_registry(&owner, ®istry)?;
156 }
157 }
158 Ok(())
159 })
160 }
161 fn remove_vertex(&mut self, vertex_id: u64, graph: &str) -> GraphStoreResult<()> {
162 self.transaction(|store| {
163 store.require_graph(graph)?;
164 if !store
165 .storage
166 .has_membership(GraphEntityKind::Vertex, vertex_id, graph)?
167 {
168 return Ok(());
169 }
170 for outgoing in [true, false] {
171 let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
172 if outgoing {
173 filter.source = Some(vertex_id);
174 } else {
175 filter.target = Some(vertex_id);
176 }
177 store.for_each_selected_id(filter, |id| {
178 store.detach_entity(GraphEntityKind::Edge, id, graph)
179 })?;
180 }
181 store.detach_entity(GraphEntityKind::Vertex, vertex_id, graph)
182 })
183 }
184 fn remove_edge(&mut self, edge_id: u64, graph: &str) -> GraphStoreResult<()> {
185 self.transaction(|store| {
186 store.require_graph(graph)?;
187 store.detach_entity(GraphEntityKind::Edge, edge_id, graph)
188 })
189 }
190
191 fn neighbors(
192 &self,
193 vertex_id: u64,
194 label: Option<&str>,
195 direction: Direction,
196 graph: &str,
197 ) -> GraphStoreResult<Vec<u64>> {
198 self.require_vertex_in_graph(vertex_id, graph)?;
199 let mut neighbors = Vec::new();
200 for outgoing in [true, false] {
201 if (outgoing && direction == Direction::In)
202 || (!outgoing && direction == Direction::Out)
203 {
204 continue;
205 }
206 let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
207 filter.label = label;
208 if outgoing {
209 filter.source = Some(vertex_id);
210 } else {
211 filter.target = Some(vertex_id);
212 }
213 self.for_each_selected_id(filter, |id| {
214 let edge = self.require_edge(id, graph)?;
215 neighbors.push(if outgoing {
216 edge.target_id
217 } else {
218 edge.source_id
219 });
220 Ok(())
221 })?;
222 }
223 if direction == Direction::Both {
224 neighbors.sort_unstable();
225 neighbors.dedup();
226 }
227 Ok(neighbors)
228 }
229 fn vertices_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<Vertex>> {
230 self.require_graph(graph)?;
231 let mut filter = GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph));
232 filter.label = Some(label);
233 let mut result = Vec::new();
234 self.for_each_selected_id(filter, |id| {
235 self.observe_entity(GraphEntityKind::Vertex, id)?;
236 result.push(self.require_vertex(id)?);
237 Ok(())
238 })?;
239 Ok(result)
240 }
241 fn vertex_ids_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<u64>> {
242 self.require_graph(graph)?;
243 let mut filter = GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph));
244 filter.label = Some(label);
245 Ok(self.collect_ids(filter)?.into_iter().collect())
246 }
247 fn vertices_in_graph(&self, graph: &str) -> GraphStoreResult<Vec<Vertex>> {
248 self.require_graph(graph)?;
249 let mut result = Vec::new();
250 self.for_each_selected_id(
251 GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph)),
252 |id| {
253 self.observe_entity(GraphEntityKind::Vertex, id)?;
254 result.push(self.require_vertex(id)?);
255 Ok(())
256 },
257 )?;
258 Ok(result)
259 }
260 fn edges_in_graph(&self, graph: &str) -> GraphStoreResult<Vec<Edge>> {
261 self.require_graph(graph)?;
262 let mut result = Vec::new();
263 self.for_each_selected_id(
264 GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph)),
265 |id| {
266 self.observe_entity(GraphEntityKind::Edge, id)?;
267 result.push(self.require_edge(id, graph)?);
268 Ok(())
269 },
270 )?;
271 Ok(result)
272 }
273 fn vertex_graphs(&self, id: u64) -> GraphStoreResult<BTreeSet<String>> {
274 self.observe_membership(GraphEntityKind::Vertex, id, None)?;
275 Ok(self
276 .storage
277 .memberships(GraphEntityKind::Vertex, id)?
278 .into_iter()
279 .collect())
280 }
281 fn edges_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<Edge>> {
282 self.require_graph(graph)?;
283 let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
284 filter.label = Some(label);
285 let mut edges = Vec::new();
286 self.for_each_selected_id(filter, |id| {
287 self.observe_entity(GraphEntityKind::Edge, id)?;
288 edges.push(self.require_edge(id, graph)?);
289 Ok(())
290 })?;
291 Ok(edges)
292 }
293
294 fn edge_graphs(&self, id: u64) -> GraphStoreResult<BTreeSet<String>> {
295 self.observe_membership(GraphEntityKind::Edge, id, None)?;
296 Ok(self
297 .storage
298 .memberships(GraphEntityKind::Edge, id)?
299 .into_iter()
300 .collect())
301 }
302 fn out_edge_ids(&self, id: u64, graph: &str) -> GraphStoreResult<BTreeSet<u64>> {
303 self.require_vertex_in_graph(id, graph)?;
304 let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
305 filter.source = Some(id);
306 let ids = self.collect_ids(filter)?;
307 for id in &ids {
308 self.require_edge(*id, graph)?;
309 }
310 Ok(ids)
311 }
312 fn in_edge_ids(&self, id: u64, graph: &str) -> GraphStoreResult<BTreeSet<u64>> {
313 self.require_vertex_in_graph(id, graph)?;
314 let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
315 filter.target = Some(id);
316 let ids = self.collect_ids(filter)?;
317 for id in &ids {
318 self.require_edge(*id, graph)?;
319 }
320 Ok(ids)
321 }
322 fn edge_ids_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<BTreeSet<u64>> {
323 self.require_graph(graph)?;
324 let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
325 filter.label = Some(label);
326 let ids = self.collect_ids(filter)?;
327 for id in &ids {
328 self.require_edge(*id, graph)?;
329 }
330 Ok(ids)
331 }
332 fn vertex_ids_in_graph(&self, graph: &str) -> GraphStoreResult<BTreeSet<u64>> {
333 self.require_graph(graph)?;
334 self.collect_ids(GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph)))
335 }
336 fn require_vertex_in_graph(&self, id: u64, graph: &str) -> GraphStoreResult<()> {
337 self.require_graph(graph)?;
338 self.observe_membership(GraphEntityKind::Vertex, id, Some(graph))?;
339 if !self
340 .storage
341 .has_membership(GraphEntityKind::Vertex, id, graph)?
342 {
343 return Err(GraphStoreError::InvalidQuery(format!(
344 "vertex {id} is not a member of graph {graph:?}"
345 )));
346 }
347 self.require_vertex(id)?;
348 Ok(())
349 }
350
351 fn degree_distribution(&self, graph: &str) -> GraphStoreResult<BTreeMap<u64, u64>> {
352 self.require_graph(graph)?;
353 let mut result = BTreeMap::new();
354 self.for_each_selected_id(
355 GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph)),
356 |id| {
357 let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
358 filter.source = Some(id);
359 self.observe_selection(filter, None)?;
360 result.insert(id, self.storage.count(filter)?);
361 Ok(())
362 },
363 )?;
364 Ok(result)
365 }
366 fn label_degree(&self, label: &str, graph: &str) -> GraphStoreResult<f64> {
367 self.require_graph(graph)?;
368 let mut sources = BTreeSet::new();
369 let mut count = 0_usize;
370 let mut filter = GraphEntityFilter::new(GraphEntityKind::Edge, Some(graph));
371 filter.label = Some(label);
372 self.for_each_selected_id(filter, |id| {
373 sources.insert(self.require_edge(id, graph)?.source_id);
374 count += 1;
375 Ok(())
376 })?;
377 if sources.is_empty() {
378 return Ok(0.0);
379 }
380 Ok(
381 crate::memory_store::usize_to_f64_exact(count, "edge label count")?
382 / crate::memory_store::usize_to_f64_exact(
383 sources.len(),
384 "edge label source count",
385 )?,
386 )
387 }
388 fn vertex_label_counts(&self, graph: &str) -> GraphStoreResult<BTreeMap<String, u64>> {
389 self.require_graph(graph)?;
390 let mut result = BTreeMap::new();
391 self.for_each_selected_id(
392 GraphEntityFilter::new(GraphEntityKind::Vertex, Some(graph)),
393 |id| {
394 *result.entry(self.require_vertex(id)?.label).or_default() += 1;
395 Ok(())
396 },
397 )?;
398 Ok(result)
399 }
400 fn get_vertex(&self, id: u64) -> GraphStoreResult<Option<Vertex>> {
401 self.observe_entity(GraphEntityKind::Vertex, id)?;
402 self.storage.vertex(id)
403 }
404 fn for_each_vertex_borrowed(
405 &self,
406 ids: &[u64],
407 visit: &mut dyn FnMut(u64, Option<&Vertex>) -> bool,
408 ) -> GraphStoreResult<Option<usize>> {
409 if self.read.is_some() {
412 return Ok(None);
413 }
414 self.storage.for_each_vertex_borrowed(ids, visit)
415 }
416 fn get_edge(&self, id: u64) -> GraphStoreResult<Option<Edge>> {
417 self.observe_entity(GraphEntityKind::Edge, id)?;
418 self.storage.edge(id)
419 }
420 fn next_vertex_id(&mut self) -> GraphStoreResult<u64> {
421 self.allocate_counter(GraphEntityKind::Vertex)
422 }
423 fn next_edge_id(&mut self) -> GraphStoreResult<u64> {
424 self.allocate_counter(GraphEntityKind::Edge)
425 }
426 fn allocate_vertex_id(&mut self, label: &str, graph: &str) -> GraphStoreResult<u64> {
427 self.allocate_label_id(label, graph, LabelKind::Vertex)
428 }
429 fn allocate_edge_id(&mut self, label: &str, graph: &str) -> GraphStoreResult<u64> {
430 self.allocate_label_id(label, graph, LabelKind::Edge)
431 }
432 fn clear(&mut self) -> GraphStoreResult<()> {
433 self.transaction(|store| {
434 for graph in store.graph_names()? {
435 store.drop_graph(&graph)?;
436 }
437 for kind in [GraphEntityKind::Vertex, GraphEntityKind::Edge] {
438 store.for_each_selected_id(
440 GraphEntityFilter::new(kind, None),
441 |id| match kind {
442 GraphEntityKind::Vertex => store.storage.delete_vertex(id),
443 GraphEntityKind::Edge => store.storage.delete_edge(id),
444 },
445 )?;
446 store.storage.save_counter(kind, 1)?;
447 }
448 store.storage.reset_identifiers()?;
449 Ok(())
450 })
451 }
452 fn vertices(&self) -> GraphStoreResult<BTreeMap<u64, Vertex>> {
453 let mut result = BTreeMap::new();
454 self.for_each_selected_id(
455 GraphEntityFilter::new(GraphEntityKind::Vertex, None),
456 |id| {
457 self.observe_entity(GraphEntityKind::Vertex, id)?;
458 result.insert(id, self.require_vertex(id)?);
459 Ok(())
460 },
461 )?;
462 Ok(result)
463 }
464 fn edges(&self) -> GraphStoreResult<BTreeMap<u64, Edge>> {
465 let mut result = BTreeMap::new();
466 self.for_each_selected_id(GraphEntityFilter::new(GraphEntityKind::Edge, None), |id| {
467 self.observe_entity(GraphEntityKind::Edge, id)?;
468 let edge = self
469 .storage
470 .edge(id)?
471 .ok_or_else(|| GraphStoreError::CorruptGraph(format!("missing edge {id}")))?;
472 result.insert(id, edge);
473 Ok(())
474 })?;
475 Ok(result)
476 }
477}