| 3860 | * @since 3.18.0 |
| 3861 | */ |
| 3862 | export const stronglyConnectedComponents = <N, E>( |
| 3863 | graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed"> |
| 3864 | ): Array<Array<NodeIndex>> => { |
| 3865 | if ((graph as Graph<N, E, Kind> | MutableGraph<N, E, Kind>).type === "undirected") { |
| 3866 | throw new GraphError({ message: "Cannot find strongly connected components of undirected graph" }) |
| 3867 | } |
| 3868 | |
| 3869 | const impl = graphImpl(graph) |
| 3870 | const visited = new Set<NodeIndex>() |
| 3871 | const finishOrder: Array<NodeIndex> = [] |
| 3872 | // Iterate directly over node keys |
| 3873 | |
| 3874 | // Step 1: Stack-safe DFS on original graph to get finish times |
| 3875 | // Stack entry: [node, neighbors, neighborIndex, isFirstVisit] |
| 3876 | type DfsStackEntry = [NodeIndex, Array<NodeIndex>, number, boolean] |
| 3877 | |
| 3878 | for (const startNode of impl.nodes.keys()) { |
| 3879 | if (visited.has(startNode)) { |
| 3880 | continue |
| 3881 | } |
| 3882 | |
| 3883 | const stack: Array<DfsStackEntry> = [[startNode, [], 0, true]] |
| 3884 | |
| 3885 | while (stack.length > 0) { |
| 3886 | const [node, nodeNeighbors, neighborIndex, isFirstVisit] = stack[stack.length - 1] |
| 3887 | |
| 3888 | if (isFirstVisit) { |
| 3889 | if (visited.has(node)) { |
| 3890 | stack.pop() |
| 3891 | continue |
| 3892 | } |
| 3893 | |
| 3894 | visited.add(node) |
| 3895 | const nodeNeighborsList = getDirectedNeighbors(graph, node, "outgoing") |
| 3896 | stack[stack.length - 1] = [node, nodeNeighborsList, 0, false] |
| 3897 | continue |
| 3898 | } |
| 3899 | |
| 3900 | // Process next neighbor |
| 3901 | if (neighborIndex < nodeNeighbors.length) { |
| 3902 | const neighbor = nodeNeighbors[neighborIndex] |
| 3903 | stack[stack.length - 1] = [node, nodeNeighbors, neighborIndex + 1, false] |
| 3904 | |
| 3905 | if (!visited.has(neighbor)) { |
| 3906 | stack.push([neighbor, [], 0, true]) |
| 3907 | } |
| 3908 | } else { |
| 3909 | // Done with this node - add to finish order (post-order) |
| 3910 | finishOrder.push(node) |
| 3911 | stack.pop() |
| 3912 | } |
| 3913 | } |
| 3914 | } |
| 3915 | |
| 3916 | // Step 2: Stack-safe DFS on transpose graph in reverse finish order |
| 3917 | visited.clear() |
| 3918 | const sccs: Array<Array<NodeIndex>> = [] |
| 3919 | |