use crate::error::Result;
use crate::graph::{Direction, Edge, GraphEngine, Node};
use crate::vector::{DistanceMetric, cosine_similarity, euclidean_distance};
use std::collections::{BinaryHeap, HashMap, HashSet};
#[derive(Debug, Clone)]
pub struct TraversalStep {
pub direction: Direction,
pub edge_label: Option<String>,
pub min_weight: Option<f32>,
}
#[derive(Debug, Clone)]
pub enum NodeFilter {
Label(String),
PropertyContains {
key: String,
val: String,
},
}
#[derive(Debug, Clone, PartialEq)]
pub struct ChainMatch {
pub node: Node,
pub score: f32,
pub path: Vec<Edge>,
}
#[derive(Debug)]
struct ScoredCandidate<'b> {
node: &'b Node,
score: f32,
path: Vec<Edge>,
}
impl<'b> PartialEq for ScoredCandidate<'b> {
fn eq(&self, other: &Self) -> bool {
self.cmp(other).is_eq()
}
}
impl<'b> Eq for ScoredCandidate<'b> {}
impl<'b> PartialOrd for ScoredCandidate<'b> {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
impl<'b> Ord for ScoredCandidate<'b> {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
other
.score
.total_cmp(&self.score)
.then_with(|| other.node.id.cmp(&self.node.id))
}
}
pub struct GraphChain<'a> {
graph: &'a GraphEngine,
external_vectors: Option<&'a HashMap<u64, Vec<f32>>>,
external_resolver: Option<&'a dyn Fn(u64) -> Option<Vec<f32>>>,
start_nodes: Vec<u64>,
steps: Vec<TraversalStep>,
node_filters: Vec<NodeFilter>,
max_hops: usize,
}
impl<'a> GraphChain<'a> {
pub fn new(graph: &'a GraphEngine, start_nodes: Vec<u64>) -> Self {
Self {
graph,
external_vectors: None,
external_resolver: None,
start_nodes,
steps: Vec::new(),
node_filters: Vec::new(),
max_hops: 10,
}
}
pub fn with_external_vectors(mut self, vectors: &'a HashMap<u64, Vec<f32>>) -> Self {
self.external_vectors = Some(vectors);
self
}
pub fn with_vector_resolver(mut self, resolver: &'a dyn Fn(u64) -> Option<Vec<f32>>) -> Self {
self.external_resolver = Some(resolver);
self
}
pub fn out<S: Into<String>>(mut self, label: Option<S>) -> Self {
self.steps.push(TraversalStep {
direction: Direction::Outgoing,
edge_label: label.map(Into::into),
min_weight: None,
});
self
}
pub fn in_<S: Into<String>>(mut self, label: Option<S>) -> Self {
self.steps.push(TraversalStep {
direction: Direction::Incoming,
edge_label: label.map(Into::into),
min_weight: None,
});
self
}
pub fn both<S: Into<String>>(mut self, label: Option<S>) -> Self {
self.steps.push(TraversalStep {
direction: Direction::Both,
edge_label: label.map(Into::into),
min_weight: None,
});
self
}
pub fn min_weight(mut self, weight: f32) -> Self {
if let Some(last) = self.steps.last_mut() {
last.min_weight = Some(weight);
}
self
}
pub fn filter_label<S: Into<String>>(mut self, label: S) -> Self {
self.node_filters.push(NodeFilter::Label(label.into()));
self
}
pub fn filter_property<S1: Into<String>, S2: Into<String>>(mut self, key: S1, val: S2) -> Self {
self.node_filters.push(NodeFilter::PropertyContains {
key: key.into(),
val: val.into(),
});
self
}
pub fn max_hops(mut self, hops: usize) -> Self {
self.max_hops = hops;
self
}
fn resolve_candidates(&self) -> Vec<(&'a Node, Vec<Edge>)> {
if self.start_nodes.is_empty() {
return Vec::new();
}
let mut frontier: Vec<(&'a Node, Vec<Edge>)> = self
.start_nodes
.iter()
.filter_map(|&id| self.graph.get_node(id).map(|n| (n, Vec::new())))
.collect();
for step in &self.steps {
let mut next_frontier = Vec::new();
let mut visited_step = HashSet::new();
for (curr_node, path) in frontier {
let neighbors = self.graph.neighbor_refs(
curr_node.id,
step.direction,
step.edge_label.as_deref(),
);
for (neighbor, edge) in neighbors {
if let Some(min_w) = step.min_weight
&& edge.weight < min_w
{
continue;
}
if visited_step.insert((curr_node.id, neighbor.id, edge.id)) {
let mut new_path = path.clone();
new_path.push((*edge).clone());
next_frontier.push((neighbor, new_path));
}
}
}
frontier = next_frontier;
if frontier.is_empty() {
break;
}
}
frontier
.into_iter()
.filter(|(node, _)| {
for filter in &self.node_filters {
match filter {
NodeFilter::Label(expected) => {
if !node.label.eq_ignore_ascii_case(expected) {
return false;
}
}
NodeFilter::PropertyContains { key, val } => {
let needle = format!("\"{key}\":\"{val}\"");
let needle_unquoted = format!("\"{key}\":{val}");
if !node.properties.contains(&needle)
&& !node.properties.contains(&needle_unquoted)
{
return false;
}
}
}
}
true
})
.collect()
}
fn get_node_vector<'b>(&'b self, node: &'b Node) -> Option<std::borrow::Cow<'b, [f32]>> {
if let Some(ref v) = node.vector {
return Some(std::borrow::Cow::Borrowed(v.as_slice()));
}
if let Some(ext) = self.external_vectors
&& let Some(v) = ext.get(&node.id)
{
return Some(std::borrow::Cow::Borrowed(v.as_slice()));
}
if let Some(ref resolver) = self.external_resolver
&& let Some(v) = resolver(node.id)
{
return Some(std::borrow::Cow::Owned(v));
}
None
}
pub fn vector_near(
&self,
query_vec: &[f32],
top_k: usize,
metric: DistanceMetric,
) -> Result<Vec<ChainMatch>> {
if top_k == 0 {
return Ok(Vec::new());
}
let candidates = self.resolve_candidates();
if candidates.is_empty() {
return Ok(Vec::new());
}
let mut heap: BinaryHeap<ScoredCandidate<'a>> = BinaryHeap::with_capacity(top_k + 1);
for (node, path) in candidates {
if let Some(node_vec) = self.get_node_vector(node) {
let s = node_vec.as_ref();
if s.len() != query_vec.len() {
continue; }
let score = match metric {
DistanceMetric::Cosine => cosine_similarity(query_vec, s),
DistanceMetric::DotProduct => crate::vector::dot_product(query_vec, s),
DistanceMetric::Euclidean => -euclidean_distance(query_vec, s),
};
heap.push(ScoredCandidate { node, score, path });
if heap.len() > top_k {
heap.pop();
}
}
}
let mut results: Vec<ChainMatch> = heap
.into_iter()
.map(|c| ChainMatch {
node: (*c.node).clone(),
score: c.score,
path: c.path,
})
.collect();
results.sort_by(|a, b| {
b.score
.partial_cmp(&a.score)
.unwrap_or(std::cmp::Ordering::Equal)
});
Ok(results)
}
pub fn bm25_search(&self, query_text: &str, top_k: usize) -> Result<Vec<ChainMatch>> {
if top_k == 0 {
return Ok(Vec::new());
}
let candidates = self.resolve_candidates();
if candidates.is_empty() {
return Ok(Vec::new());
}
let query_tokens = crate::memory::bm25::tokenize(query_text);
if query_tokens.is_empty() {
return Ok(Vec::new());
}
let n = candidates.len() as f32;
let mut doc_tokens_list = Vec::with_capacity(candidates.len());
let mut total_len = 0usize;
for (node, _) in &candidates {
let text = format!("{} {}", node.label, node.properties);
let toks = crate::memory::bm25::tokenize(&text);
total_len += toks.len();
doc_tokens_list.push(toks);
}
let avgdl = if n > 0.0 { total_len as f32 / n } else { 1.0 };
let k1 = 1.2f32;
let b = 0.75f32;
let mut heap: BinaryHeap<ScoredCandidate<'a>> = BinaryHeap::with_capacity(top_k + 1);
for (idx, (node, path)) in candidates.into_iter().enumerate() {
let doc_tokens = &doc_tokens_list[idx];
let doc_len = doc_tokens.len() as f32;
let mut score = 0.0f32;
for q_term in &query_tokens {
let tf = doc_tokens.iter().filter(|t| *t == q_term).count() as f32;
if tf > 0.0 {
let df = doc_tokens_list
.iter()
.filter(|d| d.contains(q_term))
.count() as f32;
let idf = ((n - df + 0.5) / (df + 0.5) + 1.0).ln().max(0.0);
let tf_norm =
(tf * (k1 + 1.0)) / (tf + k1 * (1.0 - b + b * (doc_len / avgdl.max(1.0))));
score += idf * tf_norm;
}
}
if score > 0.0 {
heap.push(ScoredCandidate { node, score, path });
if heap.len() > top_k {
heap.pop();
}
}
}
let mut results: Vec<ChainMatch> = heap
.into_iter()
.map(|c| ChainMatch {
node: (*c.node).clone(),
score: c.score,
path: c.path,
})
.collect();
results.sort_by(|a, b| {
b.score
.partial_cmp(&a.score)
.unwrap_or(std::cmp::Ordering::Equal)
});
Ok(results)
}
pub fn hybrid_rank(
&self,
query_text: &str,
query_vec: &[f32],
top_k: usize,
vector_weight: f32,
) -> Result<Vec<ChainMatch>> {
if top_k == 0 {
return Ok(Vec::new());
}
let candidates = self.resolve_candidates();
if candidates.is_empty() {
return Ok(Vec::new());
}
let vw = vector_weight.clamp(0.0, 1.0);
let bw = 1.0 - vw;
let query_tokens = crate::memory::bm25::tokenize(query_text);
let n = candidates.len() as f32;
let mut doc_tokens_list = Vec::with_capacity(candidates.len());
let mut total_len = 0usize;
for (node, _) in &candidates {
let text = format!("{} {}", node.label, node.properties);
let toks = crate::memory::bm25::tokenize(&text);
total_len += toks.len();
doc_tokens_list.push(toks);
}
let avgdl = if n > 0.0 { total_len as f32 / n } else { 1.0 };
let k1 = 1.2f32;
let b = 0.75f32;
let mut heap: BinaryHeap<ScoredCandidate<'a>> = BinaryHeap::with_capacity(top_k + 1);
for (idx, (node, path)) in candidates.into_iter().enumerate() {
let mut bm25_raw = 0.0f32;
if !query_tokens.is_empty() {
let doc_tokens = &doc_tokens_list[idx];
let doc_len = doc_tokens.len() as f32;
for q_term in &query_tokens {
let tf = doc_tokens.iter().filter(|t| *t == q_term).count() as f32;
if tf > 0.0 {
let df = doc_tokens_list
.iter()
.filter(|d| d.contains(q_term))
.count() as f32;
let idf = ((n - df + 0.5) / (df + 0.5) + 1.0).ln().max(0.0);
let tf_norm = (tf * (k1 + 1.0))
/ (tf + k1 * (1.0 - b + b * (doc_len / avgdl.max(1.0))));
bm25_raw += idf * tf_norm;
}
}
}
let bm25_norm = if bm25_raw > 0.0 {
bm25_raw / (bm25_raw + 1.0)
} else {
0.0
};
let vec_sim = if let Some(node_vec) = self.get_node_vector(node) {
let s = node_vec.as_ref();
if s.len() == query_vec.len() {
cosine_similarity(query_vec, s).max(0.0)
} else {
0.0
}
} else {
0.0
};
let combined_score = (vw * vec_sim) + (bw * bm25_norm);
heap.push(ScoredCandidate {
node,
score: combined_score,
path,
});
if heap.len() > top_k {
heap.pop();
}
}
let mut results: Vec<ChainMatch> = heap
.into_iter()
.map(|c| ChainMatch {
node: (*c.node).clone(),
score: c.score,
path: c.path,
})
.collect();
results.sort_by(|a, b| {
b.score
.partial_cmp(&a.score)
.unwrap_or(std::cmp::Ordering::Equal)
});
Ok(results)
}
pub fn collect_nodes(&self) -> Vec<Node> {
let mut seen = HashSet::new();
self.resolve_candidates()
.into_iter()
.map(|(n, _)| n)
.filter(|n| seen.insert(n.id))
.cloned()
.collect()
}
pub fn collect_ids(&self) -> Vec<u64> {
let mut seen = HashSet::new();
self.resolve_candidates()
.into_iter()
.map(|(n, _)| n.id)
.filter(|&id| seen.insert(id))
.collect()
}
pub fn collect_matches(&self) -> Vec<ChainMatch> {
self.resolve_candidates()
.into_iter()
.map(|(node, path)| ChainMatch {
node: (*node).clone(),
score: 1.0,
path,
})
.collect()
}
}