graphlib — 操作图形结构的功能

源代码： :source:`Lib/graphlib.py`

class graphlib.TopologicalSorter(graph=None)

提供对可散列节点图进行拓扑排序的功能。

拓扑顺序是图中顶点的线性排序，使得对于从顶点 u 到顶点 v 的每条有向边 u -> v，顶点 u 在排序中排在顶点 v 之前。例如，图的顶点可以表示要执行的任务，边可以表示一个任务必须在另一个任务之前执行的约束；在这个例子中，拓扑排序只是任务的有效序列。当且仅当图没有有向环，即，如果它是有向无环图，则完整的拓扑排序是可能的。

如果提供了可选的 graph 参数，它必须是一个表示有向无环图的字典，其中键是节点，值是图中该节点的所有前驱（具有指向键中的值）。可以使用 add() 方法将其他节点添加到图中。

在一般情况下，对给定图进行排序所需的步骤如下：

使用可选的初始图创建 TopologicalSorter 的实例。

向图中添加其他节点。

在图表上调用 prepare()。

当 is_active() 是 True 时，迭代 [X76X]get_ready() 返回的节点并处理它们。在每个节点完成处理时调用 done()。

如果只需要对图中的节点进行立即排序并且不涉及并行性，则可以直接使用便捷方法 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)

向图中添加一个新节点及其前驱节点。节点和 前驱体 中的所有元素都必须是可散列的。

如果使用相同的节点参数多次调用，则依赖集将是传入的所有依赖项的并集。

可以添加一个没有依赖项的节点（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 将节点添加到图中，则引发 ValueError ()，如果在没有调用 prepare() 的情况下调用，或者节点尚未被 get_ready() 返回。

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

graphlib — 使用类似图的结构进行操作的功能 — Python 文档

graphlib — 操作图形结构的功能

例外