Bron-Kerbosch-Algorithmus zur Cliquensuche

Kann mir jemand sagen, wo im Internet ich eine Erklärung für Bron-Kerbosch-Algorithmus für Cliquen finden oder hier erklären kann, wie es funktioniert?Bron-Kerbosch-Algorithmus zur Cliquensuche

Ich weiß, dass es in "Algorithmus 457: Finden aller Cliquen eines ungerichteten Graphen" Buch veröffentlicht wurde, aber ich kann keine freie Quelle finden, die den Algorithmus beschreiben wird.

Ich brauche keinen Quellcode für den Algorithmus, ich brauche eine Erklärung, wie es funktioniert.

Quelle

2008-09-27 Alex Reitbort

Alex Ich wette, dieser Beitrag wurde für "Sag mir, wo im Internet ..." abgelehnt. Bitten Sie die Leute nicht, Ihre Arbeit zu machen. Fragen Sie sie einfach, um zu klären, wie es funktioniert – aku

Ich meinte im Internet wie in nicht im Buch, da ich keinen Zugriff auf die Bibliothek für etwa zwei Wochen haben werde :( –

Anstatt nach einer Quelle zu fragen, besser zu sagen "erzählen Ich, wie ... funktioniert ", zusammen mit einer Beschreibung dessen, was dich besonders verwirrt, dann wird die Antwort (und der Kontext deiner Frage) hier für andere sein, die ihr in Zukunft begegnen. Die akzeptierte Antwort ist hier fast nutzlos. – SimonJ

Versuchen Sie jemanden mit einem ACM Studentenkonto zu finden, der eine Kopie des Papiers geben kann, der hier: http://portal.acm.org/citation.cfm?doid=362342.362367

ich es gerade heruntergeladen, und es ist nur zwei Seiten lang, mit einer Implementierung in Algol 60!

Quelle

2008-09-27 09:03:07 HenryR

kannst du Bitte schicken Sie es mir an [email protected]? –

Für was es wert ist, fand ich eine Java-Implementierung: http://joelib.cvs.sourceforge.net/joelib/joelib2/src/joelib2/algo/clique/BronKerbosch.java?view=markup

HTH.

Quelle

2008-09-27 11:51:37 PhiLho

Ich habe 2 Java-Implementierungen und eine C-Implementierung gefunden. Mag sein, dass es funktioniert, aber ich muss auch verstehen, wie es funktioniert, und Quellcode hat nicht viele Kommentare darüber, wie es funktioniert. –

Es ist der Algorithmus richtig here ich geschrieben habe es Java LinkedLists unter Verwendung der folgenden Mengen R, P, X und es funktioniert wie ein Zauber (o gute Sache ist, die Funktion „retainAll“ zu verwenden, wenn gesetzt Operationen tun nach der Algorithmus).

Ich schlage vor, denken Sie ein wenig über die Umsetzung aufgrund der Optimierung Probleme, wenn der Algorithmus Umschreiben

Quelle

2008-10-11 21:20:10

ich die Erklärung des Algorithmus finden Sie hier: http://www.dfki.de/~neumann/ie-seminar/presentations/finding_cliques.pdf es ist eine gute Erklärung ... aber ich brauche eine Bibliothek oder Implementierung in C# -.- '

Quelle

2010-03-30 16:38:57 dani

Ich habe beide in der Veröffentlichung angegebenen Versionen implementiert. Ich habe gelernt, dass die unoptimierte Version, wenn sie rekursiv gelöst wird, viel hilft, den Algorithmus zu verstehen. Hier ist Python-Implementierung für Version 1 (nicht optimiert):

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)

Und Sie diese Funktion aufrufe:

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

Die Variablen cliques gefunden Cliquen enthalten.

Sobald Sie dies verstehen, ist es einfach, ein optimiertes zu implementieren.

Quelle

2012-01-28 16:54:02 Amol

Sollte nicht einmal Version 1 des Algorithmus überprüfen, ob nicht ein Element, das ein Nachbar jedes Elements in Kandidaten ist, und Backtrack enthält, wenn das der Fall ist? –

Boost :: Graph hat eine hervorragende Implementierung des Bron-Kerbosh-Algorithmus, geben Sie ihm einen Haken.

Quelle

2012-06-17 12:41:18 linello

Ich versuchte auch, meinen Kopf um den Bron-Kerbosch-Algorithmus zu wickeln, also schrieb ich meine eigene Implementierung in Python. Es enthält einen Testfall und einige Kommentare. Hoffe das hilft.

Quelle

2014-06-25 17:59:03 Shahaf

Bron-Kerbosch-Algorithmus zur Cliquensuche

Antwort

Verwandte Themen