End of Life Ruby 3.2 has reached end of life and gets no more fixes. Switch to Ruby 4.0 →

class method

TSort.each_strongly_connected_component

each_strongly_connected_component(each_node, each_child) { |nodes| ... }

# File tmp/rubies/ruby-3.2.0/lib/tsort.rb, line 342
def self.each_strongly_connected_component(each_node, each_child) # :yields: nodes
  return to_enum(__method__, each_node, each_child) unless block_given?

  id_map = {}
  stack = []
  each_node.call {|node|
    unless id_map.include? node
      each_strongly_connected_component_from(node, each_child, id_map, stack) {|c|
        yield c
      }
    end
  }
  nil
end

The iterator version of the TSort.strongly_connected_components method.

The graph is represented by each_node and each_child. each_node should have call method which yields for each node in the graph. each_child should have call method which takes a node argument and yields for each child node.

Example

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

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

See also #each_strongly_connected_component .each_strongly_connected_component_from .strongly_connected_components also in 4.0 · 3.4 · 3.3 · 3.1 · 3.0

next ›.each_strongly_connected_component_from