Method traverseBFS

src/graph/traversal.ts:48–145

* Traverse the graph using breadth-first search * * @param startId - Starting node ID * @param options - Traversal options * @returns Subgraph containing traversed nodes and edges

(startId: string, options: TraversalOptions = {})

   * @returns Subgraph containing traversed nodes and edges
   */
  traverseBFS(startId: string, options: TraversalOptions = {}): Subgraph {
    const opts = { ...DEFAULT_OPTIONS, ...options };
    const startNode = this.queries.getNodeById(startId);

    if (!startNode) {
      return { nodes: new Map(), edges: [], roots: [] };
    }

    const nodes = new Map<string, Node>();
    const edges: Edge[] = [];
    const visited = new Set<string>();
    // Enqueue-once guard, tracked separately from `visited` (which is only set
    // on dequeue). Guarding the enqueue on `visited` alone let a target
    // reachable via two edges get queued twice; the second dequeue then hit
    // `visited.has → continue` and its edge was never recorded, so parallel
    // edges (A calls AND references B, or two `calls` on different lines — edges
    // are unique on source+target+kind+line+col) went missing from the result
    // (#1090). `enqueued` makes each node queued exactly once.
    const enqueued = new Set<string>([startNode.id]);
    // Edge-identity dedup so a `direction:'both'` scan — which encounters A→B
    // from both endpoints — records each edge once.
    const seenEdges = new Set<string>();
    const edgeKey = (e: Edge) =>
      `${e.source}|${e.target}|${e.kind}|${e.line ?? -1}|${e.column ?? -1}`;
    const queue: TraversalStep[] = [{ node: startNode, edge: null, depth: 0 }];

    if (opts.includeStart) {
      nodes.set(startNode.id, startNode);
    }

    while (queue.length > 0 && nodes.size < opts.limit) {
      const step = queue.shift()!;
      const { node, depth } = step;

      if (visited.has(node.id)) {
        continue;
      }
      visited.add(node.id);

      // Check depth limit
      if (depth >= opts.maxDepth) {
        continue;
      }

      // Get adjacent edges, prioritizing structural edges (contains, calls)
      // over reference edges so BFS discovers internal structure before
      // fanning out to external references (e.g., component usages in templates).
      const adjacentEdges = this.getAdjacentEdges(node.id, opts.direction, opts.edgeKinds);
      adjacentEdges.sort((a, b) => {
        const priority = (e: Edge) => e.kind === 'contains' ? 0 : e.kind === 'calls' ? 1 : 2;
        return priority(a) - priority(b);
      });

      // Batch-fetch neighbors we might newly enqueue in one query (was N+1 per
      // BFS step). Already-queued/visited neighbors are already in `nodes`, so
      // they don't need re-fetching to record an edge back to them.
      const wantIds = adjacentEdges
        .map((e) => (e.source === node.id ? e.target : e.source))