Following the Tsort docs simple example:

require 'tsort'

class Hash
  include TSort
  alias tsort_each_node each_key
  def tsort_each_child(node, &block)
    fetch(node).each(&block)
  end
end

When I run it with this dataset, the resulting array seems wrong to me:

{ 1 => [], 2 => [1], 3 => [2], 4 => [1], 5 => [2] }.tsort
#=> [1, 2, 3, 4, 5]

I was expected one of these arrays instead:

[1, 4, 2, 3, 5]
[1, 4, 2, 5, 3]
[1, 2, 4, 3, 5]
[1, 2, 4, 5, 3]

Am I misunderstanding Tsort or is there something else I'm missing to get to these arrays?

CodePudding user response：

As Amadan mentioned in the comment nothing is wrong with the result that you retrieve. Topological sort requires that for any edge u -> v vertex u should precede v in the result - and [1,2,3,4,5] satisfies this requirement pretty well.

The particular order is determined by the way you traverse the graph. For example, if you slightly change the code so that we would traverse the keys in a reversed order

require 'tsort'

class Hash
  include TSort

  def tsort_each_child(node, &block)
    fetch(node).each(&block)
  end

  def tsort_each_node(&block)
    each_key.reverse_each(&block)
  end
end

the result would be different too:

{ 1 => [], 2 => [1], 3 => [2], 4 => [1], 5 => [2] }.tsort
# => [1, 2, 5, 4, 3]

This new result doesn't meet any of your expectations too, but again it fully satisfies the topological sort definition - all nodes appear strictly after their dependencies.