Graph Construction & Traversal

Relevant source files

The following files were used as context for generating this wiki page:

• crates/arbor-graph/src/builder.rs
• crates/arbor-graph/src/graph.rs
• crates/arbor-graph/src/impact.rs
• crates/arbor-graph/src/lib.rs
• crates/arbor-core/src/parser_v2.rs

Graph Construction and Traversal represent the core operational layer of Arbor, responsible for transforming raw source code into a semantic dependency graph and enabling complex structural queries. This system utilizes high-performance parsing to extract code entities (Nodes) and their relationships (Edges), subsequently facilitating pathfinding and impact analysis. Sources: crates/arbor-graph/src/lib.rs:1-10, crates/arbor-core/src/parser_v2.rs:1-10

The architecture is built upon the petgraph library, augmented with specialized indices for fast lookups by name, file, and ID. This allows Arbor to serve as a Code Property Graph (CPG) that AI agents and developers can navigate to understand the "blast radius" of code changes with structural certainty. Sources: crates/arbor-graph/src/graph.rs:10-20, README.md

Graph Construction Pipeline

The construction of the code graph follows a multi-stage pipeline, moving from source file parsing to symbol resolution.

1. Symbol Extraction

The ArborParser uses Tree-sitter queries to extract CodeNode objects from source files. These nodes represent functions, classes, interfaces, structs, and other language-specific constructs. Each node captures metadata such as line numbers, file paths, and fully qualified names (FQN). Sources: crates/arbor-core/src/parser_v2.rs:170-200

2. The Two-Pass Builder

The GraphBuilder coordinates the insertion of nodes into the ArborGraph. This is handled in two distinct passes to ensure all potential edge targets are indexed before relationships are resolved.

• Pass 1: Node Addition: Nodes are added to the graph and registered in the SymbolTable. The table maps FQNs to internal NodeId values.
• Pass 2: Edge Resolution: The builder iterates through the references captured in each node. It attempts to resolve these references to other nodes using exact FQN matches or context-aware suffix matching. Sources: crates/arbor-graph/src/builder.rs:40-100

The diagram above illustrates the sequential flow from raw source code to a fully linked ArborGraph. Sources: crates/arbor-graph/src/builder.rs:40-100, crates/arbor-core/src/parser_v2.rs:90-120

Data Structures

The following table summarizes the primary data structures involved in graph management:

Structure	Purpose	Key Attributes
ArborGraph	Central graph container	graph (DiGraph), id_index, name_index, file_index
CodeNode	Represents a code entity	id, name, kind, file, line_start, references
Edge	Represents a relationship	kind (Calls, Imports, Extends, Implements)
GraphBuilder	Orchestrates construction	symbol_table, graph
SymbolTable	Resolves cross-file symbols	Maps String (FQN) to NodeId

Sources: crates/arbor-graph/src/graph.rs:24-40, crates/arbor-graph/src/builder.rs:17-25, crates/arbor-core/src/parser_v2.rs:25-45

Graph Traversal & Impact Analysis

Once constructed, the graph supports specialized traversal algorithms to analyze code relationships.

Impact Analysis (Blast Radius)

The analyze_impact function performs a bidirectional Breadth-First Search (BFS) from a target node to identify all affected entities. Sources: crates/arbor-graph/src/impact.rs:135-150

• Upstream (Incoming Edges): Identifies nodes that depend on the target (e.g., callers). These nodes are likely to break if the target's interface changes.
• Downstream (Outgoing Edges): Identifies nodes the target depends on (e.g., callees).

The traversal classifies results by ImpactSeverity based on hop distance: Direct (1 hop), Transitive (2-3 hops), and Distant (4+ hops). Sources: crates/arbor-graph/src/impact.rs:25-45

Pathfinding

The system utilizes the A* algorithm to find the shortest path between two nodes. This is particularly useful for tracing logic flows between distant modules.
Sources: crates/arbor-graph/src/graph.rs:225-240

pub fn find_path(&self, from: NodeId, to: NodeId) -> Option<Vec<&CodeNode>> {
    let path_indices = petgraph::algo::astar(
        &self.graph,
        from,
        |finish| finish == to,
        |_| 1, // weight of 1
        |_| 0, // heuristic
    )?;
    // ... maps indices back to weights
}

Sources: crates/arbor-graph/src/graph.rs:226-233

Key Functions for Traversal

Function	File	Description
get_callers	graph.rs	Returns immediate incoming nodes connected via Calls edges.
get_callees	graph.rs	Returns immediate outgoing nodes connected via Calls edges.
get_dependents	graph.rs	Recursively finds all incoming nodes up to a specified max_depth.
analyze_impact	impact.rs	Returns a comprehensive ImpactAnalysis struct containing bidirectional impact data.
search	graph.rs	Performs fast substring queries using a specialized SearchIndex.

Sources: crates/arbor-graph/src/graph.rs:115-150, crates/arbor-graph/src/impact.rs:135-140

Conclusion

The Graph Construction & Traversal system provides the deterministic engine required for semantic code analysis. By combining precise Tree-sitter parsing with robust graph theory implementations, Arbor enables developers and AI agents to move beyond simple text-based searching into structural understanding of complex codebases. Sources: crates/arbor-graph/src/lib.rs:1-10, crates/arbor-graph/src/impact.rs:1-10