graphlib — 그래프 유사 구조를 다루는 기능

graphlib 모듈은 해시 가능한 노드의 그래프를 위상 정렬(topological sort)하는 기능을 제공해요. 위상 순서는 그래프의 정점에 대한 선형 순서로, 모든 방향 간선 u -> v(정점 u에서 정점 v로)에 대해 u가 순서상 v보다 앞에 오는 순서예요. 예를 들어 그래프의 정점이 수행할 작업을 나타내고 간선이 한 작업이 다른 작업보다 먼저 수행되어야 한다는 제약을 나타낸다면, 위상 순서는 그 작업들의 유효한 순서가 돼요. 완전한 위상 순서는 그래프에 방향 순환이 없을 때, 즉 방향 비순환 그래프(directed acyclic graph)일 때만 가능해요.

출처: Python documentation

본문

클래스

class graphlib.TopologicalSorter(graph=None) — 해시 가능한 노드의 그래프를 위상 정렬하는 기능을 제공해요.

선택적 graph 인자를 제공하면, 키가 노드이고 값이 그 노드의 모든 선행자(predecessor)의 iterable인 방향 비순환 그래프를 나타내는 딕셔너리여야 해요. add() 메서드로 그래프에 추가 노드를 넣을 수 있어요.

일반적인 경우, 주어진 그래프를 정렬하는 데 필요한 단계는 다음과 같아요:

선택적 초기 그래프를 가진 TopologicalSorter 인스턴스를 만든다.
그래프에 추가 노드를 넣는다.
그래프에서 prepare()를 호출한다.
is_active()가 True인 동안 get_ready()가 반환하는 노드를 순회하며 처리하고, 각 노드의 처리가 끝나면 done()을 호출한다.

그래프의 노드를 즉시 정렬만 하면 되고 병렬 처리가 필요 없는 경우, 편의 메서드 TopologicalSorter.static_order()를 직접 사용할 수 있어요:

>>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
>>> ts = TopologicalSorter(graph)
>>> tuple(ts.static_order())
('A', 'C', 'B', 'D')

이 클래스는 노드가 준비될 때 노드의 병렬 처리를 쉽게 지원하도록 설계됐어요:

topological_sorter = TopologicalSorter()
# Add nodes to 'topological_sorter'...
topological_sorter.prepare()
while topological_sorter.is_active():
    for node in topological_sorter.get_ready():
        task_queue.put(node)
    node = finalized_tasks_queue.get()
    topological_sorter.done(node)

add(node, *predecessors) — 새 노드와 그 선행자들을 그래프에 추가해요. 노드와 predecessors의 모든 요소는 해시 가능해야 해요. 같은 노드 인자로 여러 번 호출하면 의존성 집합은 전달된 모든 의존성의 합집합이 돼요. 의존성이 없는 노드(predecessors가 제공되지 않음)를 추가하거나 의존성을 두 번 제공할 수 있어요. 이전에 제공되지 않았던 노드가 선행자에 포함되면 그 노드는 자체 선행자 없이 그래프에 자동으로 추가돼요. prepare() 이후에 호출하면 ValueError가 발생해요.

prepare() — 그래프를 완료된 것으로 표시하고 그래프에서 순환을 확인해요. 순환이 감지되면 CycleError가 발생하지만, 순환이 더 이상의 진행을 막을 때까지 get_ready()로 가능한 많은 노드를 얻는 데는 여전히 사용할 수 있어요. 이 함수를 호출한 후에는 그래프를 수정할 수 없으므로 add()로 더 이상 노드를 추가할 수 없어요. static_order()나 get_ready()로 정렬이 시작되었다면 ValueError가 발생해요.

버전 3.14에서 변경: 정렬이 시작되지 않은 한 prepare()를 두 번 이상 호출할 수 있어요. 이전에는 ValueError가 발생했어요.

is_active() — 더 진행할 수 있으면 True를, 그렇지 않으면 False를 반환해요. 순환이 해결을 막지 않고, 아직 get_ready()가 반환하지 않은 준비된 노드가 있거나 done()으로 표시된 노드 수가 get_ready()가 반환한 수보다 적으면 진행할 수 있어요. 이 클래스의 __bool__() 메서드는 이 함수로 위임하므로 if ts.is_active(): 대신 if ts:라고 쓸 수 있어요. 이전에 prepare()를 호출하지 않고 호출하면 ValueError가 발생해요.

done(*nodes) — get_ready()가 반환한 노드 집합을 처리된 것으로 표시해, nodes의 각 노드의 후속자(successor)들의 차단을 풀어 이후 get_ready() 호출에서 반환되게 해요. nodes의 어떤 노드가 이 메서드의 이전 호출로 이미 처리된 것으로 표시됐거나, add()로 그래프에 추가되지 않았거나, prepare()를 호출하지 않고 호출했거나, 노드가 아직 get_ready()로 반환되지 않았다면 ValueError가 발생해요.

get_ready() — 준비된 모든 노드를 담은 tuple을 반환해요. 처음에는 선행자가 없는 모든 노드를 반환하고, done()으로 처리된 것으로 표시되면 이후 호출은 모든 선행자가 이미 처리된 새 노드를 모두 반환해요. 더 이상 진행할 수 없으면 빈 튜플이 반환돼요. 이전에 prepare()를 호출하지 않고 호출하면 ValueError가 발생해요.

static_order() — 위상 순서의 노드를 순회할 이터레이터 객체를 반환해요. 이 메서드를 사용할 때 prepare()와 done()은 호출하면 안 돼요. 반환되는 특정 순서는 항목이 그래프에 삽입된 특정 순서에 따라 달라질 수 있어요. 예를 들어:

>>> ts = TopologicalSorter()
>>> ts.add(3, 2, 1)
>>> ts.add(1, 0)
>>> print([*ts.static_order()])
[2, 0, 1, 3]

순환이 감지되면 CycleError가 발생해요. 버전 3.9에서 추가됨.

예외

exception graphlib.CycleError — 작업 중인 그래프에 순환이 있을 때 TopologicalSorter.prepare()가 발생시키는 ValueError의 하위 클래스예요. 여러 순환이 있으면 그중 하나만 보고되고 예외에 포함돼요. 감지된 순환은 예외 인스턴스의 args 속성 두 번째 요소로 접근할 수 있는데, 각 노드가 다음 노드의 즉시 선행자인 노드 리스트로 구성돼요. 보고된 리스트에서 첫 번째와 마지막 노드는 순환임을 명확히 하기 위해 같아요.

더 알아보기 (Learn more)

Python 공식 문서