graphlib — 그래프 형태 구조를 다루는 기능

graphlib — 그래프 형태 구조를 다루는 기능

graphlib 모듈은 hashable한 노드들의 그래프를 위상 정렬(topological sort)하는 기능을 제공해요.

출처: Python 표준 라이브러리

TopologicalSorter

• class graphlib.TopologicalSorter(graph=None)

**위상 순서(topological order)**란 그래프의 꼭짓점들을 선형으로 나열한 것으로, 꼭짓점 u에서 v로 가는 모든 방향 간선 u -> v에 대해 순서에서 u가 v보다 앞에 오는 것을 말해요. 예를 들어 그래프의 꼭짓점들이 수행할 작업을, 간선들은 어떤 작업이 다른 작업보다 먼저 수행돼야 한다는 제약을 나타낼 수 있어요; 이 경우 위상 순서는 그저 작업들의 유효한 순서입니다. 완전한 위상 순서가 가능한 것은 그래프에 방향 순환이 없을 때, 즉 directed acyclic graph(유향 비순환 그래프)일 때뿐입니다.

선택적 graph 인자를 제공하면, 그것은 directed acyclic graph를 나타내는 사전이어야 해요. 이때 키는 노드이고 값들은 그래프에서 그 노드의 모든 선행자(predecessor)들의 이터러블입니다(노드에 대한 간선이 키의 값을 가리키는 노드들). add() 메서드로 그래프에 추가 노드를 넣을 수 있어요.

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

1. 선택적 초기 그래프와 함께 TopologicalSorter 인스턴스를 만든다.
2. 그래프에 추가 노드를 넣는다.
3. 그래프에 prepare()를 호출한다.
4. 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():
        # Worker threads or processes take nodes to work on off the
        # 'task_queue' queue.
        task_queue.put(node)

    # When the work for a node is done, workers put the node in
    # 'finalized_tasks_queue' so we can get more nodes to work on.
    # The definition of 'is_active()' guarantees that, at this point, at
    # least one node has been placed on 'task_queue' that hasn't yet
    # been passed to 'done()', so this blocking 'get()' must (eventually)
    # succeed. After calling 'done()', we loop back to call 'get_ready()'
    # again, so put newly freed nodes on 'task_queue' as soon as
    # logically possible.
    node = finalized_tasks_queue.get()
    topological_sorter.done(node)

add()

• add(node, *predecessors)

새 노드와 그 선행자들을 그래프에 추가해요. node와 predecessors의 모든 요소는 hashable이어야 합니다.

같은 노드 인자로 여러 번 호출하면, 의존성 집합은 전달된 모든 의존성의 합집합이 됩니다.

의존성이 없는 노드(predecessors를 주지 않음)를 추가하거나, 의존성을 두 번 제공하는 것도 가능해요. 이전에 제공되지 않았던 노드가 predecessors에 포함돼 있으면, 그것이 자신의 선행자 없이 그래프에 자동 추가됩니다.

prepare() 후에 호출하면 ValueError를 발생시켜요.

prepare()

• prepare()

그래프를 완성된 것으로 표시하고 그래프의 순환을 검사해요. 순환이 감지되면 CycleError가 발생하지만, 순환이 진행을 막을 때까지 가능한 한 많은 노드를 얻는 데 get_ready()를 여전히 쓸 수 있어요. 이 함수 호출 후에는 그래프를 수정할 수 없으므로 add()로 더 이상 노드를 추가할 수 없습니다.

static_order()나 get_ready()로 정렬이 시작됐으면 ValueError가 발생해요.

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

is_active()

• is_active()

더 진행할 수 있으면 True, 그렇지 않으면 False를 반환해요. 순환이 해결을 막지 않고, 아직 TopologicalSorter.get_ready()가 반환하지 않은 준비된 노드가 여전히 있거나, TopologicalSorter.done()으로 표시된 노드 수가 TopologicalSorter.get_ready()가 반환한 수보다 적으면 진행할 수 있습니다.

이 클래스의 __bool__() 메서드는 이 함수에 위임하므로, 다음처럼 쓰는 대신:

if ts.is_active():
    ...

단순히 이렇게 해도 돼요:

if ts:
    ...

이전에 prepare()를 호출하지 않고 호출하면 ValueError를 발생시킵니다.

done()

• done(*nodes)

TopologicalSorter.get_ready()가 반환한 노드 집합을 처리된 것으로 표시하고, nodes에 있는 각 노드의 후속자(successor)가 미래의 TopologicalSorter.get_ready() 호출로 반환되는 것을 막지 않게 해제해요.

nodes의 어떤 노드가 이 메서드 이전 호출로 이미 처리된 것으로 표시됐거나, TopologicalSorter.add()로 그래프에 추가되지 않았거나, prepare()를 호출하지 않고 호출했거나, 아직 get_ready()가 반환하지 않은 노드면 ValueError를 발생시킵니다.

get_ready()

• get_ready()

준비된 모든 노드를 담은 tuple을 반환해요. 처음에는 선행자가 없는 모든 노드를 반환하고, 이들을 TopologicalSorter.done()으로 처리된 것으로 표시하면, 이후 호출은 모든 선행자가 이미 처리된 모든 새 노드를 반환합니다. 더 이상 진행할 수 없으면 빈 튜플을 반환해요.

이전에 prepare()를 호출하지 않고 호출하면 ValueError를 발생시킵니다.

static_order()

• static_order()

위상 순서로 노드들을 순회할 이터레이터 객체를 반환해요. 이 메서드를 사용할 때는 prepare()와 done()을 호출하면 안 됩니다. 이 메서드는 다음과 동일합니다:

def static_order(self):
    self.prepare()
    while self.is_active():
        node_group = self.get_ready()
        yield from node_group
        self.done(*node_group)

반환되는 특정 순서는 항목들이 그래프에 삽입된 특정 순서에 따라 달라질 수 있어요. 예를 들어:

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

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

이는 "0"과 "2"가 그래프에서 같은 레벨에 있기 때문인데(둘이 같은 get_ready() 호출로 반환될 텐데), 그 사이의 순서는 삽입 순서에 의해 결정됩니다.

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

예외

graphlib 모듈은 다음 예외 클래스를 정의해요:

CycleError

• exception graphlib.CycleError

작업 그래프에 순환이 존재하면 TopologicalSorter.prepare()가 발생시키는 ValueError의 하위 클래스예요. 여러 순환이 존재하면 그중 하나의 정의되지 않은 선택만 보고되고 예외에 포함됩니다.

감지된 순환은 예외 인스턴스의 args 속성의 두 번째 요소로 접근할 수 있는데, 노드들의 리스트로 구성되며 각 노드는 그래프에서 리스트의 다음 노드의 직접 선행자입니다. 보고된 리스트에서 첫 번째와 마지막 노드는 같아서, 순환적임을 분명히 해 줘요.

더 알아보기

• Python 공식 문서: graphlib