fix(core): use Set for O(1) visited node lookup in hasPath (#33754)

adwait1290 · web-flow · commit 300493ec0b89 · 2025-12-08T14:03:23.000-05:00
## Current Behavior The `hasPath` function in `graph.ts` uses an array with `indexOf()` for tracking visited nodes during recursive graph traversal: ```typescript function hasPath(graph, target, node, visited: string[]) { for (let d of graph.dependencies[node] || []) { if (visited.indexOf(d.target) > -1) continue; // O(n) lookup visited.push(d.target); // recursive call... } } ``` This results in O(n) lookups per node visited, making worst-case traversal O(n²). ## Expected Behavior Use `Set` for O(1) visited node tracking: ```typescript function hasPath(graph, target, node, visited: Set<string>) { for (const d of graph.dependencies[node] || []) { if (visited.has(d.target)) continue; // O(1) lookup visited.add(d.target); // recursive call... } } ``` ## Performance Impact ``` Before (Array + indexOf): After (Set + has): ┌─────────────────────────┐ ┌─────────────────────────┐ │ hasPath() called │ │ hasPath() called │ └───────────┬─────────────┘ └───────────┬─────────────┘ │ │ ▼ ▼ ┌─────────────────────────┐ ┌─────────────────────────┐ │ visited.indexOf(target) │ │ visited.has(target) │ │ O(n) lookup │ │ O(1) lookup │ └───────────┬─────────────┘ └───────────┬─────────────┘ │ │ ▼ ▼ ┌─────────────────────────┐ ┌─────────────────────────┐ │ visited.push(target) │ │ visited.add(target) │ │ O(1) │ │ O(1) │ └───────────┬─────────────┘ └───────────┬─────────────┘ │ │ ▼ ▼ Complexity: O(n²) Complexity: O(n) for full traversal for full traversal ``` **Example with 500 nodes:** - Before: 500 nodes × avg 250 indexOf lookups = ~125,000 comparisons - After: 500 nodes × 1 Set lookup each = 500 operations ## Why Accept This PR 1. **Zero risk**: Same semantics, just faster data structure 2. **Standard pattern**: Set is the idiomatic choice for visited tracking in graph algorithms 3. **Measurable impact**: Graph filtering with `--focus` flag will be significantly faster on large monorepos ## Related Issue(s) Contributes to #32265 ## Merge Dependencies This PR has no dependencies and can be merged independently. ---
diff --git a/packages/nx/src/command-line/graph/graph.ts b/packages/nx/src/command-line/graph/graph.ts
@@ -183,13 +183,13 @@ function hasPath(
   graph: ProjectGraph,
   target: string,
   node: string,
-  visited: string[]
+  visited: Set<string>
 ) {
   if (target === node) return true;
 
-  for (let d of graph.dependencies[node] || []) {
-    if (visited.indexOf(d.target) > -1) continue;
-    visited.push(d.target);
+  for (const d of graph.dependencies[node] || []) {
+    if (visited.has(d.target)) continue;
+    visited.add(d.target);
     if (hasPath(graph, target, d.target, visited)) return true;
   }
   return false;
@@ -210,7 +210,8 @@ function filterGraph(
     filteredProjectNames = new Set<string>();
     projectNames.forEach((p) => {
       const isInPath =
-        hasPath(graph, p, focus, []) || hasPath(graph, focus, p, []);
+        hasPath(graph, p, focus, new Set()) ||
+        hasPath(graph, focus, p, new Set());
 
       if (isInPath) {
         filteredProjectNames.add(p);
