Skip to main content

qualia_core_db/nlp/
graphrag.rs

1//! Graph-augmented retrieval — keyword-based triple retrieval.
2//!
3//! A tiny in-memory triple store with an entity → triple-index map. Queries
4//! are ranked by term overlap between the query and each triple's components.
5//! Deterministic, WASM-compatible, no embeddings.
6
7use std::collections::HashMap;
8
9/// One ranked retrieval result.
10#[derive(Debug, Clone, PartialEq)]
11pub struct GraphRagResult {
12    pub triple: (String, String, String),
13    pub score: f64,
14}
15
16/// In-memory graph-RAG index.
17#[derive(Debug, Clone, Default)]
18pub struct GraphRagIndex {
19    pub triples: Vec<(String, String, String)>,
20    pub entity_index: HashMap<String, Vec<usize>>,
21}
22
23impl GraphRagIndex {
24    /// Creates a default `GraphRagIndex`.
25    pub fn new() -> Self {
26        Self::default()
27    }
28
29    /// Add a triple and index every component token.
30    pub fn add_triple(&mut self, subject: &str, predicate: &str, object: &str) {
31        let id = self.triples.len();
32        let triple = (
33            subject.to_string(),
34            predicate.to_string(),
35            object.to_string(),
36        );
37        for token in tokenize_triple(&triple) {
38            self.entity_index.entry(token).or_default().push(id);
39        }
40        self.triples.push(triple);
41    }
42
43    /// Query the index: rank triples by overlap of query terms with triple
44    /// components. Returns up to `k` results, highest score first.
45    pub fn query(&self, query_text: &str, k: usize) -> Vec<GraphRagResult> {
46        let q_terms: Vec<String> = query_text
47            .split(|c: char| !c.is_alphanumeric())
48            .filter(|s| !s.is_empty())
49            .map(|s| s.to_ascii_lowercase())
50            .collect();
51        if q_terms.is_empty() || self.triples.is_empty() {
52            return Vec::new();
53        }
54        let mut scored: Vec<(usize, f64)> = self
55            .triples
56            .iter()
57            .enumerate()
58            .map(|(i, t)| {
59                let triple_terms: Vec<String> = tokenize_triple(t);
60                let mut hits = 0usize;
61                for q in &q_terms {
62                    if triple_terms.iter().any(|tt| tt == q) {
63                        hits += 1;
64                    }
65                }
66                let score = hits as f64 / q_terms.len() as f64;
67                (i, score)
68            })
69            .filter(|(_, s)| *s > 0.0)
70            .collect();
71        // Deterministic sort: score desc, then index asc for stable ties.
72        scored.sort_by(|a, b| {
73            b.1.partial_cmp(&a.1)
74                .unwrap_or(std::cmp::Ordering::Equal)
75                .then(a.0.cmp(&b.0))
76        });
77        scored
78            .into_iter()
79            .take(k)
80            .map(|(i, score)| GraphRagResult {
81                triple: self.triples[i].clone(),
82                score,
83            })
84            .collect()
85    }
86}
87
88/// Lowercase alphanumeric tokens across all three components of a triple.
89fn tokenize_triple(t: &(String, String, String)) -> Vec<String> {
90    let mut out = Vec::new();
91    for comp in [&t.0, &t.1, &t.2] {
92        for tok in comp.split(|c: char| !c.is_alphanumeric()) {
93            if !tok.is_empty() {
94                out.push(tok.to_ascii_lowercase());
95            }
96        }
97    }
98    out
99}
100
101#[cfg(test)]
102mod tests {
103    use super::*;
104
105    #[test]
106    fn build_and_query_basic() {
107        let mut idx = GraphRagIndex::new();
108        idx.add_triple("Paris", "locatedIn", "France");
109        idx.add_triple("Socrates", "rdf:type", "philosopher");
110        idx.add_triple("cat", "has", "tail");
111        let results = idx.query("Paris France", 10);
112        assert_eq!(results.len(), 1);
113        assert_eq!(results[0].triple.0, "Paris");
114        assert_eq!(results[0].triple.2, "France");
115        assert!(results[0].score > 0.0);
116    }
117
118    #[test]
119    fn query_ranks_by_overlap() {
120        let mut idx = GraphRagIndex::new();
121        idx.add_triple("dog", "has", "tail");
122        idx.add_triple("cat", "has", "tail");
123        idx.add_triple("bird", "has", "wings");
124        let results = idx.query("cat tail", 10);
125        // "cat has tail" matches both terms → score 1.0; "dog has tail" matches
126        // one → 0.5; "bird has wings" matches none.
127        assert_eq!(results.len(), 2);
128        assert_eq!(results[0].triple.0, "cat");
129        assert!(results[0].score > results[1].score);
130    }
131
132    #[test]
133    fn empty_query_returns_empty() {
134        let mut idx = GraphRagIndex::new();
135        idx.add_triple("a", "b", "c");
136        assert!(idx.query("", 10).is_empty());
137    }
138
139    #[test]
140    fn empty_index_returns_empty() {
141        let idx = GraphRagIndex::new();
142        assert!(idx.query("anything", 10).is_empty());
143    }
144
145    #[test]
146    fn k_limits_results() {
147        let mut idx = GraphRagIndex::new();
148        idx.add_triple("a", "has", "x");
149        idx.add_triple("b", "has", "x");
150        idx.add_triple("c", "has", "x");
151        let results = idx.query("x", 2);
152        assert_eq!(results.len(), 2);
153    }
154
155    #[test]
156    fn entity_index_populated() {
157        let mut idx = GraphRagIndex::new();
158        idx.add_triple("Paris", "locatedIn", "France");
159        assert!(idx.entity_index.contains_key("paris"));
160        assert!(idx.entity_index.contains_key("france"));
161        assert!(idx.entity_index.contains_key("locatedin"));
162    }
163}