# How Graph Traversal (BFS/DFS) Works with Token Budgets in Code Review Graph

> Learn how graph traversal BFS DFS manages token budgets in code review graphs. Discover how to stay within LLM context windows effectively.

- Repository: [Tirth Kanani/code-review-graph](https://github.com/tirth8205/code-review-graph)
- Tags: deep-dive
- Published: 2026-07-25

---

**The code-review-graph repository implements BFS and DFS traversal on code dependency graphs with a dual-constraint system that halts expansion when either the maximum depth is reached or the accumulated token estimate exceeds the user-defined budget, ensuring results fit within LLM context windows.**

The `tirth8205/code-review-graph` repository provides intelligent code review capabilities by analyzing dependency graphs to surface impacted code. Its traversal algorithms uniquely incorporate **token budgets** alongside traditional depth limits to prevent exceeding language model context windows while exploring code relationships.

## Understanding Token-Constrained Graph Traversal

The implementation operates on a dual-constraint model that balances logical exploration depth against practical LLM limitations.

**Depth Limit** acts as a traditional graph traversal boundary, capping the number of hops from seed nodes. In the VS Code extension, this is controlled via a depth slider that sets `depthLimit` (where `0` indicates unlimited depth) and drives the expansion loop `for (let d = 0; d < depthLimit; d++)` in [`code-review-graph-vscode/src/webview/graph.ts`](https://github.com/tirth8205/code-review-graph/blob/main/code-review-graph-vscode/src/webview/graph.ts) at lines 136-300.

**Token Budget** provides a hard ceiling on total output size. The CLI tool `traverse_graph_tool` accepts a `--token_budget` argument (defaulting to `2000`) and terminates expansion once the accumulated token estimate exceeds this threshold, as implemented in [`code_review_graph/main.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/main.py) at lines 899-913.

## Core Traversal Mechanics

### Seed Selection

Traversal begins by identifying **seed nodes** that match user-provided identifiers such as fully-qualified symbol names. In the SQLite backend ([`code-review-graph-vscode/src/backend/sqlite.ts`](https://github.com/tirth8205/code-review-graph/blob/main/code-review-graph-vscode/src/backend/sqlite.ts) lines 44-49), seeds are collected by iterating over all nodes belonging to changed files, establishing the starting frontier for expansion.

### BFS vs. DFS Expansion

The repository supports both breadth-first and depth-first strategies through the same underlying edge exploration logic.

**BFS** (used for impact-radius queries) explores outward through **forward edges** (where the node is the source) and **backward edges** (where the node is the target). The implementation maintains a `frontier` set, visits each node, adds unvisited neighbors to a `nextFrontier`, and increments a depth counter until the frontier empties or the maximum depth is reached ([`code-review-graph-vscode/src/backend/sqlite.ts`](https://github.com/tirth8205/code-review-graph/blob/main/code-review-graph-vscode/src/backend/sqlite.ts) lines 57-80).

**DFS** follows the identical edge set but substitutes the frontier queue with a stack (or recursion), altering only the visitation order while maintaining the same constraint checks. The Python CLI offers a `--dfs` flag that swaps expansion strategies without modifying the token-budget enforcement logic.

### Token-Budget Enforcement

After each expansion step, the traversal estimates token consumption using `approx_tokens = sum(len(node.source) for node in visited_nodes)`, treating source character count as a token proxy. If `approx_tokens > token_budget`, the algorithm halts immediately, returning the nodes collected up to that point. This guard guarantees that result sets remain within LLM-prompt size limits regardless of graph density.

### Result Assembly

Upon stopping—whether by depth limit, token budget, or frontier exhaustion—the traversal constructs an `ImpactRadius` result object containing:

- `changedNodes`: The original seed nodes
- `impactedNodes`: Newly discovered nodes within constraints
- `impactedFiles`: Distinct file paths of impacted nodes
- `edges`: All edges connecting involved nodes

Both the TypeScript backend and Python CLI return this consistent structure, enabling uniform API consumption across the VS Code UI and command-line interfaces.

## Implementation Deep Dive

The traversal logic spans multiple components:

- **[`code_review_graph/main.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/main.py)**: Defines the `traverse_graph_tool` CLI entry point, parsing `--depth` and `--token_budget` arguments (lines 899-913)
- **[`code_review_graph/graph.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/graph.py)**: Implements low-level graph data structures and traversal helpers
- **[`code-review-graph-vscode/src/backend/sqlite.ts`](https://github.com/tirth8205/code-review-graph/blob/main/code-review-graph-vscode/src/backend/sqlite.ts)**: Executes SQLite-backed BFS impact-radius queries using frontier-based expansion (lines 57-80)
- **[`code-review-graph-vscode/src/webview/graph.ts`](https://github.com/tirth8205/code-review-graph/blob/main/code-review-graph-vscode/src/webview/graph.ts)**: Handles UI-side depth slider interactions and BFS loop coordination (lines 136-300)

## Practical Usage Examples

Execute a BFS traversal with a 1500-token budget:

```bash
crg traverse_graph \
  --node "MyProject.services.UserService" \
  --depth 3 \
  --token_budget 1500

```

Execute a DFS traversal with stricter constraints:

```bash
crg traverse_graph \
  --node "utils.calculateScore" \
  --depth 2 \
  --dfs \
  --token_budget 1000

```

Programmatic usage via the Python API:

```python
from code_review_graph.main import traverse_graph_tool

# BFS up to depth 2, stopping when ~2000 tokens are collected

result = traverse_graph_tool(
    node="my_pkg.module.ClassName",
    depth=2,
    token_budget=2000,
    dfs=False,
)

print("Impacted files:", result.impactedFiles)

```

VS Code webview interaction:

```javascript
// The UI automatically updates depthLimit via the slider.
// When the user clicks "Expand", the front-end sends the current depth
// and token budget to the backend, which runs the same BFS logic.
graph.expandDepth();   // increments depthLimit, then fetches new nodes

```

## Summary

- **Dual constraints**: The system respects both `depthLimit` (hop count) and `token_budget` (content size) to prevent LLM context overflow
- **Algorithm parity**: Both BFS and DFS implementations use identical edge exploration and token-checking logic, differing only in visitation order
- **Early termination**: Token budgets are evaluated after each expansion wave, ensuring immediate halt when limits are exceeded
- **Consistent API**: The `ImpactRadius` result structure provides uniform output across CLI, Python API, and VS Code extension
- **Source-based estimation**: Token counts are approximated via source string length, providing a fast, deterministic proxy for actual tokenization

## Frequently Asked Questions

### What happens when the token budget is exceeded during traversal?

The traversal halts immediately upon detecting that `approx_tokens` exceeds the specified budget, returning all nodes discovered up to that point. This early-exit mechanism occurs in [`code_review_graph/main.py`](https://github.com/tirth8205/code-review-graph/blob/main/code_review_graph/main.py) after each frontier expansion, ensuring the result set never exceeds LLM context windows.

### How does the token estimation calculate token count?

The implementation uses a character-length proxy: `sum(len(node.source) for node in visited_nodes)`. This approximation treats each character as roughly one token, providing a fast, deterministic estimate without requiring external tokenization libraries.

### Can I use DFS instead of BFS in the VS Code extension?

The VS Code webview currently implements BFS exclusively for its impact-radius visualization. However, the underlying backend supports both algorithms, and the CLI tool offers the `--dfs` flag to switch strategies while maintaining identical token-budget enforcement.

### What is the default token budget if not specified?

The CLI tool defaults to `2000` tokens when the `--token_budget` argument is omitted. The VS Code extension manages budgets through its UI controls, typically defaulting to values that fit within standard model context windows (approximately 4K tokens).