* Detect if there's a cycle in the graph
(nodes: FlowNode[], edges: FlowEdge[])
| 86 | * Detect if there's a cycle in the graph |
| 87 | */ |
| 88 | function detectCycle(nodes: FlowNode[], edges: FlowEdge[]): boolean { |
| 89 | // Build adjacency list |
| 90 | const graph: Record<string, string[]> = {} |
| 91 | nodes.forEach((node) => { |
| 92 | graph[node.id] = [] |
| 93 | }) |
| 94 | edges.forEach((edge) => { |
| 95 | if (graph[edge.source]) { |
| 96 | graph[edge.source].push(edge.target) |
| 97 | } |
| 98 | }) |
| 99 | |
| 100 | // DFS with colors: 0 = white (unvisited), 1 = gray (in progress), 2 = black (done) |
| 101 | const colors: Record<string, number> = {} |
| 102 | nodes.forEach((node) => { |
| 103 | colors[node.id] = 0 |
| 104 | }) |
| 105 | |
| 106 | function dfs(nodeId: string): boolean { |
| 107 | colors[nodeId] = 1 // Mark as in progress |
| 108 | |
| 109 | for (const neighbor of graph[nodeId] || []) { |
| 110 | if (colors[neighbor] === 1) { |
| 111 | // Back edge found - cycle detected |
| 112 | return true |
| 113 | } |
| 114 | if (colors[neighbor] === 0 && dfs(neighbor)) { |
| 115 | return true |
| 116 | } |
| 117 | } |
| 118 | |
| 119 | colors[nodeId] = 2 // Mark as done |
| 120 | return false |
| 121 | } |
| 122 | |
| 123 | // Run DFS from all unvisited nodes |
| 124 | for (const node of nodes) { |
| 125 | if (colors[node.id] === 0 && dfs(node.id)) { |
| 126 | return true |
| 127 | } |
| 128 | } |
| 129 | |
| 130 | return false |
| 131 | } |
| 132 | |
| 133 | /** |
| 134 | * Detect hanging edges where source or target node no longer exists |