用于发现派系的 Bron-Kerbosch 算法

Question

谁能告诉我，在网上哪里可以找到用于派系查找的 Bron-Kerbosch 算法的解释或在这里解释它是如何工作的？

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

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

Answer 1

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

Answer 2

尝试寻找拥有 ACM 学生帐户的人，他可以为您提供论文副本，如下：http://portal.acm.org/itation.cfm?doid=362342.362367

我刚刚下载了它，它只有两页长，在 Algol 60 中实现了！

Answer 3

这里有算法我已经用Java重写了它链表作为集合 R,P,X 并且它可以工作
就像一个魅力（好的事情是在根据算法进行集合操作时使用函数“retainAll”）。

我建议你在重写算法时考虑一下实现，因为优化问题

Answer 4

我还试图了解 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)

Answer 5

对于它的价值，我找到了一个Java实现： http://joelib.cvs.sourceforge.net/joelib/joelib2/src/joelib2/algo/clique/BronKerbosch.java?view=markup

HTH。

Answer 6

我已经实现了论文中指定的两个版本。 我了解到，未优化的版本如果递归求解，将有助于理解算法。
这是版本 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 将包含找到的 cliques。

一旦理解了这一点，实施优化的方案就很容易了。

Answer 7

Boost::Graph 具有 Bron-Kerbosh 算法的出色实现，请检查一下。