Algoritmo Bron-Kerbosch para encontrar camarilla
-
02-07-2019 - |
Pregunta
¿Alguien puede decirme dónde puedo encontrar una explicación del algoritmo Bron-Kerbosch para encontrar clique en la web o explicar cómo funciona?
Sé que se publicó en "Algoritmo 457: búsqueda de todas las camarillas de un gráfico no dirigido" libro, pero no puedo encontrar una fuente gratuita que describa el algoritmo.
No necesito un código fuente para el algoritmo, necesito una explicación de cómo funciona.
Solución
Intente encontrar a alguien con una cuenta de estudiante de ACM que le pueda dar una copia del documento, que se encuentra aquí: http://portal.acm.org/citation.cfm?doid=362342.362367
Acabo de descargarlo, ¡y solo tiene dos páginas, con una implementación en Algol 60!
Otros consejos
Encuentro la explicación del algoritmo aquí: http: // www.dfki.de/~neumann/ie-seminar/presentations/finding_cliques.pdf Es una buena explicación ... pero necesito una biblioteca o implementación en C # -.- '
Hay un algoritmo correcto aquí he reescrito usando listas enlazadas de Java como los conjuntos R, P, X y funciona como un hechizo (o lo bueno es usar la función "retener todo" al realizar operaciones de configuración de acuerdo con el algoritmo).
Le sugiero que piense un poco sobre la implementación debido a los problemas de optimización al reescribir el algoritmo
También estaba tratando de envolver mi cabeza alrededor del algoritmo Bron-Kerbosch, así que escribí mi propia implementación en python. Incluye un caso de prueba y algunos comentarios. Espero que esto ayude.
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)
Para lo que vale, encontré una implementación de Java: http://joelib.cvs.sourceforge.net/joelib/joelib2/src/joelib2/algo/clique/BronKerbosch.java?view=markup
HTH.
He implementado ambas versiones especificadas en el documento. Aprendí que la versión no optimizada, si se resuelve de forma recursiva, ayuda mucho a comprender el algoritmo. Aquí está la implementación de Python para la versión 1 (no optimizada):
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)
Y tú invocas esta función:
graph = # 2x2 boolean matrix
cliques = []
bron([], [], graph, cliques)
La variable cliques
contendrá cliques encontrados.
Una vez que entiendas esto, es fácil implementar uno optimizado.
Boost :: Graph tiene una excelente implementación del algoritmo Bron-Kerbosh, dale una comprobación.