for a college project I'm trying to implement the Bron–Kerbosch algorithm, that is, listing all maximal cliques in a given graph.
I'm trying to implement the first algorithm (without pivoting) , but my code doesn't yield all the answers after testing it on the Wikipedia's example , my code so far is :
# dealing with a graph as list of lists
graph = [[0,1,0,0,1,0],[1,0,1,0,1,0],[0,1,0,1,0,0],[0,0,1,0,1,1],[1,1,0,1,0,0],[0,0,0,1,0,0]]
#function determines the neighbors of a given vertex
def N(vertex):
c = 0
l = []
for i in graph[vertex]:
if i is 1 :
l.append(c)
c+=1
return l
#the Bron-Kerbosch recursive algorithm
def bronk(r,p,x):
if len(p) == 0 and len(x) == 0:
print r
return
for vertex in p:
r_new = r[::]
r_new.append(vertex)
p_new = [val for val in p if val in N(vertex)] # p intersects N(vertex)
x_new = [val for val in x if val in N(vertex)] # x intersects N(vertex)
bronk(r_new,p_new,x_new)
p.remove(vertex)
x.append(vertex)
bronk([], [0,1,2,3,4,5], [])
Any help why I'm getting only a part of the answer ?
As @VaughnCato correctly points out the error was iterating over
P[:]
. I thought it worth noting that you can "yield" this result, rather than printing, as follows (in this refactored code):In case someone is looking for a Bron–Kerbosch algorithm implementation in the future...
Python is getting confused because you are modifying the list that it is iterating over.
Change
to
this will cause it to iterate over a copy of p instead.
You can read more about this at http://effbot.org/zone/python-list.htm.