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()新增更多節點。

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