Bron-Kerbosch Algorithmus für die Interessen zu treffen
-
02-07-2019 - |
Frage
Kann mir jemand sagen, wo im Web ich eine Erklärung für Bron-Kerbosch Algorithmus zur Clique Erkenntnis finden oder hier erklären, wie es funktioniert?
Ich weiß, es wurde in „Algorithm 457: alle Cliquen eines ungerichteten Graphen zu finden“ veröffentlichtes Buch, aber ich kann nicht frei Quelle finden, die den Algorithmus beschreiben
.Ich brauche keinen Quellcode für den Algorithmus, ich brauche eine Erklärung, wie es funktioniert.
Lösung
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 heruntergeladen es einfach, und es ist nur zwei Seiten lang, mit einer Implementierung in Algol 60!
Andere Tipps
Ich finde die Erklärung des Algorithmus 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 # -.- '
Es ist der Algorithmus richtig hier Ich habe neu geschrieben es mit Java LinkedLists als die Mengen R, P, X und es funktioniert wie ein Zauber (o gute Sache ist, die Funktion „retainAll“ zu verwenden, wenn der Algorithmus entsprechend eingestellte Operationen tun).
Ich schlage vor, Sie denken, ein wenig über die Umsetzung aufgrund der Optimierung Probleme, wenn der Algorithmus Umschreiben
Ich habe versucht, auch meinen Kopf um den Bron-Kerbosch Algorithmus zu wickeln, so schrieb ich meine eigene Implementierung in Python. Es umfasst einen Testfall und einige Kommentare. Hoffe, das hilft.
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)
Für das, 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.
Ich habe beiden Versionen in dem Papier angegeben umgesetzt. Ich habe gelernt, dass, die nicht optimierten Version, wenn gelöst rekursiv viel hilft, den Algorithmus zu verstehen. Hier ist Python-Implementierung für Version 1 (nicht optimierten):
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 aufrufen:
graph = # 2x2 boolean matrix
cliques = []
bron([], [], graph, cliques)
Die Variable cliques
wird gefunden Cliquen enthalten.
Wenn Sie das verstehen es einfach optimiert man implementieren.
boost :: Graph eine hervorragende Umsetzung von Bron-Kerbosh Algorithmus hat, gibt ihm einen Scheck.