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() 所回傳的少，則可以繼續取得進度。

The __bool__() method of this class defers to this function, so instead of:

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() 引發。如果存在多個循環，則只會報告未定義的其中一個並包含在例外中。

The detected cycle can be accessed via the second element in the args attribute of the exception instance and consists in a list of nodes, such that each node is, in the graph, an immediate predecessor of the next node in the list. In the reported list, the first and the last node will be the same, to make it clear that it is cyclic.