Как менеджеры пакетов (aptitude, yum, portage) строят свои деревья зависимостей?

StackOverflow https://stackoverflow.com/questions/1818484

  •  10-07-2019
  •  | 
  •  

Вопрос

Я понимаю основные концепции, но используются ли какие-либо специальные алгоритмы или, может быть, какие-то блоги, статьи или даже книги по этой теме для тех, кто строит свою собственную систему?Кажется, существует очень мало информации о фактическом внедрении такой системы.

Это было полезно?

Решение

Само дерево зависимостей несложно загрузить: все, что вам нужно, — это некоторое сопоставление ключей (например, имен) с объектами.

Вы не указали язык, поэтому я выбрал Python.Ожидаемый ввод — это файл строк в форме «[имя]:[зависимости, разделенные пробелами]».

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

В этом коде предполагается, что любой элемент, не указанный в списке, не имеет никаких зависимостей, и при желании вы можете перемещаться по дереву и добавлять пустые записи.По крайней мере, вам следует проверить наличие рекурсивных зависимостей.

Пример:

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

[Примечание:Я использую ярлык, поскольку на самом деле мне нужен не файл строк, а итерация строк (которой соответствует файл), поэтому я передаю список строк в функцию.]

Вы можете создавать всевозможные функции поверх этой базовой структуры и инкапсулировать ее и эти концепции (например, «зависит», «рекомендует», «предлагает», даже «конфликты» или «заменяет» и т. д.) в различные объекты, специфичные для вашей системы.

Другие советы

Многие другие концепции также включают в себя деревья зависимостей, такие как разрешение MIB SNMP, компиляция исходного кода C/C++.Так что вы можете ссылаться на любые другие материалы, в которых говорится об этом :)

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top