ruby - Solving dependency constraints -

i have classic dependency solving problem. thought headed in right direction, i've hit roadblock , not sure how proceed.

background

in known universe (the cache of artifacts , dependencies), each there 1->n relationship between artifacts , versions, , each version may contain different set of dependencies. example:

a   1.0.0     b (>= 0.0.0)   1.0.1     b (~> 0.1) b   0.1.0   1.0.0 

given set of "demand constraints", i'd find best possible solution (where "best" highest possible version still satisfies constraints). here's example "demand constraints" solution:

solve!('a' => '~> 1.0') #=> {"a" => "1.0.1", "b" => "0.1.0"} 

in reality, there more demands:

solve!('a' => '~> 1.0', 'b' => '>= 0.0.0', 'c' => '...', 'd' => '...') 

(the versions follow semantic versioning standard)

i tried

the current solution uses back-tracing , not performant. did digging , found performance issues resulted due size of universe. decided try alternate approach , construct "possibility" dag graph just set of demands:

class graph   def initialize     @nodes = {}     @edges = {}   end    def node(object)     @nodes[object] ||= set.new     self   end    def edge(a, b)     node(a)     node(b)      @nodes[a].add(b)      self   end    def nodes     @nodes.keys   end    def edges     @nodes.values   end    def adjacencies(node)     @nodes[node]   end end 

i construct dag of possible solutions universe. drastically reduces number of possibilities , gives me actual graph real artifact possibilities work with.

def populate(artifact)   return if loaded?(artifact)    @graph.node(artifact)    artifact.dependencies.each |dependency|     versions_for(dependency).each |dependent_artifact|       @graph.edge(artifact, dependent_artifact)       populate(dependent_artifact)     end   end end  private  def versions_for(dependency)   possibles = @universe.versions(dependency.name, dependency.constraint)    # short-circuit if there no versions dependency,   # since know graph won't solvable.   raise "no solution #{dependency}!" if possibles.empty?    possibles end 

so, earlier example graph, if had demands 'a', '>= 0.0.0', dag like:

+---------+   +---------+ | a-1.0.0 |   | a-1.0.1 | +---------+   +---------+        /  \        |       /    \       |      /      \      |     /        \     | +---------+   +---------+ | b-1.0.0 |   | b-0.1.0 | +---------+   +---------+ 

since possible values a-1.0.0 "any value of b", constraints a-1.0.1 "any b in 0.1 series". working (with full test suite) expected.

in other words, dag takes abstract dependency constraints , creates "real" graph each edge dependency , each vertex (i've called node) actual artifact. if solution exists, somewhere in graph.

and sadly, stuck. i'm unable come algorithm or procedure find "best" pathway through graph. i'm unsure of way detect if graph isn't solvable.

i did research, , thought topological sort (tsort) process needed. however, algorithm determines insertion order dependencies, not best solution.

i'm np-hard problem , have inefficient runtime. though using dag reduce number of comparisons have do. wrong in assumption? there better data structure use?

final thoughts

• i have tagged question "ruby" because i'm using ruby, looking psuedo-code/direction. isn't homework problem - i'm genuinely trying learn.
• i have tried give background possible, please leave comment if more detail on particular topic. lengthy post, have more code can share.

i'm not expert on problem, i'm proposing complete solution not optimal, there many things can optimized ..

the algorithm simple, it's ideally recursive set . intersection dfs :

algorithm

def

define: name string on format [ .* ] define: version string on format [ dd.dd.dd ] define: revision { name, version, requirement } define: range<t> { min<t>, max<t> } define: condition { name, range<version> } define: requirement set<revision> or set<condition> define: component { name, range<version>, requirement } define: system set<component> 

input

input: t system aka basis input: c set<condition> aka conditions apply 

initialization

init: s set<condition> = { s[i] condition | s[i] = {t[i].name,t[i].range} } init: q stack<condition> = { push(q) | q[i] = c[i] } 

process

for (condition c in c) {     s.find(c.name).apply(c) }  while (q.size > 0) {     condition q = q.pop()      switch (t.assert(s.find(q.name),q))     {       case valid:         s.find(q.name).apply(q)         q.push(s.find(q.name).requirement)        case invalid:         s.find(q.name).set(invalid)        case identical:       case skip:     } }  return s aka solution 

operations

stack.push insert item @ front of stack

stack.pop remove item front of stack

system.assert(condition a, condition b):     if (a invalid) return skip     else if (b.range = a.range) identical     else if (b.range - a.range = {}) valid     else invalid 

set.find(x) search item based on condition x

condition.apply(condition b) = { this.name, intersection(this.range,b.range) }