Cliques in python

Question

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

Expiry

Your example doesn't have valid indentation. Please make sure you post examples with valid indentation when posting Python code. – Omalley

All the cliques with size >= 3 will contain complete_graph(3). You don't care about the rest? – Falsehood

So how can I write a code for search all K3 and eliminate them by delete one edge from all k3 on the graph? – Expiry

No, I worked on a project and this is a small part of it. – Expiry

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

Location

Looking at the source code, if I'm not mistaken, the generator works on static values. It won't know that you altered the graph. But cliques returned by find_cliques might share edges. – Falsehood

@machineyearning Can you please check out this question #45766741 – Colpitis

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

Ventriloquism

This is what I got: Traceback (most recent call last): File "C:Graph1.py", line 119, in <module> GC.remove_edge(clique[0], clique[1]) File "C:\Python27\lib\site-packages\networkx-1.6-py2.7.egg\networkx\classes \graph.py", line 859, in remove_edge raise NetworkXError("The edge %s-%s is not in the graph"%(u,v)) NetworkXError: The edge 2-11 is not in the graph – Expiry