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

instance method

TSort#strongly_connected_components

strongly_connected_components

# File tmp/rubies/ruby-3.1.3/lib/tsort.rb, line 254
def strongly_connected_components
  each_node = method(:tsort_each_node)
  each_child = method(:tsort_each_child)
  TSort.strongly_connected_components(each_node, each_child)
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.

Example

class G
  include TSort
  def initialize(g)
    @g = g
  end
  def tsort_each_child(n, &b) @g[n].each(&b) end
  def tsort_each_node(&b) @g.each_key(&b) end
end

graph = G.new({1=>[2, 3], 2=>[4], 3=>[2, 4], 4=>[]})
p graph.strongly_connected_components #=> [[4], [2], [3], [1]]

graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]})
p graph.strongly_connected_components #=> [[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.2 · 3.0

‹ prev#each_strongly_connected_component_from next ›#tsort