findPath BFS lacks the enqueue-once guard traverseBFS got in #1090: a fan-in hub re-enqueues the same target O(k²) times (with path-array copies) — perf/memory, not wrong results

[inth3shadows]

Summary

GraphTraverser.findPath's BFS lacks the enqueue-once guard that its sibling traverseBFS got in #1090. It gates queue pushes on visited only (which is set at dequeue), so the same target can be pushed many times from different predecessors in one BFS layer before any is dequeued. Unlike #1090, the result stays correct here (shortest path; duplicates are skipped at dequeue), so this is a performance / memory issue, not incomplete output — but on a fan-in-dense graph it's a latent quadratic blowup, made worse because each push copies a full path array.

Root cause

// src/graph/traversal.ts (findPath) — only `visited`, no `enqueued`
const visited = new Set<string>();                       // set on dequeue only
...
for (const edge of outgoingEdges) {
  if (!visited.has(edge.target)) {                       // <- no enqueue-once guard
    const nextNode = nextNodes.get(edge.target);
    if (nextNode) queue.push({ nodeId: edge.target, path: [...path, { node: nextNode, edge }] });
  }
}

Compare traverseBFS in the same file (the #1090 fix):

const enqueued = new Set<string>([startNode.id]);        // enqueue-once, separate from visited
...
.filter((id) => !visited.has(id) && !enqueued.has(id));
...
if (!visited.has(nextNodeId) && !enqueued.has(nextNodeId)) { ...; enqueued.add(nextNodeId); }

With a layer of k nodes all pointing into the same k targets (a shared-helper / fan-in hub, common in real call graphs), the queue receives up to k² entries for that transition instead of k. Each duplicate is only cheaply dropped at dequeue (visited.has → continue), but each also carried a copied [...path] array, so wasted work + peak memory scale with edge count rather than node count — the kind of thing that makes a path query time out (look "wrong") rather than return wrong.

Suggested direction

Mirror traverseBFS: add an enqueued Set seeded with fromId, and gate the push on !visited.has(edge.target) && !enqueued.has(edge.target), adding to enqueued at push time. Shortest-path output is unchanged; the redundant enqueues (and their path copies) go away.

Environment

main @ 5955d04, package 1.4.1. Verified by reading the current source — the asymmetry with traverseBFS is direct.

[inth3shadows]

Suggested label for triage (I lack permission to apply it myself): bug.