如何检查依赖图中的附加冲突信息？

Question

当您有一组项目的依赖图时，您可以执行标准主题排序来检查该图是否包含循环。如果存在循环，那么就存在一种依赖关系，如果不违反另一个依赖关系，就无法满足该依赖关系。

但是冲突信息呢？我的意思是您拥有的结构：

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 并且同时存在 c 是没有意义的> 给定的a 被指定为冲突。

这种模型的一个现实示例是包管理器，其中包描述可能包括依赖和冲突规范。另一个示例是基于依赖关系的运行服务，其中只有在没有正在运行的冲突作业时才能启动作业。

Answer 1

我不知道标准算法，但这有效：

1. 像往常一样找到(V,E)的拓扑排序（如果返回不稳定
   发现循环依赖）。
2. 以DFS/BFS的方式，对每个
   唯一的依赖路径/组件（解释如下）。
3. 遍历 C 并
   检查是否不存在满足 (u,v) 的对 label(u) =
标签（v）。如果有这样一对==>返回不稳定，否则==>
   回归稳定。

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

第 2 阶段的说明：

我们从依赖图的顶部开始（或者如果您愿意，可以从拓扑排序的开始）开始，选择第一个节点和第一个标签，例如 1。我们以DFS（或BFS）的方式遍历图中的每条边；只要我们仍然保持连接，我们就继续用相同的标签标记节点。一旦连接“耗尽”，我们就会增加标签并继续 DFS/BFS。

即从第一个节点可到达的所有内容都被标记为1。一旦我们耗尽了该节点（DFS 或 BFS 算法中的外循环）的可达性，我们就会增加标签并选择下一个未搜索的节点。

正确性证明：

我们做了一个关键的观察——如果C中存在一对(u,v)，则该图是不稳定的标签（u）=标签（v）。

首先，我并不是按照指示引用 C 中的元素，因为存在对称性。如果 C 中的 (u -> v) 这意味着，用你的话来说，给定 u, v不可能存在。因此它们不能同时存在，这意味着 u 都不能依赖于 v （因为要使 u 存在，v code> 必须存在，这是不可能的），反之亦然。

有了这样的理解，我们就可以证明上述观察结果：
我们注意到，如果 u 依赖于 v，则 label(u) = label(v) ，反之亦然。这是构造的一个简单结果，其中可达性（以及依赖性）定义了标签。因此，如果我们假设有这样的一对，则该图是不稳定的（如上段所述）。

观察的另一个方向（不稳定==>对）也很容易看到。如果我们假设图不稳定，那么有一些 u 不可能存在。这个u要么依赖于某些冲突的东西，要么某个其他节点依赖于它并且该对是冲突的。不管怎样，我们在 C 中找到了一对具有相同标签的 (u,v)。