我有一个经典的依赖解决问题.我以为我朝着正确的方向前进,但现在我遇到了障碍,我不知道该怎么办.

背景

在已知的Universe(所有工件的缓存及其依赖关系)中,每个工件和版本之间都存在1-> n关系,并且每个版本可能包含一组不同的依赖关系.例如:

A
  1.0.0
    B (>= 0.0.0)
  1.0.1
    B (~> 0.1)
B
  0.1.0
  1.0.0

给定一组"需求约束",我想找到最好的解决方案("最佳"是仍然满足所有约束的最高版本).以下是解决方案的"需求约束"示例:

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

实际上,有更多的要求:

solve!('A' => '~> 1.0', 'B' => '>= 0.0.0', 'C' => '...', 'D' => '...')

(版本遵循语义版本标准)

我试过了

当前的解决方案使用回溯并且性能不高.我做了一些挖掘,发现性能问题是由于宇宙的大小造成的.我决定尝试另一种方法,构建了"可能性" DAG图的只是一组要求:

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 …