MCPcopy Create free account
hub / github.com/colbymchenry/codegraph / dfsRecursive

Method dfsRecursive

src/graph/traversal.ts:211–259  ·  view source on GitHub ↗

* Recursive DFS helper

(
    node: Node,
    depth: number,
    opts: Required<TraversalOptions>,
    nodes: Map<string, Node>,
    edges: Edge[],
    visited: Set<string>
  )

Source from the content-addressed store, hash-verified

209 * Recursive DFS helper
210 */
211 private dfsRecursive(
212 node: Node,
213 depth: number,
214 opts: Required<TraversalOptions>,
215 nodes: Map<string, Node>,
216 edges: Edge[],
217 visited: Set<string>
218 ): void {
219 if (visited.has(node.id) || nodes.size >= opts.limit || depth >= opts.maxDepth) {
220 return;
221 }
222
223 visited.add(node.id);
224
225 // Get adjacent edges
226 const adjacentEdges = this.getAdjacentEdges(node.id, opts.direction, opts.edgeKinds);
227
228 // Batch-fetch unvisited neighbors (was N+1 per DFS step).
229 const wantIds = adjacentEdges
230 .map((e) => (e.source === node.id ? e.target : e.source))
231 .filter((id) => !visited.has(id));
232 const neighborNodes = wantIds.length > 0 ? this.queries.getNodesByIds(wantIds) : new Map();
233
234 for (const edge of adjacentEdges) {
235 // Cap per-add, not just at the top of each frame: the top-of-function
236 // guard only stops the next recursion, so without this every sibling of
237 // the first over-budget child still got inserted, overshooting
238 // `opts.limit` by a node's full fan-out (#1088).
239 if (nodes.size >= opts.limit) break;
240
241 const nextNodeId = edge.source === node.id ? edge.target : edge.source;
242 if (visited.has(nextNodeId)) continue;
243
244 const nextNode = neighborNodes.get(nextNodeId);
245 if (!nextNode) continue;
246
247 // Apply node kind filter
248 if (opts.nodeKinds && opts.nodeKinds.length > 0 && !opts.nodeKinds.includes(nextNode.kind)) {
249 continue;
250 }
251
252 // Add node and edge to result
253 nodes.set(nextNode.id, nextNode);
254 edges.push(edge);
255
256 // Recurse
257 this.dfsRecursive(nextNode, depth + 1, opts, nodes, edges, visited);
258 }
259 }
260
261 /**
262 * Get adjacent edges based on direction

Callers 1

traverseDFSMethod · 0.95

Calls 8

getAdjacentEdgesMethod · 0.95
hasMethod · 0.80
mapMethod · 0.80
pushMethod · 0.80
getMethod · 0.65
addMethod · 0.45
getNodesByIdsMethod · 0.45
setMethod · 0.45

Tested by

no test coverage detected