(nodes: WFNode[], edges: WFEdge[])
| 56 | // ─── Topological sort (DFS preorder, branch-first) ─────────────────────────── |
| 57 | |
| 58 | function topoSort(nodes: WFNode[], edges: WFEdge[]): WFNode[] { |
| 59 | const nodeMap = new Map(nodes.map((n) => [n.id, n])) |
| 60 | const adj = new Map(nodes.map((n) => [n.id, [] as string[]])) |
| 61 | const inDeg = new Map(nodes.map((n) => [n.id, 0])) |
| 62 | for (const e of edges) { |
| 63 | if (!nodeMap.has(e.source) || !nodeMap.has(e.target)) continue |
| 64 | adj.get(e.source)!.push(e.target) |
| 65 | inDeg.set(e.target, (inDeg.get(e.target) ?? 0) + 1) |
| 66 | } |
| 67 | |
| 68 | const visited = new Set<string>() |
| 69 | const result: WFNode[] = [] |
| 70 | |
| 71 | const visit = (id: string): void => { |
| 72 | if (visited.has(id)) return |
| 73 | for (const e of edges) { |
| 74 | if (e.target === id && !visited.has(e.source) && nodeMap.has(e.source)) return |
| 75 | } |
| 76 | const node = nodeMap.get(id) |
| 77 | if (!node) return |
| 78 | visited.add(id) |
| 79 | result.push(node) |
| 80 | for (const childId of adj.get(id) ?? []) visit(childId) |
| 81 | } |
| 82 | |
| 83 | for (const node of nodes) if ((inDeg.get(node.id) ?? 0) === 0) visit(node.id) |
| 84 | for (const node of nodes) if (!visited.has(node.id)) visit(node.id) |
| 85 | return result |
| 86 | } |
| 87 | |
| 88 | // ─── Branch identification ──────────────────────────────────────────────────── |
| 89 | // A node belongs to Wait W's branch if its single nearest upstream Wait is W |
no test coverage detected