Bron-Kerbosch Algorithmus für die Interessen zu treffen

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

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

War es hilfreich?

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)

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.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top