# トポロジカルソート ## 定義 トポロジカルソート(topological sort)とは、有限DAG(有向非巡回グラフ、[[有向グラフ]]参照)の全頂点の列であって、各頂点 `v` がそこから到達可能な他の全頂点より前に現れるものをいう。有限DAGは必ずトポロジカルソートを持つ(定理9.5.4)。この定理は、DAGの**極小元(minimal element)**——他のどの頂点からも到達不能な頂点——を1つ選んで取り除き、残りのDAGに対して同じ操作を再帰的に繰り返すという構成的な証明で示される。1つのDAGに対してトポロジカルソートは一般に複数存在し、極小元でなく**極大元(maximal element)**から構成する方法や、頂点を任意の順に選んで挿入できる位置に挿入する方法でも構成できる。トポロジカルソートは逐次実行(one task at a time)の順序付けであるのに対し、複数の処理装置で同時実行できる場合は**並列スケジュール(parallel schedule)**を考える——これは頂点集合 `V(D)` を「同じステップで実行できる頂点の集合」であるブロック `A_0, A_1, ...` に分割する`partition`であり、`j<k` のとき `A_k` のどの頂点も `A_j` のどの頂点からも到達不能であることを要求する。無限個の処理装置がある場合、全タスクの完了に要する最小時間(並列時間)は**臨界路(critical path)**——比較可能な頂点からなる最大の集合である**鎖(chain)**のうち最大のもの——のサイズに一致する(系9.5.9「並列時間=臨界路のサイズ」)。各頂点の**深さ(depth)**を「その頂点で終わる最大の鎖に含まれる、それより小さい要素の個数」と定義すると、`A_k := {a | depth(a) = k}` という深さによる層分割が、最小時間を達成する具体的な並列スケジュールになる(定理9.5.8)。これらの結果からDilworthの補題(補題9.5.12)が導かれる: `t>0` について、n頂点のDAGは大きさ `t` を超える鎖か、大きさ `n/t` 以上の**反鎖(antichain、どの2頂点も比較不能な頂点集合)**のいずれかを持つ。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]]) ## 横断的知見 (この concept は本 ingest が初出のため、複数ソースの突き合わせによる横断的知見はまだない。スケジューリング・依存関係解決を扱う他ソースが ingest された際にここへ追記する。) ## 未解決の問い - 章では処理装置数が無限の場合の最小時間(臨界路サイズ)のみを厳密に扱い、処理装置数が制限された場合の最小時間の一般式は演習問題(Problem 9.20)に委譲されている。有限個のp個の処理装置での最小時間 `M(n,t,p)` の一般公式は本文で示されていない。 - 実務のジョブスケジューラ(cron依存関係、CIパイプラインのDAG実行、ビルドシステムの依存解決)は本章のトポロジカルソート・並列スケジュールの理論とどこまで一致し、どこで乖離するか(例: タスクの実行時間が不均一な場合)。本章はタスクの所要時間が全て等しい単純化を置いている。 ## 関連 - 概念: [[有向グラフ]] / [[半順序]] / [[同値関係]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 9 Directed graphs & Partial Orders]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 9.