Cliques in python

问题:

I have this problem and I need help with it, this is my code:

      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()

first I searched in my graph to find cliques, after that I test if the clique of length 3, if its true I want to delete one edge So I can eliminate complete-graph(3). How can I do that?

Thanks

回答1:

I think the trickiest problem here is dealing with shared edges. You don't want to search for cliques each time you remove an edge, and yet you need to remember which edges you've already removed.

Looking at the documentation, we find that the find_cliques function is a generator.

This implementation is a generator of lists each of which contains the members of a maximal clique

Does this mean that you can generate a clique, remove an edge, and then generate the next clique, and our generator will know that we've removed an edge?

Answering this question with another question: why not just break out of the generator each time you break down a clique?

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...

You have to keep in mind that ANYTHING you do with cliques has the potential to be very resource-consuming, since even simply detecting a clique in a graph is NP-complete.

回答2:

if len(clique)==3:
    GC.remove_edge(*clique[0:2])

or (equivalent)

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

but i may be missing something important because that seems obvious and i'm no expert - i just read the networkx docs (which say that a clique is a list of nodes, and that remove_edge takes two nodes).