Graph.connectedComponents — API

Graph.connectedComponentsconsteffect/Graph.ts:2924

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

Finds connected components in an undirected graph. Each component is represented as an array of node indices.

Example (Finding connected components)

import { Graph } from "effect"

const graph = Graph.undirected<string, string>((mutable) => {
  const a = Graph.addNode(mutable, "A")
  const b = Graph.addNode(mutable, "B")
  const c = Graph.addNode(mutable, "C")
  const d = Graph.addNode(mutable, "D")
  Graph.addEdge(mutable, a, b, "edge") // Component 1: A-B
  Graph.addEdge(mutable, c, d, "edge") // Component 2: C-D
})

const components = Graph.connectedComponents(graph)
console.log(components) // [[0, 1], [2, 3]]

algorithms

Source effect/Graph.ts:292433 lines

export const connectedComponents = <N, E>(
  graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">
): Array<Array<NodeIndex>> => {
  const visited = new Set<NodeIndex>()
  const components: Array<Array<NodeIndex>> = []
  for (const startNode of graph.nodes.keys()) {
    if (!visited.has(startNode)) {
      // DFS to find all nodes in this component
      const component: Array<NodeIndex> = []
      const stack: Array<NodeIndex> = [startNode]

      while (stack.length > 0) {
        const current = stack.pop()!
        if (!visited.has(current)) {
          visited.add(current)
          component.push(current)

          // Add all unvisited neighbors to stack
          const nodeNeighbors = getUndirectedNeighbors(graph, current)
          for (const neighbor of nodeNeighbors) {
            if (!visited.has(neighbor)) {
              stack.push(neighbor)
            }
          }
        }
      }

      components.push(component)
    }
  }

  return components
}