graphlib — Functionality to operate with graph-like structures使用图形结构操作的功能

Source code: Lib/graphlib.py

---

classgraphlib.TopologicalSorter(graph=None)

Provides functionality to topologically sort a graph of hashable nodes.提供对哈希节点图进行拓扑排序的功能。

A topological order is a linear ordering of the vertices in a graph such that for every directed edge u -> v from vertex u to vertex v, vertex u comes before vertex v in the ordering. 拓扑序是图中顶点的线性序，使得对于从顶点u到顶点v的每个有向边u->v，在序中顶点u位于顶点v之前。For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this example, a topological ordering is just a valid sequence for the tasks. 例如，图的顶点可以表示要执行的任务，边可以表示一个任务必须在另一个任务之前执行的约束；在本例中，拓扑排序只是任务的有效序列。A complete topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph.当且仅当图没有有向圈，即，如果它是有向无环图，则完全拓扑序是可能的。

If the optional graph argument is provided it must be a dictionary representing a directed acyclic graph where the keys are nodes and the values are iterables of all predecessors of that node in the graph (the nodes that have edges that point to the value in the key). 如果提供了可选的graph参数，则它必须是一个表示有向无环图的字典，其中键是节点，值是图中该节点的所有前置节点（具有指向键中值的边的节点）的可数。Additional nodes can be added to the graph using the add() method.可以使用add()方法将其他节点添加到图中。

In the general case, the steps required to perform the sorting of a given graph are as follows:在一般情况下，执行给定图形排序所需的步骤如下：

• Create an instance of the TopologicalSorter with an optional initial graph.使用可选的初始图创建TopologicalSorter的实例。

• Add additional nodes to the graph.向图中添加其他节点。

• Call prepare() on the graph.在图上调用prepare()。

• While is_active() is True, iterate over the nodes returned by get_ready() and process them. 当is_active()为True时，迭代get_ready()返回的节点并对其进行处理。Call done() on each node as it finishes processing.在每个节点完成处理时调用done()。

In case just an immediate sorting of the nodes in the graph is required and no parallelism is involved, the convenience method TopologicalSorter.static_order() can be used directly:如果只需要对图中的节点进行即时排序，而不涉及并行性，则可以直接使用方便的方法TopologicalSorter.static_order()：

>>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
>>> ts = TopologicalSorter(graph)
>>> tuple(ts.static_order())
('A', 'C', 'B', 'D')

The class is designed to easily support parallel processing of the nodes as they become ready. 该类设计为在节点准备就绪时轻松支持节点的并行处理。For instance:例如：

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)

Add a new node and its predecessors to the graph. 将新节点及其前置节点添加到图中。Both the node and all elements in predecessors must be hashable.predecessors中的node和所有元素都必须是可散列的。

If called multiple times with the same node argument, the set of dependencies will be the union of all dependencies passed in.如果使用同一个节点参数多次调用，则依赖项集将是传入的所有依赖项的并集。

It is possible to add a node with no dependencies (predecessors is not provided) or to provide a dependency twice. 可以添加没有依赖项的节点（不提供predecessors）或提供两次依赖项。If a node that has not been provided before is included among predecessors it will be automatically added to the graph with no predecessors of its own.如果之前未提供的节点包含在predecessors中，则该节点将自动添加到图中，而其自身没有前置节点。

Raises ValueError if called after prepare().如果在prepare()之后调用，则引发ValueError。

prepare()

Mark the graph as finished and check for cycles in the graph. 将图形标记为已完成，并检查图形中是否存在循环。If any cycle is detected, CycleError will be raised, but get_ready() can still be used to obtain as many nodes as possible until cycles block more progress. 如果检测到任何循环，则会引发CycleError，但仍然可以使用get_ready()获取尽可能多的节点，直到循环阻止更多进度。After a call to this function, the graph cannot be modified, and therefore no more nodes can be added using add().调用此函数后，无法修改图形，因此无法使用add()添加更多节点。

is_active()

Returns True if more progress can be made and False otherwise. 如果可以取得更多进展，则返回True，否则返回False。Progress can be made if cycles do not block the resolution and either there are still nodes ready that haven’t yet been returned by TopologicalSorter.get_ready() or the number of nodes marked TopologicalSorter.done() is less than the number that have been returned by TopologicalSorter.get_ready().如果周期不阻止解析，并且仍然有尚未由TopologicalSorter.get_ready()返回的节点就绪，或者标记为TopologicalSorter.done()的节点数小于TopologicalSorter.get_ready()返回的节点数，则可以取得进展。

The __bool__() method of this class defers to this function, so instead of:此类的__bool__()方法遵从此函数，因此不是：

if ts.is_active():
    ...

it is possible to simply do:可以简单地执行以下操作：

if ts:
    ...

Raises ValueError if called without calling prepare() previously.如果在之前未调用prepare()的情况下调用，则引发ValueError。

done(*nodes)

Marks a set of nodes returned by TopologicalSorter.get_ready() as processed, unblocking any successor of each node in nodes for being returned in the future by a call to TopologicalSorter.get_ready().将TopologicalSorter.get_ready()返回的一组节点标记为已处理，取消阻止nodes中每个节点的任何后续节点，以便将来通过调用TopologicalSorter.get_ready()返回。

Raises ValueError if any node in nodes has already been marked as processed by a previous call to this method or if a node was not added to the graph by using TopologicalSorter.add(), if called without calling prepare() or if node has not yet been returned by get_ready().如果nodes中的任何节点已被此方法的前一个调用标记为已处理，或者如果没有使用TopologicalSorter.add()将节点添加到图中，如果在不调用prepare()的情况下调用，或者如果get_ready()尚未返回节点，则引发ValueError。

get_ready()

Returns a tuple with all the nodes that are ready. 返回包含所有就绪节点的tuple。Initially it returns all nodes with no predecessors, and once those are marked as processed by calling TopologicalSorter.done(), further calls will return all new nodes that have all their predecessors already processed. 最初，它返回所有没有前置节点的节点，一旦这些节点通过调用TopologicalSorter.done()标记为已处理，进一步的调用将返回所有已处理其前置节点的所有新节点。Once no more progress can be made, empty tuples are returned.一旦无法取得更多进展，将返回空元组。

Raises ValueError if called without calling prepare() previously.如果在之前未调用prepare()的情况下调用，则引发ValueError。

static_order()

Returns an iterator object which will iterate over nodes in a topological order. 返回一个迭代器对象，该对象将按拓扑顺序在节点上迭代。When using this method, prepare() and done() should not be called. 使用此方法时，不应调用prepare()和done()。This method is equivalent to:该方法等效于：

def static_order(self):
    self.prepare()
    while self.is_active():
        node_group = self.get_ready()
        yield from node_group
        self.done(*node_group)

The particular order that is returned may depend on the specific order in which the items were inserted in the graph. 返回的特定顺序可能取决于项目在图中插入的特定顺序。For example:例如：

>>> 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]

This is due to the fact that “0” and “2” are in the same level in the graph (they would have been returned in the same call to get_ready()) and the order between them is determined by the order of insertion.这是因为“0”和“2”在图中处于同一级别（它们将在相同的get_ready()调用中返回），它们之间的顺序由插入顺序决定。

If any cycle is detected, CycleError will be raised.如果检测到任何循环，则会引发CycleError。

New in version 3.9.版本3.9中新增。

Exceptions异常

The graphlib module defines the following exception classes:graphlib模块定义以下异常类：

exceptiongraphlib.CycleError

Subclass of ValueError raised by TopologicalSorter.prepare() if cycles exist in the working graph. 如果工作图中存在循环，则TopologicalSorter.prepare()引发的ValueError的子类。If multiple cycles exist, only one undefined choice among them will be reported and included in the exception.如果存在多个循环，则只报告其中一个未定义的选择，并将其包括在异常中。

The detected cycle can be accessed via the second element in the args attribute of the exception instance and consists in a list of nodes, such that each node is, in the graph, an immediate predecessor of the next node in the list. 可以通过异常实例的args属性中的第二个元素访问检测到的循环，该循环包含在节点列表中，因此图中的每个节点都是列表中下一个节点的直接前身。In the reported list, the first and the last node will be the same, to make it clear that it is cyclic.在报告的列表中，第一个和最后一个节点将是相同的，以明确它是循环的。