graphlib — 그래프와 유사한 구조에 작동하는 기능

소스 코드: Lib/graphlib.py

class graphlib.TopologicalSorter(graph=None)

해시 가능 노드의 그래프(graph)를 위상 정렬(topological sort)하는 기능을 제공합니다.

위상 순서(topological order)는 그래프(graph)에서 꼭짓점(vertex)의 선형 순서로, 꼭짓점 u에서 꼭짓점 v로 가는 모든 유향 변(directed edge) u -> v 에 대해, 꼭짓점 u가 꼭짓점 v보다 앞에 옵니다. 예를 들어, 그래프의 꼭짓점은 수행될 작업을 나타낼 수 있고, 변은 하나의 작업이 다른 작업보다 먼저 수행되어야 한다는 제약을 나타낼 수 있습니다; 이 예에서, 위상 순서는 유효한 작업 순서입니다. 그래프에 유향 순환이 없는 경우, 즉 유향 비순환 그래프인 경우에만 완전한 위상 정렬이 가능합니다.

선택적 graph 인자가 제공되면 키가 노드이고 값이 그래프에서 해당 노드의 모든 선행 노드(키의 값을 가리키는 변이 있는 노드)의 이터러블인 비순환 그래프를 나타내는 딕셔너리이어야 합니다). 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():
        # 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(node, *predecessors)

새 노드와 그 선행 노드를 그래프에 추가합니다. node와 predecessors의 모든 요소는 모두 해시 가능해야 합니다.

같은 노드 인자로 여러 번 호출되면, 종속성 집합은 전달된 모든 종속성의 합집합입니다.

종속성이 없는 노드를 추가하거나(predecessors가 제공되지 않는 경우) 종속성을 두 번 제공할 수 있습니다. 이전에 제공되지 않은 노드가 predecessors에 포함되면, 노드는 그 자신의 선행 노드 없이 자동으로 그래프에 추가됩니다.

prepare() 이후에 호출되면 ValueError가 발생합니다.

prepare()

그래프를 완료로 표시하고 그래프에서 순환을 검사합니다. 순환이 감지되면, CycleError가 발생하지만, 순환이 더 진행하는 것을 차단할 때까지 get_ready()를 사용하여 여전히 가능한 많은 노드를 얻을 수 있습니다. 이 함수를 호출한 후에는, 그래프를 수정할 수 없어서, add()를 사용하여 더는 노드를 추가할 수 없습니다.

is_active()

더 진행할 수 있으면 True를, 그렇지 않으면 False를 반환합니다. 순환이 결정을 차단하지 않고 TopologicalSorter.get_ready()에 의해 아직 반환되지 않은 준비된 노드가 아직 있거나 TopologicalSorter.done()으로 표시된 노드 수가 TopologicalSorter.get_ready()에 의해 반환된 수보다 작으면 진행할 수 있습니다.

이 클래스의 __bool__() 메서드는 이 함수로 위임됩니다, 그래서 다음 대신:

if ts.is_active():
    ...

다음처럼 간단하게 할 수 있습니다:

if ts:
    ...

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

done(*nodes)

TopologicalSorter.get_ready()에 의해 반환된 노드 집합이 처리된 것으로 표시하여, nodes에 있는 각 노드의 모든 후속 노드들이 TopologicalSorter.get_ready()에 대한 호출로 나중에 반환되도록 차단 해제합니다.

nodes에 있는 노드가 이 메서드에 대한 이전 호출에 의해 이미 처리된 것으로 표시되었거나 TopologicalSorter.add()를 사용하여 그래프에 추가되지 않았거나, prepare()를 호출하지 않고 호출되었거나, 또는 get_ready()가 아직 노드를 반환하지 않았으면 ValueError를 발생시킵니다.

get_ready()

준비된 모든 노드가 담긴 tuple을 반환합니다. 처음에는 선행 노드가 없는 모든 노드를 반환하며, 일단 TopologicalSorter.done()을 호출하여 처리된 것으로 표시되면, 추가 호출은 모든 선행 노드가 이미 처리된 모든 새 노드를 반환합니다. 더는 진행할 수 없으면, 빈 튜플이 반환됩니다.

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

static_order()

Returns an iterator object which will iterate over nodes in a topological order. When using this method, prepare() and done() should not be called. This method is equivalent to:

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 모듈은 다음 예외를 정의합니다:

exception graphlib.CycleError

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

감지된 순환은 예외 인스턴스의 args 속성에서 두 번째 요소를 통해 액세스 할 수 있으며 각 노드가 그래프에서 리스트에 있는 다음 노드의 직전 선행 노드가 되도록 노드 리스트로 구성됩니다. 보고된 리스트에서, 순환임을 분명히 하기 위해, 처음과 마지막 노드는 같습니다.