トポロジカルソート

これらのアルゴリズムの1つは、カーン（1962）によって最初に記述されたもので、最終的なトポロジカルソートと同じ順序で頂点を選択することによって機能します。^{[ 2 ]}まず、入力エッジを持たない「開始ノード」のリストを見つけて、それらをセットSに挿入します。少なくとも1つのそのようなノードは、空でない（有限）非巡回グラフに存在しなければなりません。次に、

L ← ソートされた要素を含む空のリスト S ← 入力エッジを持たないすべてのノードの集合 S が空でない間 、ノードnをSから削除し、 nをLに 追加する。nからmへのエッジeを持つ各ノードmについて、 エッジeをグラフから 削除する。mに他の入力エッジがない場合、mをSに挿入 する。グラフに辺が存在する場合は エラー （グラフに少なくとも1つのサイクルが存在する）を返し、そうでない場合はL （トポロジカルにソートされた順序）を返す。

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

結果として得られるソートの非一意性を反映して、構造 S は単なる集合、キュー、またはスタックのいずれかになります。集合 S からノード n が削除される順序に応じて、異なる解が生成されます。辞書式順序で同順位を解消する Kahn アルゴリズムの変種は、並列スケジューリングと階層型グラフ描画のためのCoffman–Graham アルゴリズムの重要な構成要素となっています。

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

L ← ソートされたノードを含む空のリスト。 永続的なマークのないノードが存在する間、 マークされていないノードnを選択します。visit ( n )function visit(node n ) もしnに永続的なマークが付いているなら、戻ります。もしnに一時的なマークが付いているなら、停止します（グラフには少なくとも1つのサイクルがあります）。nに一時的な印 を付ける nからmへのエッジを持つ各ノードmについて、 visit( m )を実行します。nに油性マーク を付けるLの先頭にn を追加する

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

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

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

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

最初のステップでは、PE jはインデックスを割り当てます${\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)}$別のPEのエンドポイントvと${\displaystyle l,j\neq l}$メッセージ${\displaystyle (u,v)}$PE lに投稿されます。すべての頂点が${\displaystyle Q_{j}^{1}}$削除されると、投稿されたメッセージは対応する PE に送信されます。各メッセージ${\displaystyle (u,v)}$ローカル頂点vの入次数を更新します。入次数がゼロに低下した場合、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 localOrder[u] = index++; E の各要素(u,v) に対して、頂点vを所有する PE にメッセージ ( u, v ) を投稿します。nrOfVerticesProcessed += sum(|Q i |, i = 0 to p - 1) Q内の頂点の隣接頂点にすべてのメッセージを配信する ローカル頂点Vのメッセージを受信する Q内のすべての頂点を削除する 受信した各メッセージ ( u, v ) について: --δ[v] = 0の場合Qのグローバルサイズが0より大きい間、vをQ に 追加するreturn localOrder

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