topological_sort#

topological_sort(G)[源代码]#

返回拓扑排序顺序的节点生成器。

拓扑排序是有向图的节点的非唯一排列，使得从u到v的边意味着在拓扑排序顺序中u出现在v之前。仅当图没有有向圈时，此排序才有效。

参数
G网络X有向图

有向无环图(DAG)

产量
节点

以拓扑排序的顺序生成节点。

加薪
NetworkXError

拓扑排序仅为有向图定义。如果该图 G 是无定向的，则为 NetworkXError 都被养大了。

NetworkXUnfeasible

如果 G 不是有向无环图(DAG)不存在拓扑排序，并且 NetworkXUnfeasible 引发异常。在以下情况下也可以引发此问题 G 在处理返回的迭代器时更改

RuntimeError

如果 G 在处理返回的迭代器时发生更改。

参见

is_directed_acyclic_graph, lexicographical_topological_sort

笔记

该算法基于《算法导论：创造性方法》中的描述和证明。 [1] 。

工具书类

1

Manber，U.（1989年）。 Introduction to Algorithms - A Creative Approach. Addison Wesley。

实例

要获得拓扑排序的逆顺序，请执行以下操作：

>>> DG = nx.DiGraph([(1, 2), (2, 3)])
>>> list(reversed(list(nx.topological_sort(DG))))
[3, 2, 1]

如果您的有向图自然具有表示任务/输入的边缘，以及表示启动任务的人员/流程的节点，那么拓扑排序并不完全符合您的需要。您必须将任务更改为依赖于边的节点。结果是一种拓扑类型的边。这可以用 networkx.line_graph() 如下：

>>> list(nx.topological_sort(nx.line_graph(DG)))
[(1, 2), (2, 3)]