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

Kahn 系統のトポロジカルソート」で Tarjan の欠点として、「循環が含まれるかどうかのチェックにグラフの経路探索が必要なこと」と書きました。その後、A. V. Aho、B. W. Kernighan, P. J. Weinberger 著The AWK Programming Language(1988) のSECTION 7.3 TOPOLOGICAL SORTING(page 174) に、循環検出を組み込んだ Tarjan のトポロジカルソートが記載されているのを見つけたため、自己フォローしておきます。
AWK 本記載の方法は、一見、Tarjan のトポロジカルソートにちょっとした改良を施したにすぎないように見えますけど、三色マーキングの応用になっていて素晴らしくクールなやりかたです。マーク途上のノードを灰色にし、参照先のすべてのマーク完了後に黒色にします。深さ優先探索であることが重要で、参照先を深く潜っていく途中で参照が灰色ノードに後戻りしているかどうかで循環しているかどうかを判定できます。
先に Ruby で書いた「Tarjan のトポロジカルソート」に取り入れてみます。変更箇所は depends 手続きをだけです。まず、再帰呼び出し版の差分です。AWK ではマークなし(白色)がゼロ、灰色が 1、黒色が 2 で書いてありますが、Ruby に翻訳する際に色をシンボルで記述するようにしました。

 def depends(target, dependencies, marked = {}, sorted = [])
   return if marked[target]
+  marked[target] = :gray
-  marked[target] = true
   for m in dependencies[target]
+    if ! marked[m]
+      depends(m, dependencies, marked, sorted)
+    elsif marked[m] == :gray
+      raise "nodes #{m} and #{target} are in a cycle"
+    end
-    depends(m, dependencies, marked, sorted)
    end
    sorted.push target
+   marked[target] = :black
    sorted
  end

続いて、再帰呼び出し除去版の差分です。

 def depends_loop(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] = :gray
-      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]
+        m = dependencies[n][i]
+        if ! marked[m]
+          todo.push [:node, m]
+        elsif marked[m] == :gray
+          raise "nodes #{m} and #{n} are in a cycle"
+        end
-        todo.push [:node, dependencies[n][i]]
       end
     when :push
+      n = job[1]
+      sorted.push n
+      marked[n] = :black
-      sorted.push job[1]
     end
   end
   sorted
 end