Algorithme de Bron-Kerbosch pour la recherche de cliques

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

  •  02-07-2019
  •  | 
  •  

Question

Quelqu'un peut-il me dire où, sur le Web, je peux trouver une explication à l'algorithme de Bron-Kerbosch pour la recherche de cliques ou expliquer ici comment cela fonctionne?

Je sais que cela a été publié dans "Algorithme 457: recherche de toutes les cliques d'un graphe non dirigé". livre, mais je ne trouve pas de source gratuite décrivant l’algorithme.

Je n'ai pas besoin d'un code source pour l'algorithme, j'ai besoin d'explications sur son fonctionnement.

Était-ce utile?

La solution

Essayez de trouver quelqu'un avec un compte étudiant ACM qui peut vous donner une copie du document, qui se trouve ici: http://portal.acm.org/citation.cfm?doid=362342.362367

Je viens de le télécharger, et il ne fait que deux pages, avec une implémentation dans Algol 60!

Autres conseils

Je trouve l'explication de l'algorithme ici: http: // www.dfki.de/~neumann/ie-seminar/presentations/finding_cliques.pdf c'est une bonne explication ... mais j'ai besoin d'une bibliothèque ou d'une implémentation en C # -.- '

Il existe l'algorithme à droite ici , j'ai réécrit en utilisant les listes de liens Java comme ensembles R, P, X et cela fonctionne comme un charme (il est bon d’utiliser la fonction "rétention de tous" lors de la définition des opérations selon l’algorithme).

Je suggère que vous réfléchissiez un peu à la mise en œuvre à cause des problèmes d'optimisation lors de la réécriture de l'algorithme

J'essayais aussi de comprendre l'algorithme de Bron-Kerbosch, alors j'ai écrit ma propre implémentation en python. Il comprend un cas de test et quelques commentaires. J'espère que cela vous aidera. 

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)

J'ai implémenté les deux versions spécifiées dans l'article. J'ai appris que la version non optimisée, si elle est résolue de manière récursive, aide beaucoup à comprendre l'algorithme. Voici l'implémentation de python pour la version 1 (non optimisée): 

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)

Et vous appelez cette fonction: 

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

La variable cliques contiendra les cliques trouvés.

Une fois que vous comprenez cela, il est facile de mettre en œuvre un système optimisé.

Boost :: Graph a une excellente implémentation de l’algorithme de Bron-Kerbosh, testez-le.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top