lexicographical_topological_sort#

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

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

通过首先进行拓扑排序（通常有多个有效排序），然后按字典序排序，生成节点的唯一排序。

拓扑排序安排有向图的节点，使得每条有向边的上游节点先于下游节点。对于没有环的有向图，总能找到一个解决方案。可能存在多个有效解决方案。

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

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

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

Parameters:
GNetworkX 有向图

一个有向无环图 (DAG)

key函数, 可选

一个将节点名称转换为比较键的函数。它定义并解决排序顺序中的歧义。默认为恒等函数。

Yields:
nodes

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

Raises:
NetworkXError

拓扑排序仅针对有向图定义。如果图 G 是无向的，则引发 NetworkXError 。

NetworkXUnfeasible

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

RuntimeError

如果在处理返回的迭代器时 G 发生了变化。

TypeError

由于节点名称不可排序而引发。考虑使用 key= 参数来解决排序顺序中的歧义。

See also

topological_sort

Notes

该算法基于 “Introduction to Algorithms: A Creative Approach” [1] 中的描述和证明。

References

[1]

Manber, U. (1989). Introduction to Algorithms - A Creative Approach. Addison-Wesley.

Examples

>>> 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']
On this page