Algoritmo Bron-Kerbosch para encontrar camarilla

StackOverflow https://stackoverflow.com/questions/143140

  •  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.

¿Fue útil?

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)

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.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top