method

each_strongly_connected_component_from

v2_4_6 - Show latest stable - Class: TSort

each_strongly_connected_component_from(node, each_child, id_map={}, stack=[])

public

Iterates over strongly connected components in a graph. The graph is represented by node and each_child.

node is the first node. each_child should have call method which takes a node argument and yields for each child node.

Return value is unspecified.

#TSort.each_strongly_connected_component_from is a class method and it doesn’t need a class to represent a graph which includes TSort.

graph = {1=>[2], 2=>[3, 4], 3=>[2], 4=>[]}
each_child = lambda {|n, &b| graph[n].each(&b) }
TSort.each_strongly_connected_component_from(1, each_child) {|scc|
  p scc
}
#=> [4]
#   [2, 3]
#   [1]

# File lib/tsort.rb, line 408
  def TSort.each_strongly_connected_component_from(node, each_child, id_map={}, stack=[]) # :yields: nodes
    return to_enum(__method__, node, each_child, id_map, stack) unless block_given?

    minimum_id = node_id = id_map[node] = id_map.size
    stack_length = stack.length
    stack << node

    each_child.call(node) {|child|
      if id_map.include? child
        child_id = id_map[child]
        minimum_id = child_id if child_id && child_id < minimum_id
      else
        sub_minimum_id =
          TSort.each_strongly_connected_component_from(child, each_child, id_map, stack) {|c|
            yield c
          }
        minimum_id = sub_minimum_id if sub_minimum_id < minimum_id
      end
    }

    if node_id == minimum_id
      component = stack.slice!(stack_length .. -1)
      component.each {|n| id_map[n] = nil}
      yield component
    end

    minimum_id
  end

each_strongly_connected_component_from

Related methods