Tarjan のトポロジカルソート

せっかくなので、Kahn 系統のトポロジカルソートに続いて、Tarjan のトポロジカルソートも書いてみます。タスク x を完了しないとタスク y を実行できないとするとき、Tarjan のやりかたでは、y から x へリンクが伸びるグラフで表して、y の方からリンクを深さ優先探索していきます。探索の書き方は、ガーベジ・コレクションの深さ優先 mark フェーズと同じです。

最初に依存関係を表すハッシュを作る手続きを定義します。Kahn のトポロジカルソートで作った relations の逆関係になります。

def make_dependencies(partial_ordering_list)
  h = {}
  partial_ordering_list.each do |precede, successor|
    h[precede] ||= []
    h[successor] ||= []
    h[successor].push precede
  end
  h
end

partial_ordering_list = [
  [8, 1], [2, 6], [6, 4], [4, 7], [7, 5], [3, 5], [0, 2], [6, 3], [8, 4], [1, 7],
]

dependencies = make_dependencies(partial_ordering_list)

dependencies == {
  8=>[], 1=>[8], 2=>[0], 6=>[2], 4=>[6, 8], 7=>[4, 1], 5=>[7, 3], 3=>[6], 0=>[],
} or raise 'not ok # test_make_dependencies'

Tarjan のトポロジカルソートでは、これを深さ優先で経路探索し、まだ訪れてないリンクを先へ先へと辿っていきます。経路探索を担当する depends 手続きは指定したターゲットが依存するタスクだけをトポロジカルソートするのに単体で利用することができます。make(1) の簡易版を作るのに Tarjan のトポロジカルソートが向いているのは、こういう使い方ができるためです。

def tsort(dependencies)
  marked = {}
  sorted = []
  for target in dependencies.keys
    depends(target, dependencies, marked, sorted)
  end
  sorted
end

def depends(target, dependencies, marked = {}, sorted = [])
  return if marked[target]
  marked[target] = true
  for m in dependencies[target]
    depends(m, dependencies, marked, sorted)
  end
  sorted.push target
  sorted
end

sorted = tsort(dependencies)

partial_ordering_list.all? {|a, b|
  j = sorted.index(a); k = sorted.index(b); ! j.nil? && ! k.nil? && j < k
} or raise 'not ok # tsort'

p sorted #=> [8, 1, 0, 2, 6, 4, 7, 3, 5]

p depends(3, dependencies) #=> [0, 2, 6, 3]
p depends(1, dependencies) #=> [8, 1]

上では、depends を再帰呼び出しで書いています。末尾再帰ではないので、再帰呼び出しを除去するには継続渡しするのが適切でしょう。ここでは、他の言語への移植性を考慮して、コマンドを継続渡しとしてスタックへ積むやりかたで書いてみました。

def depends(target, dependencies, marked = {}, sorted = [])
  todo = [[:node, target]]
  while job = todo.pop
    case job[0]
    when :node
      n = job[1]
      next if marked[n]
      marked[n] = true
      todo.push [:push, n]
      todo.push [:child, n, 0]
    when :child
      n, i = job[1], job[2]
      if i < dependencies[n].size
        todo.push [:child, n, i + 1]
        todo.push [:node, dependencies[n][i]]
      end
    when :push
      sorted.push job[1]
    end
  end
  sorted
end

AWK 本記載の循環検出付き改良版 Tarjan のトポロジカルソート