Como gestores de pacotes (aptidão, yum, portage) construir suas árvores de dependência?

Question

Eu entendo os conceitos básicos, mas existem algoritmos especiais utilizados ou talvez alguns blogs, jornais ou mesmo livros sobre o assunto para alguém construir seu próprio sistema? Parece haver muito pouca informação lá fora em realmente implementar um sistema como este.

Answer 1

A própria árvore de dependência é trivial para carga, tudo que você precisa é de algum mapeamento de teclas (como nomes) para objetos.

Você não tenha especificado qualquer idioma, então eu escolhi Python. A entrada é esperado um ficheiro de linhas na forma. "[Nome]: [espaço separado dependências]"

def load_depends(file):
  depends = {}
  for line in file:
    line = line.strip()
    if not line or line.startswith("#"):  # allow blanks and comments
      continue
    name, _, deps = line.partition(":")
    deps = deps.strip()
    assert deps, "invalid input"  # most basic input error-checking
    depends[name] = set(deps.split())
  return depends

Este código assume qualquer item não listada tem zero dependências, e você poderia percorrer a árvore para adicionar entradas vazias, se desejar. No mínimo você deve verificar se há dependências recursivas.

Exemplo:

>>> input = """\
... a: b c
... b: c
... c: d
... e: a
... """.split("\n")
>>> from pprint import pprint
>>> pprint(load_depends(input))
{'a': set(['b', 'c']),
 'b': set(['c']),
 'c': set(['d']),
 'e': set(['a'])}

[Nota:. I pegar um atalho, uma vez que eu realmente não precisa de um arquivo de linhas, mas um iterável de linhas (que um arquivo encontra), então eu passar uma lista de linhas para a função]

Você pode construir todos os tipos de funções no topo desta estrutura básica, e compactá-lo e esses conceitos (como depende vs recomenda vs sugere, e até mesmo conflitos vs substitui, etc.) em vários objetos específicos para o seu sistema.

Answer 2

Muitos outros conceitos também envolvem árvores de dependência, como a resolução SNMP MIB, C / C ++ compilar o código fonte. Então você pode fazer referência a quaisquer outros materiais que falar sobre isso:)