Rubyでトポロジカルソートする

トポロジカルソート - Wikipedia

依存関係を定義したグラフを元に処理順決めるときに使ったりするあれです､あれ｡
gitのコミットオブジェクト(複数の親を持つ可能性がある)を並び替える必要があったので調べた｡

Rubyには tsortというライブラリが標準添付されているので便利｡1.7あたりからある模様｡

トポロジカルソートには

• ノードの集合を取得する
• あるノードが繋がっている先のノードを取得する

というデータ構造に依存する処理が必要で､それを用意してやればtsortがうまいことやってくれる｡

require 'tsort'

class Nodes
  include TSort
  def tsort_each_node(&block)
    # ノードを列挙してblockに渡す処理を実装する
  end
  def tsort_each_child(node, &block)
    # node が繋がっている先のノードを列挙してblockに渡す処理を実装する
  end
end

nodes = Nodes.new(...)
nodes.tsort # トポロジカルソートされたノードの配列を取得する

みたいな使い方です｡