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

原始碼：Lib/graphlib.py

classgraphlib.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()whiletopological_sorter.is_active():fornodeintopological_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__() 方法遵循此函式，因此以下做法：

ifts.is_active():...

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

ifts:...

如果呼叫之前沒有先呼叫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()。此方法等效於：

defstatic_order(self):self.prepare()whileself.is_active():node_group=self.get_ready()yield fromnode_groupself.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 版被加入.