`graphlib` - 用于操作类图结构的功能¶

class graphlib.TopologicalSorter(graph=None)¶

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

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

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

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

创建一个 TopologicalSorter 的实例，并提供一个可选的初始图。
将其他节点添加到图中。
在图上调用 prepare()。
当 is_active() 为 True 时，迭代 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)¶

将一个新节点及其前驱节点添加到图中。node 和 predecessors 中的所有元素都必须是可哈希的。

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

可以添加没有依赖项的节点（不提供 predecessors）或提供两次依赖项。如果 predecessors 中包含了之前未提供过的节点，则该节点将自动添加到图中，并且自身没有任何前驱节点。

如果在 prepare() 之后调用，则引发 ValueError。

prepare()¶: 将图标记为已完成，并检查图中是否存在环。如果检测到任何环，将引发 CycleError，但仍然可以使用 get_ready() 获取尽可能多的节点，直到环阻止 further progress。调用此函数后，将无法修改图，因此无法再使用 add() 添加节点。

is_active()¶

如果可以取得 further progress，则返回 True，否则返回 False。如果环没有阻止解析，并且仍然有尚未由 TopologicalSorter.get_ready() 返回的准备就绪的节点，或者标记为 TopologicalSorter.done() 的节点数量少于 TopologicalSorter.get_ready() 返回的节点数量，则可以取得 further progress。

此类的 __bool__() 方法 defer 到此函数，因此无需

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() 被标记为已处理，则进一步的调用将返回所有前置节点都已处理的新节点。一旦无法取得 further 进度，则返回空元组。

如果在之前没有调用 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¶

如果工作图中存在循环，则由 TopologicalSorter.prepare() 引发的 ValueError 的子类。如果存在多个循环，则只会报告并包含其中一个未定义的选择。

可以通过异常实例的 args 属性中的第二个元素访问检测到的循环，该循环由节点列表组成，这样，图中的每个节点都是列表中下一个节点的直接前置节点。在报告的列表中，第一个和最后一个节点将相同，以表明它是循环的。

`graphlib` - 用于操作类图结构的功能¶

异常¶

目录

上一主题

下一主题

本页

graphlib - 用于操作类图结构的功能¶

异常¶

`graphlib` - 用于操作类图结构的功能¶