Implementing Bron–Kerbosch algorithm in python

问题:

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 ?

回答1:

Python is getting confused because you are modifying the list that it is iterating over.

Change

for vertex in p:

to

for vertex in p[:]:

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.

回答2:

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

def bronk2(R, P, X, g):
    if not any((P, X)):
        yield R
    for v in P[:]:
        R_v = R + [v]
        P_v = [v1 for v1 in P if v1 in N(v, g)]
        X_v = [v1 for v1 in X if v1 in N(v, g)]
        for r in bronk2(R_v, P_v, X_v, g):
            yield r
        P.remove(v)
        X.append(v)
def N(v, g):
    return [i for i, n_v in enumerate(g[v]) if n_v]

In [99]: list(bronk2([], range(6), [], graph))
Out[99]: [[0, 1, 4], [1, 2], [2, 3], [3, 4], [3, 5]]

In case someone is looking for a Bron–Kerbosch algorithm implementation in the future...