lexicographical_topological_sort

lexicographical_topological_sort(G, key=None)

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

拓扑排序是节点的非唯一排列，因此从u到v的边意味着u以拓扑排序顺序出现在v之前。

参数

G网络X有向图

有向无环图(DAG)

key函数，可选

此函数将节点映射到键，用来解决排序顺序中的歧义。默认为标识函数。

产量

节点

以词典编纂的拓扑排序顺序生成节点。

加薪

NetworkXError

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

NetworkXUnfeasible

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

RuntimeError

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

参见

topological_sort

笔记

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

工具书类

1

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

实例

>>> DG = nx.DiGraph([(2, 1), (2, 5), (1, 3), (1, 4), (5, 4)])
>>> list(nx.lexicographical_topological_sort(DG))
[2, 1, 3, 5, 4]
>>> list(nx.lexicographical_topological_sort(DG, key=lambda x: -x))
[2, 5, 1, 4, 3]