algorithm - example - clique problem

Algoritmo de Bron-Kerbosch para el hallazgo de la camarilla

Question

¿Alguien puede decirme dónde 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: encontrar todas las camarillas de un gráfico sin orientación", 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

Intente encontrar a alguien con una cuenta de estudiante de ACM que pueda darle una copia del trabajo, que está aquí: http://portal.acm.org/citation.cfm?doid=362342.362367

Acabo de descargarlo, y tiene solo dos páginas, ¡con una implementación en Algol 60!

Answer 2

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

Answer 3

Aquí está el algoritmo. Lo he reescrito usando listas de enlaces de Java como los conjuntos R, P, X y funciona como un amuleto (o bueno es usar la función "retener todo" al hacer operaciones de conjunto de acuerdo con el algoritmo).

Te sugiero que pienses un poco sobre la implementación debido a los problemas de optimización al reescribir el algoritmo

Answer 4

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

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í está la implementación de Python para la versión 1 (sin optimizar):

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)

E invocas esta función:

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

Las cliques variables contendrán camarillas encontradas.

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)