Erkenntnis-Zyklus von 3 Knoten ( oder Dreiecke) in einem Diagramm

Einer million Kanten ist ziemlich klein. Es sei denn, Sie tun es Tausende Male, einfach nur eine naive Implementierung.

Werde ich davon ausgehen, dass Sie über ein Wörterbuch von node_ids, die eine Folge von Ihren Nachbarn, und, dass der graph gerichtet ist.

Beispiel:

nodes = {}
nodes[0] = 1,2
nodes[1] = tuple() # empty tuple
nodes[2] = 1

Meine Lösung:

def generate_triangles(nodes):
    """Generate triangles. Weed out duplicates."""
    visited_ids = set() # remember the nodes that we have tested already
    for node_a_id in nodes:
        for node_b_id in nodes[node_a_id]:
            if nod_b_id == node_a_id:
                raise ValueError # nodes shouldn't point to themselves
            if node_b_id in visited_ids:
                continue # we should have already found b->a->??->b
            for node_c_id in nodes[node_b_id]:
                if node_c_id in visited_ids:
                    continue # we should have already found c->a->b->c
                if node_a_id in nodes[node_c_id]:
                    yield(node_a_id, node_b_id, node_c_id)
        visited_ids.add(node_a_id) # don't search a - we already have all those cycles

Überprüfung der Leistung:

from random import randint
n = 1000000
node_list = range(n)
nodes = {}
for node_id in node_list:
    node = tuple()
    for i in range(randint(0,10)): # add up to 10 neighbors
        try:
            neighbor_id = node_list[node_id+randint(-5,5)] # pick a nearby node
        except:
            continue 
        if not neighbor_id in node:
            node = node + (neighbor_id,)
    nodes[node_id] = node

cycles = list(generate_triangles(nodes))
print len(cycles)

Als ich es versucht habe, es hat länger gedauert die zu bauen, die zufällige Graphen als Anzahl der Zyklen.

Möchten Sie vielleicht, um es zu testen obwohl 😉 ich nicht garantieren, dass es richtig ist.

Konnte man auch einen Blick in networkx, das ist der große python-Grafik-Bibliothek.

InformationsquelleAutor wisty

Ziemlich einfache und klare Art und Weise zu tun, ist die Verwendung von Networkx:

Mit Networkx Sie können die loops von einem ungerichteten Graphen durch nx.cycle_basis(G) und wählen Sie dann die, die mit 3 Knoten

cycls_3 = [c for c in nx.cycle_basis(G) if len(c)==3]

oder finden Sie alle Cliquen von find_cliques(G) und dann wählen Sie die, die Sie wollen (mit 3 Knoten). Cliquen sind Teile des Graphen, wo alle Knoten miteinander verbunden sind, und das passiert in Zyklen/loops mit 3 Knoten.

InformationsquelleAutor Ash

Obwohl es ist nicht effizient, möchten Sie vielleicht, um eine Lösung implementieren, so verwenden Sie das Schleifen. Einen test schreiben, damit Sie eine Vorstellung bekommen, wie lange es dauert.

Dann, wie Sie versuchen, neue Ansätze können Sie zwei Dinge tun:
1) Stellen Sie sicher, dass die Antwort bleibt die gleiche.
2) Sehen Sie, was die Verbesserung ist.

Dass ein schneller Algorithmus, der findet etwas, das wahrscheinlich Schlimmeres, als mit einer langsameren.

Sobald Sie die langsamen Tests können Sie sehen, wenn Sie tun können diese in parallel-und sehen, was die performance-Steigerung ist.

Dann können Sie sehen, wenn Sie können markieren Sie alle Knoten mit weniger als 3 vertices.

Idealerweise möchten Sie vielleicht, um es schrumpfen zu nur 100 oder so den ersten, so können Sie es ziehen, und sehen, was geschieht grafisch.

Manchmal Ihr Gehirn zu sehen, ein Muster, das nicht so offensichtlich, wenn man auf algorithmen.

InformationsquelleAutor James Black

Brauchen Sie 'alle' die 'Dreiecke', oder nur 'einige'/'any'?
Oder vielleicht brauchen Sie nur, um zu testen, ob ein bestimmter Knoten ist Teil eines Dreiecks?

Der test ist einfach - gegeben ein Knoten A ist, gibt es keine zwei verbundenen Knoten B & C, die sind auch direkt verbunden.

Wenn Sie brauchen, um alle Dreiecke, insbesondere alle Gruppen von 3 Knoten, in denen jeder Knoten angeschlossen, die anderen beiden - dann müssen Sie prüfen, alle möglichen Gruppen in eine sehr lang andauernde "for each" - Schleife.

Die einzige Optimierung ist, die sicherstellen, dass Sie überprüfen Sie nicht die gleiche "Gruppe" zweimal, wenn Sie z.B. bereits getestet haben, dass B & C sind nicht in einer Gruppe mit einem, dann nicht überprüfen, ob Ein & C sind in einer Gruppe mit B.

InformationsquelleAutor Kirk Broadhurst

Wenn Sie nicht kümmern, über mehrere Kopien des gleichen Dreieck in einer anderen Reihenfolge dann eine Liste von 3-Tupeln arbeitet:

from itertools import combinations as combos
[(n,nbr,nbr2) for n in G for nbr, nbr2 in combos(G[n],2) if nbr in G[nbr2]]

Die Logik hier ist zu prüfen, jedes paar von Nachbarn eines jeden Knotens, um zu sehen, wenn Sie verbunden sind. G[n] ist eine schnelle Art und Weise zu Durchlaufen oder sich Nachbarn.

Wenn Sie möchten, um loszuwerden, reorderings, wiederum jeweils dreifach in ein frozenset und machen Sie einen Satz von der frozensets:

set(frozenset([n,nbr,nbr2]) for n in G for nbr, nbr2 in combos(G[n]) if nbr in G[nbr2])

Wenn Sie nicht wie frozenset wollen und eine Liste der sets dann:

triple_iter = ((n, nbr, nbr2) for n in G for nbr, nbr2 in combos(G[n],2) if nbr in G[nbr2])
triangles = set(frozenset(tri) for tri in triple_iter)
nice_triangles = [set(tri) for tri in triangles]

InformationsquelleAutor dschult