How to check additional conflict information in a dependency graph?

When you have a dependency graph of a set of items you can do a standard topical sort to check if the graph contains cycles. If there is a cycle then there is a开发者_如何学JAVA dependency that can not be satisfied without violating another.

But what about conflict informations? I mean a structure where you have:

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

What is the standard algorithm to check if the dependency graph contains conflict information that can not be satisfied?

For example:

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

This example shows an unsound dependency graph because it does not make sense that c depends on a and at the same time the presence of c given a is specified as a conflict.

One real world example of such a model is package managers, where package descriptions may include depend and conflict specifications. Another example is a dependency based run-service, where a job can only be started if no conflicting job is already running.

---

I don't know about a standard algorithm, but this works:

1. Find the topological sort of (V,E) as usual (returning unstable if a cyclic dependency is found).
2. In a DFS/BFS manner, label each dependency trail/component uniquely (explanation below).
3. Traverse C and check that there exists no pair (u,v) such that label(u) = label(v). If there is such a pair ==> return unstable, otherwise ==> return stable.

Running time O(|E|+|V|+|C|):
Since topological sort and DFS are linear in (V,E), and the third part is linear in C.

Explanation of stage 2:

We begin at the top of the dependency graph (or if you like, the beginning of the topological sort), pick the first node, and the first label, say 1. We traverse each edge in the graph in a DFS (or BFS) manner; so long as we are still connected we continue labelling the nodes with the same label. As soon as the connectivity "runs out", we increment the label and continue in the DFS/BFS.

I.e. everything reachable from the first node is labelled 1. Once we've exhausted reachability of that node (the outer loop in the DFS or BFS algorithm), we increment the label and pick the next unsearched node.

Proof of correctness:

We make one key observation - that the graph is unstable iff there exists some pair (u,v) in C such that label(u) = label(v).

Firstly, I'm not referring to elements in C as directed, because there exists a symmetry. If (u -> v) in C that means that, in your words, given u, v cannot exist. So they cannot both exist together, meaning neither u can be dependant on v (because then for u to exist, v must exist, which is impossible), nor the opposite.

With that understanding we can prove the above observation:
We note that label(u) = label(v) if either u is dependant on v, or the other way around. That is a simple result of the construction, where reachability (and thus dependency) defined the labels. So if we have assume we such a pair, the graph is unstable (as explained the the above paragraph).

The other direction of the observation (unstable ==> pair) is easy to see as well. If we assume the graph is unstable then there is some u that cannot exist. This u is either dependant on something conflicting, or some other node is dependent on it and that pair is conflicting. Either way, we found a pair (u,v) in C that have the same label.