位相ソート

コンピュータサイエンスにおいて、有向グラフの位相ソートまたは位相順序付けとは、頂点uから頂点vへのすべての有向辺(u,v)において、u がvよりも前に来るような頂点の線形順序付けです。例えば、グラフの頂点は実行すべきタスクを表し、辺は、あるタスクが他のタスクよりも先に実行されなければならないという制約を表す場合があります。このアプリケーションでは、位相順序付けとは、タスクの有効な順序付けに過ぎません。

正確には、位相ソートとは、各ノードv は、その依存関係をすべて訪問した後にのみ訪問されるグラフ走査です。位相順序付けは、グラフに有向閉路がない場合、つまり有向非巡回グラフ(DAG) である場合にのみ可能です。任意の DAG には少なくとも 1 つの位相順序付けがあり、それを構築するための線形時間アルゴリズムが存在します。位相ソートは多くの用途があり、特にフィードバックアークセットなどのランキング問題で役立ちます。位相ソートは、DAG に切断されたコンポーネントがある場合にも可能です。

例

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

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

アルゴリズム

位相ソートの通常のアルゴリズムは、ノード数とエッジ数の合計に比例して実行時間が増加する。 $O(\left|{V}\right|+\left|{E}\right|).$

カーンのアルゴリズム

これらのアルゴリズムの1つは、カーン（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 et al. (2001)によって説明されたものです。^[³^]これは、1976年にTarjanによって初めて印刷物で説明されたようです。^[⁴^]

並列アルゴリズム

並列ランダムアクセスマシンでは、多項式数のプロセッサを用いてO ((log n ) ² )時間で位相的順序付けを構築することができ、この問題は計算量クラスNC2に分類される。^{[ 5 ]}^これを実現する一つの方法は、最小値プラス行列乗法を用いて最小値プラス行列乗法で最小化の代わりに最大値を求めることで、与えられたグラフの隣接行列を対数的に何度も繰り返し二乗することである。結果として得られる行列はグラフ内の最長経路距離を表す。頂点を最長入線経路の長さでソートすることで位相的順序付けが得られる。^[⁶^]

分散メモリマシン上で並列位相ソートを行うアルゴリズムは、DAG のカーンのアルゴリズムを並列化するものである^[⁷^]。高レベルでは、カーンのアルゴリズムは入次数 0 の頂点を繰り返し削除し、削除された順に位相ソートに追加する。削除された頂点の出力エッジも削除されるため、入次数 0 の新しい頂点セットが生成され、この手順は頂点がなくなるまで繰り返される。このアルゴリズムは反復処理を実行する。ここで、 $Dは$ $G$ における最長パスである。各反復処理は並列化可能であり、これが以下のアルゴリズムの考え方である。 $G=(V,E)$ $D+1$

以下では、グラフ分割が $p個の$ 処理要素（PE）に格納され、各PEはとラベル付けされていると仮定します。各PE $i は、$ 入次数0で局所頂点の集合を初期化します。ここで、上位インデックスは現在の反復を表します。局所集合内のすべての頂点の入次数は0、つまり隣接していないため、有効な位相ソートのために任意の順序で与えることができます。各頂点にグローバルインデックスを割り当てるために、のサイズにわたってプレフィックスの合計が計算されます。したがって、各ステップで、位相ソートに頂点が追加されます。 $0,\dots ,p-1$ $Q_{i}^{1}$ $Q_{0}^{1},\dots ,Q_{p-1}^{1}$ $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}$ $Q_{j}^{1}$ $Q_{j}^{1}$ $(u,v)$ $l,j\neq l$ $(u,v)$ $Q_{j}^{1}$ $(u,v)$ $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}$ $a_{k-1}$ $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 \in 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 ～ p - 1) Q内の頂点の隣接ノードにすべてのメッセージを配信する ローカル頂点Vのメッセージを受信する Q内のすべての頂点を削除する 受信したメッセージ( u,v )ごとに: --δ[v] = 0の場合Qのグローバルサイズが0より大きい場合、Qにv を追加するローカルオーダー を返す

通信コストは与えられたグラフの分割に大きく依存する。実行時間に関しては、定数時間でフェッチ・アンド・デクリメントが可能なCRCW-PRAMモデルでは、このアルゴリズムはで実行される。ここで、 $Dは$ $G$ における最長パス、 $Δは$ 最大次数である。^[⁷^] ${\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}$

最短経路探索への応用

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

$d を$ $V と同じ長さの配列とします。これは s からの最短経路距離を保持します。d [$ $s$ ] = $0$ 、それ $以外の場合$ は $d [u] = \infty$ とします。
$p を$ $V$ と同じ長さの配列とし、すべての要素をnilに初期化する。各 $p [u]は、$ $sから$ $u$ への最短経路における $u$ の先行要素を保持する。
Vのsから始めて、頂点uを順番にループします。
- uに直接続く各頂点vについて（つまり、 uからvへの辺が存在する場合）：
  - $w を$ $uから$ $v$ への辺の重みとします。
  - エッジを緩和する: d [ v ] > d [ u ] + wの場合、
    - $d [v] \leftarrow d [u] + w$ 、
    - $p [v] \leftarrow u$ .

同様に:

$d を$ $V と同じ長さの配列とします。これは s からの最短経路距離を保持します。d [$ $s$ ] = $0$ 、それ $以外の場合$ は $d [u] = \infty$ とします。
$p を$ $V$ と同じ長さの配列とし、すべての要素をnilに初期化する。各 $p$ $[$ $u$ $]は、$ $sから$ $u$ への最短経路における $u$ の先行要素を保持する。
Vのsから始めて、頂点uを順番にループします。
- 各頂点vからuへ（つまり、 vからuへの辺が存在する）:
  - $w を$ $vから$ $u$ への辺の重みとします。
  - エッジを緩和する: d [ u ] > d [ v ] + wの場合、
    - $d [u] \leftarrow d [v] + w$ ,
    - $p [u] \leftarrow v$ .

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

ユニークさ

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

半順序との関係

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

スケジューリング最適化との関係

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

参照

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

参考文献

^ Jarnagin, MP (1960), PERTネットワークの一貫性をテストする自動機械法、技術覚書No. K-24/60、バージニア州ダールグレン：米国海軍兵器研究所
^カーン、アーサー・B.（1962）、「大規模ネットワークのトポロジカルソート」、Communications of the ACM、5（11）：558–562、doi：10.1145/368996.369025、S2CID 16728233
^ ^a ^b ^cコーメン、トーマス・H. ;レイソン、チャールズ・E. ;リベスト、ロナルド・L. ;スタイン、クリフォード(2001)、「セクション22.4: トポロジカルソート」、アルゴリズム入門（第2版）、MITプレスおよびマグロウヒル、pp. 549– 552、ISBN 0-262-03293-7
^ Tarjan, Robert E. (1976)、「辺分離スパニングツリーと深さ優先探索」、Acta Informatica、6 (2): 171– 185、doi : 10.1007/BF00268499、S2CID 12044793
^クック、スティーブン・A.（1985）、「高速並列アルゴリズムに関する問題の分類」、情報制御、64（1-3）：2-22、doi：10.1016/S0019-9958（85）80041-3
^ Dekel, Eliezer; Nassimi, David; Sahni, Sartaj (1981)、「並列行列およびグラフアルゴリズム」、SIAM Journal on Computing、10 (4): 657– 675、doi : 10.1137/0210049、MR 0635424
^ ^a ^bサンダース、ピーター; メルホーン、カート; ディーツフェルビンガー、マーティン; デメンティエフ、ローマン (2019)、シーケンシャルおよびパラレルアルゴリズムとデータ構造：基本ツールボックス、シュプリンガーインターナショナルパブリッシング、ISBN 978-3-030-25208-3
^ Vernet, Oswaldo; Markenzon, Lilian (1997)、「Hamiltonian problems for reducible flowgraphs」（PDF）、Proceedings: 17th International Conference of the Chilean Computer Science Society、pp. 264– 267、doi : 10.1109/SCCC.1997.637099、hdl : 11422 /2585 、ISBN 0-8186-8052-0、S2CID 206554481

さらに読む

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、2009 年、第 15 章「アルゴリズムの考案とエンジニアリング: トポロジカルソート」では、データ構造設計、API 設計、ソフトウェアエンジニアリングの問題を考慮したトポロジカルソート (カーンのアルゴリズムのバリエーションを使用) の詳細な教育的プレゼンテーションとして、最新のプログラミング言語を使用しています。

外部リンク

[Jarnagin-1] Jarnagin, MP (1960), PERTネットワークの一貫性をテストする自動機械法、技術覚書No. K-24/60、バージニア州ダールグレン：米国海軍兵器研究所

[Kahn-2] カーン、アーサー・B.（1962）、「大規模ネットワークのトポロジカルソート」、Communications of the ACM、5（11）：558–562、doi：10.1145/368996.369025、S2CID 16728233

[CLRS-3] コーメン、トーマス・H. ;レイソン、チャールズ・E. ;リベスト、ロナルド・L. ;スタイン、クリフォード(2001)、「セクション22.4: トポロジカルソート」、アルゴリズム入門（第2版）、MITプレスおよびマグロウヒル、pp. 549– 552、ISBN 0-262-03293-7

[Tarjan-4] Tarjan, Robert E. (1976)、「辺分離スパニングツリーと深さ優先探索」、Acta Informatica、6 (2): 171– 185、doi : 10.1007/BF00268499、S2CID 12044793

[Cook-5] クック、スティーブン・A.（1985）、「高速並列アルゴリズムに関する問題の分類」、情報制御、64（1-3）：2-22、doi：10.1016/S0019-9958（85）80041-3

[DNS-6] Dekel, Eliezer; Nassimi, David; Sahni, Sartaj (1981)、「並列行列およびグラフアルゴリズム」、SIAM Journal on Computing、10 (4): 657– 675、doi : 10.1137/0210049、MR 0635424

[SMDD-7] サンダース、ピーター; メルホーン、カート; ディーツフェルビンガー、マーティン; デメンティエフ、ローマン (2019)、シーケンシャルおよびパラレルアルゴリズムとデータ構造：基本ツールボックス、シュプリンガーインターナショナルパブリッシング、ISBN 978-3-030-25208-3

[VM-8] Vernet, Oswaldo; Markenzon, Lilian (1997)、「Hamiltonian problems for reducible flowgraphs」（PDF）、Proceedings: 17th International Conference of the Chilean Computer Science Society、pp. 264– 267、doi : 10.1109/SCCC.1997.637099、hdl : 11422 /2585 、ISBN 0-8186-8052-0、S2CID 206554481

[

[ 2 ]

[

[

[ 5 ]

[

[

[