problem example cliques algorithm graph-theory clique

algorithm - example - clique problem



Algoritmo de Bron-Kerbosch para el hallazgo de la camarilla (7)

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

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

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.

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

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)