1use std::collections::{BTreeMap, BTreeSet};
12
13use uqa_core::{Edge, EdgeId, Vertex, VertexId};
14
15use crate::posting_list::GraphPostingListError;
16use crate::types::Direction;
17
18mod error;
19pub use error::GraphStorageError;
20
21#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
22pub enum GraphStoreError {
23 #[error("graph {0:?} does not exist")]
24 UnknownGraph(String),
25 #[error("graph id space exhausted: {0}")]
26 IdExhausted(String),
27 #[error("invalid graph mutation: {0}")]
28 InvalidMutation(String),
29 #[error("invalid graph query: {0}")]
30 InvalidQuery(String),
31 #[error("corrupt graph state: {0}")]
32 CorruptGraph(String),
33 #[error("graph storage error: {0}")]
34 Storage(String),
35 #[error("graph storage error: {0}")]
36 Backend(#[source] GraphStorageError),
37 #[error("graph serialization failure: {0}")]
38 SerializationFailure(String),
39 #[error(transparent)]
40 InvalidPostingList(#[from] GraphPostingListError),
41}
42
43pub type GraphStoreResult<T> = Result<T, GraphStoreError>;
44
45pub trait GraphStore {
51 fn transaction<T>(
55 &mut self,
56 operation: impl FnOnce(&mut Self) -> GraphStoreResult<T>,
57 ) -> GraphStoreResult<T>
58 where
59 Self: Sized;
60
61 fn create_graph(&mut self, name: &str) -> GraphStoreResult<()>;
65
66 fn drop_graph(&mut self, name: &str) -> GraphStoreResult<()>;
70
71 fn graph_names(&self) -> GraphStoreResult<Vec<String>>;
73
74 fn has_graph(&self, name: &str) -> GraphStoreResult<bool>;
75
76 fn union_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()>;
80
81 fn intersect_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()>;
83
84 fn difference_graphs(&mut self, g1: &str, g2: &str, target: &str) -> GraphStoreResult<()>;
86
87 fn copy_graph(&mut self, source: &str, target: &str) -> GraphStoreResult<()>;
88
89 fn add_vertex(&mut self, vertex: Vertex, graph: &str) -> GraphStoreResult<()>;
92
93 fn add_edge(&mut self, edge: Edge, graph: &str) -> GraphStoreResult<()>;
94
95 fn remove_vertex(&mut self, vertex_id: VertexId, graph: &str) -> GraphStoreResult<()>;
96
97 fn remove_edge(&mut self, edge_id: EdgeId, graph: &str) -> GraphStoreResult<()>;
98
99 fn neighbors(
105 &self,
106 vertex_id: VertexId,
107 label: Option<&str>,
108 direction: Direction,
109 graph: &str,
110 ) -> GraphStoreResult<Vec<VertexId>>;
111
112 fn vertices_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<Vertex>>;
113
114 fn vertex_ids_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<VertexId>> {
116 Ok(self
117 .vertices_by_label(label, graph)?
118 .into_iter()
119 .map(|vertex| vertex.vertex_id)
120 .collect())
121 }
122
123 fn vertices_in_graph(&self, graph: &str) -> GraphStoreResult<Vec<Vertex>>;
124
125 fn edges_in_graph(&self, graph: &str) -> GraphStoreResult<Vec<Edge>>;
126
127 fn edges_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<Vec<Edge>> {
130 self.edge_ids_by_label(label, graph)?
131 .into_iter()
132 .map(|id| {
133 self.get_edge(id)?
134 .ok_or_else(|| GraphStoreError::CorruptGraph(format!("missing edge {id}")))
135 })
136 .collect()
137 }
138
139 fn vertex_graphs(&self, vertex_id: VertexId) -> GraphStoreResult<BTreeSet<String>>;
140 fn edge_graphs(&self, edge_id: EdgeId) -> GraphStoreResult<BTreeSet<String>>;
141
142 fn out_edge_ids(&self, vertex_id: VertexId, graph: &str) -> GraphStoreResult<BTreeSet<EdgeId>>;
145
146 fn in_edge_ids(&self, vertex_id: VertexId, graph: &str) -> GraphStoreResult<BTreeSet<EdgeId>>;
147
148 fn edge_ids_by_label(&self, label: &str, graph: &str) -> GraphStoreResult<BTreeSet<EdgeId>>;
149
150 fn vertex_ids_in_graph(&self, graph: &str) -> GraphStoreResult<BTreeSet<VertexId>>;
151
152 fn vertex_id_page(
155 &self,
156 graph: &str,
157 after: Option<u64>,
158 limit: usize,
159 ) -> GraphStoreResult<Vec<u64>> {
160 if !(1..=uqa_storage::MAX_GRAPH_ID_PAGE).contains(&limit) {
161 return Err(GraphStoreError::InvalidQuery(
162 "invalid graph page size".into(),
163 ));
164 }
165 Ok(self
166 .vertex_ids_in_graph(graph)?
167 .into_iter()
168 .filter(|id| after.is_none_or(|after| *id > after))
169 .take(limit)
170 .collect())
171 }
172
173 fn edge_id_page(
175 &self,
176 graph: &str,
177 after: Option<u64>,
178 limit: usize,
179 ) -> GraphStoreResult<Vec<u64>> {
180 if !(1..=uqa_storage::MAX_GRAPH_ID_PAGE).contains(&limit) {
181 return Err(GraphStoreError::InvalidQuery(
182 "invalid graph page size".into(),
183 ));
184 }
185 let mut ids = BTreeSet::new();
186 for vertex in self.vertex_ids_in_graph(graph)? {
187 ids.extend(self.out_edge_ids(vertex, graph)?);
188 }
189 Ok(ids
190 .into_iter()
191 .filter(|id| after.is_none_or(|after| *id > after))
192 .take(limit)
193 .collect())
194 }
195
196 fn require_vertex_in_graph(&self, vertex_id: VertexId, graph: &str) -> GraphStoreResult<()> {
201 if !self.vertex_ids_in_graph(graph)?.contains(&vertex_id) {
202 return Err(GraphStoreError::InvalidQuery(format!(
203 "vertex {vertex_id} is not a member of graph {graph:?}"
204 )));
205 }
206 if self.get_vertex(vertex_id)?.is_none() {
207 return Err(GraphStoreError::CorruptGraph(format!(
208 "graph {graph:?} references missing vertex {vertex_id}"
209 )));
210 }
211 Ok(())
212 }
213
214 fn degree_distribution(&self, graph: &str) -> GraphStoreResult<BTreeMap<VertexId, u64>>;
217
218 fn label_degree(&self, label: &str, graph: &str) -> GraphStoreResult<f64>;
219
220 fn vertex_label_counts(&self, graph: &str) -> GraphStoreResult<BTreeMap<String, u64>>;
221
222 fn get_vertex(&self, vertex_id: VertexId) -> GraphStoreResult<Option<Vertex>>;
227
228 fn for_each_vertex_borrowed(
233 &self,
234 _ids: &[VertexId],
235 _visit: &mut dyn FnMut(VertexId, Option<&Vertex>) -> bool,
236 ) -> GraphStoreResult<Option<usize>> {
237 Ok(None)
238 }
239
240 fn get_edge(&self, edge_id: EdgeId) -> GraphStoreResult<Option<Edge>>;
241
242 fn next_vertex_id(&mut self) -> GraphStoreResult<VertexId>;
244
245 fn next_edge_id(&mut self) -> GraphStoreResult<EdgeId>;
247
248 fn allocate_vertex_id(&mut self, _label: &str, _graph: &str) -> GraphStoreResult<VertexId> {
253 self.next_vertex_id()
254 }
255
256 fn allocate_edge_id(&mut self, _label: &str, _graph: &str) -> GraphStoreResult<EdgeId> {
259 self.next_edge_id()
260 }
261
262 fn clear(&mut self) -> GraphStoreResult<()>;
263
264 fn vertices(&self) -> GraphStoreResult<BTreeMap<VertexId, Vertex>>;
269
270 fn edges(&self) -> GraphStoreResult<BTreeMap<EdgeId, Edge>>;
273}
274
275impl From<uqa_storage::StorageBackendError> for GraphStoreError {
276 fn from(error: uqa_storage::StorageBackendError) -> Self {
277 Self::Backend(error.into())
278 }
279}