algorithm to resolve version scope based dependency

Question

I have a problem on a dependency algorithm, the dependency is similar to maven dependency, except it's strict version scope based.

For example:

component A, version 1 depends on: component B, version 1~3; and component C, version 2~3
component D, version 1 depends on: component B, version 2~4; and component C, version 1~2

Now, I want to get dependencies when I want to install component A, version 1 and component D, version 1. Because they are all depend on component B,C so I need a correct algorithm to get correct version of B and C

Further more, I may need to upgrade component A and D. For example, now I have below new versions:

component A, version 2 depends on: component B, version 3~5; and component C, version 4~5
component A, version 3 depends on: component B, version 6~7; and component C, version 4~5
component D, version 2 depends on: component B, version 3~4; and component C, version 3~4

Now I need a algorithm to get the correct version of A and D which I can upgrade to and all their dependencies. One problem here is Component A, version 3 and Component D, version 2 has dependency conflict of component B

Is there existing algorithm to resolve such problem? Or similar(easier) problem. Do you have any suggestion?

As there should not be lots of data, so don't consider the performance.

Thanks in advance!

Answer 1

This problem is NP-hard via the following reduction from 3SAT. Given a 3CNF formula, for each variable, there is a component with two versions, and for each clause, there is a component with three versions. We would like to install one version of a "super" component, which depends on all of the clause components but is not picky about versions. For each clause, clause component 1 depends on the first variable to appear in the clause, with version 1 required if the literal is positive, and 0 if it's negative. Clause component 2 depends on the second variable, etc. We can install the super component if and only if the formula is satisfiable.

In light of this reduction, it makes sense to formulate your problem as constraint satisfaction. Each component is a variable whose possible values are the versions of that component, plus "not installed" if not having that component installed is an option. For every component A with a version that depends on a version of component B, there is a constraint involving the variable for A and B, restricting the choices of versions to a particular subset of the product of their domains. For A and B in the first example, this is {(1, 1), (1, 2), (1, 3)}, since A version 1 depends on B versions 1~3. If version 2 of A were available as well, this constraint would be {(1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (2, 5)}. If we didn't have to install A or B, then {(none, none), (none, 1), (none, 2), (none, 3), (none, 4), (none, 5), (1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (2, 5)}.

Since your instances are small, you probably want a complete backtracking search, possibly with constraint propagation. A common algorithm for constraint propagation is AC-3, which enforces arc consistency, namely, removing from consideration all versions that clearly won't work, based on what's been eliminated. For example, given the constraint {(1, 1), (1, 2), (1, 3)}, we can eliminate B = none, since none never appears. Now that the choices for B are restricted, we can make inferences about B's dependency C, etc. When there's no more simplification left to do, we have to guess; one strategy is to pick the component with the fewest versions left and recursively try all of them (backtracking).