graphlib --- 操作類(lèi)似圖的結構的功能?

源代碼: Lib/graphlib.py

class graphlib.TopologicalSorter(graph=None)?

提供以拓撲方式對可哈希節點(diǎn)的圖進(jìn)行排序的功能。

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

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

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

• 通過(guò)可選的初始圖創(chuàng )建一個(gè) TopologicalSorter 的實(shí)例。

• 添加額外的節點(diǎn)到圖中。

• 在圖上調用 prepare()。

• 當 is_active() 為 True 時(shí)，迭代 get_ready() 所返回的節點(diǎn)并加以處理。 完成處理后在每個(gè)節點(diǎn)上調用 done()。

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

>>>

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

這個(gè)類(lèi)被設計用來(lái)在節點(diǎn)就緒時(shí)方便地支持對其并行處理。 例如:

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

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

如果附帶相同的節點(diǎn)參數多次調用，則依賴(lài)項的集合將為所有被傳入依賴(lài)項的并集。

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

如果在 prepare() 之后被調用則會(huì )引發(fā) ValueError。

prepare()?

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

is_active()?

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

該類(lèi)的 __bool__() 方法要使用此函數，因此除了:

if ts.is_active():
    ...

可能會(huì )簡(jiǎn)單地執行:

if ts:
    ...

如果之前未調用 prepare() 就調用此函數則會(huì )引發(fā) ValueError。

done(*nodes)?

將 TopologicalSorter.get_ready() 所返回的節點(diǎn)集合標記為已處理，解除對 nodes 中每個(gè)節點(diǎn)的后續節點(diǎn)的阻塞以便在將來(lái)通過(guò)對 TopologicalSorter.get_ready() 的調用來(lái)返回它們。

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

get_ready()?

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

如果之前未調用 prepare() 就調用此函數則會(huì )引發(fā) ValueError。

static_order()?

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

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]

這是由于實(shí)際上 "0" 和 "2" 在圖中的級別相同（它們將在對 get_ready() 的同一次調用中被返回） 并且它們之間的順序是由插入順序決定的。

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

3.9 新版功能.