Advertisement
Guest User

Untitled

a guest
Mar 17th, 2014
259
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.59 KB | None | 0 0
  1. # Returns false if G does not have a clique of size k. Otherwise it returns G. Note
  2. # that returning G does not necesarily implies G has a clique of size >= k.
  3. def hasLargeClique(G,k):
  4.     n = G.order()
  5.  
  6.     if n < 250:
  7.         c = G.clique_number()
  8.         if c < k :
  9.             return false
  10.         return G
  11.  
  12.     O = G.automorphism_group(return_group=false, orbits=True)
  13.     o = min(O, key=lambda x: G.degree(x[0]))
  14.     v = o[0]
  15.     ret = hasLargeClique(subgraph(G, G[v]), k - 1)
  16.  
  17.     if ret: return G
  18.  
  19.     H = G.copy()
  20.  
  21.     H.delete_vertices(o)
  22.     return hasLargeClique(H,k)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement