`graphlib` ---使用图形结构操作的功能¶

class graphlib.TopologicalSorter(graph=None)¶

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

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

如果可选图表参数必须是表示有向非循环图的字典，其中键是节点，值是图中该节点的所有前导（具有指向键中值的边的节点）的可重复项。可以使用 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 所有的元素前人必须是散列的。

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

可以添加没有依赖关系的节点( 前人或提供两次依赖项。如果以前未提供的节点包含在前人它将自动添加到图形中，而不需要自己的前置任务。

加薪 ValueError 如果在之后调用 prepare() .

prepare()¶: 将图形标记为已完成，并检查图形中是否有循环。如果检测到任何循环， CycleError 会被提高，但是 get_ready() 仍然可以用于获取尽可能多的节点，直到周期阻止更多的进度。调用此函数后，无法修改图形，因此不能使用 add() .

is_active()¶

返回 True 如果能取得更多进展 False 否则。如果周期不阻止解决方案，或者仍有节点准备就绪，但尚未返回 TopologicalSorter.get_ready() 或标记的节点数 TopologicalSorter.done() 小于返回的数字 TopologicalSorter.get_ready() .

这个 __bool__() 这个类的方法属于这个函数，因此不是：

if ts.is_active():
    ...

可以简单地做：

if ts:
    ...

加薪 ValueError 如果不打电话就打 prepare() 以前。

done(*nodes)¶

标记由返回的一组节点 TopologicalSorter.get_ready() 在处理时，解除阻止中每个节点的任何后续节点结点因为在未来被打电话给 TopologicalSorter.get_ready() .

加薪 ValueError 如果有节点在结点已被此方法的上一个调用标记为已处理，或者如果使用 TopologicalSorter.add() ，如果不打电话就打 prepare() 或者如果节点尚未返回 get_ready() .

get_ready()¶

返回A tuple 所有节点都准备好了。最初，它返回没有前置任务的所有节点，一旦这些节点被标记为通过调用 TopologicalSorter.done() ，进一步的调用将返回所有已处理其所有前置任务的新节点。一旦不能再取得进展，就会返回空元组。

加薪 ValueError 如果不打电话就打 prepare() 以前。

static_order()¶

以拓扑顺序返回一个节点的iterable。使用此方法不需要调用 TopologicalSorter.prepare() 或 TopologicalSorter.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` ---使用图形结构操作的功能¶

例外情况¶

Table of Contents

上一个主题

下一个主题

graphlib ---使用图形结构操作的功能¶

例外情况¶

`graphlib` ---使用图形结构操作的功能¶