派克发现的Bron-Kerbosch算法

Question

任何人都可以告诉我，在网上我可以找到一个解释Bron-Kerbosch算法为派系寻找或解释它是如何工作的？

我知道它发表在“算法457：查找无向图的所有派系”一书中，但是我找不到描述该算法的免费源代码。

我不需要算法的源代码，我需要解释它是如何工作的。

Answer 1

尝试找到一个与ACM学生帐户谁可以给你的文件，这是这里的副本：http://portal.acm.org/citation.cfm?doid=362342.362367

我只是下载了它，而且只有两页长，在Algol 60是一个实现！

Answer 2

对于什么是值得，我发现了一个Java实现：http://joelib.cvs.sourceforge.net/joelib/joelib2/src/joelib2/algo/clique/BronKerbosch.java?view=markup

HTH。

Answer 3

有正确的here我已经使用Java linkedlists重写它作为集合R是算法，P，X和它的作品 就像一个魅力（O好事是根据做设置操作时要使用的功能“中的retainAll”该算法）。

我建议你觉得一点关于实现，因为优化问题重写算法

Answer 4

时，我发现这里的算法的解释：http://www.dfki.de/~neumann/ie-seminar/presentations/finding_cliques.pdf 这是一个很好的解释...但我需要一个库或在C＃中实现-'-'

Answer 5

我已经实现了本文中指定的两个版本。我了解到，未经优化的版本，如果递归解决有助于理解算法。 下面是版本1（未优化）Python实现：

def bron(compsub, _not, candidates, graph, cliques): 
    if len(candidates) == 0 and len(_not) == 0: 
     cliques.append(tuple(compsub)) 
     return 
    if len(candidates) == 0: return 
    sel = candidates[0] 
    candidates.remove(sel) 
    newCandidates = removeDisconnected(candidates, sel, graph) 
    newNot = removeDisconnected(_not, sel, graph) 
    compsub.append(sel) 
    bron(compsub, newNot, newCandidates, graph, cliques) 
    compsub.remove(sel) 
    _not.append(sel) 
    bron(compsub, _not, candidates, graph, cliques) 

你调用这个函数：

graph = # 2x2 boolean matrix 
cliques = [] 
bron([], [], graph, cliques) 

变量cliques将包含找到拉帮结派。

一旦你明白了这一点，很容易实现优化。

Answer 6

Boost :: Graph具有Bron-Kerbosh算法的优秀实现，请给它一个检查。

Answer 7

我还试图围绕Bron-Kerbosch算法包裹头部，所以我在python中编写了自己的实现。它包含一个测试用例和一些评论。希望这可以帮助。

class Node(object): 

    def __init__(self, name): 
     self.name = name 
     self.neighbors = [] 

    def __repr__(self): 
     return self.name 

A = Node('A') 
B = Node('B') 
C = Node('C') 
D = Node('D') 
E = Node('E') 

A.neighbors = [B, C] 
B.neighbors = [A, C] 
C.neighbors = [A, B, D] 
D.neighbors = [C, E] 
E.neighbors = [D] 

all_nodes = [A, B, C, D, E] 

def find_cliques(potential_clique=[], remaining_nodes=[], skip_nodes=[], depth=0): 

    # To understand the flow better, uncomment this: 
    # print (' ' * depth), 'potential_clique:', potential_clique, 'remaining_nodes:', remaining_nodes, 'skip_nodes:', skip_nodes 

    if len(remaining_nodes) == 0 and len(skip_nodes) == 0: 
     print 'This is a clique:', potential_clique 
     return 

    for node in remaining_nodes: 

     # Try adding the node to the current potential_clique to see if we can make it work. 
     new_potential_clique = potential_clique + [node] 
     new_remaining_nodes = [n for n in remaining_nodes if n in node.neighbors] 
     new_skip_list = [n for n in skip_nodes if n in node.neighbors] 
     find_cliques(new_potential_clique, new_remaining_nodes, new_skip_list, depth + 1) 

     # We're done considering this node. If there was a way to form a clique with it, we 
     # already discovered its maximal clique in the recursive call above. So, go ahead 
     # and remove it from the list of remaining nodes and add it to the skip list. 
     remaining_nodes.remove(node) 
     skip_nodes.append(node) 

find_cliques(remaining_nodes=all_nodes)