我有一个有多个循环的有向循环图，我需要一种方法来检测（和列出）有向图中的每个循环 .
图表可以在这里看到：http://img412.imageshack.us/img412/3327/schematic.gif
这是为了调试我的python脚本而放在一起的虚拟图 . 它包含周期：
[n13, n14], [n6, n8, n15, n16, n7], [n6, n8, n9, n7]
该算法必须检测有向图中的每个周期，而不仅仅是它遇到的最小值和第一个周期 .
我有一个有多个循环的有向循环图，我需要一种方法来检测（和列出）有向图中的每个循环 .
图表可以在这里看到：http://img412.imageshack.us/img412/3327/schematic.gif
这是为了调试我的python脚本而放在一起的虚拟图 . 它包含周期：
[n13, n14], [n6, n8, n15, n16, n7], [n6, n8, n9, n7]
该算法必须检测有向图中的每个周期，而不仅仅是它遇到的最小值和第一个周期 .
3 回答
您没有真正指定如何表示定向图，但您可以查看Neopythonic:Detecting Cycles in directed graph .
AFAIK，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年设计的算法
您可能想尝试使用此library . 它有一个循环检测算法 .