How do package managers (aptitude, yum, portage) build their dependency trees? [closed]

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

开发者_Go百科

We don’t allow questions seeking recommendations for books, tools, software libraries, and more. You can edit the question so it can be answered with facts and citations.

Closed last year.

Improve this question

I understand the basic concepts, but are there any special algorithms used or maybe some blogs, papers or even books on the subject for someone building their own system? There seems to be very little information out there on actually implementing a system like this.

---

The dependency tree itself is trivial to load, all you need is some mapping from keys (such as names) to objects.

You've not specified any language, so I've chosen Python. The expected input is a file of lines in the form "[name]: [space separated dependencies]".

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

This code assumes any item not listed has zero dependencies, and you could traverse the tree to add empty entries if desired. At the very least you should check for recursive dependencies.

Example:

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

[Note: I take a shortcut, since I really don't require a file of lines, but an iterable of lines (which a file meets), so I pass a list of lines to the function.]

You can build all sorts of functions on top of this basic structure, and encapsulate it and those concepts (like depends vs recommends vs suggests, and even conflicts vs replaces, etc.) into various objects specific to your system.

---

Many other concepts also involve dependency trees, such as SNMP MIB resolution, C/C++ source code compiling. So you can reference any other materials that talk about this :)