我有一個有多個循環的定向循環圖,我需要一種方法來檢測(並列出)有向圖中存在的每個循環。檢測循環有向圖中的多個循環
該圖可以看這裏: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]
該算法必須檢測每個週期有向圖,而不僅僅是最小的,也不是第一次遇到。
您沒有真正指定您如何表示定向圖,但您可以查看Neopythonic:Detecting Cycles in directed graph。
您可能想嘗試使用此library。它有一個循環檢測算法。
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年