uqa_graph/
subgraph_index.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Cached subgraph pattern results for repeated `GMatch` queries.
8
9use std::collections::{BTreeMap, BTreeSet};
10
11use uqa_core::VertexId;
12
13use crate::operators::GMatch;
14use crate::pattern::GraphPattern;
15use crate::store::{GraphStore, GraphStoreResult};
16
17#[derive(Debug, Clone, Default)]
18pub struct SubgraphIndex {
19    pattern_to_matches: BTreeMap<String, BTreeSet<BTreeSet<VertexId>>>,
20}
21
22impl SubgraphIndex {
23    pub fn build<G: GraphStore>(
24        store: &G,
25        patterns: &[GraphPattern],
26        graph: &str,
27    ) -> GraphStoreResult<Self> {
28        let mut index = Self::default();
29        for pattern in patterns {
30            let key = canonicalize(pattern);
31            let result = GMatch::new(pattern.clone(), graph).execute(store)?;
32            let mut matches = BTreeSet::new();
33            for entry in result.inner().entries() {
34                if let Some(payload) = result.get_graph_payload(entry.doc_id) {
35                    matches.insert(payload.subgraph_vertices.iter().copied().collect());
36                }
37            }
38            index.pattern_to_matches.insert(key, matches);
39        }
40        Ok(index)
41    }
42
43    pub fn lookup(&self, pattern: &GraphPattern) -> Option<&BTreeSet<BTreeSet<VertexId>>> {
44        self.pattern_to_matches.get(&canonicalize(pattern))
45    }
46
47    pub fn has_pattern(&self, pattern: &GraphPattern) -> bool {
48        self.pattern_to_matches.contains_key(&canonicalize(pattern))
49    }
50
51    pub fn indexed_patterns(&self) -> Vec<String> {
52        self.pattern_to_matches.keys().cloned().collect()
53    }
54
55    pub fn invalidate_by_edge_labels(&mut self, labels: &BTreeSet<String>) {
56        self.pattern_to_matches
57            .retain(|key, _| !labels.iter().any(|label| key.contains(label)));
58    }
59}
60
61fn canonicalize(pattern: &GraphPattern) -> String {
62    let mut vertices: Vec<String> = pattern
63        .vertex_patterns
64        .iter()
65        .map(|vp| format!("{}:{:?}", vp.variable, vp.constraints))
66        .collect();
67    vertices.sort();
68
69    let mut edges: Vec<String> = pattern
70        .edge_patterns
71        .iter()
72        .map(|ep| {
73            format!(
74                "{}>{}:{:?}:{:?}:{}",
75                ep.source_var, ep.target_var, ep.label, ep.constraints, ep.negated
76            )
77        })
78        .collect();
79    edges.sort();
80
81    format!("V:{}|E:{}", vertices.join(","), edges.join(","))
82}
83
84#[cfg(test)]
85mod tests {
86    use uqa_core::{Edge, Vertex};
87
88    use super::*;
89    use crate::{EdgePattern, GraphStore, MemoryGraphStore, VertexPattern};
90
91    #[test]
92    fn build_and_lookup_cached_pattern() {
93        let graph = "g";
94        let mut store = MemoryGraphStore::new();
95        store.create_graph(graph);
96        store.add_vertex(Vertex::new(1, "Person"), graph).unwrap();
97        store.add_vertex(Vertex::new(2, "Person"), graph).unwrap();
98        store.add_edge(Edge::new(10, 1, 2, "knows"), graph).unwrap();
99
100        let pattern = GraphPattern::new()
101            .add_vertex(VertexPattern::new("a"))
102            .add_vertex(VertexPattern::new("b"))
103            .add_edge(EdgePattern::new("a", "b").with_label("knows"));
104        let index = SubgraphIndex::build(&store, std::slice::from_ref(&pattern), graph).unwrap();
105
106        assert!(index.has_pattern(&pattern));
107        assert_eq!(index.lookup(&pattern).unwrap().len(), 1);
108    }
109}
uqa_graph/subgraph_index.rs

uqa_graph/
subgraph_index.rs
