python - 是否可以（快速）在networkx图中仅找到第一个循环？

Question

我有一个定向网络，其中可能有也可能没有循环。我需要找到它们并消除周期性。如果我有一个 networkx DiGraph (G)，我可以找到所有的循环

cycle_nodes = nx.simple_cycles(G)

它创建了一个循环返回生成器。

但是，我不想返回所有循环，list(cycle_nodes)因为许多循环是彼此的子集，修复一个会修复其他循环。相反，我只想找到循环的第一个实例。作为cycle_nodes发电机，我试过了

next(cycle_nodes)

只返回第一个实例。但是，我发现返回第一个实例所需的时间与返回所有实例所需的时间相比并没有小多少：

list(cycle_nodes) : 58s
next(cycle_nodes) : 44s

这仅仅是由于我的图表的性质（即第一个循环远离搜索顺序），还是有更有效的方法来返回任何循环（不一定需要是第一个）？

我怀疑可能有更快的方法的原因是因为当我运行时nx.is_directed_acyclic_graph(G)，它只需要一两秒钟并返回 False，所以它显然在一秒钟左右找到至少一个循环。

标签： pythonpython-3.xnetworkxcycle

Answer 1

答案很明显。没有提供起始节点的算法 nx.find_cycle() 将快速返回它找到的第一个循环。我的印象是需要提供一个起始节点，RTFM！