Skip to main content

transitive_closure

sqlitegraph::algo

Function transitive_closure 

Source 
pub fn transitive_closure(
    graph: &SqliteGraph,
    bounds: Option<TransitiveClosureBounds>,
) -> Result<AHashMap<(i64, i64), bool>, SqliteGraphError>
Expand description

Computes transitive closure for all-pairs reachability.

Transitive closure determines which nodes can reach which other nodes in the graph. Returns a HashMap where keys are (source, target) pairs and values are always true for reachable pairs. Self-reachability is included (every node can reach itself).

§Arguments

  • graph - The graph to analyze
  • bounds - Optional bounds to limit computation

§Returns

HashMap mapping (source_id, target_id) -> true for all reachable pairs.

§Complexity

  • Time: O(|V| * (|V| + |E|)) worst case for unbounded
  • Space: O(|V|²) for full transitive closure

§Algorithm

Uses BFS from each source node:

  1. For each source node, run BFS limited by max_depth
  2. Track visited nodes to prevent infinite loops on cycles
  3. Store (source, target) pairs for all reachable nodes
  4. Self-reachability is always true (node can reach itself)

§Bounds Behavior

  • max_depth - Limits BFS depth from each source
  • max_sources - Processes only first N source nodes
  • max_pairs - Stops early after finding N reachable pairs

§Example

ⓘ
use sqlitegraph::{SqliteGraph, algo::transitive_closure};

let graph = SqliteGraph::open_in_memory()?;
// ... add nodes and edges ...

// Full transitive closure
let closure = transitive_closure(&graph, None)?;

// Query: can node 1 reach node 5?
let can_reach = closure.get(&(1, 5)).copied().unwrap_or(false);

// Count reachable nodes from source 1
let reachable_count: usize = closure.iter()
    .filter(|((&src, _), _)| src == 1)
    .count();

§See Also