"graphlib" --- Functionality to operate with graph-like structures
******************************************************************

**소스 코드:** 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()

      노드들을 위상 순서로 이터레이트하는 이터레이터 객체를 반환합니다
      . 이 메서드를 사용할 때, "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" 모듈은 다음 예외를 정의합니다:

exception graphlib.CycleError

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

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