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.
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)
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!
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With