パッケージマネージャー（aptitude、yum、portage）はどのように依存関係ツリーを構築しますか？

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

  •  10-07-2019
  •  | 
  •  

質問

基本的な概念は理解していますが、独自のシステムを構築している人のために、使用されている特別なアルゴリズムや、そのテーマに関するいくつかのブログ、論文、あるいは本がありますか？このようなシステムの実際の実装に関する情報はほとんどないようです。

役に立ちましたか？

解決

依存関係ツリー自体の読み込みは簡単で、必要なのはキー（名前など）からオブジェクトへのマッピングです。

言語を指定していないため、Pythonを選択しました。予想される入力は、＆quot; [name]：[スペースで区切られた依存関係]＆quot;という形式の行のファイルです。

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

[注：本当に行のファイルを必要としないので、ショートカットを使用しますが、行の反復可能（ファイルが満たす）なので、関数に行のリストを渡します。]

この基本構造の上にあらゆる種類の関数を構築し、それとそれらの概念（依存vs推奨vs提案、さらには競合vs置換など）をシステム固有のさまざまなオブジェクトにカプセル化できます。

他のヒント

他の多くの概念には、SNMP MIB解決、C / C ++ソースコードのコンパイルなどの依存関係ツリーも含まれます。したがって、これについて説明している他の資料を参照できます：）

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top