私は非常にばかげた方法でリング検出プログラムを書きました。誰でもそれを改善するのを助けることができますか? 次のコードは、すべての 5 員環を見つけるためのものです。N 員環 (N は通常 10 未満) を見つけることができる一般的な関数が必要です。ありがとうございます!
私の問題では、約2000ポイントあります。各ポイントは他のいくつかのポイントに接続されており、これらの接続されたポイントは に保存されneighbor_listます。そして、point[i].neighbor_list()point[i] の近傍のリストを返します。次のコードのアイデアは、1 つのポイントから開始し、そのネイバー リストとそのネイバーのネイバー リストをトラバースし、ルート/サイクル/リングを見つけて元のポイントに戻るというものです。私のコードの中心部分は次のとおりです。これは、5 つのポイントで形成されたリングのみを検索します。すべての N 員環を検索するには、一般的なコードが必要です。何か不明な点があればコメントを残してください。
for r0 in range(2000): #ring member 0
rin.append(r0)
for r1 in point[r0].neighbor_list():
rin.append(r1) #ring member 1
for r2 in point[r1].neighbor_list():
if r2 == r0: continue # to avoid the case of a-b-a ...
else: rin.append(r2)
for r3 in point[r2].neighbor_list():
if r3 == r1: continue
else: rin.append(r3)
for r4 in point[r3].neighbor_list():
if r4 == r2: continue
else: rin.append(r4)
for r5 in point[r4].neighbor_list():
if r5 == r0:
rin.append(r5)
rings.append(list(rin)) # find a ring, save it
rin.pop()
else: continue
rin.pop()
rin.pop()
rin.pop()
rin.pop()
rin.pop()