Method: RGL::Graph#each_connected_component

Defined in:
lib/rgl/connected_components.rb

#each_connected_component {|comp| ... } ⇒ Object

Compute the connected components of an undirected graph, using a DFS (Depth-first search)-based approach. A _connected component_ of an undirected graph is a set of vertices that are all reachable from each other.

The function is implemented as an iterator which calls the client with an array of vertices for each component.

It raises an exception if the graph is directed.

Yields:

  • (comp)

Raises:



23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/rgl/connected_components.rb', line 23

def each_connected_component
  raise NotUndirectedError,
        "each_connected_component only works " +
            "for undirected graphs." if directed?

  comp = []
  vis  = DFSVisitor.new(self)
  vis.set_finish_vertex_event_handler { |v| comp << v }

  vis.set_start_vertex_event_handler do |v|
    yield comp unless comp.empty?
    comp = []
  end

  depth_first_search(vis) { |v| }
  yield comp unless comp.empty?
end