2012年8月29日水曜日

トポロジカルソート

TAOCPの第1巻にトポロジカルソートのアルゴリズムがある(Algorithm 2.2.3-T). リストの使い方の例である.

例に使う順序には, TAOCPのをそのまま使わせてもらおう. ただ, あの本でのデータは1から始まり, 0は別の機能を持っているが, 私は0から始めるのが好きなので, そういうふうに変更した.

8<1, 2<6, 6<4, 4<7, 7<5, 3<5, 0<2, 6<3, 8<4, 1<7のようなデータがあるとする. 8は1に先行し, 2は6に先行し,...と読む. この関係をグラフにすると, 上の図の上のようになる.

トポロジカルソートはそれを上の図の下のように, 前後関係を保ったまま, 1列に並べるものである.

Algorithm 2.2.3-Tでは, まず要素の個数(上の例では0から8の9個)を受け取り, 下の図のAのようなデータ構造を用意する. 左端の番号は元のデータに出てくる数である.

countはある要素に先行する要素の数を保持する. topはこの要素に後続する要素のリストを保持する. countは最初は0, topは最初はnilである. 8<1を読み込むと, 要素1には先行者8があったので, 1のcountを1増やし, 1を要素8のtopのリストにつなげる. したがってデータ構造はBのようになる.

2<6を読み込むとCになる. 関係をすべて読んだのがDだ.

8<1と8<4を読んだわけだが, 4が1の前にあるのはリスト処理が楽だからで, topのリストの中での順は重要ではない.

count=0の要素0と8は先頭になる資格がある. 従ってソートしたリストに書き出すことが出来る. そしてそれらがソートリストに並んだら, そのtopリストの各要素は邪魔者が1つなくなったので, countを1減らす. その結果0になったら, ソートリストにならぶ権利が得られる. これがトポロジカルソートの基本だ.

TAOCPのアルゴリズムでは, 入力が終わるとcountをしらべ, 権利をもつもののキュー(FIFO)を構成する. count=0になったもののcountの欄を流用する. 以下の図では, キューの関係は赤字で示す. キューを作るには, 先頭(Front)から末尾(Rear)へ至るリストを使う. キューの最後にはnilを入れておく. キューに要素を挿入するのは末尾の側で, 削除するのは先頭の側である. その場所を覚えるためにの変数fとrを用意し, キューが空の時は, f=r=nilとする(E).

要素0のcountが0なので, Fに示すように, 1要素だけのキューが出来, fもrも0を指し, 0のcountがnilになる(F).

さらにcountが0のものを探すと, 要素8が見つかり, Gのようになる. つまりfは0を指し, 0のcountは8になり, 8のcountはnil, rは8となる.

0の探索が終了すると, トポロジカルソートの出力が始まる. その前に変数Nを要素数nにしておき, 出力のたびにNを1減らし, 最後にすべて出力したかをN=0で確認する. まずfの値0を出力, N=N-1とする. 0のtopからリストを辿り, それらに先行していたものがなくなった処理をする. つまり要素2のcountを1減らす. その結果countが0になったら, この要素も先行するものがなくなり, 出力できるようになったわけで, この要素をcountのキューにつなぐ(H). 0のcountは8のままだが, これはゴミである. Algorithm 2.2.3-Tでは, topのリストはそのままにしているが, 演習問題2.2.3-23にあるように, トポロジカルソートが出来なかったときの原因探索用に, 済んだリストはnilにしておくのがよい.

fにfのcountを代入してfを進め, 次の要素の出力に取りかかる. 図Iは要素8も出力したところ, Jは2も出力したところである. キューの先頭をfで辿り出力を続ける. fがnilになったら終わりで, Nは0になったはずである. 0にならなければ, 元のデータがおかしかった(ループがあった)ので, topのリストを出力してみると, 原因がわかる.
,br> 私がSchemeで書いたプログラムは以下のようだ. 変数Nの代わりにnnにしてある.
(define (algorithm223t n ls)
 (let* ((count (make-vector n 0)) (top (make-vector n '()))
        (r '()) (f '()) (nn n))
  (define (getrel ls)   ;データを読み込む 
   (if (not (null? ls))
    (let ((j (caar ls)) (k (cadar ls)))
     (vector-set! count k (+ (vector-ref count k) 1))
     (vector-set! top j (cons k (vector-ref top j)))
     (getrel (cdr ls)))))
  (define (outloop f)   ;出力のループ
   (define (eraserel p) ;topのリストを解消する
    (if (not (null? p))
     (let ((c (- (vector-ref count (car p)) 1)))
      (if (> c 0) (vector-set! count (car p) c)
       (begin (vector-set! count r (car p)) (set! r (car p))
              (vector-set! count r '())))
      (eraserel (cdr p)))
     (begin (vector-set! top f '())
      (outloop (vector-ref count f)))))
   (if (not (null? f))
    (begin (display f) (display " ") (set! nn (- nn 1))
     (eraserel (vector-ref top f)))))
  (getrel ls)
  (do ((k 0 (+ k 1))) ((= k n)) ;count=0のキューを作る
   (if (= (vector-ref count k) 0)
    (begin (if (null? r) (set! f k) (vector-set! count r k))
     (set! r k) (vector-set! count r '()))))
  (outloop f)   ;出力開始
  (if (= nn 0) 'ok (list 'nn nn))))

(algorithm223t 9
'((8 1) (2 6) (6 4) (4 7) (7 5) (3 5) (0 2) (6 3) (8 4) (1 7)))
このプログラムを走らせると 0 8 2 1 6 3 4 7 5 が出力される.

このプログラムに出力命令を追加し, データ入力が終った時のcountとtopの値は #(8 1 1 1 2 2 1 2 ())#((2) (7) (6) (5) (7) () (3 4) (5) (4 1))である.

またデータの最後に(3 0)を追加すると, ループが出来, トポロジカルソートが出来ない. それをやってみると8 1でソートの出力は終り, 残ったtopとして#((2) () (6) (0 5) (7) () (3 4) (5) ())が得られる. これからだとループの発見は面倒だが, 演習問題23のように拡張すると, どこが悪いかが判明する