use crate::error::Result;
use crate::graph::{Direction, Edge, GraphEngine};
use crate::vector::{cosine_similarity, ProductQuantizer};
use serde::{Deserialize, Serialize};
use std::collections::{HashMap, HashSet, VecDeque};
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct GraphRagConfig {
pub top_seeds: usize,
pub max_hops: usize,
pub rrf_k: f32,
pub vector_weight: f32,
pub graph_weight: f32,
pub lexical_weight: f32,
#[serde(default)]
pub direction: Option<Direction>,
pub min_score: f32,
pub limit: usize,
}
impl Default for GraphRagConfig {
fn default() -> Self {
Self {
top_seeds: 3,
max_hops: 2,
rrf_k: 60.0,
vector_weight: 0.50,
graph_weight: 0.30,
lexical_weight: 0.20,
direction: Some(Direction::Both),
min_score: 0.0,
limit: 5,
}
}
}
impl GraphRagConfig {
pub fn new() -> Self {
Self::default()
}
pub fn with_seeds(mut self, seeds: usize) -> Self {
self.top_seeds = seeds;
self
}
pub fn with_max_hops(mut self, hops: usize) -> Self {
self.max_hops = hops;
self
}
pub fn with_limit(mut self, limit: usize) -> Self {
self.limit = limit;
self
}
pub fn with_weights(mut self, vector: f32, graph: f32, lexical: f32) -> Self {
self.vector_weight = vector;
self.graph_weight = graph;
self.lexical_weight = lexical;
self
}
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct GraphRagResult {
pub entity_id: u64,
pub label: String,
pub properties: String,
pub rrf_score: f32,
pub seed_similarity: Option<f32>,
pub hop_distance: usize,
pub related_edges: Vec<Edge>,
}
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct GraphRagContext {
pub query: String,
pub results: Vec<GraphRagResult>,
pub prompt_context: String,
}
pub struct GraphRagEngine;
impl GraphRagEngine {
pub fn query(
graph: &GraphEngine,
query_text: &str,
query_vec: Option<&[f32]>,
pq: Option<&ProductQuantizer>,
config: &GraphRagConfig,
) -> Result<GraphRagContext> {
let all_nodes = graph.all_nodes();
if all_nodes.is_empty() {
return Ok(GraphRagContext {
query: query_text.to_string(),
results: Vec::new(),
prompt_context: String::from("No entities found in knowledge graph."),
});
}
let mut seed_candidates: Vec<(u64, f32)> = Vec::new();
if let Some(q_vec) = query_vec {
for node in &all_nodes {
if let Some(ref n_vec) = node.vector {
if n_vec.len() == q_vec.len() {
let sim = if let Some(quantizer) = pq {
let code = quantizer.encode(n_vec);
let dist = quantizer.asymmetric_distance(&code, q_vec);
1.0 / (1.0 + dist)
} else {
cosine_similarity(q_vec, n_vec).max(0.0)
};
seed_candidates.push((node.id, sim));
}
}
}
}
if seed_candidates.is_empty() {
let terms: Vec<String> = query_text
.to_lowercase()
.split_whitespace()
.map(|s| s.trim_matches(|c: char| !c.is_alphanumeric()).to_string())
.filter(|s| !s.is_empty())
.collect();
for node in &all_nodes {
let text = format!("{} {}", node.label, node.properties).to_lowercase();
let match_count = terms.iter().filter(|&t| text.contains(t)).count();
if match_count > 0 {
let score = match_count as f32 / terms.len().max(1) as f32;
seed_candidates.push((node.id, score));
}
}
}
seed_candidates.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
let seed_limit = config.top_seeds.max(1);
let seeds: Vec<(u64, f32)> = seed_candidates.into_iter().take(seed_limit).collect();
let traversal_dir = config.direction.unwrap_or(Direction::Both);
let mut visited_nodes: HashMap<u64, (usize, f32)> = HashMap::new(); let mut node_edges: HashMap<u64, Vec<Edge>> = HashMap::new();
let mut queue: VecDeque<(u64, usize, f32)> = VecDeque::new();
for &(seed_id, seed_score) in &seeds {
visited_nodes.insert(seed_id, (0, seed_score));
queue.push_back((seed_id, 0, 1.0));
}
while let Some((curr_id, curr_hops, curr_weight)) = queue.pop_front() {
if curr_hops >= config.max_hops {
continue;
}
let neighbors = graph.neighbors(curr_id, traversal_dir, None);
for (neighbor_node, edge) in neighbors {
let next_hops = curr_hops + 1;
let next_weight = curr_weight * (edge.weight / (1.0 + next_hops as f32));
node_edges
.entry(neighbor_node.id)
.or_default()
.push(edge.clone());
node_edges
.entry(curr_id)
.or_default()
.push(edge.clone());
let should_visit = match visited_nodes.get(&neighbor_node.id) {
Some(&(prev_hops, prev_weight)) => {
next_hops < prev_hops || (next_hops == prev_hops && next_weight > prev_weight)
}
None => true,
};
if should_visit {
visited_nodes.insert(neighbor_node.id, (next_hops, next_weight));
queue.push_back((neighbor_node.id, next_hops, next_weight));
}
}
}
for edges in node_edges.values_mut() {
let mut seen_edge_ids = HashSet::new();
edges.retain(|e| seen_edge_ids.insert(e.id));
}
let candidate_ids: Vec<u64> = visited_nodes.keys().copied().collect();
if candidate_ids.is_empty() {
return Ok(GraphRagContext {
query: query_text.to_string(),
results: Vec::new(),
prompt_context: String::from("No related facts discovered for query."),
});
}
let mut vector_scores: Vec<(u64, f32)> = Vec::new();
if let Some(q_vec) = query_vec {
for &id in &candidate_ids {
let score = if let Some(node) = graph.get_node(id) {
if let Some(ref n_vec) = node.vector {
if n_vec.len() == q_vec.len() {
cosine_similarity(q_vec, n_vec).max(0.0)
} else {
0.0
}
} else {
0.0
}
} else {
0.0
};
vector_scores.push((id, score));
}
} else {
for &id in &candidate_ids {
let s_score = seeds.iter().find(|&&(s_id, _)| s_id == id).map(|&(_, s)| s).unwrap_or(0.0);
vector_scores.push((id, s_score));
}
}
vector_scores.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
let vec_ranks: HashMap<u64, usize> = vector_scores
.iter()
.enumerate()
.map(|(rank, &(id, _))| (id, rank + 1))
.collect();
let terms: Vec<String> = query_text
.to_lowercase()
.split_whitespace()
.map(|s| s.trim_matches(|c: char| !c.is_alphanumeric()).to_string())
.filter(|s| !s.is_empty())
.collect();
let mut lexical_scores: Vec<(u64, f32)> = Vec::new();
for &id in &candidate_ids {
let score = if let Some(node) = graph.get_node(id) {
let text = format!("{} {}", node.label, node.properties).to_lowercase();
let matches = terms.iter().filter(|&t| text.contains(t)).count();
matches as f32 / terms.len().max(1) as f32
} else {
0.0
};
lexical_scores.push((id, score));
}
lexical_scores.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
let lex_ranks: HashMap<u64, usize> = lexical_scores
.iter()
.enumerate()
.map(|(rank, &(id, _))| (id, rank + 1))
.collect();
let mut graph_proximity: Vec<(u64, usize, f32)> = candidate_ids
.iter()
.map(|&id| {
let &(hops, weight) = visited_nodes.get(&id).unwrap_or(&(usize::MAX, 0.0));
(id, hops, weight)
})
.collect();
graph_proximity.sort_by(|a, b| {
if a.1 != b.1 {
a.1.cmp(&b.1) } else {
b.2.partial_cmp(&a.2).unwrap_or(std::cmp::Ordering::Equal) }
});
let graph_ranks: HashMap<u64, usize> = graph_proximity
.iter()
.enumerate()
.map(|(rank, &(id, _, _))| (id, rank + 1))
.collect();
let mut final_results: Vec<GraphRagResult> = Vec::new();
let worst_rank = candidate_ids.len() + 10;
for &id in &candidate_ids {
if let Some(node) = graph.get_node(id) {
let r_vec = *vec_ranks.get(&id).unwrap_or(&worst_rank) as f32;
let r_lex = *lex_ranks.get(&id).unwrap_or(&worst_rank) as f32;
let r_graph = *graph_ranks.get(&id).unwrap_or(&worst_rank) as f32;
let rrf_score = (config.vector_weight / (config.rrf_k + r_vec))
+ (config.lexical_weight / (config.rrf_k + r_lex))
+ (config.graph_weight / (config.rrf_k + r_graph));
if rrf_score >= config.min_score {
let &(hop_dist, _) = visited_nodes.get(&id).unwrap_or(&(0, 0.0));
let seed_sim = seeds.iter().find(|&&(s_id, _)| s_id == id).map(|&(_, s)| s);
let edges = node_edges.get(&id).cloned().unwrap_or_default();
final_results.push(GraphRagResult {
entity_id: id,
label: node.label.clone(),
properties: node.properties.clone(),
rrf_score,
seed_similarity: seed_sim,
hop_distance: hop_dist,
related_edges: edges,
});
}
}
}
final_results.sort_by(|a, b| b.rrf_score.partial_cmp(&a.rrf_score).unwrap_or(std::cmp::Ordering::Equal));
final_results.truncate(config.limit);
let mut prompt_context = String::new();
prompt_context.push_str("### 🧠Verified Knowledge Graph Context\n\n");
prompt_context.push_str("#### Entities & Facts:\n");
for r in &final_results {
prompt_context.push_str(&format!(
"- **{}** (ID: {}) [Hops: {}, Confidence: {:.4}]\n - Properties: {}\n",
r.label, r.entity_id, r.hop_distance, r.rrf_score, r.properties
));
}
let retrieved_ids: HashSet<u64> = final_results.iter().map(|r| r.entity_id).collect();
let mut distinct_edges: Vec<Edge> = Vec::new();
let mut seen_edge_ids = HashSet::new();
for r in &final_results {
for e in &r.related_edges {
if seen_edge_ids.insert(e.id) {
if retrieved_ids.contains(&e.from_id) || retrieved_ids.contains(&e.to_id) {
distinct_edges.push(e.clone());
}
}
}
}
if !distinct_edges.is_empty() {
prompt_context.push_str("\n#### Relationships:\n");
for e in &distinct_edges {
let from_name = graph
.get_node(e.from_id)
.map(|n| n.label.as_str())
.unwrap_or("Unknown");
let to_name = graph
.get_node(e.to_id)
.map(|n| n.label.as_str())
.unwrap_or("Unknown");
prompt_context.push_str(&format!(
"- (`{}`: #{}) ───[{}]───► (`{}`: #{}) (weight: {:.2})\n",
from_name, e.from_id, e.label, to_name, e.to_id, e.weight
));
}
}
Ok(GraphRagContext {
query: query_text.to_string(),
results: final_results,
prompt_context,
})
}
}