패키지 관리자 (aptitude, yum, portage)는 종속성 트리를 어떻게 구성합니까?

Question

나는 기본적인 개념을 이해하고 있지만 특별한 알고리즘이 사용되었거나 또는 블로그, 논문 또는 심지어 자신의 시스템을 구축하는 누군가의 주제에 관한 책이 있습니까? 이와 같은 시스템을 실제로 구현하는 데는 정보가 거의없는 것 같습니다.

Answer 1

종속성 트리 자체는로드하기가 쉽지 않으므로 키 (예 : 이름)에서 개체로의 매핑 만 있으면됩니다.

언어를 지정하지 않았으므로 Python을 선택했습니다. 예상되는 입력은 "[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 

이 코드는 나열되지 않은 항목이 0 개의 종속성이 없다고 가정하고 원하는 경우 빈 항목을 추가하기 위해 트리를 통과 할 수 있습니다. 적어도 재귀 적 종속성을 확인해야합니다.

예 :

>>> 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 대체 등) 시스템에 특정한 객체.

Answer 2

많은 다른 개념은 SNMP MIB 분석, C/C++ 소스 코드 컴파일과 같은 종속성 트리도 포함합니다. 그래서 이것에 대해 이야기하는 다른 자료를 참조 할 수 있습니다.