( graph: Graph<N, E, "undirected"> | MutableGraph<N, E, "undirected"> )
| 3797 | * @since 3.18.0 |
| 3798 | */ |
| 3799 | export 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. |
nothing calls this directly
no test coverage detected