python - 循環有向グラフでの複数サイクルの検出

Question

複数のサイクルを含む有向非巡回グラフがあり、ダイグラフに存在する各サイクルを検出（および一覧表示）する方法が必要です。

グラフはここで見ることができます：http：//img412.imageshack.us/img412/3327/schematic.gif

これは、Pythonスクリプトをデバッグするためにまとめたダミーグラフです。サイクルが含まれています：

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

アルゴリズムは、最小のものだけでなく、最初に遭遇したものだけでなく、有向グラフのすべてのサイクルを検出する必要があります。

score 2 · Accepted Answer

有向グラフをどのように表現するかを実際に指定していませんが、Neopythonic：有向グラフでのサイクルの検出を確認できます。

score 1 · Accepted Answer

私の知る限り、python-graph は、考えられるすべてのサイクルではなく、1 つのサイクルのみを検出します。見る：

この他の記事は、この質問で提示された問題を解決するようです:

1972 年に RE Tarjan によって考案されたアルゴリズムを使用しています。

score 0 · Accepted Answer

このライブラリを試してみてください。サイクル検出アルゴリズムを備えています。

3 に答える 3