lexicographical_topological_sort#

lexicographical_topological_sort(G, key=None)[source]#

生成唯一词典序拓扑排序中的节点。

通过先进行拓扑排序（通常有多种有效排序），然后额外进行词典序排序，生成唯一的节点顺序。

拓扑排序排列有向图的节点，使得每条有向边的上游节点在其下游节点之前。对于没有环的有向图，总是可以找到一个解。可能存在多个有效解。

词典序排序就是按字母顺序排序。在这里用于打破拓扑排序中的平局，并确定唯一的排序。这对于比较排序结果很有用。

可以通过为 key= 参数提供一个函数来定制词典序。key 函数的定义与 Python 内置的 sort() 中使用的相同。该函数接受一个参数，并返回一个用于排序目的的键。

如果节点名称不可排序，词典序排序可能会失败。请参阅下面的示例。解决方案是为 key= 参数提供一个函数，该函数返回可排序的键。

参数:
GNetworkX 有向图

有向无环图 (DAG)

key函数，可选

一个接受一个参数的函数，用于将节点名称转换为比较键。它定义并解决排序顺序中的模糊性。默认为恒等函数。

生成:
节点

按词典序拓扑排序顺序生成 G 的节点。

抛出:
NetworkXError

拓扑排序仅适用于有向图。如果图 G 是无向的，则抛出 NetworkXError。

NetworkXUnfeasible

如果 G 不是有向无环图 (DAG)，则不存在拓扑排序，并抛出 NetworkXUnfeasible 异常。如果在处理返回的迭代器时更改了 G，也可能抛出此异常。

RuntimeError

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

TypeError

由不可排序的节点名称导致。考虑使用 key= 参数来解决排序顺序中的模糊性。

另请参阅

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]

对于包含整数和字符串节点的任何图，排序都会失败。Python 中未定义整数与字符串的比较。3 比 'red' 大还是小？

>>> DG = nx.DiGraph([(1, "red"), (3, "red"), (1, "green"), (2, "blue")])
>>> list(nx.lexicographical_topological_sort(DG))
Traceback (most recent call last):
...
TypeError: '<' not supported between instances of 'str' and 'int'
...

可以使用 key 函数来解决不可比较的节点。这个示例函数通过返回一个元组来实现整数和字符串的比较，其中第一个元素对于 str 为 True，否则为 False。第二个元素是节点名称。这会将字符串和整数分开分组，以便它们只能在各自的组内进行比较。

>>> key = lambda node: (isinstance(node, str), node)
>>> list(nx.lexicographical_topological_sort(DG, key=key))
[1, 2, 3, 'blue', 'green', 'red']
在此页上