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 属性中的第二个元素访问，它由一个节点列表组成，使得图中的每个节点都是列表中下一个节点的直接前驱。在报告的列表中，第一个节点和最后一个节点将相同，以明确它是循环的。