在Python中实现Bron-Kerbosch算法

Question

我正在为一个大学项目尝试实现Bron-Kerbosch算法，即列出给定图中的所有最大团。

我正在尝试实现第一个算法（不使用枢轴），但是在维基百科的示例上测试后，我的代码没有得出所有答案，目前我的代码是：

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

请问为什么我只得到了部分答案？

- a.u.r

---

首先，不要使用“is”进行值比较 - 这就是“==”的作用。 - Jon Clements

我建议不要在具有副作用的情况下使用递归（递归本身已经足够棘手了！）。此外，您可以使用列表推导式和enumerate编写N。 - Andy Hayden

Answer 1

您修改了Python正在迭代的列表，导致程序出现混乱。

请改为

for vertex in p:

to

for vertex in p[:]:

这将导致它迭代p的副本。你可以在http://effbot.org/zone/python-list.htm阅读更多相关信息。

- Vaughn Cato

---

非常感谢！那就是问题所在。 - a.u.r

Answer 2

正如 @VaughnCato 正确指出的那样，错误是在迭代 P [:] 时发生的。我认为值得注意的是，您可以使用以下重构后的代码将其“yield”（而不是打印）：

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

< p > 如果有人在未来寻找Bron-Kerbosch算法的实现...

- Andy Hayden

---

我现在需要这个。enumerate(g[v])是什么意思？你能发一下你的Graph类吗？ - D Left Adjoint to U

@DanielDonnelly 图形是一个由0和1组成的列表，就像问题中所描述的那样。如果您有更具体的问题，请提出一个新问题，我不确定我能为此添加太多内容。enumerate函数在标准库中。 :) - Andy Hayden

我认为函数调用应该是 list(bronk2([], [*range(6)], [], graph))。 - Flo

Answer 3

来自维基百科的Bron-Kerbosch算法实现：

不使用枢轴点

算法 BronKerbosch1(R, P, X) 是
    如果 P 和 X 都为空 那么：
        报告 R 为极大团
    对于每个 点 v 在 P 中执行
        BronKerbosch1(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}]

使用枢轴元素的算法

算法 BronKerbosch2(R, P, X) 是
    如果 P 和 X 都为空 那么
        报告R作为最大团
    选择一个枢轴元素 u 在 P ⋃ X 中
    对于每个顶点 v 在 P \ N(u) 中:
        BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

---

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

- Mykola Zotko

---

这个基于集合的实现比基于列表的版本快几个数量级，而且更清晰地与维基百科伪代码相关联。 - rwalroth