# `graphlib` —-- 使用類圖 (graph-like) 結構進行操作的功能

原始碼：Lib/graphlib.py

class graphlib.TopologicalSorter(graph=None)

  提供對包含可雜湊 (hashable) 節點之圖 (graph) 進行拓撲排序 (topologically sort) 的功能。

  拓撲排序是圖中頂點 (vertex) 的線性排序，使得對於從頂點 u 到頂點 v 的每條有向邊 (directed edge) u -> v，頂點 u 在排序中會位於頂點 v 之前。例如，圖的頂點可能代表要執行的任務，而邊可能代表一個任務必須在另一個任務之前執行的限制；在此範例中，拓撲排序只是任務的一種有效序列。若且唯若 (if and only if) 圖沒有有向環 (directed cycle) 時，即如果它是個有向無環圖 (directed acyclic graph)，則完整的拓撲排序才是可行的。

  如果提供了可選的 graph 引數，它必須是表示有向無環圖的字典，其中鍵是節點，值是圖中該節點的包含所有前驅節點 (predecessor) 之可疊代物件（這些前驅節點具有指向以鍵表示之節點的邊）。可以使用 `add()` 方法將其他節點新增到圖中。

  在一般情況下，對給定的圖執行排序所需的步驟如下：

  - 以選用的初始圖建立 `TopologicalSorter` 的實例。

  - 在圖中新增其他節點。

  - 呼叫圖的 `prepare()`。

  - 當 `is_active()` 為 `True` 時，疊代 `get_ready()` 回傳的節點並處理它們。在每個節點完成處理時呼叫 `done()`。

  如果只需要立即對圖中的節點進行排序且不涉及平行性 (parallelism)，則可以直接使用便捷方法 `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`。如果循環不阻塞解析 (resolution) 並且仍有節點準備就緒但尚未由 `TopologicalSorter.get_ready()` 回傳或標記為 `TopologicalSorter.done()` 的節點數量較 `TopologicalSorter.get_ready()` 所回傳的少，則可以繼續取得進度。

    此類別的 `__bool__()` 方法遵循此函式，因此以下做法：

        if ts.is_active():
            ...

    可以簡單地用以下方式替換：

        if ts:
            ...

    如果呼叫之前沒有先呼叫 `prepare()` 則引發 `ValueError`。

  done(*nodes)

    將 `TopologicalSorter.get_ready()` 回傳的一組節點標記為已處理，停止阻塞 nodes 中每個節點的任何後繼節點 (successor)，以便將來通過呼叫 `TopologicalSorter.get_ready()` 回傳。

    若沒有和該呼叫一起呼叫 `prepare()` 或節點還沒有被 `get_ready()` 回傳，且如果 nodes 中有任何節點已被先前對此方法的呼叫標記為已處理、或者未使用 `TopologicalSorter.add()` 將節點新增到圖中，則引發 `ValueError`。

  get_ready()

    回傳一個包含所有準備就緒節點的 `tuple`。最初它回傳沒有前驅節點的所有節點，一旦通過呼叫 `TopologicalSorter.done()` 來將這些節點標記為已處理後，進一步的呼叫將回傳所有其全部前驅節點都已被處理的新節點。若無法取得更多進度，將回傳空 tuple。

    如果呼叫之前沒有先呼叫 `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

  `ValueError` 的子類別，如果作用的圖中存在循環則由 `TopologicalSorter.prepare()` 引發。如果存在多個循環，則只會報告未定義的其中一個並包含在例外中。

  檢測到的循環可以通過例外實例的 `args` 屬性中第二個元素來存取，其為一個節點列表，每個節點在圖中都是列表中下一個節點的直接前驅節點（immediate predecessor，即父節點）。在報告列表中，第一個和最後一個節點將會是相同的，用以明確表示它是循環的。