トポロジカルソート

グラフ理論において、トポロジカルソート(英: topological sort)とは無閉路有向グラフ（英: directed acyclic graph、DAG)の各ノードを順序付けして、どのノードもその出力辺の先のノードより前にくるように並べることである。DAGは必ずトポロジカルソートすることができる。

DAG のノードの集合に到達可能性関係 R (ノード x から y への(各辺の向きに逆行しない)経路が存在するとき、またそのときに限り xRy とする)を定めると、R は半順序関係となる。トポロジカルソートとは、この R を全順序になるように拡張したものとみなせる。

例

トポロジカルソートの典型的な利用例はジョブのスケジューリングである。トポロジカルソートのアルゴリズムはPERTというプロジェクト管理手法（(Jarnagin 1960)）のスケジューリングのために1960年代初頭に研究が開始された。ジョブはノードとして表現され、XからYへの辺はジョブXが終了しなければジョブYを始められないということを意味する（例えば洗濯が完了しなければ服を乾燥機にかけられないなど）。ジョブをトポロジカルソートすると、ジョブに着手すべき順番がわかることになる。

コンピュータサイエンスでの利用例は、命令スケジューリング、表計算で式を変更したとき再計算が必要なセルの評価順序の決定、論理合成、Makefileで指定されたファイルのコンパイル順序の決定、リンカのシンボル依存関係の解決などがある。

左のグラフには次のように複数の結果にトポロジカルソートできる 7, 5, 3, 11, 8, 2, 9, 10 (見た目において左から右、上から下への順) 3, 5, 7, 8, 11, 2, 9, 10 (数値的に小さなノードを前に持ってくる) 3, 7, 8, 5, 11, 10, 2, 9 5, 7, 3, 8, 11, 10, 9, 2 (辺の数が少ないノードを前に持ってくる) 7, 5, 11, 3, 10, 8, 9, 2 (辺の数が多いノードを前に持ってくる) 7, 5, 11, 2, 3, 8, 9, 10

アルゴリズム

通常トポロジカルソートに使われるアルゴリズムはノードと辺の数に対して線形な時間を必要とする（O(|V|+|E|)）.

Kahn (1962)が発明したアルゴリズムは、トポロジカルソートされた結果になるようにノードを順に選択していくというものである。まずは入力辺を持たない開始ノードを探してそれを集合Sに追加する。グラフに循環がなければ少なくとも1つはそういうノードが存在する。その次に、

L ← 空リスト（ソートされた要素を蓄積する）
S ← 入力辺を持たないすべてのノードの集合
while Sが空ではない do
    Sからノードnを削除する
    Lにnを追加する
    for each nの出力辺eとその先のノードm do
        辺eをグラフから削除する
        if mがその他の入力辺を持っていなければ then
            mをSに追加する
if グラフが辺を持っている then
    エラーを出力する（グラフに少なくとも1つの循環がある）
else
    メッセージを出力する（Lにトポロジカルソートの結果が入っている）

グラフが無閉路有向グラフならばLが解となる（解は1つとは限らない）。そうでなければグラフには1つ以上の循環があり、トポロジカルソートは不可能である。

Sは単なる集合だけではなくキューやスタックでもよい。集合Sからノードnが取り除かれる順番に応じて、異なる解が生成される。

トポロジカルソートの別のアルゴリズムは深さ優先探索をベースにしている。このアルゴリズムでは、ノードの辺は先程のアルゴリズムの逆向きになる。ノードXからYへの辺は、ジョブXがジョブYに依存しているという意味になる（つまり、ジョブXに着手するより前にジョブYが完了していなければならない）。このアルゴリズムではグラフの各ノードについて、トポロジカルソートを始めてからすでに訪れたノードに到達するまで深さ優先探索を行う。

L ← ソートされた結果の入るリスト。初期値は空
S ← すべてのノードの集合

function visit(node n)
    if nをまだ訪れていなければ
        nを訪問済みとしてマーク
        for each nの出力辺eとその先のノードm do
            visit(m)
        nをLに追加

for each Sに含まれるノードn do
    visit(n)

上のアルゴリズムでノードnがリストLに追加されるのは、ノードnが依存している他のノード（グラフ中でnから到達可能な全てのノード）を訪れた後であることに注意。このアルゴリズムでは、ノードnが追加されるときnが依存するすべてのノードはすでにリストLに追加されていることが保証されている。そのようなノードはノードnからvisit()の再帰で到達するか、あるいはnを訪れるより前にすでに到達されているはずである。辺とノードは一度しか訪問されないのでこのアルゴリズムは線形時間しか必要としない。上の擬似コードはグラフに循環がある場合にそれをエラーとして検出することはできない。循環を検出するには、visit()の再帰呼び出しで複数回到達するノードがあるかどうかをチェックすればよい（そのためにはvisit()に引数を追加して、現在の呼び出しスタックでvisit()が訪問済みノードのリストを渡せばよい）。この深さ優先探索ベースのアルゴリズムはCormen, Leiserson & Rivest (1990)で解説されている。Tarjan (1976)が最初に出版されたものと思われる。

解の一意性

もしトポロジカルソートされたノードのすべてのノードが隣接する次のノードへの辺を持つなら、元の無閉路有向グラフはハミルトン路を含む。もしハミルトン路が含まれるなら、トポロジカルソートの結果は一意、つまり2つ以上の解は存在しない。逆に、トポロジカルソートがハミルトン路を作らないなら、元の無閉路有向グラフはは2つ以上のトポロジカルソート結果を持つ。その場合、ある結果のうち直接辺によってつながっていないノードを交換することで2番目のトポロジカルソート結果を得ることができる。従って、一般のグラフにおけるハミルトン路の問題はNP困難であるが、一意なトポロジカルソート結果が存在するかどうか、あるいはハミルトン路が存在するかどうかは多項式時間で決定することができる。

関連項目

• tsort(en), トポロジカルソートを行う Unix プログラム
• make, プログラムのビルドを自動化する Unix プログラム
• Feedback arc set, a (possibly empty) set of arcs which, if removed from the graph, make it possible to topologically sort it. Useful for dealing with graphs with cycles.
• スパニング木, which reduces a DAG to a hierarchical, rather than a linear, structure

参考文献

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press and McGraw-Hill. First Edition, 1990, ISBN 0-07-013143-0, Section 23.4: Topological sort, pp.485–488; Second Edition, 2001, ISBN 0-262-03293-7, Section 22.4: Topological sort, pp.549–552.

• Jarnagin, M. P. (1960), Automatic machine methods of testing PERT networks for consistency, Technical Memorandum No. K-24/60, Dahlgren, Virginia: U. S. Naval Weapons Laboratory .

• Kahn, A. B. (1962), “Topological sorting of large networks”, Communications of the ACM 5 (11): 558–562, doi:10.1145/368996.369025 .

• Tarjan, Robert E. (1976), “Edge-disjoint spanning trees and depth-first search”, Algorithmica 6 (2): 171–185, doi:10.1007/BF00268499 .

• Vernet, Lilian; Markenzon (1997), “Hamiltonian problems for reducible flowgraphs”, Proc. 17th International Conference of the Chilean Computer Science Society (SCCC '97), pp. 264–267, doi:10.1109/SCCC.1997.637099 .

外部リンク

• NIST Dictionary of Algorithms and Data Structures: topological sort
• Weisstein, Eric W. "TopologicalSort". mathworld.wolfram.com (英語).