Datenstruktur zum Speichern von Kanten eines Diagramms

8

Ich arbeite derzeit an meiner Masterarbeit und es geht um das Clustering in Grafiken. Ich arbeite mit einer Idee, bei der Ameisen das Problem lösen. Ich arbeite derzeit an der Implementierung und frage mich genau, wie gut die Kanten des Diagramms dargestellt werden sollen.

Jede Kante wird mit bestimmten Informationen wie dem Pheromonwert und der Häufigkeit, mit der eine Ameise diese Kante besucht hat, ergänzt. Ich werde mit ungerichteten Diagrammen arbeiten, die sehr groß sein können (über eine Million Eckpunkte), und ich habe mich gefragt, wie ich die Kanten am effizientesten speichern und nachschlagen kann. Ich dachte daran, mich an eine Konvention zu halten und Endpunkte gemäß der zu speichern, die eine niedrigere Scheitelpunkt-ID für und die höhere für v 2 hat ( v 1 und v 2 sind die Endpunkte der Kante in der Datenstruktur). Aber ich frage mich, wie ich in diesem Fall nachschlagen soll.v1v2v1v2

Es gibt eine Zuordnung, die ich von der Adjazenzmatrix zum Kantenarray erstellt habe, die jedoch nur funktioniert, wenn das zugrunde liegende Diagramm ein vollständiges Diagramm ist. Deshalb bin ich hierher gekommen, um einige Vorschläge zu machen, wie ich vorgehen soll, da meine Suche effizient sein muss, während ich gleichzeitig den Speicherplatz für die Kanten nicht vergrößern möchte, da die Grafiken sehr groß sein werden.

graph-theory data-structures evolutionary-computing schlammig
quelle
1
Sind Ihre Grafiken spärlich oder dicht? Weil die Antwort darauf beruht.
Bartosz Przybylski
Oh, ich hätte das erwähnen sollen, ja, es sind meistens spärliche Graphen. Grundsätzlich repräsentieren die Grafiken, mit denen ich arbeiten werde, reale Netzwerke, die normalerweise spärlich sind. :)
schlammig
Sortierte Adjazenzlisten?
Raphael

Antworten:

5

Wenn Ihr Diagramm spärlich ist, sollten Sie es mithilfe von Adjazenz- "Listen" speichern, obwohl Sie wahrscheinlich etwas Effizienteres als eine Liste wünschen (oder vielleicht auch nicht, je nach Verwendung). Am einfachsten ist es, wenn Sie jede Kante an beiden Endpunkten speichern. Dies kann auf viele Arten implementiert werden, zum Beispiel können Sie alle Daten in einem großen Array speichern und nur Zeiger in den Adjazenz- "Listen" speichern.

Yuval Filmus
quelle
Bisher habe ich einen Adjazenzlisten-Ansatz verwendet, bei dem ich für jeden Scheitelpunkt ein Array seiner Nachbarn habe (jeder Scheitelpunkt ist ein Objekt). Dieser Weg hilft, weil jede Ameise die Nachbarn jedes Scheitelpunkts kennt. Aber ich muss anhand der Pheromoninformationen und einiger anderer Daten, die ich berechnen werde, auswählen, welche Kante als nächstes durchlaufen werden soll. Ich möchte keine Duplizierung einführen, daher habe ich mich gefragt, ob es eine Möglichkeit gibt, jede Kante einzeln darzustellen, sie aber gleichzeitig effizient indizieren zu können, da ich in jeder Iteration viel nach jeder Kante suchen muss .
schlammig
Hier ist als Beispiel die mögliche Zuordnung zu den Indizes des Kantenarrays, wenn der Graph vollständig war. In diesem Fall wissen wir bereits, dass die Größe des Kantenarrays n (n-1) ist, wobei n die Anzahl der Eckpunkte ist. Die Übersetzung der [x] [y] -Adjazenzmatrix in den Array-Index (idx) kann also wie folgt erfolgen: Wenn x <= y, dann ist idx = n * x - x * (x + 1) / 2 + (y - x - 1) sonst idx = n * y - y * (y + 1) / 2 + (x - y - 1) Sagen wir also, Kante (5,11) oder (11,5) werden beide in denselben Array-Index übersetzt. Da ich aber nicht mit vollständigen Grafiken arbeite, fällt mir keine Zuordnung ein.
schlammig
2
Sie bestehen weiterhin darauf, Datenstrukturen zu verwenden, die nur für dichte Diagramme sinnvoll sind. Bei spärlichen Graphen besteht der Ansatz immer darin, für jeden Scheitelpunkt alle darauf einfallenden Kanten zu speichern. Es gibt keine Vervielfältigung - die Daten werden nur an einem Ort gespeichert; Es gibt jedoch zwei Zeiger auf die Daten. Eine schnelle Indizierung könnte mithilfe von Suchbäumen, Hash-Tabellen usw. implementiert werden. Mit diesen können Sie G implementierenG[x][y]