強連結成分分解とトポロジカルソート

有向グラフの構造を解析する基盤アルゴリズム群。

強連結成分 (SCC)

有向グラフで任意の 2 頂点 $i,j$ について $i\to j$ かつ $j\to i$ の経路がある頂点同士を同じ成分にまとめる。強連結成分分解で各成分を 1 頂点に縮約 (condensation) すると DAG が得られる。

トポロジカルソート

DAG の頂点を、全ての辺が前方を向くように一列に並べる。依存関係の直列化に使い、巡回除去で DAG 化した後に適用するのが serigraph のパイプライン。

関連手法

• 木分解 (Tree Decomposition) — 木幅を定義してグラフを木にマッピングする。グラフの分割・近似に使う。
• PageRank — 遷移行列の定常状態でノードを重み付ける。グラフ上の重要度算出。
• 並列グラフ簡約 — プログラムを DAG として表現し各部分を並列評価する。データ競合が本質的にこの処理内に閉じるため、デッドロック等を意識せず並列実行できる。

関連: feedback-arc-set / minimum-spanning-tree / _moc-algorithm