能够将系统的依赖项映射为DAG（定向的无环图）有什么好处？

Question

如果我要将对象的依赖关系集合到DAG中，那么在哪种情况下，比其他数据结构（例如BDD（二进制决策图））更可取？

Answer 1

DAG具有几个属性，非常适合分析依赖关系。

首先，您可以轻松识别系统的“基础级别”组件。这些是DAG中的节点，没有任何边缘。了解系统的相对层意味着您知道重构的影响。 （链条的一切。）

其次，如果您能产生一个DAG，您会知道该系统没有奇怪的相互依存关系。依赖图中的周期将意味着您有两个彼此依赖的组件 - 奇怪的错误和构建错误的食谱。在微软，我们使用了一种称为的工具 ASMMETA 解决这个问题。

Answer 2

我对二进制决策图的了解不太了解，但是Wikipedia似乎声明它们是从根本上定向的，无环形的。我对达格有些了解。如果您可以将问题表示为DAG，则可以确保没有任何周期（如前所述的克里斯·史密斯（Chris Smith））。

二进制决策树的另一个属性可能（或可能不相关）是它们是二进制的。但是，我不确定如何将问题建模为二进制决策图。看起来BDD的每个节点在每个节点上有一个或两个选择。我很难看到如何映射依赖关系。将依赖性映射到图表上对我来说更有意义。

主要是，我认为这仅取决于您要在表示形式上运行的算法。如果您不确定自己有DAG，可以运行一个 循环检测算法 告诉你是否是。如果您想找到最短的路径，可以运行 Dijkstra的 在上面。我认为这确实取决于您想做的事情，而且我知道您可以使用一般图表可以做的事情，这主要涉及证明它是一个DAG。一旦您获得了DAG，我想确定的大多数东西都已建立。那就是我。

-Brian J. Stinar-