Skip to main content

sevensense_vector/infrastructure/
graph_store.rs

1//! Graph storage for similarity relationships between embeddings.
2//!
3//! This module provides storage and querying for the similarity graph,
4//! supporting edge types like SIMILAR, SEQUENTIAL, and SAME_CLUSTER.
5
6use 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/// In-memory graph store for similarity edges.
19///
20/// This implementation uses adjacency lists for efficient edge traversal
21/// and supports bidirectional lookups.
22#[derive(Debug, Default)]
23pub struct InMemoryGraphStore {
24    /// Forward edges: from_id -> list of edges
25    forward: RwLock<HashMap<EmbeddingId, Vec<SimilarityEdge>>>,
26
27    /// Reverse edges: to_id -> list of edges
28    reverse: RwLock<HashMap<EmbeddingId, Vec<SimilarityEdge>>>,
29
30    /// Total edge count
31    count: RwLock<usize>,
32}
33
34impl InMemoryGraphStore {
35    /// Create a new empty graph store.
36    pub fn new() -> Self {
37        Self::default()
38    }
39
40    /// Get the number of edges.
41    pub fn len(&self) -> usize {
42        *self.count.read()
43    }
44
45    /// Check if the store is empty.
46    pub fn is_empty(&self) -> bool {
47        self.len() == 0
48    }
49
50    /// Get all unique node IDs in the graph.
51    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    /// Get the degree (number of connections) for a node.
62    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    /// Export the graph for serialization.
73    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    /// Import a graph from serialized data.
81    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        // Remove outgoing edges
251        if let Some(edges) = forward.remove(id) {
252            *count = count.saturating_sub(edges.len());
253
254            // Clean up reverse references
255            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        // Remove incoming edges
266        if let Some(edges) = reverse.remove(id) {
267            *count = count.saturating_sub(edges.len());
268
269            // Clean up forward references
270            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        // BFS
299        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(&current) {
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(&current) {
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        // Remove the starting node
360        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        // Get all nodes
370        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(&current) {
386                    continue;
387                }
388
389                visited.insert(current);
390                component.push(current);
391
392                // Add neighbors (both directions for undirected view)
393                if let Some(edges) = forward.get(&current) {
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(&current) {
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        // Simple degree centrality (normalized)
419        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/// Serializable export format for the graph.
443#[derive(Debug, Clone, Serialize, Deserialize)]
444pub struct GraphExport {
445    /// All edges in the graph.
446    pub edges: Vec<SimilarityEdge>,
447}
448
449impl GraphExport {
450    /// Create a new empty export.
451    pub fn new() -> Self {
452        Self { edges: Vec::new() }
453    }
454
455    /// Save to a file.
456    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    /// Load from a file.
464    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(); // 0.9 similarity
552        store.add_edge(SimilarityEdge::new(id1, id3, 0.5)).await.unwrap(); // 0.5 similarity
553
554        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)); // 3 hops away
597    }
598
599    #[tokio::test]
600    async fn test_connected_components() {
601        let store = InMemoryGraphStore::new();
602
603        // Component 1
604        let id1 = EmbeddingId::new();
605        let id2 = EmbeddingId::new();
606        store.add_edge(SimilarityEdge::new(id1, id2, 0.1)).await.unwrap();
607
608        // Component 2
609        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}