Out of Core verbundenen Komponenten Algorithmen

Question

Ich habe 4.000.000.000 (vier Milliarden) Kanten für eine ungerichtete Grafik. Sie werden in einer großen Textdatei als Paare von Knoten-IDs dargestellt. Ich möchte die verbundenen Komponenten dieses Graphen berechnen. Leider, sobald Sie die Knoten-IDs mit den Kanten in den Speicher laden, dauert dies mehr als die 128 GB RAM, die ich zur Verfügung habe.

Gibt es einen Out-of-Core-Algorithmus zum Auffinden von Komponenten mit starker Verbindung, der relativ einfach zu implementieren ist? Oder noch besser, kann es mit Unix-Befehlstools und vorhandenen (Python) -Bibliotheken zusammengeschustert werden?

Answer 1

Sie können nur ein Array von Scheitelpunkten als ihre "Farbe" (ein int-Wert) speichern, dann die Datei ohne Laden des gesamten Satzes von Links durchlaufen, Scheitelpunkte mit einer Farbe markieren, eine neue, wenn keine der Scheitelpunkte farbig ist , die gleiche Farbe, wenn die eine Farbe ist und die andere nicht, und die niedrigste von zwei Farben, zusammen mit dem Übermalen aller anderen Scheitelpunkte in der Anordnung, die mit der höchsten Farbe bemalt sind, wenn beide gefärbt sind. Ein Pseudo-Code Beispiel:

int nextColor=1; 
int merges=0; 
int[] vertices; 
while (!file.eof()) { 
    link=file.readLink(); 
    c1=vertices[link.a]; 
    c2=vertices[link.b]; 
    if ((c1==0)&&(c2==0)) { 
     vertices[link.a]=nextColor; 
     vertices[link.b]=nextColor; 
     nextColor++; 
    } else if ((c1!=0)&&(c2!=0)) { 
     // both colored, merge 
     for (i=vertices.length-1;i>=0;i--) if (vertices[i]==c2) vertices[i]=c1; 
     merges++; 
    } else if (c1==0) vertices[link.a]=c2; // only c1 is 0 
    else vertices[link.b]=c1; // only c2 is 0 
} 

Im Fall wählen Sie die kleiner als 32-Bit-Typ für Farbe eines Knotens zu speichern, müssen Sie zunächst prüfen, ob nextColor ausgereizt ist, haben eine Reihe von Farben nicht verwendeten (veröffentlicht in merge), und überspringt das Einfärben eines neuen Satzes von zwei Scheitelpunkten, wenn keine Farbe verwendet werden kann, dann führen Sie den Dateilesevorgang erneut aus, wenn beide Farben verwendet werden und alle Verschmelzungen auftreten.

UPDATE: Da die Scheitelpunkte nicht wirklich ints sondern Zeichenketten sind, sollten Sie auch eine Karte von String zu int haben, während Sie diese Datei analysieren. Wenn Ihre Strings durch die Länge begrenzt sind, können Sie sie wahrscheinlich alle als Hashtabelle in den Speicher einfügen, aber ich würde die Datei vorverarbeiten, indem Sie eine andere Datei erstellen, bei der alle Strings "s1" durch "1", "s2" ersetzt werden "mit" 2 ", usw., wobei" s1 "," s2 "alle Namen sind, die als Vertices in der Datei erscheinen, so dass die Daten zu einer Liste von Ints-Paaren verdichtet werden. Wenn Sie später ähnliche Daten verarbeiten (das heißt, Ihr Diagramm ändert sich nicht viel und enthält weitgehend die gleichen Namen von Scheitelpunkten), speichern Sie die "Metadaten" -Datei mit Links von Namen zu Ints, um weitere Vorverarbeitungen zu erleichtern.

Answer 2

Basierend auf der Beschreibung des Problems, das Sie angegeben haben, und den Antworten, die Sie in den Kommentaren gegeben haben, denke ich, dass der einfachste Weg darin besteht, einen Ansatz wie den beschriebenen @dreamzor zu verwenden. Version der Antwort

Die Grundidee besteht darin, die Daten in ein komprimierteres Format zu konvertieren, das in den Speicher passt, einen regulären Algorithmus für verbundene Komponenten auf diesen Daten auszuführen und sie dann zu dekomprimieren Verknüpfen Sie eine numerische 32-Bit-ID und geben Sie dann den Gesamtspeicherplatz für alle Knoten ist höchstens der Platz für vier Milliarden Knoten und acht Milliarden Kanten (vorausgesetzt, Sie speichern zwei Kopien jeder Kante). Dies ist Platz für zwölf Milliarden 32-Bit-Ganzzahlen, nur etwa 48 GB Speicherplatz unter Ihrer Speicherschwelle.

Um zu beginnen, schreiben Sie ein Skript, das die Kanten-Datei einliest, weist jedem Knoten eine numerische ID zu (vielleicht sequenziell in der Reihenfolge, in der sie erscheinen). Lassen Sie dieses Mapping von diesem Skript in eine Datei schreiben und schreiben Sie eine neue Edges-Datei, die anstelle der String-Namen die numerischen IDs der Knoten verwendet. Wenn Sie fertig sind, haben Sie eine Namensdatei, die IDs auf Namen und eine Edge-Datei zuordnet, die viel weniger Platz als zuvor benötigt. Sie haben in den Kommentaren erwähnt, dass Sie alle Knotennamen in den Speicher einfügen können, daher sollte dieser Schritt sehr vernünftig sein. Beachten Sie, dass Sie nicht alle Kanten im Speicher ablegen müssen - Sie können sie durch das Programm streamen - damit sollte kein Flaschenhals entstehen.

Als nächstes schreiben Sie ein Programm, das die Kanten-Datei - aber nicht die Names-Datei - in den Speicher liest und verbundene Komponenten mit einem vernünftigen Algorithmus findet (BFS oder DFS wäre hier großartig).Wenn Sie mit Ihrem Speicher vorsichtig sind (mit etwas wie C oder C++ hier wäre ein guter Anruf), sollte dies bequem in den Hauptspeicher passen. Wenn Sie fertig sind, schreiben Sie alle Cluster in eine externe Datei mit numerischer ID. Sie haben jetzt eine Liste aller CCs nach ID.

Schreiben Sie schließlich ein Programm, das die ID in die Knotenzuordnung aus der Names-Datei einliest, dann die Cluster-IDs eingibt und die Namen aller Knoten in jedem Cluster in eine endgültige Datei schreibt.

Dieser Ansatz sollte relativ einfach zu implementieren sein, da der Schlüsselgedanke darin besteht, die vorhandenen Algorithmen beizubehalten, aber die Darstellung des Diagramms nur so zu ändern, dass die Speichereffizienz erhöht wird. Ich habe Ansätze wie diese in der Vergangenheit verwendet, wenn es um riesige Graphen (Wikipedia) ging, und es funktionierte sogar auf Systemen mit weniger Speicher als deine.