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

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.

Answer 1

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 :)

Answer 2

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.