テックツリーと​DAG — 依存関係の​正体

ゲームの​「クラフトツリー」は​CS​（＝コンピュータサイエンス）の​用語で​正確には​DAG​（有向非循環グラフ）と​呼ばれる​構造である。​npm install や​ make、​CI​（＝継続的インテグレーション。​コードの​変更を​自動で​ビルド・テストする​仕組み）の​ジョブ順序付けも、​すべて​同じ​仕組みで​動いている。

テックツリーとは​何か

テックツリーとは​「Bを​作るには​Aが​先に​必要」と​いう​関係を​矢印で​つないだ図である。​例と​して、​Dr.STONE の​硫黄から​硫酸を​経て​サルファ剤に​至る​流れ、​Minecraft の​レシピ、​Civilization の​テックツリーが​挙げられる。​いずれも​素材から​中間生成物を​経て​最終成果物に​至る​流れを、​有向の​矢印で​つなぐと​いう​共通パターンを​持つ。

DAGを​3語で​理解する

DAG​（Directed Acyclic Graph、​有向非循環グラフ）は​3つの​性質で​説明できる。​グラフ（Graph）とは​ノード​（点）を​エッジ​（線）で​つないだ構造である。​有向​（Directed）とは​矢印に​向きが​ある​ことを​指し、​「Aは​Bの​材料である」と​いう​関係を​表す。​非循環​（Acyclic）とは​ループが​存在しない​ことを​指し、​「Cは​Dが​必要、​Dは​Cが​必要」と​いうような​循環依存が​あると、​実行順序を​決定できなくなる。

トポロジカルソート​（位相的整列）

トポロジカルソートとは、​DAGの​ノードを​依存関係を​満たす順に​一列に​並べる​操作である。​代表的な​アルゴリズムには、​入次数​（＝​その​ノードに​向かう​矢印の​数）が​0の​ノードから​順に​キューへ​入れていく​カーンの​アルゴリズムと、​DFS​（深さ優先探索）の​結果を​逆順に​たどる​方​法が​ある。​この​操作は​ make、​npm install、​CIパイプライン、​タスクスケジューラの​内部で​実際に​使われている。

描画ライブラリの​選び方

DAGを​図と​して​描く​ライブラリには​いく​つかの​選択肢が​ある。​Mermaid​（マーメイド）は​テキスト記法で​ドキュメントや​READMEに​向いており、flowchart LRと​いう​書き方で​DAGを​表現できる。​React Flow は​Webアプリへの​組み込みに​向いており、​ノードを​ドラッグできる​インタラクティブな​表示が​できる。​D3 / d3-dag は​完全に​カスタムできる分、​自由度が​最大である​一方、​実装コストも​最大に​なる。

依存関係の​グラフは​必ずDAGに​なる。​トポロジカルソートを​使えば、​ビルドや​インストールの​正しい​実行順序が​自動で​決まる。