Graph.stronglyConnectedComponents — API

Graph.stronglyConnectedComponentsconsteffect/Graph.ts:2987

<N, E>(
  graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">
): Array<Array<NodeIndex>>

Finds strongly connected components in a directed graph using Kosaraju's algorithm. Each SCC is represented as an array of node indices.

Gotchas

Throws a GraphError when used with an undirected graph.

Example (Finding strongly connected components)

import { Graph } from "effect"

const graph = Graph.directed<string, string>((mutable) => {
  const a = Graph.addNode(mutable, "A")
  const b = Graph.addNode(mutable, "B")
  const c = Graph.addNode(mutable, "C")
  Graph.addEdge(mutable, a, b, "A->B")
  Graph.addEdge(mutable, b, c, "B->C")
  Graph.addEdge(mutable, c, a, "C->A") // Creates SCC: A-B-C
})

const sccs = Graph.stronglyConnectedComponents(graph)
console.log(sccs) // [[0, 1, 2]]

algorithms

Source effect/Graph.ts:298796 lines

export const stronglyConnectedComponents = <N, E>(
  graph: Graph<N, E, "directed"> | MutableGraph<N, E, "directed">
): Array<Array<NodeIndex>> => {
  if ((graph as Graph<N, E, Kind> | MutableGraph<N, E, Kind>).type === "undirected") {
    throw new GraphError({ message: "Cannot find strongly connected components of undirected graph" })
  }

  const visited = new Set<NodeIndex>()
  const finishOrder: Array<NodeIndex> = []
  // Iterate directly over node keys

  // Step 1: Stack-safe DFS on original graph to get finish times
  // Stack entry: [node, neighbors, neighborIndex, isFirstVisit]
  type DfsStackEntry = [NodeIndex, Array<NodeIndex>, number, boolean]

  for (const startNode of graph.nodes.keys()) {
    if (visited.has(startNode)) {
      continue
    }

    const stack: Array<DfsStackEntry> = [[startNode, [], 0, true]]

    while (stack.length > 0) {
      const [node, nodeNeighbors, neighborIndex, isFirstVisit] = stack[stack.length - 1]

      if (isFirstVisit) {
        if (visited.has(node)) {
          stack.pop()
          continue
        }

        visited.add(node)
        const nodeNeighborsList = getDirectedNeighbors(graph, node, "outgoing")
        stack[stack.length - 1] = [node, nodeNeighborsList, 0, false]
        continue
      }

      // Process next neighbor
      if (neighborIndex < nodeNeighbors.length) {
        const neighbor = nodeNeighbors[neighborIndex]
        stack[stack.length - 1] = [node, nodeNeighbors, neighborIndex + 1, false]

        if (!visited.has(neighbor)) {
          stack.push([neighbor, [], 0, true])
        }
      } else {
        // Done with this node - add to finish order (post-order)
        finishOrder.push(node)
        stack.pop()
      }
    }
  }

  // Step 2: Stack-safe DFS on transpose graph in reverse finish order
  visited.clear()
  const sccs: Array<Array<NodeIndex>> = []

  for (let i = finishOrder.length - 1; i >= 0; i--) {
    const startNode = finishOrder[i]
    if (visited.has(startNode)) {
      continue
    }

    const scc: Array<NodeIndex> = []
    const stack: Array<NodeIndex> = [startNode]

    while (stack.length > 0) {
      const node = stack.pop()!

      if (visited.has(node)) {
        continue
      }

      visited.add(node)
      scc.push(node)

      // Use reverse adjacency (transpose graph)
      const reverseAdjacency = graph.reverseAdjacency.get(node)
      if (reverseAdjacency !== undefined) {
        for (const edgeIndex of reverseAdjacency) {
          const edge = graph.edges.get(edgeIndex)
          if (edge !== undefined) {
            const predecessor = edge.source
            if (!visited.has(predecessor)) {
              stack.push(predecessor)
            }
          }
        }
      }
    }

    sccs.push(scc)
  }

  return sccs
}