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() 方法將其他節點新增到圖中。

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

如果只需要立即對圖中的節點進行排序且不涉及平行性 (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，即父節點）。在報告列表中，第一個和最後一個節點將會是相同的，用以明確表示它是循環的。