How to find connected components in graph with Ruby

algorithm, graph, graph-algorithm, libraries, ruby

Solution

Two things that might help (caveat: I do not know this gem well, and there may be better approaches)

You need to add a require to make the method available: `require 'rgl/connected_components'`

`each_connected_component` assumes an undirected graph, but you can convert a directed graph to an undirected one if necessary

The following code seems to do what you want:

require 'rgl/base'
require 'rgl/adjacency'
require 'rgl/connected_components'

g = RGL::DirectedAdjacencyGraph[1,2, 2,3, 4,5]

components = []

g.to_undirected.each_connected_component { |c| components <<  c }

p components

# => [[3, 2, 1], [5, 4]]

Problem

What is the easiest way to find connected components of graph? Not strongly connected components which can be found with `TSort` module. There is a library `RGL` which has a method in module `RGL::Graph::each_connected_component` but how to build a graph and call this method for this graph? I have created sample graph like ``` g = RGL::DirectedAdjacencyGraph[1,2, 2,3, 4,5] ``` and want to find it's connected components, which are [[1,2,3],[4,5]] but there is no method `each_connected_component` in `g` ``` class RGL::DirectedAdjacencyGraph include RGL::Graph end ``` did not help.

Original source