システムの依存関係をDAG（指示された非環式グラフ）としてマッピングできることの利点は何ですか？

Question

オブジェクトの依存関係のコレクションをDAGに整理する場合、それはどのような状況で、BDDなどの別のデータ構造（バイナリ決定図）よりも望ましいでしょうか？

Answer 1

DAGには、依存関係を分析するのに理想的ないくつかのプロパティがあります。

まず、システムの「ベースレベル」コンポーネントを簡単に識別できます。これらは、エッジが入っていないダグのノードです。システムの相対層を知ることは、リファクタリングの影響を知っていることを意味します。 （チェーンのすべて。）

第二に、DAGを作成できる場合、システムには奇妙な相互依存関係がないことがわかります。依存関係グラフのサイクルは、奇妙なバグとビルドエラーのレシピである互いに依存する2つのコンポーネントがあることを意味します。 Microsoftでは、呼ばれるツールを使用しました Asmmeta この問題を回避するために。

Answer 2

私はバイナリの決定図についてあまり知識がありませんが、ウィキペディアは、それらが根本的に指示され、非環式グラフであると述べているようです。私はダグについて少し知っています。問題をDAGとして表現できる場合は、サイクルがないことを確認できます（Chris Smithが前述したように）。

ここで関連するかもしれない（またはそうでないかもしれない）バイナリ決定ツリーの別の属性は、それらがバイナリであるということです。ただし、問題をバイナリ決定図にどのようにモデル化したいかわかりません。 BDDにはゼロがあり、各ノードで1つまたは2つの選択肢があるようです。依存関係をこれにどのようにマッピングするかを見るのは難しいです。依存関係をグラフにマッピングすることは、私にとってはるかに理にかなっています。

主に、それはあなたがあなたの表現で実行したいアルゴリズムに依存するだけだと思います。あなたがダグを持っていると確信していない場合、あなたは サイクル検出アルゴリズム それがそうであるかどうかを伝えるために。最短パスを見つけたい場合は、実行できます ディクストラ その上。これは本当にあなたがやりたいことに依存していると思います。そして、私はあなたが一般的なグラフでできることを知っています。ダグを手に入れたら、私が確立したいことのほとんどが確立されました。それは私だけです。

-Brian J. Stinar-