トポロジカルソート

コンピュータサイエンスにおいて、有向グラフのトポロジカルソートまたはトポロジカル順序付けとは、頂点uから頂点vへのすべての有向エッジ(u,v)について、順序付けにおいてu がv の前にくるように頂点を線形に順序付けすることです。たとえば、グラフの頂点は実行されるタスクを表し、エッジは 1 つのタスクが別のタスクの前に実行されなければならないという制約を表す場合があります。このアプリケーションでは、トポロジカル順序付けはタスクの有効なシーケンスにすぎません。正確には、トポロジカルソートは、すべての依存関係が訪問された後にのみ各ノードvが訪問されるグラフトラバーサルです。トポロジカル順序付けは、グラフに有向サイクルがない場合、つまり有向非巡回グラフ(DAG)である場合に限り可能です。どの DAG にも少なくとも 1 つのトポロジカル順序付けがあり、線形時間で任意の DAG のトポロジカル順序付けを構築するアルゴリズムが知られています。トポロジカルソートには多くの用途があり、特にフィードバックアークセットなどのランキング問題に使用されます。 DAGに切断されたコンポーネントがある場合でも、トポロジカル ソートは可能です。

トポロジカルソートの標準的な応用は、一連のジョブまたはタスクをそれらの依存関係に基づいてスケジュールすることです。ジョブは頂点で表され、ジョブxが完了してからジョブyを開始する必要がある場合は、 xからyへのエッジが存在します(たとえば、衣類を洗濯する場合、衣類を乾燥機に入れる前に洗濯機が終了している必要があります)。次に、トポロジカルソートによってジョブを実行する順序が与えられます。トポロジカルソートアルゴリズムの密接に関連する応用は、1960 年代初頭にプロジェクト管理のスケジューリングのためのPERT手法のコンテキストで初めて研究されました。^[1]このアプリケーションでは、グラフの頂点はプロジェクトのマイルストーンを表し、エッジは 1 つのマイルストーンと別のマイルストーンの間で実行する必要があるタスクを表します。トポロジカルソートは、プロジェクトのクリティカルパス、つまりプロジェクト全体のスケジュールの長さを制御する一連のマイルストーンとタスクを見つけるための線形時間アルゴリズムの基礎となります。

コンピュータサイエンスでは、このタイプのアプリケーションは、命令のスケジューリング、スプレッドシートで数式の値を再計算する際の数式セルの評価の順序付け、論理合成、メイクファイルで実行するコンパイルタスクの順序の決定、データのシリアル化、リンカーでのシンボル依存関係の解決などで使用されます。また、データベースで外部キーを持つテーブルをロードする順序を決定するためにも使用されます。

通常のトポロジカルソートアルゴリズムでは、実行時間はノード数とエッジ数に比例し、漸近的には${\displaystyle O(\left|{V}\right|+\left|{E}\right|).}$

これらのアルゴリズムの 1 つは、Kahn (1962) によって初めて説明され、最終的なトポロジカル ソートと同じ順序で頂点を選択することによって機能します。^[2]まず、入力エッジを持たない「開始ノード」のリストを見つけて、それをセット S に挿入します。空でない (有限の) 非巡回グラフには、少なくとも 1 つのそのようなノードが存在する必要があります。次に、次の操作を実行します。

L ← ソートされた要素を含む空のリスト
S ← 入ってくるエッジを持たないすべてのノードの集合

 S が空でない限り、Sから
    ノードnを削除します。nからmへのエッジeを持つ各ノードmに対してnをLに
    追加します。グラフから
        
        エッジeを削除します。mに他の入力エッジがない場合は、mをSに
            挿入します。
      

 グラフにエッジがある場合はエラー
    を   返します（グラフには少なくとも 1 つのサイクルがあります）。
それ以外の場合は 
    L を返します （位相的にソートされた順序）。   

グラフがDAGの場合、解はリスト L に含まれます (ただし、解は必ずしも一意ではありません)。それ以外の場合、グラフには少なくとも 1 つのサイクルが存在する必要があるため、トポロジカル ソートは不可能です。

結果として得られるソートの非一意性を反映して、構造 S は単なるセット、キュー、またはスタックになります。セット S からノード n が削除される順序に応じて、異なるソリューションが作成されます。辞書式順序で同点を解消するカーンのアルゴリズムのバリエーションは、並列スケジューリングと階層化グラフ描画のためのコフマン-グラハム アルゴリズムの重要なコンポーネントを形成します。

トポロジカルソートの代替アルゴリズムは、深さ優先探索に基づいています。このアルゴリズムは、グラフの各ノードを任意の順序でループし、深さ優先探索を開始します。この探索は、トポロジカルソートの開始以降にすでに訪問されたノードに到達するか、ノードに出力エッジがない場合 (つまり、リーフノード) に終了します。

L ← 空のリスト。ソートされたノードが含まれますが、
永続的なマークのないノードが存在する場合は、
    マークされていないノードn を選択します。 
    visit( n )

関数visit(ノードn )
     n に永続的なマークがある場合 は戻り、n に一時的なマークがある場合は停止します(グラフには少なくとも 1 つのサイクルがあります)
        
     
           
一時的なマークでn
    をマークする

    nからmへのエッジを持つ各ノードmに対して
        visit( m )を実行する。 
永久的なマークでn
    をマークするLの先頭にnを
    追加する

各ノードn は、 nに依存する他のすべてのノード(グラフ内のnのすべての子孫) を考慮した後にのみ、出力リスト L の先頭に追加されます。具体的には、アルゴリズムがノードn を追加するとき、 nに依存するすべてのノードがすでに出力リスト L に含まれていることが保証されます。これらのノードは、 visit nの呼び出し前に終了した visit() の再帰呼び出しによって、または visit nの呼び出し前に開始された visit() の呼び出しによってL に追加されています。各エッジとノードは 1 回訪問されるため、アルゴリズムは線形時間で実行されます。この深さ優先探索ベースのアルゴリズムは、Cormen ら (2001) によって説明されています。^[3]これは、1976 年に Tarjan によって初めて印刷物で説明されたようです。^[4]

並列ランダムアクセスマシンでは、多項式数のプロセッサを使用してO ((log n ) ^{2 ) 時間で位相的順序付けを構築できるため、問題は複雑度クラス}NC ²に分類されます。^[5] これを実行する方法の 1 つは、最小化の代わりに最大化を使用して、最小プラス行列乗算を使用して、指定されたグラフの隣接行列を対数的に何度も繰り返し二乗することです。結果の行列は、グラフ内の最長パス距離を表します。頂点を最長入力パスの長さで並べ替えると、位相的順序付けが生成されます。^[6]

分散メモリマシン上の並列トポロジカルソートのアルゴリズムは、 DAG のカーンのアルゴリズムを並列化します。^[7]大まかに言うと、カーンのアルゴリズムは、入次数 0 の頂点を繰り返し削除し、削除された順序でトポロジカルソートに追加します。削除された頂点の出力エッジも削除されるため、入次数 0 の新しい頂点セットが作成され、頂点がなくなるまでこの手順が繰り返されます。このアルゴリズムは反復を実行します。ここで、DはG内の最長パスです。各反復は並列化できます。これが次のアルゴリズムの考え方です。 ${\displaystyle G=(V,E)}$${\displaystyle D+1}$

以下では、グラフ パーティションがp 個の処理要素 (PE) に格納され、 というラベルが付けられていると仮定します。各 PE i は、入次数0でローカル頂点のセットを初期化します。ここで、上位のインデックスは現在の反復を表します。ローカル セット内のすべての頂点の入次数は 0 であるため、つまり、隣接していないため、有効なトポロジカル ソートに対して任意の順序で指定できます。各頂点にグローバル インデックスを割り当てるには、のサイズにわたってプレフィックスの合計を計算します。したがって、各ステップで、トポロジカル ソートに頂点が追加されます。 ${\displaystyle 0,\dots ,p-1}$${\displaystyle Q_{i}^{1}}$${\displaystyle Q_{0}^{1},\dots ,Q_{p-1}^{1}}$${\displaystyle Q_{0}^{1},\dots ,Q_{p-1}^{1}}$${\textstyle \sum _{i=0}^{p-1}|Q_{i}|}$

最初のステップでは、PE j は内のローカル頂点にインデックスを割り当てます。 内のこれらの頂点は、対応する出力エッジとともに削除されます。別の PE 内のエンドポイントvを持つ出力エッジごとに、メッセージがPE lに投稿されます。 内のすべての頂点が削除された後、投稿されたメッセージが対応する PE に送信されます。受信した各メッセージは、ローカル頂点vの入次数を更新します。入次数がゼロになると、vが に追加されます。次に、次の反復が開始されます。 ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$${\displaystyle Q_{j}^{1}}$${\displaystyle Q_{j}^{1}}$${\displaystyle (u,v)}$${\displaystyle l,j\neq l}$${\displaystyle (u,v)}$${\displaystyle Q_{j}^{1}}$${\displaystyle (u,v)}$${\displaystyle Q_{j}^{2}}$

ステップkでは、PE j はインデックス を割り当てます。ここで、 は ステップ⁠ ⁠の後に処理された頂点の合計数です。この手順は、処理する頂点がなくなるまで繰り返されます。したがって、 となります。以下は、このアルゴリズムの高レベル、単一プログラム、複数データの疑似コードの概要です。 ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$${\displaystyle a_{k-1}}$${\displaystyle k-1}$${\textstyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}$

ローカル オフセットのプレフィックスの合計は、並列で効率的に計算できること に注意してください。${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$

IDが0からp -1
までのp個の処理要素入力: G = (V, E) DAG、PEに分散、PEインデックスj = 0、...、p-1
出力: Gのトポロジカルソート

関数traverseDAGDistributed
    δ ローカル頂点の入次数V 
    Q = { v ∈ V | δ[ v ] = 0}                      // 入次数が 0 のすべての頂点
    処理された頂点数 = 0

    
        Qのサイズに対してグローバルビルド プレフィックスの合計を実行します     // このステップのオフセットと頂点の合計数を取得します
        offset = nrOfVerticesProcessed + sum(Q i , i = 0 to j - 1) // jはプロセッサインデックス
        foreach u in Q
            ローカル順序[u] = インデックス++;
            E 内のforeach (u,v) は、頂点 v を所有する PE にメッセージ ( u, v ) を投稿します。nrOfVerticesProcessed 
        += sum(|Q i |, i = 0 to p - 1)
        Q内の頂点の隣接ノードにすべてのメッセージを配信する
        ローカル頂点Vのメッセージを受信する
        Q内のすべての頂点を削除する
        受信した各メッセージ（u、v）について：
             --δ[v] = 0の場合Qのグローバルサイズが0より大きいときに、Qにvを
                追加する
    

    ローカルオーダー
を返す

通信コストは与えられたグラフのパーティションに大きく依存する。実行時間に関しては、フェッチとデクリメントを定数時間で実行できるCRCW -PRAMモデルでは、このアルゴリズムは で実行される。ここで、DはG内の最長パスであり、Δは最大次数である。^[7]${\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}$

位相的順序付けは、重み付き有向非巡回グラフの最短経路を素早く計算するためにも使用できます。このようなグラフの頂点のリストを位相的順序でVとします。次のアルゴリズムは、いくつかの始点頂点から他のすべての頂点までの最短経路を計算します。 ^[3]

同様に:

n頂点m辺のグラフでは、このアルゴリズムはΘ( n + m )、つまり線形時間がかかります。^[3]

位相ソートが、ソート順で連続する頂点のペアすべてが辺で接続されているという特性を持つ場合、これらの辺はDAGで有向ハミルトン経路を形成します。ハミルトン経路が存在する場合、位相ソート順序は一意であり、他の順序は経路の辺を尊重しません。逆に、位相ソートがハミルトン経路を形成しない場合、DAG には 2 つ以上の有効な位相順序があります。この場合、辺で接続されていない 2 つの連続する頂点を交換することで、常に 2 番目の有効な順序を形成できるためです。したがって、より一般的な有向グラフ (つまり、巡回有向グラフ) に対するハミルトン経路問題のNP 困難性にもかかわらず、一意の順序が存在するかどうか、およびハミルトン経路が存在するかどうかを線形時間でテストできます。^[8]

位相的順序付けは、数学における半順序の線形拡張の概念とも密接に関連しています。半順序付けされた集合は、単にオブジェクトの集合と「≤」不等式関係の定義を組み合わせたもので、反射性 ( x  ≤  x )、反対称性 ( x  ≤  yかつy  ≤  xの場合、x  =  y )、推移性( x  ≤  yかつy  ≤  zの場合、x  ≤  z ) の公理を満たしています。全順序付けは、集合内の2 つのオブジェクトxとyごとに、 x  ≤  yまたはy  ≤  xのいずれかとなる半順序付けです。全順序付けは、比較ソートアルゴリズムを実行するために必要な比較演算子としてコンピューター サイエンスでよく知られています。有限集合の場合、全順序付けはオブジェクトの線形シーケンスと同一視できます。この場合、「≤」関係は、順序で最初のオブジェクトが 2 番目のオブジェクトより前にあるときは常に真です。このようにして、比較ソート アルゴリズムを使用して全順序付けをシーケンスに変換できます。半順序の線形拡張は、半順序で x ≤ y であれば全順序でも x  ≤  yで ある という意味において、半順序と互換性のある全順序です。

オブジェクトの集合を DAG の頂点とし、xからyへの有向パスが存在する場合、つまり、 xからyに到達可能な場合は常に、任意の 2 つの頂点xとyについてx  ≤  y が真であると定義することで、任意のDAGから部分順序を定義できます。これらの定義では、DAG の位相的順序付けは、この部分順序の線形拡張と同じものになります。逆に、任意の部分順序付けは、DAG の到達可能性関係として定義できます。これを行う 1 つの方法は、部分順序付けされたセット内のすべてのオブジェクトに対して頂点を持ち、x  ≤  yであるすべてのオブジェクトのペアに対して辺xyを持つ DAG を定義することです。これを行う別の方法は、部分順序付けの推移的縮小を使用することです。一般に、これにより辺の少ない DAG が生成されますが、これらの DAG の到達可能性関係は依然として同じ部分順序です。これらの構成を使用することで、位相的順序付けアルゴリズムを使用して部分順序の線形拡張を見つけることができます。

定義上、優先順位グラフを含むスケジューリング問題の解決は、トポロジカル ソートの有効な解決法です (マシンの数に関係なく)。ただし、トポロジカル ソートだけでは、スケジューリング最適化問題を最適に解決するには不十分です。Hu のアルゴリズムは、優先順位グラフを必要とし、処理時間を含むスケジューリング問題 (すべてのジョブの中で最大の完了時間を最小化することが目標) を解決するために使用される一般的な方法です。トポロジカル ソートと同様に、Hu のアルゴリズムは一意ではなく、DFS (最大パス長を見つけてジョブを割り当てる) を使用して解決できます。

• tsort、トポロジカルソート用の Unix プログラム
• フィードバックアークセット、つまり、除去することで残りのサブグラフを位相的にソートできるエッジの集合
• Tarjanの強連結成分アルゴリズムは、グラフ内の強連結成分の位相的にソートされたリストを提供するアルゴリズムである。
• 前位相的秩序

• DE Knuth著『The Art of Computer Programming』第 1 巻、セクション 2.2.3 では、部分順序のトポロジカル ソートのアルゴリズムと簡単な歴史が説明されています。
• Bertrand Meyer著『Touch of Class: Learning to Program Well with Objects and Contracts』、Springer、2099 年、第 15 章「アルゴリズムの考案とエンジニアリング: トポロジカル ソート」では、データ構造設計、API 設計、ソフトウェア エンジニアリングの問題を考慮したトポロジカル ソート (カーンのアルゴリズムのバリエーションを使用) の詳細な教育的プレゼンテーションについて、最新のプログラミング言語を使用して説明しています。

• NIST アルゴリズムとデータ構造辞書: トポロジカルソート
• ワイスタイン、エリック W.、「トポロジカルソート」、MathWorld