Hatena::ブログ(Diary)

<s>gnarl,</s>技術メモ”’<marquee><textarea>¥ このページをアンテナに追加 RSSフィード

2013-06-24

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 # トポロジカルソートされたノードの配列を取得する

みたいな使い方です。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/gnarl/20130624/1372011436
リンク元