graphlib — 操作圖狀結構的功能

原始碼: Lib/graphlib.py

class graphlib.TopologicalSorter(graph=None)

提供拓撲排序可雜湊節點圖的功能。

拓撲排序是圖中頂點的線性排序，使得對於從頂點 u 到頂點 v 的每條有向邊 u -> v，頂點 u 在排序中都出現在頂點 v 之前。例如，圖的頂點可以表示要執行的任務，邊可以表示一個任務必須在另一個任務之前執行的約束；在這個例子中，拓撲排序就是任務的一個有效序列。當且僅當圖沒有有向迴圈，即它是一個有向無環圖時，才可能進行完整的拓撲排序。

如果提供了可選的 graph 引數，它必須是一個表示有向無環圖的字典，其中鍵是節點，值是該節點在圖中的所有前驅（具有指向該鍵中值的邊的節點）的可迭代物件。可以使用 add() 方法向圖中新增其他節點。

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

如果只需要對圖中的節點進行立即排序，並且不涉及並行處理，可以直接使用便利方法 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() 新增節點。

如果已透過 static_order() 或 get_ready() 啟動排序，則會引發 ValueError。

3.14 版本中的變化: 只要排序未開始，prepare() 現在可以多次呼叫。以前這會引發 ValueError。

is_active()

如果可以取得更多進展則返回 True，否則返回 False。如果迴圈不阻塞解析，並且仍然有尚未透過 TopologicalSorter.get_ready() 返回的已準備好的節點，或者標記為 TopologicalSorter.done() 的節點數量少於透過 TopologicalSorter.get_ready() 返回的節點數量，則可以取得進展。

此類的 __bool__() 方法會委託給此函式，因此無需

if ts.is_active():
    ...

只需執行即可

if ts:
    ...

如果未事先呼叫 prepare()，則會引發 ValueError。

done(*nodes)

將 TopologicalSorter.get_ready() 返回的一組節點標記為已處理，解除對 nodes 中每個節點的所有後繼節點的阻塞，以便將來透過呼叫 TopologicalSorter.get_ready() 返回。

如果 nodes 中的任何節點已透過先前的此方法呼叫標記為已處理，或者節點未透過 TopologicalSorter.add() 新增到圖中，或者在未呼叫 prepare() 的情況下呼叫，或者節點尚未透過 get_ready() 返回，則會引發 ValueError。

get_ready()

返回一個 tuple，其中包含所有已準備好的節點。最初，它返回所有沒有前驅的節點，一旦這些節點透過呼叫 TopologicalSorter.done() 被標記為已處理，後續呼叫將返回所有已處理其所有前驅的新節點。一旦無法再取得進展，將返回空元組。

如果未事先呼叫 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 屬性中的第二個元素訪問，它由一個節點列表組成，使得圖中的每個節點都是列表中下一個節點的直接前驅。在報告的列表中，第一個節點和最後一個節點將相同，以明確它是迴圈的。