Algoritmo Bron-Kerbosch per la ricerca della cricca

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

  •  02-07-2019
  •  | 
  •  

Domanda

Qualcuno può dirmi, dove sul web posso trovare una spiegazione per l'algoritmo Bron-Kerbosch per la ricerca della cricca o spiegare qui come funziona?

So che è stato pubblicato in "Algorithm 457: trovare tutte le cricche di un grafico non indirizzato" libro, ma non riesco a trovare la fonte gratuita che descriverà l'algoritmo.

Non ho bisogno di un codice sorgente per l'algoritmo, ho bisogno di una spiegazione di come funziona.

È stato utile?

Soluzione

Prova a trovare qualcuno con un account studente ACM in grado di darti una copia del documento, che è qui: http://portal.acm.org/citation.cfm?doid=362342.362367

L'ho appena scaricato ed è lungo solo due pagine, con un'implementazione in Algol 60!

Altri suggerimenti

Trovo la spiegazione dell'algoritmo qui: http: // www.dfki.de/~neumann/ie-seminar/presentations/finding_cliques.pdf è una buona spiegazione ... ma ho bisogno di una libreria o implementazione in C # -.- '

Esiste l'algoritmo giusto qui Ho riscritto usando le liste dei collegamenti Java come i set R, P, X e funziona come un incantesimo (o buona cosa è usare la funzione "keepAll" quando si eseguono operazioni impostate secondo l'algoritmo).

Ti suggerisco di pensare un po 'all'implementazione a causa dei problemi di ottimizzazione durante la riscrittura dell'algoritmo

Stavo anche cercando di avvolgere la testa attorno all'algoritmo Bron-Kerbosch, quindi ho scritto la mia implementazione in Python. Include un caso di test e alcuni commenti. Spero che questo aiuti. 

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)

Ho implementato entrambe le versioni specificate nel documento. Ho imparato che, la versione non ottimizzata, se risolta in modo ricorsivo aiuta molto a comprendere l'algoritmo. Ecco l'implementazione di Python per la versione 1 (non ottimizzata): 

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 invochi questa funzione: 

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

La variabile cricche conterrà le cricche trovate.

Una volta capito questo, è facile implementarne uno ottimizzato.

Boost :: Graph ha un'eccellente implementazione dell'algoritmo Bron-Kerbosh, provalo.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top