MCPcopy Create free account
hub / github.com/Effect-TS/effect / stronglyConnectedComponents

Function stronglyConnectedComponents

packages/effect/src/Graph.ts:3862–3958  ·  view source on GitHub ↗
(
  graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">
)

Source from the content-addressed store, hash-verified

3860 * @since 3.18.0
3861 */
3862export 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

Callers

nothing calls this directly

Calls 7

graphImplFunction · 0.85
getDirectedNeighborsFunction · 0.85
pushMethod · 0.80
clearMethod · 0.80
addMethod · 0.65
getMethod · 0.65
hasMethod · 0.45

Tested by

no test coverage detected