python - ネットワークの内部ループの削除

Question

多くの自己ループで構成される大きなグラフがあります。大きな (外部) ループが 1 つだけ残るように、すべての内部ループを削除しようとしています。特定のループ内のすべてのエッジを見つける方法はありますか? 私は使ってみましgraph.nodes_with_selfloops()たgraph.selfloop_edgesが、どちらもあまりうまくいきませんでした。

Answer 1

networkx.algorithmsライブラリを使用してこの問題に取り組む方法を見つけました。

import networkx as netx
import networkx.algorithms as al

# build graph
g = netx.DiGraph()
edges = [(1,2),(2,3),(3,4),(4,1),(1,2),(2,5),(5,3),(3,4),(4,1)]
g.add_edges_from(edges)

# find cycles
cycles = al.simple_cycles(g)

# assuming that the exterior cycle will contain the most nodes
for cycle in cycles:
    print len(cycle)

結果は次のようになります。

>>> 5

>>> 6