sevensense_vector/infrastructure/
graph_store.rs1use std::collections::{HashMap, HashSet, VecDeque};
7
8use async_trait::async_trait;
9use parking_lot::RwLock;
10use serde::{Deserialize, Serialize};
11use tracing::{debug, instrument};
12
13use crate::domain::{
14 EdgeType, EmbeddingId, GraphEdgeRepository, GraphTraversal, SimilarityEdge, VectorError,
15};
16use crate::domain::repository::RepoResult;
17
18#[derive(Debug, Default)]
23pub struct InMemoryGraphStore {
24 forward: RwLock<HashMap<EmbeddingId, Vec<SimilarityEdge>>>,
26
27 reverse: RwLock<HashMap<EmbeddingId, Vec<SimilarityEdge>>>,
29
30 count: RwLock<usize>,
32}
33
34impl InMemoryGraphStore {
35 pub fn new() -> Self {
37 Self::default()
38 }
39
40 pub fn len(&self) -> usize {
42 *self.count.read()
43 }
44
45 pub fn is_empty(&self) -> bool {
47 self.len() == 0
48 }
49
50 pub fn node_ids(&self) -> Vec<EmbeddingId> {
52 let forward = self.forward.read();
53 let reverse = self.reverse.read();
54
55 let mut ids: HashSet<EmbeddingId> = forward.keys().copied().collect();
56 ids.extend(reverse.keys().copied());
57
58 ids.into_iter().collect()
59 }
60
61 pub fn degree(&self, id: &EmbeddingId) -> usize {
63 let forward = self.forward.read();
64 let reverse = self.reverse.read();
65
66 let out_degree = forward.get(id).map(|e| e.len()).unwrap_or(0);
67 let in_degree = reverse.get(id).map(|e| e.len()).unwrap_or(0);
68
69 out_degree + in_degree
70 }
71
72 pub fn export(&self) -> GraphExport {
74 let forward = self.forward.read();
75 let edges: Vec<_> = forward.values().flatten().cloned().collect();
76
77 GraphExport { edges }
78 }
79
80 pub fn import(&self, data: GraphExport) -> RepoResult<()> {
82 let mut forward = self.forward.write();
83 let mut reverse = self.reverse.write();
84 let mut count = self.count.write();
85
86 forward.clear();
87 reverse.clear();
88 *count = 0;
89
90 for edge in data.edges {
91 forward
92 .entry(edge.from_id)
93 .or_default()
94 .push(edge.clone());
95
96 reverse
97 .entry(edge.to_id)
98 .or_default()
99 .push(edge);
100
101 *count += 1;
102 }
103
104 Ok(())
105 }
106}
107
108#[async_trait]
109impl GraphEdgeRepository for InMemoryGraphStore {
110 #[instrument(skip(self, edge))]
111 async fn add_edge(&self, edge: SimilarityEdge) -> RepoResult<()> {
112 let mut forward = self.forward.write();
113 let mut reverse = self.reverse.write();
114 let mut count = self.count.write();
115
116 forward
117 .entry(edge.from_id)
118 .or_default()
119 .push(edge.clone());
120
121 reverse
122 .entry(edge.to_id)
123 .or_default()
124 .push(edge);
125
126 *count += 1;
127
128 debug!("Added edge, total count: {}", *count);
129 Ok(())
130 }
131
132 #[instrument(skip(self, edges), fields(count = edges.len()))]
133 async fn add_edges(&self, edges: &[SimilarityEdge]) -> RepoResult<()> {
134 let mut forward = self.forward.write();
135 let mut reverse = self.reverse.write();
136 let mut count = self.count.write();
137
138 for edge in edges {
139 forward
140 .entry(edge.from_id)
141 .or_default()
142 .push(edge.clone());
143
144 reverse
145 .entry(edge.to_id)
146 .or_default()
147 .push(edge.clone());
148
149 *count += 1;
150 }
151
152 debug!("Added {} edges, total count: {}", edges.len(), *count);
153 Ok(())
154 }
155
156 async fn remove_edge(&self, from: &EmbeddingId, to: &EmbeddingId) -> RepoResult<()> {
157 let mut forward = self.forward.write();
158 let mut reverse = self.reverse.write();
159 let mut count = self.count.write();
160
161 let mut removed = false;
162
163 if let Some(edges) = forward.get_mut(from) {
164 let len_before = edges.len();
165 edges.retain(|e| &e.to_id != to);
166 if edges.len() < len_before {
167 removed = true;
168 }
169 if edges.is_empty() {
170 forward.remove(from);
171 }
172 }
173
174 if let Some(edges) = reverse.get_mut(to) {
175 edges.retain(|e| &e.from_id != from);
176 if edges.is_empty() {
177 reverse.remove(to);
178 }
179 }
180
181 if removed {
182 *count = count.saturating_sub(1);
183 }
184
185 Ok(())
186 }
187
188 async fn get_edges_from(&self, id: &EmbeddingId) -> RepoResult<Vec<SimilarityEdge>> {
189 let forward = self.forward.read();
190 Ok(forward.get(id).cloned().unwrap_or_default())
191 }
192
193 async fn get_edges_to(&self, id: &EmbeddingId) -> RepoResult<Vec<SimilarityEdge>> {
194 let reverse = self.reverse.read();
195 Ok(reverse.get(id).cloned().unwrap_or_default())
196 }
197
198 async fn get_edges_by_type(
199 &self,
200 id: &EmbeddingId,
201 edge_type: EdgeType,
202 ) -> RepoResult<Vec<SimilarityEdge>> {
203 let forward = self.forward.read();
204 Ok(forward
205 .get(id)
206 .map(|edges| {
207 edges
208 .iter()
209 .filter(|e| e.edge_type == edge_type)
210 .cloned()
211 .collect()
212 })
213 .unwrap_or_default())
214 }
215
216 async fn get_strong_edges(
217 &self,
218 id: &EmbeddingId,
219 min_similarity: f32,
220 ) -> RepoResult<Vec<SimilarityEdge>> {
221 let forward = self.forward.read();
222 Ok(forward
223 .get(id)
224 .map(|edges| {
225 edges
226 .iter()
227 .filter(|e| e.similarity() >= min_similarity)
228 .cloned()
229 .collect()
230 })
231 .unwrap_or_default())
232 }
233
234 async fn edge_count(&self) -> RepoResult<usize> {
235 Ok(*self.count.read())
236 }
237
238 async fn clear(&self) -> RepoResult<()> {
239 self.forward.write().clear();
240 self.reverse.write().clear();
241 *self.count.write() = 0;
242 Ok(())
243 }
244
245 async fn remove_edges_for(&self, id: &EmbeddingId) -> RepoResult<()> {
246 let mut forward = self.forward.write();
247 let mut reverse = self.reverse.write();
248 let mut count = self.count.write();
249
250 if let Some(edges) = forward.remove(id) {
252 *count = count.saturating_sub(edges.len());
253
254 for edge in edges {
256 if let Some(rev_edges) = reverse.get_mut(&edge.to_id) {
257 rev_edges.retain(|e| &e.from_id != id);
258 if rev_edges.is_empty() {
259 reverse.remove(&edge.to_id);
260 }
261 }
262 }
263 }
264
265 if let Some(edges) = reverse.remove(id) {
267 *count = count.saturating_sub(edges.len());
268
269 for edge in edges {
271 if let Some(fwd_edges) = forward.get_mut(&edge.from_id) {
272 fwd_edges.retain(|e| &e.to_id != id);
273 if fwd_edges.is_empty() {
274 forward.remove(&edge.from_id);
275 }
276 }
277 }
278 }
279
280 Ok(())
281 }
282}
283
284#[async_trait]
285impl GraphTraversal for InMemoryGraphStore {
286 async fn shortest_path(
287 &self,
288 from: &EmbeddingId,
289 to: &EmbeddingId,
290 max_depth: usize,
291 ) -> RepoResult<Option<Vec<EmbeddingId>>> {
292 if from == to {
293 return Ok(Some(vec![*from]));
294 }
295
296 let forward = self.forward.read();
297
298 let mut visited: HashSet<EmbeddingId> = HashSet::new();
300 let mut queue: VecDeque<(EmbeddingId, Vec<EmbeddingId>)> = VecDeque::new();
301
302 visited.insert(*from);
303 queue.push_back((*from, vec![*from]));
304
305 while let Some((current, path)) = queue.pop_front() {
306 if path.len() > max_depth {
307 continue;
308 }
309
310 if let Some(edges) = forward.get(¤t) {
311 for edge in edges {
312 if &edge.to_id == to {
313 let mut result = path.clone();
314 result.push(edge.to_id);
315 return Ok(Some(result));
316 }
317
318 if !visited.contains(&edge.to_id) {
319 visited.insert(edge.to_id);
320 let mut new_path = path.clone();
321 new_path.push(edge.to_id);
322 queue.push_back((edge.to_id, new_path));
323 }
324 }
325 }
326 }
327
328 Ok(None)
329 }
330
331 async fn neighbors_within_hops(
332 &self,
333 id: &EmbeddingId,
334 hops: usize,
335 ) -> RepoResult<Vec<(EmbeddingId, usize)>> {
336 let forward = self.forward.read();
337
338 let mut visited: HashMap<EmbeddingId, usize> = HashMap::new();
339 let mut queue: VecDeque<(EmbeddingId, usize)> = VecDeque::new();
340
341 visited.insert(*id, 0);
342 queue.push_back((*id, 0));
343
344 while let Some((current, depth)) = queue.pop_front() {
345 if depth >= hops {
346 continue;
347 }
348
349 if let Some(edges) = forward.get(¤t) {
350 for edge in edges {
351 if !visited.contains_key(&edge.to_id) {
352 visited.insert(edge.to_id, depth + 1);
353 queue.push_back((edge.to_id, depth + 1));
354 }
355 }
356 }
357 }
358
359 visited.remove(id);
361
362 Ok(visited.into_iter().collect())
363 }
364
365 async fn connected_components(&self) -> RepoResult<Vec<Vec<EmbeddingId>>> {
366 let forward = self.forward.read();
367 let reverse = self.reverse.read();
368
369 let mut all_nodes: HashSet<EmbeddingId> = forward.keys().copied().collect();
371 all_nodes.extend(reverse.keys().copied());
372
373 let mut visited: HashSet<EmbeddingId> = HashSet::new();
374 let mut components: Vec<Vec<EmbeddingId>> = Vec::new();
375
376 for &start in &all_nodes {
377 if visited.contains(&start) {
378 continue;
379 }
380
381 let mut component: Vec<EmbeddingId> = Vec::new();
382 let mut stack: Vec<EmbeddingId> = vec![start];
383
384 while let Some(current) = stack.pop() {
385 if visited.contains(¤t) {
386 continue;
387 }
388
389 visited.insert(current);
390 component.push(current);
391
392 if let Some(edges) = forward.get(¤t) {
394 for edge in edges {
395 if !visited.contains(&edge.to_id) {
396 stack.push(edge.to_id);
397 }
398 }
399 }
400 if let Some(edges) = reverse.get(¤t) {
401 for edge in edges {
402 if !visited.contains(&edge.from_id) {
403 stack.push(edge.from_id);
404 }
405 }
406 }
407 }
408
409 if !component.is_empty() {
410 components.push(component);
411 }
412 }
413
414 Ok(components)
415 }
416
417 async fn centrality_scores(&self) -> RepoResult<Vec<(EmbeddingId, f32)>> {
418 let forward = self.forward.read();
420 let reverse = self.reverse.read();
421
422 let mut degrees: HashMap<EmbeddingId, usize> = HashMap::new();
423
424 for (id, edges) in forward.iter() {
425 *degrees.entry(*id).or_default() += edges.len();
426 }
427 for (id, edges) in reverse.iter() {
428 *degrees.entry(*id).or_default() += edges.len();
429 }
430
431 let max_degree = degrees.values().copied().max().unwrap_or(1) as f32;
432
433 let scores: Vec<_> = degrees
434 .into_iter()
435 .map(|(id, degree)| (id, degree as f32 / max_degree))
436 .collect();
437
438 Ok(scores)
439 }
440}
441
442#[derive(Debug, Clone, Serialize, Deserialize)]
444pub struct GraphExport {
445 pub edges: Vec<SimilarityEdge>,
447}
448
449impl GraphExport {
450 pub fn new() -> Self {
452 Self { edges: Vec::new() }
453 }
454
455 pub fn save(&self, path: &std::path::Path) -> Result<(), VectorError> {
457 let file = std::fs::File::create(path)?;
458 let writer = std::io::BufWriter::new(file);
459 bincode::serialize_into(writer, self)?;
460 Ok(())
461 }
462
463 pub fn load(path: &std::path::Path) -> Result<Self, VectorError> {
465 let file = std::fs::File::open(path)?;
466 let reader = std::io::BufReader::new(file);
467 let export = bincode::deserialize_from(reader)?;
468 Ok(export)
469 }
470}
471
472impl Default for GraphExport {
473 fn default() -> Self {
474 Self::new()
475 }
476}
477
478#[cfg(test)]
479mod tests {
480 use super::*;
481
482 #[tokio::test]
483 async fn test_add_and_query_edges() {
484 let store = InMemoryGraphStore::new();
485
486 let id1 = EmbeddingId::new();
487 let id2 = EmbeddingId::new();
488 let id3 = EmbeddingId::new();
489
490 let edge1 = SimilarityEdge::new(id1, id2, 0.1);
491 let edge2 = SimilarityEdge::new(id1, id3, 0.2);
492
493 store.add_edge(edge1).await.unwrap();
494 store.add_edge(edge2).await.unwrap();
495
496 assert_eq!(store.edge_count().await.unwrap(), 2);
497
498 let from_edges = store.get_edges_from(&id1).await.unwrap();
499 assert_eq!(from_edges.len(), 2);
500
501 let to_edges = store.get_edges_to(&id2).await.unwrap();
502 assert_eq!(to_edges.len(), 1);
503 }
504
505 #[tokio::test]
506 async fn test_remove_edge() {
507 let store = InMemoryGraphStore::new();
508
509 let id1 = EmbeddingId::new();
510 let id2 = EmbeddingId::new();
511
512 store.add_edge(SimilarityEdge::new(id1, id2, 0.1)).await.unwrap();
513 assert_eq!(store.edge_count().await.unwrap(), 1);
514
515 store.remove_edge(&id1, &id2).await.unwrap();
516 assert_eq!(store.edge_count().await.unwrap(), 0);
517 }
518
519 #[tokio::test]
520 async fn test_edges_by_type() {
521 let store = InMemoryGraphStore::new();
522
523 let id1 = EmbeddingId::new();
524 let id2 = EmbeddingId::new();
525 let id3 = EmbeddingId::new();
526
527 store
528 .add_edge(SimilarityEdge::new(id1, id2, 0.1).with_type(EdgeType::Similar))
529 .await
530 .unwrap();
531 store
532 .add_edge(SimilarityEdge::sequential(id1, id3))
533 .await
534 .unwrap();
535
536 let similar = store.get_edges_by_type(&id1, EdgeType::Similar).await.unwrap();
537 assert_eq!(similar.len(), 1);
538
539 let sequential = store.get_edges_by_type(&id1, EdgeType::Sequential).await.unwrap();
540 assert_eq!(sequential.len(), 1);
541 }
542
543 #[tokio::test]
544 async fn test_strong_edges() {
545 let store = InMemoryGraphStore::new();
546
547 let id1 = EmbeddingId::new();
548 let id2 = EmbeddingId::new();
549 let id3 = EmbeddingId::new();
550
551 store.add_edge(SimilarityEdge::new(id1, id2, 0.1)).await.unwrap(); store.add_edge(SimilarityEdge::new(id1, id3, 0.5)).await.unwrap(); let strong = store.get_strong_edges(&id1, 0.8).await.unwrap();
555 assert_eq!(strong.len(), 1);
556 assert_eq!(strong[0].to_id, id2);
557 }
558
559 #[tokio::test]
560 async fn test_shortest_path() {
561 let store = InMemoryGraphStore::new();
562
563 let id1 = EmbeddingId::new();
564 let id2 = EmbeddingId::new();
565 let id3 = EmbeddingId::new();
566
567 store.add_edge(SimilarityEdge::new(id1, id2, 0.1)).await.unwrap();
568 store.add_edge(SimilarityEdge::new(id2, id3, 0.1)).await.unwrap();
569
570 let path = store.shortest_path(&id1, &id3, 10).await.unwrap();
571 assert!(path.is_some());
572 let path = path.unwrap();
573 assert_eq!(path.len(), 3);
574 assert_eq!(path[0], id1);
575 assert_eq!(path[2], id3);
576 }
577
578 #[tokio::test]
579 async fn test_neighbors_within_hops() {
580 let store = InMemoryGraphStore::new();
581
582 let id1 = EmbeddingId::new();
583 let id2 = EmbeddingId::new();
584 let id3 = EmbeddingId::new();
585 let id4 = EmbeddingId::new();
586
587 store.add_edge(SimilarityEdge::new(id1, id2, 0.1)).await.unwrap();
588 store.add_edge(SimilarityEdge::new(id2, id3, 0.1)).await.unwrap();
589 store.add_edge(SimilarityEdge::new(id3, id4, 0.1)).await.unwrap();
590
591 let neighbors = store.neighbors_within_hops(&id1, 2).await.unwrap();
592 let neighbor_ids: HashSet<_> = neighbors.iter().map(|(id, _)| *id).collect();
593
594 assert!(neighbor_ids.contains(&id2));
595 assert!(neighbor_ids.contains(&id3));
596 assert!(!neighbor_ids.contains(&id4)); }
598
599 #[tokio::test]
600 async fn test_connected_components() {
601 let store = InMemoryGraphStore::new();
602
603 let id1 = EmbeddingId::new();
605 let id2 = EmbeddingId::new();
606 store.add_edge(SimilarityEdge::new(id1, id2, 0.1)).await.unwrap();
607
608 let id3 = EmbeddingId::new();
610 let id4 = EmbeddingId::new();
611 store.add_edge(SimilarityEdge::new(id3, id4, 0.1)).await.unwrap();
612
613 let components = store.connected_components().await.unwrap();
614 assert_eq!(components.len(), 2);
615 }
616
617 #[tokio::test]
618 async fn test_remove_edges_for() {
619 let store = InMemoryGraphStore::new();
620
621 let id1 = EmbeddingId::new();
622 let id2 = EmbeddingId::new();
623 let id3 = EmbeddingId::new();
624
625 store.add_edge(SimilarityEdge::new(id1, id2, 0.1)).await.unwrap();
626 store.add_edge(SimilarityEdge::new(id1, id3, 0.1)).await.unwrap();
627 store.add_edge(SimilarityEdge::new(id3, id1, 0.1)).await.unwrap();
628
629 assert_eq!(store.edge_count().await.unwrap(), 3);
630
631 store.remove_edges_for(&id1).await.unwrap();
632
633 assert_eq!(store.edge_count().await.unwrap(), 0);
634 }
635
636 #[tokio::test]
637 async fn test_export_import() {
638 let store = InMemoryGraphStore::new();
639
640 let id1 = EmbeddingId::new();
641 let id2 = EmbeddingId::new();
642
643 store.add_edge(SimilarityEdge::new(id1, id2, 0.1)).await.unwrap();
644
645 let export = store.export();
646 assert_eq!(export.edges.len(), 1);
647
648 let new_store = InMemoryGraphStore::new();
649 new_store.import(export).unwrap();
650
651 assert_eq!(new_store.edge_count().await.unwrap(), 1);
652 }
653}