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,即父節點)。在報告列表中,第一個和最後一個節點將會是相同的,用以明確表示它是循環的。