파이썬에서 Bron-Kerbosch 알고리즘 구현 대학 프로젝트 용

Question

주어진 그래프에서 모든 최대 클럭을 나열하는 Bron–Kerbosch algorithm을 구현하려고합니다.

는

내가 (회전없이) 최초의 알고리즘을 구현하기 위해 노력하고있어,하지만 내 코드는 Wikipedia's example에서 테스트 한 후 모든 해답을 얻을하지 않습니다, 내 코드는 지금까지 있습니다 :

# 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], []) 

어떤 도움 왜 나는 대답의 일부만을 얻고 있는가?

Answer 1

반복되는 목록을 수정하기 때문에 Python이 혼란스러워집니다.

변경

for vertex in p: 

for vertex in p[:]: 

이는 대신 페이지의 복사본을 반복하게됩니다.

자세한 내용은 http://effbot.org/zone/python-list.htm에서 확인할 수 있습니다.

Answer 2

@VaughnCato가 정확하게 오류가 P[:]을 반복하고 있음을 지적했습니다. 경우 누군가에

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

는 미래에 브론 - Kerbosch 알고리즘 구현을 찾고있다 : 나는 그것이 가치가 당신이 할 수있는 "수율"이 결과가 아니라 인쇄보다,로 (이 리팩토링 코드에서) 다음 것을주의 생각 ...