Clustering durch wiederholte Daten

Question

Gibt es eine Möglichkeit, einen Datensatz bestehend aus Paaren von 3D-Punkten (oder nur deren Indexnummern) in verbundene Cluster aufzuteilen? Das heißt, zwei Paare (a, b) und (c, d) sollten sich im selben Cluster befinden, wenn sie einen gemeinsamen Punkt teilen (dh a = c, b = c, a = d oder b = d) oder falls vorhanden eine Kette von einem oder mehreren anderen Paaren, von denen jedes einen gemeinsamen Punkt mit dem vorherigen hat, von einem Paar zum anderen.

Zum Beispiel kann die Liste von Paaren:

[[1,2],[2,3],[4,5],[6,7],[7,8],[9,4],[8,5]] 

würde wie folgt zusammengefasst werden:

[[1,2],[2,3]] 

[[4,5],[6,7],[7,8],[9,4],[8,5]] 

im ersten Cluster, die die Paare (1,2) und (2,3) habe den Punkt 2 gemeinsam und teile keine Punkte mit Paaren außerhalb des Clusters. Im zweiten Cluster teilt das Paar (4,5) gemeinsame Punkte mit (9,4) und (8,5), während (8,5) einen gemeinsamen Punkt mit (7,8) hat, der einen gemeinsamen Punkt hat mit (6,7).

Die Daten werden ursprünglich in einem Array gespeichert, aber das Ausgabeformat ist nicht so wichtig.

Ich muss in der Lage sein, auf die Daten zuzugreifen, die jeden einzelnen Cluster danach bilden.

Answer 1

Mit networkx:

import networkx 

edges = [[1, 2], [2, 3], [4, 5], [6, 7], [7, 8], [9, 4], [8, 5]] 

graph = networkx.Graph(edges) 
print(list(networkx.connected_components(graph))) 

Ausgang:

[set([1, 2, 3]), set([4, 5, 6, 7, 8, 9])]