Resolvendo restrições de dependência
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.
fundoNo 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 tenteiA 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.