ruby - ruby 中的字母拓扑排序

Question

假设我有这个依赖树:

digraph G {
    view1_1 -> view1
    view1_2 -> view1
    a_view1_1_1 -> view1_1
    c_view1_and_1_1 -> view1_1
    c_view1_and_1_1 -> view1
    z_view1_1_2 -> view1_1
}

我怎样才能得到这个作为结果订单:

view1
view1_1
a_view1_1_1
c_view1_and_1_1
view1_2
z_view1_1_2

在某些情况下，它是为了在开源项目上生成可重现的文件输出:https://github.com/thoughtbot/scenic/pull/191

我开始混合使用 tsort 和原始字母排序，例如:

Answer 1

我意识到 tsort 给我的输出实际上是正确的，即使与我的直觉不一样:

require 'tsort'

tree = {
  "view1" => [],
  "view1_1" => ["view1"],
  "view1_2" => ["view1"],
  "a_view1_1_1" => ["view1_1"],
  "c_view1_and_1_1" => ["view1_1", "view1"],
  "z_view1_1_2" => ["view1_1"],
}

class Hash
  include TSort

  def tsort_each_node(&block)
    keys.sort.each(&block)
  end

  def tsort_each_child(node, &block)
    fetch(node).each { |n| yield(n) }
  end
end

tree = Hash[*tree.to_a.shuffle.flatten(1)]

puts tree.tsort

# BONUS: p tree.strongly_connected_components

给出:

view1
view1_1
a_view1_1_1
c_view1_and_1_1
view1_2
z_view1_1_2