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