Bron-Kerbosch algorithm for clique finding

Question

Can anyone tell me, where on the web I can find an explanation for Bron-Kerbosch algorithm for clique finding or explain here how it works?

I know it was published in "Algorithm 457: finding all cliques of an undirected graph" book, but I can't find free source that will describe the algorithm.

I don't need a source code for the algorithm, I need an explanation of how it works.

Alex I bet that post was down-voted for "tell me, where on the web..." Don't ask people to do you job. Just ask them to clarify how it works — aku, Sep 27 '08 at 06:52
I meant on the web as in not in the book, since I won't have any access to library for about two weeks :( — Alex Reitbort, Sep 27 '08 at 08:33
Rather than asking for a source, better to say "tell me how ... works", along with a description of what's specifically puzzling you, then the answer (and context of your question) will be here for others encountering it in future. The accepted answer here is near-useless. — SimonJ, Nov 13 '10 at 23:28

score 8 · Answer 1 · answered Mar 30 '10 at 16:38

8

i find the explanation of the algorithm here: http://www.dfki.de/~neumann/ie-seminar/presentations/finding_cliques.pdf it's a good explanation... but i need a library or implementation in C# -.-'

answered Mar 30 '10 at 16:38

dani

81
1
1

the link is a dead link – macros Sep 07 '21 at 14:25

score 4 · Accepted Answer · answered Sep 27 '08 at 09:03

4

Try finding someone with an ACM student account who can give you a copy of the paper, which is here: http://portal.acm.org/citation.cfm?doid=362342.362367

I just downloaded it, and it's only two pages long, with an implementation in Algol 60!

answered Sep 27 '08 at 09:03

HenryR

8,219
7
35
39

can you please send it to me at joker99+bron@gmail.com ? – Alex Reitbort Sep 27 '08 at 13:26

score 2 · Answer 3 · answered Oct 11 '08 at 21:20

There is the algorithm right here I have rewritten it using Java linkedlists as the sets R,P,X and it works like a charm (o good thing is to use the function "retainAll" when doing set operations according to the algorithm).

I suggest you think a little about the implementation because of the optimization issues when rewriting the algorithm

score 2 · Answer 4 · answered Jun 25 '14 at 17:59

I was also trying to wrap my head around the Bron-Kerbosch algorithm, so I wrote my own implementation in python. It includes a test case and some comments. Hope this helps.

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)

score 0 · Answer 5 · answered Jun 17 '12 at 12:41

0

Boost::Graph has an excellent implementation of Bron-Kerbosh algorithm, give it a check.

answered Jun 17 '12 at 12:41

linello

8,451
18
63
109

score 0 · Answer 6 · answered Sep 27 '08 at 11:51

0

For what it is worth, I found a Java implementation: http://joelib.cvs.sourceforge.net/joelib/joelib2/src/joelib2/algo/clique/BronKerbosch.java?view=markup

HTH.

answered Sep 27 '08 at 11:51

PhiLho

40,535
6
96
134

I found 2 java implementations and one C implementation. May be it works, but I also need an understanding of how does it work, and source code doesn't have a lot of comments about how does it works. – Alex Reitbort Sep 27 '08 at 13:25

Amol · Answer 7 · 2012-01-28T17:05:13.137

I have implemented both versions specified in the paper. I learned that, the unoptimized version, if solved recursively helps a lot to understand the algorithm. Here is python implementation for version 1 (unoptimized):

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)

And you invoke this function:

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

The variable cliques will contain cliques found.

Once you understand this it's easy to implement optimized one.

Shouldn't even version 1 of the algorithm check if not contains an element which is a neighbor of every element in candidates and backtrack if that is the case? — Andreas Vinter-Hviid, May 24 '14 at 17:56

Bron-Kerbosch algorithm for clique finding

7 Answers7