Pre-build adjacency list for relation graph traversal

[devin-ai-integration]

Objective

Pre-build an adjacency list (Map<string, RelationEdge[]>) during compilation or at query-engine initialization so that buildFrontier() uses O(1) per-node lookups instead of scanning the full relationGraph array.

Current behavior: buildFrontier() iterates over the entire relationGraph for every selected node — O(selected_nodes × total_edges).

Proposed fix:

const adjacency = new Map<string, RelationEdge[]>();
for (const edge of snapshot.relationGraph) {
  if (!adjacency.has(edge.source)) adjacency.set(edge.source, []);
  adjacency.get(edge.source)!.push(edge);
  if (!adjacency.has(edge.target)) adjacency.set(edge.target, []);
  adjacency.get(edge.target)!.push(edge);
}

Then buildFrontier() calls adjacency.get(nodeId) instead of scanning.

"Done" looks like: buildFrontier() uses a pre-built adjacency list; same results, faster execution; no API changes.

Kind

refactor

Affected area

src/runtime/ (compiler & query engine)

Acceptance criteria

• Adjacency list built once from snapshot.relationGraph
• buildFrontier() uses map lookup instead of full array scan
• No behavioral change — identical results
• All existing tests pass

Agent-delegable?

yes

Additional context

• src/runtime/query-engine.ts: buildFrontier() method (line ~865), full scan at line ~912
• src/runtime/types.ts: RelationEdge type
• Low complexity, self-contained change with no API surface changes

Measurable impact

Metric	Before	After (target)	How to measure
buildFrontier() uses adjacency map lookup	No (full array scan)	Yes (O(1) per-node)	grep -c 'adjacency.get' src/runtime/query-engine.ts (before: 0, after: ≥1)
Full relationGraph iteration in buildFrontier()	1 (line ~912: for...of snapshot.relationGraph)	0	grep -c 'for.*of.*\.relationGraph' src/runtime/query-engine.ts
Existing test pass rate	all pass	all pass (no regressions)	bun run test
Behavioral change	N/A	none — identical query results	bun run cli -- query --question "What is U.BoundedContext?" --mode verbose (diff output before/after)

[venikman]

Take on the premise

Skeptical. The problem is asserted without measurement.

The proposal claims buildFrontier() is O(selected_nodes × total_edges). Mathematically true. But:

• Compiled nodes: ~200
• Total edges in relationGraph: probably a few hundred to ~1000
• Typical selected_nodes at frontier expansion time: single digits

That's at worst a few thousand simple iterations per query — well under a millisecond on any modern runtime. No one has shown this is a bottleneck.

What's missing from this issue:

1. A benchmark. "buildFrontier() is currently P99 XX ms, target P99 YY ms." Without a before/after number, the "perf" framing is speculative.
2. A user-facing signal. Is any MCP tool call perceptibly slow? Is there a specific query that times out or stalls? If the answer is "no, it just looks O(N×E)," this is a micro-optimization dressed as a problem statement.

The change itself is fine as code hygiene — iterating an index map is clearer than filtering an array. Nothing wrong with landing it. But:

• Don't claim "perf" without numbers
• Don't spend review attention on a non-problem when issues Split query-engine.ts into retrieval stages #2, Add stage-local contract tests for compiler and query pipelines #6, Add public browse/search MCP discovery layer for Codex-facing workflows #15 deliver user-visible value

PR #26 already partially lands this (uses existing neighborEdges for the per-node lookup). That's the clean 90% of the win, and it was essentially free. The full Map<string, RelationEdge[]> adjacency list from this issue's proposal is the other 10% — if you're going to land it, measure first.

Problem is marginal; land the refactor if it's cheap, don't prioritize it.

[devin-ai-integration]

Merger plan update

Status: PR #26 — deprioritized per owner feedback

Incorporating venikman's feedback from this issue:

1. "Skeptical. Problem asserted without measurement." — Agreed. No benchmark shows buildFrontier() is a bottleneck. With ~200 nodes and ~1000 edges, the per-query cost is sub-millisecond.

2. "PR perf: use precomputed neighborEdges in query-engine loops #26 already partially lands this" — The existing neighborEdges per-node lookup is the clean 90% of the win. The full Map<string, RelationEdge[]> adjacency list is the other 10%.

3. "Land the refactor if it's cheap, don't prioritize it" — Agreed.

Merge order: PR #26 is last in the queue. Will only land if time permits after all higher-value PRs are merged.