Tociyuki::Diary RSSフィード

tociyuki による Perl・Ruby・C++・C で書き散らしたコードを中心に、日常雑記も混在 : B  F  twitter  GitHub  CPAN  本館  公開鍵
 | 

2012年09月04日

[]Kahn 系統のトポロジカルソー

トポロジカルソートは、例えば make(1) のような依存関係をもつ個々のタスクを順番に実行したいときに使うものです。依存関係は循環を含まないグラフで表すことができます。タスク x をタスク y の直前に実行しなければならないとき、ノード x からノード y へのベクトルでつながったグラフとみなし、それをトポロジカルソートして、x が y より前に出現するノードの線形リストに並べ替えるのです。

トポロジカルソートの現実的なアルゴリズムには、おおまかに分けて A. B. Kahn (1962) 系統と、R. E. Tarjan (1972) の 2 種類があります。厳密には前者がトポロジカルソートで、後者はグラフ頂点の依存関係を逆向き、上の例では y から x 方向、に深さ優先で辿る探索アルゴリズムです。それぞれ一長一短があります。前者の利点はグラフに循環が含まれないことを自然にチェックできる点があります。欠点は、再実行時にすべてのタスクを実行するには良いものの、あるターゲットが依存しているタスクを抜き出すには、グラフ探索が別途必要になることです。後者の利点は、あるターゲットに対する依存タスクをトポロジカルソートしつつ容易に抜き出せることです。自分の経験では、圧倒的にこの手の使い方が多く、Tarjan の利用率の方が多かったと言えます。欠点は循環が含まれるかどうかのチェックにグラフの経路探索が必要なことです*1。両方の利点を兼ね備えたアルゴリズムが望まれて頭脳優秀な方々による 50 年間のチャレンジが続いているわけですけど、結局のところ、Kahn か Tarjan のいずれかのアルゴリズムの改良版が使われているのが現状のように見えます。

ちなみに私が最初に使ったのは Kahn 系統の一つ、N. Wirth アルゴリズム+データ構造=PASCAL プログラム 第一版 (1979)、207 ページ記載の 4.3.3 応用: トポロジカル・ソートを Turbo PASCAL 3.0 へ自力で移植してみたものです。30 年近く前のことです。目的は Turbo PASCAL 3.0 のおまけに付いていた表計算アプリケーションを、セルの評価順序に従って式を計算していくように拡張したかったからでした。おまけについてきた代物は、安直にもセルの左上から右下へと順に評価していくだけで、行きつ戻りつしながら計算させることができなかったのです。あのときは、表中のすべての式をトポロジカルソート結果の順で再計算するという、8 ビットプロセッサZ80 にとってあまりに富豪的な手抜きだったのですが、DRAM を 32kiB しか積んでない CP/M マシンだったので、遅さを感じられるほどの巨大な表を作れっこないのが幸運でした。

続いて作ったのは Tarjan のアルゴリズムを実装した、CP/M 用の手作り make ツールでした。当初は Turbo PASCAL 3.0 で記述したものの、実行スピードを改善したくてメモリ常駐させたくて Z80 アセンブラへ書き直したものです。make のようにあるターゲットが依存しているタスクを実行させたいときには、やはり Tarjan 系統の方が向いています。そういう事情から、私には Kahn 系統よりも Tarjan の方が使い勝手がよく、以来、主に Tarjan を使ってきました。

それなのに、なんでまた、今頃になって Kahn 系統のトポロジカルソートを ruby で組んでみようという気になった理由は、和田先生のブログに D. Knuth The Art of Computer Programming, Vol. 1: Fundamental Algorithms (1997)、265 ページ記載の Algorithm T (Topological sort)scheme に直訳したエントリ が登場したためです。Knuth のアルゴリズムは Wirth のアルゴリズムの兄貴分で、データ構造は 1 点を除いて共通です。Knuth が配列を使うのに対して、Wirth は線形リストを使います。そこを除くと、カウンタを使うこととポインタのやりくりは共通しており、メモリ消費の少ない省スペースな、言い換えると両先生お得意のポインタ操作の魔術が展開されるというわけです。元が魔術なだけに、scheme で書いても、魔術っぽさが消えてないというのがなんとも。scheme であっても、せめて Gauche で記述すれば、すっきりポイントを際だせて記述できるだろうにとは思いつつ、この手のデータ構造メインのアルゴリズムは ruby で書いた方が素直だろうと考えたりしたのでした。

比較のために Tarjan も実装しても良いのですが、Ruby 添付ライブラリ tsort にそのものずばりがあるので、ここでは Kahn 系統だけにしておきます。なお、この実装では successors (上の例の y) を線形リストではなく Array に入れています。Knuth と Wirth のアルゴリズムで大切なのはデータ構造で、precede (上の例の x) ごとに直前のノードの個数を count メンバに数え上げておくことと、それへ successors の集合を結びつけておくことです。集合をどのようなデータ構造で表現するかは重要ではありません。余談ながら、Kahn 系統のトポロジカルソートはガーベジ・コレクションのリファレンス・カウンタ法と Cheney コピーを組み合わせてアレンジした形をしています。一方、Tarjan は再帰型の深さ優先 mark フェーズそのものです。Tarjan で循環判定が一発でできないのはそのためです。

蛇足ながら、トポロジカルソートの結果は何通りもあるのが普通です。この実装では ruby 処理系の Hash の実装に依存します。CRuby の Hash は、双方向リストにチェイン法ハッシュ・テーブルのインデックスをつけたものですので、Wirth 版と同じ挙動をします。mruby の Hash は、オープン・アドレス法ハッシュ・テーブルなので、異なる結果になります。同じ Ruby 言語でも処理系によって結果が変わるのはユニット・テスト向けではないので、まじめにやるなら Hash を使わずに顕に双方向リストや Array を使う方が望ましいのでしょう。

#!/usr/bin/env ruby

module TopologicalSorting
  # [ref 1] D. Knuth, ``The Art of Computer Programming Volume 1 Third Edition'',
  #   1997, ISBN 0-201-89683-4, page 265
  #   2.2.3 Algorithm T (Topological sort)
  # [ref 2] N. Wirth, ``アルゴリズム+データ構造=PASCAL プログラム 第1版'',
  #   1979, page 207
  #   4.3.3 応用: トポロジカル・ソート

  def tsort(partial_ordering_list)
    relations = Relations.new(partial_ordering_list)
    sorted = []
    queue = relations.find_all_not_preceded
    while precede = queue.shift
      sorted.push precede
      relations.delete(precede).successors.each do |successor|
        if relations.decrement!(successor) == 0
          queue.unshift successor
        end
      end
    end
    relations.empty? or raise Cyclic, 'Circular definitions'
    sorted
  end

  module_function :tsort

  Cyclic = Class.new(StandardError)

  class Relations
    Relation = Struct.new(:count, :successors)

    def initialize(partial_ordering_list)
      @top = {}
      partial_ordering_list.each do |precede, successor|
        @top[precede] ||= Relation.new(0, [])
        @top[successor] ||= Relation.new(0, [])
        @top[precede].successors << successor
        @top[successor].count += 1
      end
    end

    def find_all_not_preceded()
      @top.keys.select{|k| @top[k].count == 0 }
    end

    def decrement!(precede) @top[precede].count -= 1 end

    def delete(precede) @top.delete(precede) end
    def empty?() @top.empty? end
  end
end

p TopologicalSorting.tsort([
  [8, 1], [2, 6], [6, 4], [4, 7], [7, 5], [3, 5], [0, 2], [6, 3], [8, 4], [1, 7],
]) #=> [8, 1, 0, 2, 6, 3, 4, 7, 5]

Tarjan のトポロジカルソート

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


画像認証

トラックバック - http://d.hatena.ne.jp/tociyuki/20120904/1346729189
 |