在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算法

回答

相关问题