How to find connected components in graph with Ruby

Question

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.

Answer 1

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]]