Wie kann Paketmanager (Eignung, yum, portage) ihre Abhängigkeit Bäume bauen?

Question

Ich verstehe die grundlegenden Konzepte, aber gibt es spezielle Algorithmen verwendet, oder vielleicht ein paar Blogs, Papiere oder sogar Bücher über das Thema für jemand ihr eigenes System bauen? Es scheint, dass es nur sehr wenige Informationen werden heraus tatsächlich ein System wie dieses umzusetzen.

Answer 1

Der Abhängigkeitsbaum selbst ist trivial zu laden, alles, was Sie brauchen, ist eine Zuordnung von Tasten (Namen) zu Objekten.

Sie haben keine Sprache angegeben, also habe ich Python gewählt. Der erwartete Eingang ist eine Datei von Linien in der Form "[name]: [Leerzeichen getrennt Abhängigkeiten]".

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

Dieser Code geht davon aus irgendeinem Element nicht aufgelistet Null Abhängigkeiten hat, und man kann den Baum durchquert leere Einträge hinzufügen, falls gewünscht. Zumindest sollten Sie für rekursive Abhängigkeiten überprüfen.

Beispiel:

>>> 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'])}

[Anmerkung:. Ich nehme eine Abkürzung, da ich wirklich nicht, eine Datei von Zeilen erfordern, sondern eine iterable von Linien (das ist eine Datei erfüllt), so gebe ich eine Liste von Zeilen in die Funktion]

Sie können alle Arten von Funktionen im oberen Teil der Grundstruktur aufzubauen, und kapseln sie und diese Konzepte (wie abhängig vs empfiehlt vs schon sagt, und sogar Konflikte vs ersetzt, etc.) in verschiedene Objekte speziell für Ihr System.

Answer 2

Viele andere Konzepte auch Abhängigkeitsbäume, wie SNMP MIB Auflösung, C / C ++ Quellcode kompilieren einzubeziehen. So können Sie alle anderen Materialien verweisen, die darüber sprechen:)