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

有帮助吗?

解决方案

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

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

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

其他提示

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

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

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

-Brian J. Stinar-

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top