如何检查依赖关系图中的其他冲突信息？

当您有一组项目的依赖关系图时，您可以执行标准的主题排序来检查该图是否包含周期。如果有一个循环，那么就有一个依赖，在不违反另一个的情况下不能满足。如何检查依赖关系图中的其他冲突信息？

但是，冲突信息呢？我的意思是你有一个结构：

 
V - a set of items 
E - a set of dependency edges: E\subset V\times V 
C - a set of conflict edges: C\subset V\times V

什么是标准算法来检查依赖关系图是否包含不能满足的冲突信息？

例如：

 
V = { a, b, c } 
E = { (a -> b), (b->c) } 
C = { (a -> c) }

此示例显示一个不健全的依赖图，因为它没有任何意义的是c取决于a和在给定的ac存在被指定为冲突的同时。

这样一个模型的一个现实世界的例子是包管理器，包描述可能包括依赖和冲突规范。另一个例子是基于依赖关系的运行服务，其中只有在没有冲突的作业已经运行的情况下才能启动作业。

我不知道一个标准算法，但这个工程：

运行时间O(|E|+|V|+|C|)：
由于拓扑排序和DFS在(V,E)线性的，并且所述第三部分是在C线性的。

第2阶段的说明：

我们开始在依赖关系图的顶部（或者，如果你喜欢，拓扑分类的开始），选择第一个节点，第一个标签，说1 。我们以DFS（或BFS）方式遍历图中的每条边;只要我们仍然连接，我们继续用相同的标签标记节点。一旦连接“耗尽”，我们就增加标签并继续在DFS/BFS中运行。

I.e.从第一个节点到达的所有东西都标记为1。一旦我们用尽了该节点的可达性（DFS或BFS算法中的外部循环），我们就增加标签并选择下一个未搜索节点。

证明的正确性：

我们做出一个重要发现 - 该图是不稳定的当且仅当存在一些对(u,v)在C这样label(u) = label(v)。

首先，我不是指C中的元素，因为存在对称性。如果(u -> v)在C这意味着，用你的话说，给出u，v不能存在。所以它们不能同时存在，这意味着既不是u也不能依赖于v（因为那么对于u存在，v必须存在，这是不可能的），也不相反。

了解这一点，我们可以证明以上的观察：
我们注意到，label(u) = label(v)如果任u取决于v，或者反过来。这是构造的一个简单结果，可达性（从而依赖）定义了标签。所以如果我们假设我们有这样一对，那么这个图是不稳定的（正如上面的段落所解释的那样）。

观察的另一个方向（不稳定==>对）也很容易看到。如果我们假设图形不稳定，那么存在一些不存在的u。此u要么依赖于某些冲突，要么依赖于某些其他节点，并且该对冲突。无论哪种方式，我们在C中找到一对具有相同标签的(u,v)。

2011-10-07 07:13:34 davin

回答