sqlite_graphrag/graph/
bfs.rs

1//! Predecessor-tracking BFS used to reconstruct evidence chains.
2//!
3//! Unlike [`super::traverse`], this records HOW each entity was reached, so a
4//! caller can walk the path back to its seed. The walk itself is the shared
5//! [`super::walk`] engine; this module only reshapes its arrival map.
6
7use super::walk::{GraphWalk, SqlNeighbors};
8use crate::errors::AppError;
9use rusqlite::Connection;
10
11/// Depth map from BFS: entity_id → hop distance from seeds.
12pub type EntityDepthMap = std::collections::HashMap<i64, u32>;
13
14/// Predecessor map from BFS: entity_id → (parent_entity_id, relation_type, edge_weight).
15///
16/// Enables path reconstruction from any discovered entity back to a seed.
17pub type PredecessorMap = std::collections::HashMap<i64, (i64, String, f64)>;
18
19/// BFS that also returns a predecessor map for path reconstruction.
20///
21/// Used by `deep-research` to reconstruct directed evidence chains from
22/// discovered entities back to their seeds.
23///
24/// Returns `(entity_depth, predecessor)` where:
25/// - `entity_depth`: minimum depth of each reached entity (0 = seed).
26/// - `predecessor`: the BFS tree edge that first reached each non-seed entity.
27///
28/// When `max_neighbors_per_hop` is `Some(k)`, only the top-`k` unvisited
29/// neighbours by `weight DESC` are followed at each entity expansion.
30///
31/// # Errors
32///
33/// Propagates [`AppError::Database`] (exit 10) on SQLite query failures.
34pub fn bfs_with_predecessors(
35    conn: &Connection,
36    seed_entity_ids: &[i64],
37    namespace: &str,
38    min_weight: f64,
39    max_hops: u32,
40    max_neighbors_per_hop: Option<usize>,
41) -> Result<(EntityDepthMap, PredecessorMap), AppError> {
42    let walk = GraphWalk::directed(min_weight, max_hops).with_neighbor_cap(max_neighbors_per_hop);
43    let outcome = walk.run(&SqlNeighbors::new(conn, namespace), seed_entity_ids)?;
44
45    let predecessor: PredecessorMap = outcome
46        .arrival
47        .into_iter()
48        .map(|(id, edge)| (id, (edge.from_id, edge.relation, edge.weight)))
49        .collect();
50
51    Ok((outcome.depth, predecessor))
52}
sqlite_graphrag/graph/bfs.rs

sqlite_graphrag/graph/
bfs.rs
