在python中實現Bron-Kerbosch算法

我試圖實現Bron–Kerbosch algorithm，即列出給定圖中的所有最大派系。在python中實現Bron-Kerbosch算法

我想實現第一種算法（不轉動），但在測試它的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], [])

任何幫助爲什麼我只能得到答案的一部分？

來源

2012-12-16 a.u.r

第一件事情 - 沒有爲值比較使用'is' - 那就是''==是 –

我建議不要使用遞歸的副作用（遞歸本身是棘手足以讓那些圍繞頭！）。 *另外，你可以使用list comprehension和['enumerate']來編寫'N'（http://docs.python.org/2/library/functions.html#enumerate）。* –

Python越來越困惑，因爲您正在修改它正在迭代的列表。

變化

for vertex in p:

到

for vertex in p[:]:

，這將導致它遍歷p的複印件。

您可以在http://effbot.org/zone/python-list.htm瞭解更多。

來源

2012-12-16 19:39:37

非常感謝！那是那裏的問題。 –

由於@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算法的實現...

來源

2012-12-16 21:35:23

在python中實現Bron-Kerbosch算法

回答

相關問題