Eu tenho um problema clássico de resolução de dependências. Eu pensei que estava indo na direção certa, mas agora encontrei um obstáculo e não sei ao certo como proceder.

fundo

No universo conhecido (o cache de todos os artefatos e suas dependências), cada um existe um relacionamento 1-> n entre artefatos e versões, e cada versão pode conter um conjunto diferente de dependências. Por exemplo:

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

Dado um conjunto de "restrições de demanda", eu gostaria de encontrar a melhor solução possível (onde "melhor" é a versão mais alta possível que ainda satisfaz todas as restrições). Aqui está um exemplo de "restrições de demanda" com a solução:

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

Na realidade, há significativamente mais demandas:

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

(As versões seguem oversionamento semântico padrão)

Eu tentei

A solução atual usa back-tracing e não tem muito desempenho. Eu pesquisei e descobri os problemas de desempenho resultantes do tamanho do universo. Decidi tentar uma abordagem alternativa e construir um gráfico DAG de "possibilidade" parasomente o conjunto de demandas:

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

Eu então construo um DAG de todas as soluções possíveis do universo. Isso reduz drasticamente o número de possibilidades e me fornece um gráfico real com possibilidades reais de artefato para trabalhar.

def populate(artifact)
  return if loaded?(artifact)

  @graph.node(artifact)

  artifact.dependencies.each do |dependency|
    versions_for(dependency).each do |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 are no versions for this dependency,
  # since we know the graph won't be solvable.
  raise "No solution for #{dependency}!" if possibles.empty?

  possibles
end

Então, no gráfico de exemplo anterior, se eu tivesse as demandas'A', '>= 0.0.0', meu DAG ficaria assim:

+---------+   +---------+
| A-1.0.0 |   | A-1.0.1 |
+---------+   +---------+
       /  \        |
      /    \       |
     /      \      |
    /        \     |
+---------+   +---------+
| B-1.0.0 |   | B-0.1.0 |
+---------+   +---------+

Como os valores possíveis para A-1.0.0 são "qualquer valor de B", mas as restrições para A-1.0.1 são "qualquer B da série 0.1". No momento, ele está funcionando (com um conjunto de testes completo) conforme o esperado.

Em outras palavras, o DAG pega as restrições abstratas de dependência e cria um gráfico "real", em que cada aresta é uma dependência e cada vértice (eu o chamei denode) é um artefato real. Se existe uma solução, ela está em algum lugar neste gráfico.

E, infelizmente, é aqui que eu fico preso. Não consigo criar um algoritmo ou procedimento para encontrar o "melhor" caminho através deste gráfico. Também não tenho certeza de como detectar se o gráfico não é solucionável.

Eu fiz algumas pesquisas e achei que o tipo topológico (tsort) era o processo que eu precisava. No entanto, esse algoritmo determina a ordem de inserção das dependências, não a melhor solução.

Estou bastante certo de que este é um problema np-hard e provavelmente terá um tempo de execução ineficiente. Embora o uso de um DAG reduzisse o número de comparações que tenho que fazer. Estou errado nessa suposição? Existe uma estrutura de dados melhor para usar?

Pensamentos finaisEu marquei esta questão como "Ruby" porque estou usando Ruby, no entanto, estou procurando código-psuedo / direção. Este não é um problema de lição de casa - estou realmente tentando aprender.Tentei fornecer o máximo de informações possíveis, mas deixe um comentário se desejar obter mais detalhes sobre um tópico específico. Este já é um post longo, mas tenho mais código que posso compartilhar.