all_topological_sorts#

all_topological_sorts(G)[源代码]#

返回的生成器 _all_ 有向图G的拓扑类。

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

参数
G网络X有向图

有向图

产量
topological_sort_order列表

中的节点列表 G ,表示一种拓扑排序顺序

加薪
NetworkXNotImplemented

如果 G 不定向

NetworkXUnfeasible

如果 G 不是非循环的

笔记

实现中给出的算法的迭代版本 [1] .

工具书类

1

Knuth,Donald E.,Szwarcfiter,Jayme L.(1974年)。”生成所有拓扑排序安排的结构化程序“信息处理信函”,第2卷,1974年第6期,第153-157页,ISSN 0020-0190,https://doi.org/10.1016/0020-0190(74)90001-5。爱思唯尔(北荷兰),阿姆斯特丹

实例

要枚举所有拓扑类型的有向图:

>>> DG = nx.DiGraph([(1, 2), (2, 3), (2, 4)])
>>> list(nx.all_topological_sorts(DG))
[[1, 2, 4, 3], [1, 2, 3, 4]]