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

Function connectedComponents

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

Source from the content-addressed store, hash-verified

3797 * @since 3.18.0
3798 */
3799export const connectedComponents = <N, E>(
3800 graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected">
3801): Array<Array<NodeIndex>> => {
3802 const impl = graphImpl(graph)
3803 const visited = new Set<NodeIndex>()
3804 const components: Array<Array<NodeIndex>> = []
3805 for (const startNode of impl.nodes.keys()) {
3806 if (!visited.has(startNode)) {
3807 // DFS to find all nodes in this component
3808 const component: Array<NodeIndex> = []
3809 const stack: Array<NodeIndex> = [startNode]
3810
3811 while (stack.length > 0) {
3812 const current = stack.pop()!
3813 if (!visited.has(current)) {
3814 visited.add(current)
3815 component.push(current)
3816
3817 // Add all unvisited neighbors to stack
3818 const nodeNeighbors = getUndirectedNeighbors(graph, current)
3819 for (const neighbor of nodeNeighbors) {
3820 if (!visited.has(neighbor)) {
3821 stack.push(neighbor)
3822 }
3823 }
3824 }
3825 }
3826
3827 components.push(component)
3828 }
3829 }
3830
3831 return components
3832}
3833
3834/**
3835 * Finds strongly connected components in a directed graph using Kosaraju's algorithm.

Callers

nothing calls this directly

Calls 5

graphImplFunction · 0.85
getUndirectedNeighborsFunction · 0.85
pushMethod · 0.80
addMethod · 0.65
hasMethod · 0.45

Tested by

no test coverage detected