TSort.tsort

[T] (::TSort::_EachNode[T] each_node, ::TSort::_EachChild[T] each_child) -> ::Array[T]

[T] (^() { (T) -> void } -> void each_node, ^(T) { (T) -> void } -> void each_child) -> ::Array[T]

tsort(each_node, each_child)

# File tmp/rubies/ruby-3.4.1/lib/tsort.rb, line 178
def self.tsort(each_node, each_child)
  tsort_each(each_node, each_child).to_a
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.

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.

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

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.tsort(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.tsort(each_node, each_child) # raises TSort::Cyclic

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

‹ prev.strongly_connected_components next ›.tsort_each