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

class method

TSort.strongly_connected_components

strongly_connected_components(each_node, each_child)

# File tmp/rubies/ruby-3.2.0/lib/tsort.rb, line 280
def self.strongly_connected_components(each_node, each_child)
  each_strongly_connected_component(each_node, each_child).to_a
end

Returns strongly connected components as an array of arrays of nodes. The array is sorted from children to parents. Each elements of the array represents a strongly connected component.

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) }
p TSort.strongly_connected_components(each_node, each_child)
#=> [[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) }
p TSort.strongly_connected_components(each_node, each_child)
#=> [[4], [2, 3], [1]]

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

‹ prev.each_strongly_connected_component_from next ›.tsort