graphlib --- 操作類似圖的結(jié)構(gòu)的功能?

源代碼: Lib/graphlib.py

class graphlib.TopologicalSorter(graph=None)?

提供以拓撲方式對可哈希節(jié)點的圖進行排序的功能。

拓撲排序是指圖中頂點的線性排序，使得對于每條從頂點 u 到頂點 v 的有向邊 u -> v，頂點 u 都排在頂點 v 之前。 例如，圖的頂點可以代表要執(zhí)行的任務(wù)，而邊代表某一個任務(wù)必須在另一個任務(wù)之前執(zhí)行的約束條件；在這個例子中，拓撲排序只是任務(wù)的有效序列。 完全拓撲排序 當且僅當圖不包含有向環(huán)，也就是說為有向無環(huán)圖時，完全拓撲排序才是可能的。

如果提供了可選的 graph 參數(shù)則它必須為一個表示有向無環(huán)圖的字典，其中的鍵為節(jié)點而值為包含圖中該節(jié)點的所有上級節(jié)點（即具有指向鍵中的值的邊的節(jié)點）的可迭代對象。 額外的節(jié)點可以使用 add() 方法添加到圖中。

在通常情況下，對給定的圖執(zhí)行排序所需的步驟如下:

• 通過可選的初始圖創(chuàng)建一個 TopologicalSorter 的實例。

• 添加額外的節(jié)點到圖中。

• 在圖上調(diào)用 prepare()。

• 當 is_active() 為 True 時，迭代 get_ready() 所返回的節(jié)點并加以處理。 完成處理后在每個節(jié)點上調(diào)用 done()。

在只需要對圖中的節(jié)點進行立即排序并且不涉及并行性的情況下，可以直接使用便捷方法 TopologicalSorter.static_order():

>>>

>>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
>>> ts = TopologicalSorter(graph)
>>> tuple(ts.static_order())
('A', 'C', 'B', 'D')

這個類被設(shè)計用來在節(jié)點就緒時方便地支持對其并行處理。 例如:

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)?

將一個新節(jié)點及其上級節(jié)點添加到圖中。 node 以及 predecessors 中的所有元素都必須為可哈希對象。

如果附帶相同的節(jié)點參數(shù)多次調(diào)用，則依賴項的集合將為所有被傳入依賴項的并集。

可以添加不帶依賴項的節(jié)點 (即不提供 predecessors) 或者重復提供依賴項。 如果有先前未提供的節(jié)點包含在 predecessors 中則它將被自動添加到圖中并且不帶自己的上級節(jié)點。

如果在 prepare() 之后被調(diào)用則會引發(fā) ValueError。

prepare()?

將圖標記為已完成并檢查圖中是否存在環(huán)。 如何檢測到任何環(huán)，則將引發(fā) CycleError，但 get_ready() 仍可被用來獲取盡可能多的節(jié)點直到環(huán)阻塞了操作過程。 在調(diào)用此函數(shù)后，圖將無法再修改，因此不能再使用 add() 添加更多的節(jié)點。

is_active()?

如果可以取得更多進展則返回 True，否則返回 False。 如果環(huán)沒有阻塞操作，并且還存在尚未被 TopologicalSorter.get_ready() 返回的已就緒節(jié)點或者已標記為 TopologicalSorter.done() 的節(jié)點數(shù)量少于已被 TopologicalSorter.get_ready() 所返回的節(jié)點數(shù)量則還可以取得進展。

該類的 __bool__() 方法要使用此函數(shù)，因此除了:

if ts.is_active():
    ...

可能會簡單地執(zhí)行:

if ts:
    ...

如果之前未調(diào)用 prepare() 就調(diào)用此函數(shù)則會引發(fā) ValueError。

done(*nodes)?

將 TopologicalSorter.get_ready() 所返回的節(jié)點集合標記為已處理，解除對 nodes 中每個節(jié)點的后續(xù)節(jié)點的阻塞以便在將來通過對 TopologicalSorter.get_ready() 的調(diào)用來返回它們。

如果 nodes 中的任何節(jié)點已經(jīng)被之前對該方法的調(diào)用標記為已處理或者如果未通過使用 TopologicalSorter.add() 將一個節(jié)點添加到圖中，如果未調(diào)用 prepare() 即調(diào)用此方法或者如果節(jié)點尚未被 get_ready() 所返回則將引發(fā) ValueError。

get_ready()?

返回由所有已就緒節(jié)點組成的 tuple。 初始狀態(tài)下它將返回所有不帶上級節(jié)點的節(jié)點，并且一旦通過調(diào)用 TopologicalSorter.done() 將它們標記為已處理，之后的調(diào)用將返回所有上級節(jié)點已被處理的新節(jié)點。 一旦無法再取得進展，則會返回空元組。

如果之前未調(diào)用 prepare() 就調(diào)用此函數(shù)則會引發(fā) ValueError。

static_order()?

返回一個迭代器，它將按照拓撲順序來迭代所有節(jié)點。 當使用此方法時，prepare() 和 done() 不應被調(diào)用。 此方法等價于:

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() 的同一次調(diào)用中被返回） 并且它們之間的順序是由插入順序決定的。

如果檢測到任何環(huán)，則將引發(fā) CycleError。

3.9 新版功能.