Algoritmo Bron-Kerbosch para clique encontrar

Question

¿Alguien me puede decir, en la web puedo encontrar una explicación para el algoritmo de Bron-Kerbosch para encontrar camarillas o explicar aquí cómo funciona?

Sé que fue publicado en el "Algoritmo 457: búsqueda de todas las camarillas de un gráfico no dirigido", pero no puedo encontrar la fuente gratuita que describa el algoritmo.

No necesito un código fuente para el algoritmo, necesito una explicación de cómo funciona.

Answer 1

Trate de encontrar a alguien con una cuenta de estudiante de ACM que le puede dar una copia del documento, que está aquí: http://portal.acm.org/citation.cfm?doid=362342.362367

simplemente he descargado, y está a sólo dos páginas de largo, con una implementación en Algol 60!

Answer 2

Por lo que vale la pena, he encontrado una aplicación Java: http://joelib.cvs.sourceforge.net/joelib/joelib2/src/joelib2/algo/clique/BronKerbosch.java?view=markup

HTH.

Answer 3

No es el algoritmo de derecho here He reescrito usando linkedlists Java como los conjuntos R, P, X y funciona como un encanto (o bueno es utilizar la función de "retainAll" al realizar operaciones establecidas de acuerdo con la el algoritmo).

le sugiero que pensar un poco acerca de la aplicación debido a los problemas de optimización al reescribir el algoritmo

Answer 4

i encontrar 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# -.- '

Answer 5

He implementado las dos versiones especificadas en el documento. Aprendí eso, la versión no optimizada, si se resuelve recursivamente ayuda mucho a entender el algoritmo. Aquí es implementación de Python para la versión 1 (no optimizado):

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 se invoca esta función:

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

La variable cliques contendrá camarillas encontrados.

Una vez que comprenda esto, es fácil implementar uno optimizado.

Answer 6

Boost :: Graph tiene una excelente implementación del algoritmo de Bron-Kerbosh, pruébala.

Answer 7

También estaba tratando de entender el 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)