依存関係グラフ

Directed graph representing dependencies

数学、コンピュータサイエンス、デジタルエレクトロニクスにおいて、依存グラフとは、複数のオブジェクト間の依存関係を表す有向グラフです。依存グラフから、与えられた依存関係を尊重する評価順序、あるいは評価順序が存在しないことを導出することができます。

意味

AはBとCに依存し、BはDに依存する

オブジェクトのセットと、依存関係「a はbに依存」(「a は最初にbを評価する必要がある」) をモデル化した推移関係が与えられた場合、依存関係グラフはRの推移的縮小を持つグラフになります。 ${\displaystyle S}$ ${\displaystyle R\subseteq S\times S}$ ${\displaystyle (a,b)\in R}$ ${\displaystyle G=(S,T)}$ ${\displaystyle T\subseteq R}$

たとえば、簡単な計算機があるとします。この計算機は、変数に定数値を割り当て、2 つの変数の合計を 3 番目の変数に割り当てます。「A = B + C ; B = 5+ D ; C =4; D =2;」のような方程式がいくつかある場合、および となります。この関係を直接導くことができます。A はBとCに依存します。これは、2 つの変数を加算できるのは、両方の変数の値を知っている場合のみであるためです。したがって、 A を計算する前に、 Bを計算する必要があります。B を計算するには D に依存しているため、 AもDを計算してから計算する必要があります(これが上記の推移的性質です)。一方、CとDの値は数値リテラルであるため、すぐにわかります。 ${\displaystyle S=\{A,B,C,D\}}$ ${\displaystyle R=\{(A,B),(A,C),(B,D),(A,D)\}}$

不可能な評価を認識する

依存関係グラフにおいて、依存関係の循環（循環依存関係とも呼ばれる）は、循環内のどのオブジェクトも最初に評価されないため、有効な評価順序が存在しない状況につながります。依存関係グラフに循環依存関係がない場合、それは有向非巡回グラフを形成し、位相ソートによって評価順序を見つけることができます。ほとんどの位相ソートアルゴリズムは、入力内の循環を検出することもできますが、検出された循環を適切に処理するために、位相ソートとは別に循環検出を実行することが望ましい場合があります。

先ほどの単純な計算機を例に挙げましょう。方程式系「A = B ; B = D + C ; C = D + A ; D =12; 」には、 A、B、Cによって形成される循環依存関係が含まれています。つまり、 BはAより前に評価されなければならず、C はBより前に評価されなければならず、A はCより前に評価されなければなりません。

評価順序の導出

正しい評価順序とは、依存グラフのノードを形成するオブジェクトに、次の式が成り立つように番号を付けることです。で。つまり、番号付けによって2つの要素と が順序付けられ、がの前に評価される場合、 はに依存してはなりません。 ${\displaystyle n:S\rightarrow \mathbb {N} }$ ${\displaystyle n(a)<n(b)\Rightarrow (a,b)\notin R}$ ${\displaystyle a,b\in S}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$

正しい評価順序は複数存在する可能性があります。実際、正しい番号付けは位相順序であり、任意の位相順序は正しい番号付けです。したがって、正しい位相順序を導出するアルゴリズムは、正しい評価順序も導出します。

先ほどの簡単な計算機をもう一度考えてみましょう。「A = B + C ; B = 5+ D ; C =4; D =2;」という方程式系を考えると、正しい評価順序は ( D , C , B , A )です。しかし、 ( C , D , B , A ) も正しい評価順序です。

モノイド構造

非巡回依存グラフは次のようにトレースモノイドのトレースに対応する: ^{[1] : 12}

• 関数は各頂点にアルファベットの記号をラベル付けする ${\displaystyle \phi :S\to \Sigma }$ ${\displaystyle \Sigma }$
• 依存関係にある場合にのみ、エッジまたはが存在します。 ${\displaystyle a\to b}$ ${\displaystyle b\to a}$ ${\displaystyle (\phi (a),\phi (b))}$ ${\displaystyle D}$
• 2 つのグラフのラベルとエッジが対応している場合、それらのグラフは等しいとみなされます。

すると、正しい評価順序で並べられた頂点ラベルで構成される文字列が、トレースの文字列に対応します。

モノイド演算は、2つのグラフの頂点集合の互いに素な和集合を取り、各グラフの既存の辺を保存し、依存関係が許す限り、最初のグラフから2番目のグラフへ新しい辺を描く。[ ^{1] : 14} ${\displaystyle (S_{12},R_{12})=(S_{1},R_{1})\bullet (S_{2},R_{2})}$ ${\displaystyle S_{12}=S_{1}\sqcup S_{2}}$

${\displaystyle R_{12}=R_{1}\sqcup R_{2}\sqcup \{(a,b)\mid a\in S_{1}\land b\in S_{2}\land (\phi (a),\phi (b))\in D\}}$

アイデンティティは空のグラフです。

例

依存関係グラフは次の場合に使用されます。

• 自動ソフトウェアインストーラー：グラフを辿り、必要なのにまだインストールされていないソフトウェアパッケージを探します。依存関係はパッケージ間の結合によって決まります。
• Unix Make、Node npm install、php composer、Twitter bower install、Apache Antなどのソフトウェアビルドスクリプト。これらのスクリプトは、どのファイルが変更されたかを把握する必要があるため、正しいファイルのみを再コンパイルする必要があります。
• コンパイラ技術と形式言語実装において:
  • 命令のスケジューリング:アセンブリ命令または中間命令のオペランドの依存関係グラフが計算され、命令の最適な順序を決定するために使用されます。
  • デッドコードの除去: 副作用のある操作が変数に依存していない場合、この変数はデッドコードとみなされ、削除できます。
• 動的グラフ分析：GraphBolt ^[2]とKickStarter ^{[3]は、グラフ構造が変化したときに}増分計算のために値の依存関係をキャプチャします。
• スプレッドシート計算機。この記事で使用した例と同様の正しい計算順序を導き出す必要があります。
• モデル内のデータが変更された場合にどの視覚要素を更新するかを把握するためのXFormsなどの Web フォーム標準。
• ビデオゲーム、特にパズルゲームやアドベンチャーゲームは、ゲーム内のアクション間の依存関係のグラフとして設計されることが多い。^[4]

依存関係グラフは次の 1 つの側面です。

• 製造工場の種類: 原材料はいくつかの従属段階を経て製品に加工されます。
• ジョブショップスケジューリング: コンピュータサイエンスにおける関連する理論的問題のコレクション。

参照

• コールグラフ
• 優先順位グラフ
• トポロジカルソート
• データ依存性

参考文献

1. Mazurkiewicz, Antoni (1995). 「トレース理論入門」(PDF) . Rozenberg, G.; Diekert, V. (編). 『トレースの書』 シンガポール: World Scientific. ISBN 981-02-2058-8. 2021年4月18日閲覧。
2. Mugilan Mariappan; Keval Vora (2019). 「GraphBolt: ストリーミンググラフの依存関係駆動型同期処理」.ヨーロッパコンピュータシステム会議 (EuroSys'19) . pp. 25:1–25:16. doi :10.1145/3302424.3303974.
3. Keval Vora、Rajiv Gupta、Guoqing Xu (2017). 「KickStarter: トリム近似によるストリーミンググラフの高速かつ正確な計算」.プログラミング言語とオペレーティングシステムのアーキテクチャサポートに関する国際会議 (ASPLOS'17) . pp.  237– 251. doi : 10.1145/3093337.3037748 .
4. ギルバート、ロン. 「パズルの依存関係チャート」. Grumpy Gamer . 2020年1月11日閲覧。

さらに読む

• Balmas, Francoise (2001)依存関係グラフの表示：階層的アプローチ Archived 2012-02-11 at the Wayback Machine , [1] wcre, p. 261, 第8回リバースエンジニアリング会議 (WCRE'01)

Retrieved from "https://en.wikipedia.org/w/index.php?title=Dependency_graph&oldid=1321487336"