traverseBFS: same target enqueued via two edges; second dequeue skips edge, producing incomplete edge set

[inth3shadows]

File: src/graph/traversal.ts
Lines: 101 (inner loop visited check), 110–111 (nodes.set/queue.push), 69–77 (dequeue visited check and edge push)

Defect: The inner for loop in traverseBFS (L99–112) guards on visited.has(nextNodeId) (L101) before enqueuing. visited is only updated at L72 — inside the outer while body, after dequeuing. This means a node reachable from the current node via two different edges (e.g., two calls edges or a calls + references edge to the same target) is enqueued twice. When the queue is later drained: the first dequeue marks the node visited and pushes edge1 into edges; the second dequeue hits visited.has → continue, dropping edge2. The resulting Subgraph.edges array is incomplete.

Failure trace:

• Node A has two edges to B: e1 (A→B, kind:calls) and e2 (A→B, kind:references).
• Processing A: adjacentEdges = [e1, e2].
  • e1: !visited.has("B") = true → nodes.set(B), queue.push({B, e1}).
  • e2: !visited.has("B") = true (B still not in visited) → nodes.set(B) (no-op), queue.push({B, e2}).
  • Queue: [{B,e1}, {B,e2}].
• Dequeue {B,e1}: !visited.has("B") → visited.add("B"), edges.push(e1).
• Dequeue {B,e2}: visited.has("B") → continue. e2 never pushed to edges.
• Final edges is missing e2 — a real A→B relationship is invisible to callers.

Expected fix:
Track which node IDs have already been enqueued (separately from visited) and skip re-enqueueing the same node:

const queued = new Set<string>();
queued.add(startNode.id);
// …
for (const adjEdge of adjacentEdges) {
  const nextNodeId = …;
  if (visited.has(nextNodeId) || queued.has(nextNodeId)) continue;
  …
  queued.add(nextNodeId);
  nodes.set(nextNode.id, nextNode);
  queue.push({ node: nextNode, edge: adjEdge, depth: depth + 1 });
}

This ensures each node is enqueued exactly once (preserving BFS semantics) while still recording the first edge to it. If multi-edge completeness is required, edges should be collected separately from the queue and all edges to a node merged before or after traversal.

[inth3shadows]

---

Verification & metadata (added after filing)

Anchor: Introduced in cc6e7a5c (2026-01-18, the original graph-traversal implementation); present in every release through v1.1.6 and still on main @ 712a406. Not a recent regression.

These 5 issues are really 3 root defects:

• Depth guard returns before visited.add → getCallersRecursive/getCalleesRecursive: depth guard returns before visited.add, causing duplicate results #1086, getImpactRecursive: inconsistent visited vs nodes gate causes incoming edges to be silently dropped #1089
• Dedup gate also gates edge collection (an edge is dropped when its endpoint was already collected) → getImpactRecursive: inconsistent visited vs nodes gate causes incoming edges to be silently dropped #1089, traverseBFS: same target enqueued via two edges; second dequeue skips edge, producing incomplete edge set #1090
• limit checked once per stack frame, not per node added → traverseBFS: inner neighbor loop adds nodes without limit check, overshooting opts.limit #1087, dfsRecursive: nodes.set called before limit check in inner loop, overshooting opts.limit for all siblings #1088

Regression coverage belongs in __tests__/graph.test.ts.

Reproduced against the compiled dist/ build with the real GraphTraverser and a mock QueryBuilder (only getNodeById/getNodesByIds/get{In,Out}goingEdges).

A→B exists via both calls and references (two distinct edges):

traverseBFS('A', {})
// Observed: edges array keeps only 1 of the 2 A→B edges

The target is enqueued twice (visited is set only on dequeue); the second dequeue hits visited.has → continue and its edge is never pushed. Line 101's current form is from the batch-fetch refactor (b13f2f1b, 2026-05-22), but the edge-drop predates it (cc6e7a5c).

[colbymchenry]

Fixed in 43a6fa6 (#1106) — thanks, your trace was spot on.

traverseBFS now collects edges during the adjacency scan (deduped on full edge identity source|target|kind|line|column) with a separate enqueued set so each node is queued exactly once. All parallel edges to the same target are preserved — A calls B + A references B, or two calls on different lines — not just the highest-priority one. As you noted, the queued-set approach alone wouldn't have restored the dropped edge, so the fix decouples edge collection from enqueueing (your footnote's approach).

This backs the traverse()/buildContext() library APIs rather than the MCP explore path, but the returned subgraph is now edge-complete. Regression test added in graph.test.ts. Ships in the next release.