Rubyでトポロジカルソートする - <s>gnarl,</s>技術メモ”’<marquee><textarea>￥

トポロジカルソート - 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 が繋がっ