对于一个大学项目,我正在尝试实现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], [])
任何帮助我为什么只得到答案的一部分?
Python感到困惑,因为您正在修改要迭代的列表。
更改
for vertex in p:
to
for vertex in p[:]:
这将导致它遍历p的副本。
您可以在http://effbot.org/zone/python-list.htm上了解有关此内容的更多信息。
正如@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]]
如果将来有人在寻找Bron–Kerbosch算法的实现...
Wikipedia中两种形式的Bron-Kerbosch算法的实现:
无枢轴旋转
算法 BronKerbosch1(R,P,X)是如果 P 和 X都是空的[[then:报告R作为最大集团for each顶点v in P doBronKerbosch1(R⋃{v},P⋂N(v),X⋂N(v ))P:= P \ {v}X:= X⋃{v}
adj_matrix = [
[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]]
N = { i: set(num for num, j in enumerate(row) if j) for i, row in enumerate(adj_matrix) } print(N) # {0: {1, 4}, 1: {0, 2, 4}, 2: {1, 3}, 3: {2, 4, 5}, 4: {0, 1, 3}, 5: {3}} def BronKerbosch1(P, R=None, X=None): P = set(P) R = set() if R is None else R X = set() if X is None else X if not P and not X: yield R while P: v = P.pop() yield from BronKerbosch1( P=P.intersection(N[v]), R=R.union([v]), X=X.intersection(N[v])) X.add(v) P = N.keys() print(list(BronKerbosch1(P))) # [{0, 1, 4}, {1, 2}, {2, 3}, {3, 4}, {3, 5}]
和X均为空then报告R作为最大集团在P⋃X中选择一个枢轴点ufor each顶点v in P \ N(u):BronKerbosch2(R⋃{v},P⋂N(v),X⋂N(v))P:= P \ {v}X:= X⋃{v}有旋转
算法 BronKerbosch2(R,P,X)是if P
import random
def BronKerbosch2(P, R=None, X=None):
P = set(P)
R = set() if R is None else R
X = set() if X is None else X
if not P and not X:
yield R
try:
u = random.choice(list(P.union(X)))
S = P.difference(N[u])
# if union of P and X is empty
except IndexError:
S = P
for v in S:
yield from BronKerbosch2(
P=P.intersection(N[v]), R=R.union([v]), X=X.intersection(N[v]))
P.remove(v)
X.add(v)
print(list(BronKerbosch2(P)))
# [{0, 1, 4}, {1, 2}, {2, 3}, {3, 4}, {3, 5}]