检测有向图中的多个环

Question

我有一个有向图，这个图里有不止一个循环，我需要一种方法来检测并列出图中每一个循环。

你可以在这里看到这个图： http://img412.imageshack.us/img412/3327/schematic.gif

这个图是我为了调试我的Python脚本而随便画的。它包含了以下循环：

[n13, n14], [n6, n8, n15, n16, n7], [n6, n8, n9, n7]

这个算法必须能够检测到有向图中的每一个循环，而不仅仅是最小的或者第一个遇到的循环。

Answer 1

你可以试试这个库。它里面有一个可以检测循环的算法。

Answer 2

据我所知，python-graph 这个库只能找到一个循环，而不是所有可能的循环。你可以查看这个链接了解更多：

http://groups.google.com/group/python-graph/browse_thread/thread/9170926f1bdd097b

另外一篇文章似乎解决了这个问题：

http://www.bitformation.com/art/python_toposort.html

这篇文章使用了 R. E. Tarjan 在1972年提出的算法。

Answer 3

你没有具体说明你是怎么表示有向图的，不过你可以看看这个链接：Neopythonic: 检测有向图中的循环。