Struct KnowledgeGraphTraverser 

pub struct KnowledgeGraphTraverser {
    pub graph: KnowledgeGraph,
}

Provides graph traversal, path-finding, and subgraph extraction over a KnowledgeGraph.

All algorithms are iterative (no recursion) to avoid stack-overflow on large graphs and to give predictable performance for distributed workloads.

Fields

graph: KnowledgeGraph

The underlying knowledge graph.

Implementations

impl KnowledgeGraphTraverser

pub fn new(graph: KnowledgeGraph) -> Self

Wrap a KnowledgeGraph in a traverser.

pub fn bfs(&self, start: &str, max_depth: usize) -> Vec<String>

Breadth-first search starting from start.

Returns the node IDs in BFS visit order. Nodes deeper than max_depth hops from start are not visited. A visited-set prevents cycles from causing duplicate visits.

Returns an empty Vec if start does not exist in the graph.

pub fn dfs(&self, start: &str, max_depth: usize) -> Vec<String>

Depth-first search starting from start.

Returns node IDs in DFS visit order (pre-order). Nodes deeper than max_depth hops from start are not visited. A visited-set prevents revisiting nodes in cyclic graphs.

Returns an empty Vec if start does not exist in the graph.

pub fn find_path(&self, from: &str, to: &str) -> Option<Vec<String>>

Find the shortest path (fewest hops) from from to to using BFS.

Returns Some(path) where path is the sequence of node IDs from from to to inclusive, or None if no path exists or either endpoint is absent.

pub fn subgraph(&self, roots: &[String], depth: usize) -> KnowledgeGraph

Extract the subgraph reachable from any of the roots within depth hops (inclusive).

The returned KnowledgeGraph contains all reachable nodes together with every edge whose both endpoints are in the reachable set.

pub fn connected_components(&self) -> Vec<Vec<String>>

Compute the connected components of the undirected version of the graph using union-find (path-compressed, union-by-rank).

Returns one Vec<String> per component. Each component’s node IDs are sorted lexicographically. Components are themselves ordered by their smallest member.

pub fn has_cycle(&self) -> bool

Detect whether the directed graph contains at least one cycle.

Uses iterative DFS with three-colour marking:

• White (0): unvisited
• Gray (1): on the current DFS path (recursion stack)
• Black (2): fully processed