DAG（有向非巡回グラフ）の基礎とトポロジカルソートによる実務応用ガイド
エバープレイ編集部DAG（Directed Acyclic Graph）とは
DAG（有向非巡回グラフ、Directed Acyclic Graph）は、ノード（頂点）とそれらを結ぶ有向辺から構成されるグラフの一種で、どのノードから出発しても同じノードに戻ってくるような「有向サイクル（巡回）」を含まないという性質を持ちます。つまり、有向辺の向きに沿って辿っていった場合、必ず終点に到達しループしない構造です。
基本的な性質
- 非巡回性: 有向サイクルが存在しないことが定義の核心です。自己ループや循環経路があればDAGではありません。
- 部分順序の表現: DAGは事象やタスク間の「先行関係（依存関係）」を表現できます。例えば「Aの後にBを実行する必要がある」なら、A → Bという有向辺で表せます。
- トポロジカル順序: DAGの頂点には、すべての有向辺 (u → v) について u が v の前に来る順序（トポロジカルソート）が存在します。トポロジカル順序は必ず少なくとも一つ存在します。
- アルゴリズム的性質: 多くの問題（最長経路、最短経路、到達可能性など）は、DAGでは効率よく（線形時間に近い）解けます。代表的には O(V + E) の時間で処理できることが多いです。
トポロジカルソートと主要アルゴリズム
トポロジカルソートはDAGの中心的操作です。主に次の2つの方法があります。
- Kahnのアルゴリズム:
- 入次数が0のノードをキューに入れる。
- キューからノードを取り出して出力し、そのノードから出る辺を取り除き、辺先の入次数が0になったらキューに入れる。
- すべての辺を処理できればトポロジカル順序が得られる。途中で処理済みのノードが全てでないのにキューが空になればサイクルがある。
- 深さ優先探索（DFS）を用いる方法:
- 各ノードを未訪問→訪問中→完了の状態で管理し、訪問中に訪れるノードが再度訪問されるとサイクル検出となる（オトッカリング）。
- 再帰終了時にノードをスタックに積むと、スタックの逆順がトポロジカル順序になる。
どちらの方法も計算量は O(V + E) です（Vは頂点数、Eは辺数）。
DAGで効率化できる問題例
- 最長経路問題: 一般グラフではNP困難な場合がありますが、DAGではトポロジカル順序に従って動的計画法を行えば O(V + E) で解けます（負の辺があっても可）。
- 最短経路: 重み付きDAGの単一始点最短経路もトポロジカル順序を利用して線形時間で計算可能です。
- 到達可能性・依存関係解析: コンパイラの最適化、ビルドシステムの依存解決、ワークフローエンジンにおけるタスクスケジューリングなど。
- トランジティブ・クロージャ／リダクション: 到達可能性行列の事前計算（トランジティブ・クロージャ）や冗長な辺を取り除くトランジティブ・リダクションもDAG上で意味を持ちます。
代表的な応用分野と具体例
- ワークフロー管理（ETL・バッチ処理）:
Apache Airflow、Luigi、Prefect 等のワークフローエンジンは「DAG」という概念を主要なデータ構造として使います。ここでのノードはタスク、辺はタスク依存を表し、トポロジカル順でジョブをスケジュールします。実装上はDAGクラスでタスクの定義や依存関係を管理します（注意: Airflowの「DAG」は実世界のDAG概念を実装したもので、メタ情報やスケジューリングポリシーが付加されています）。
- バージョン管理（Git）:
Gitのコミット履歴は親コミットへの参照を持つ有向グラフで、基本的に過去に戻る循環は発生しないためDAGとして扱えます（ブランチやマージがあるがサイクルは作らない）。これが履歴の部分順序性を保証します。
- 確率的グラフィカルモデル（ベイジアンネットワーク）:
ベイジアンネットワークは確率変数間の有向因果依存をDAGで表します。非巡回性により因果関係の整合性が保たれ、条件付き独立性の解析が可能になります。
- ブロックチェーン代替のデータ構造:
一部の分散台帳技術（IOTAのTangleやNanoのブロックDAGなど）は、直列のブロックチェーンの代わりにDAGベースの構造を採用して高い並列性やスループットを目指しています。ただし、コンセンサスや二重支出防止の設計はチェーン型と異なり慎重な検討が必要です。
- コンパイラ最適化・式の再構成:
式や命令の依存関係をDAGで表現し、共通部分式の除去や命令スケジューリングに利用します（基本ブロック内のDAG化など）。
実装上のポイント
- 表現方法: 辺が疎な場合は隣接リスト（Adjacency List）が適切で、密な場合は隣接行列が使われます。膨大なグラフには圧縮表現や外部記憶が必要になります。
- 循環検出: KahnやDFSによるトポロジカルソートで容易に検出できます。ライブラリやフレームワークでは事前に循環チェックを行い、依存の設定ミスを通知することが重要です。
- トポロジカル順序の一意性: DAGのトポロジカル順序は一意でないことが多いです（複数の入次数0のノードをどの順で処理するかで変わる）。順序の安定性が必要なら追加の優先度ルールを設けます。
- 並列実行: トポロジカル順に従えば依存のないノードは並列に実行可能です。スケジューラ実装ではリソース制約や優先度を考慮して並列度を制御します。
DAGの利点と欠点
- 利点
- 依存関係を明確に表現できるため分析や最適化が容易。
- トポロジカル順序によりスケジュールや最短/最長経路が効率的に求まる。
- 並列性を取り込みやすく、パフォーマンス向上に寄与する。
- 欠点／課題
- 循環があると破綻するため、実世界の循環依存をどう分離するかの設計が必要。
- 分散環境ではDAG構造の正当性（整合性）を保つための合意形成や整合性チェックが複雑になる。
- 大規模DAGではトランジティブ・クロージャや到達性クエリが重くなるため専用インデックスが必要。
よくある誤解と注意点
- ツリーと同じではない: ツリーは一つの根を持つ特別なDAG（ただしツリーは各ノードが親を1つだけ持つという制限がある）。DAGはより一般的で、複数の親を持つノードが許されます。
- 有向だが巡回するグラフはDAGではない: エッジに向きがあるだけでなく巡回がないことが必須です。
- Airflowの「DAG」は実装概念: Airflow等のプロダクトで使われるDAGはワークフローやスケジューリング用に拡張されたオブジェクトであり、純粋な数学的DAGにメタデータ（スケジュール、リトライ設定等）が付与されています。
実務でのポイント（チェックリスト）
- 依存関係の定義に漏れや逆向きがないかを検証する（自動テストで循環検出を組み込む）。
- トポロジカルソートの結果が複数候補になる場合、実行順序の優先度ルールを明確にする。
- 並列実行時の副作用（競合するリソース、外部状態の変更）を設計で吸収する。
- 大規模DAGでは到達性クエリのためのインデックスや、部分グラフのキャッシュを検討する。
- 分散・耐障害性が必要な場合は、DAGの永続化と一貫性確保（トランザクション、リコンシリエーション）を設計する。
まとめ
DAGは「有向であり、かつ巡回がない」ことで、順序関係や依存性を明確に扱える強力なデータ構造です。トポロジカルソートや動的計画法により多くの問題が効率よく解け、ワークフロー管理、バージョン管理、確率モデル、分散台帳など広範な分野で利用されています。一方で、循環の管理や大規模化に伴う性能・整合性の課題もあり、実装や運用では注意が必要です。
参考文献
- Directed acyclic graph — Wikipedia
- Topological sorting — Wikipedia
- Kahn's algorithm — Wikipedia
- Apache Airflow — Documentation
- Pro Git — Git Documentation
- Bayesian network — Wikipedia
- IOTA (cryptocurrency) — Wikipedia
- Nano (cryptocurrency) — Wikipedia
投稿者プロフィール
