instance method

TSort#tsort

() -> ::Array[Node]

tsort

# File tmp/rubies/ruby-4.0.0/lib/tsort.rb, line 154
def tsort
  each_node = method(:tsort_each_node)
  each_child = method(:tsort_each_child)
  TSort.tsort(each_node, each_child)
end

Returns a topologically sorted array of nodes. The array is sorted from children to parents, i.e. the first element has no child and the last node has no parent.

If there is a cycle, TSort::Cyclic is raised.

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.tsort #=> [4, 2, 3, 1]

graph = G.new({1=>[2], 2=>[3, 4], 3=>[2], 4=>[]})
p graph.tsort # raises TSort::Cyclic

See also .tsort #strongly_connected_components #tsort_each #each_strongly_connected_component_from also in 3.4 · 3.3 · 3.2 · 3.1 · 3.0

‹ prev#strongly_connected_components next ›#tsort_each