4

この問題があり、助けが必要です。これが私のコードです:

      cliques=[clique for clique in nx.find_cliques(GC) if len(clique)>2]    

      for clique in cliques:
        if len (clique)==3:
        GC.remove_edge()
        print "Clique to appear: ",clique
      #draw the graph        
      nx.draw(GC)
      plt.show()

最初にグラフを検索してクリークを見つけ、その後長さ 3 のクリークかどうかをテストし、それが true の場合は 1 つのエッジを削除したいので、complete-graph(3) を削除できます。どうやってやるの？

ありがとう

4

2 に答える 2

4

ここで最も難しい問題は、共有エッジの処理だと思います。エッジを削除するたびにクリークを検索する必要はありませんが、すでに削除したエッジを覚えておく必要があります。

ドキュメントを見ると、find_cliques関数がジェネレーターであることがわかります。

この実装は、それぞれが最大クリークのメンバーを含むリストのジェネレーターです。

これは、クリークを生成し、エッジを削除してから、次のクリークを生成できることを意味します。ジェネレータは、エッジが削除されたことを認識しますか？

この質問に別の質問で答えます。クリークを分解するたびにジェネレーターから抜け出してみませんか？

edge_removed = True
while edge_removed:
    edge_removed = False
    for clique in nx.find_cliques(GC):
        if len (clique)>=3:
            GC.remove_edge(clique[0], clique[1])
            edge_removed = True
            break # Gotta restart the generator now...

グラフでクリークを検出するだけでもNP完全であるため、クリークを使用して行うことはすべて、非常にリソースを消費する可能性があることに注意する必要があります。

于 2012-03-15T04:11:32.680 に答える
0 
if len(clique)==3:
    GC.remove_edge(*clique[0:2])

または（同等）

if len(clique)==3:
    GC.remove_edge(clique[0], clique[1])

しかし、それは明らかであり、私は専門家ではないため、重要なことを見逃している可能性があります-networkxドキュメントを読んだだけです（クリークはノードのリストであり、remove_edge2つのノードが必要であると書かれています）。

于 2012-03-15T03:20:45.423 に答える