| 2203 | * @category algorithms |
| 2204 | */ |
| 2205 | export const stronglyConnectedComponents = <N, E, T extends Kind = "directed">( |
| 2206 | graph: Graph<N, E, T> | MutableGraph<N, E, T> |
| 2207 | ): Array<Array<NodeIndex>> => { |
| 2208 | const visited = new Set<NodeIndex>() |
| 2209 | const finishOrder: Array<NodeIndex> = [] |
| 2210 | // Iterate directly over node keys |
| 2211 | |
| 2212 | // Step 1: Stack-safe DFS on original graph to get finish times |
| 2213 | // Stack entry: [node, neighbors, neighborIndex, isFirstVisit] |
| 2214 | type DfsStackEntry = [NodeIndex, Array<NodeIndex>, number, boolean] |
| 2215 | |
| 2216 | for (const startNode of graph.nodes.keys()) { |
| 2217 | if (visited.has(startNode)) { |
| 2218 | continue |
| 2219 | } |
| 2220 | |
| 2221 | const stack: Array<DfsStackEntry> = [[startNode, [], 0, true]] |
| 2222 | |
| 2223 | while (stack.length > 0) { |
| 2224 | const [node, nodeNeighbors, neighborIndex, isFirstVisit] = stack[stack.length - 1] |
| 2225 | |
| 2226 | if (isFirstVisit) { |
| 2227 | if (visited.has(node)) { |
| 2228 | stack.pop() |
| 2229 | continue |
| 2230 | } |
| 2231 | |
| 2232 | visited.add(node) |
| 2233 | const nodeNeighborsList = neighbors(graph, node) |
| 2234 | stack[stack.length - 1] = [node, nodeNeighborsList, 0, false] |
| 2235 | continue |
| 2236 | } |
| 2237 | |
| 2238 | // Process next neighbor |
| 2239 | if (neighborIndex < nodeNeighbors.length) { |
| 2240 | const neighbor = nodeNeighbors[neighborIndex] |
| 2241 | stack[stack.length - 1] = [node, nodeNeighbors, neighborIndex + 1, false] |
| 2242 | |
| 2243 | if (!visited.has(neighbor)) { |
| 2244 | stack.push([neighbor, [], 0, true]) |
| 2245 | } |
| 2246 | } else { |
| 2247 | // Done with this node - add to finish order (post-order) |
| 2248 | finishOrder.push(node) |
| 2249 | stack.pop() |
| 2250 | } |
| 2251 | } |
| 2252 | } |
| 2253 | |
| 2254 | // Step 2: Stack-safe DFS on transpose graph in reverse finish order |
| 2255 | visited.clear() |
| 2256 | const sccs: Array<Array<NodeIndex>> = [] |
| 2257 | |
| 2258 | for (let i = finishOrder.length - 1; i >= 0; i--) { |
| 2259 | const startNode = finishOrder[i] |
| 2260 | if (visited.has(startNode)) { |
| 2261 | continue |
| 2262 | } |