Was sind gute Möglichkeiten, um gerichtete Graph-Daten zu organisieren?

Question

Hier ist meine Situation. Ich habe ein Diagramm, bei dem verschiedene Datensätze zu unterschiedlichen Zeiten hinzugefügt werden. Zum Beispiel kann set1 einige tausend Knoten haben, und dann kommt set2 zu einem späteren Zeitpunkt und wir wenden Geschäftslogik an, um Kanten von set1 bis set2 zu erzeugen (und alle Vertices von set1, die keine Kanten haben, an set2). Dann, zu einem späteren Zeitpunkt, erhalten wir set3, set4 usw. und derselbe Prozess gilt zwischen jedem Satz und seinem vorherigen Satz.

Frage, was ist der beste Weg, dies zu organisieren? Was ich vorher getan habe, war der Name der Knoten set1-xx, set2-xx, etc .. Das Problem, dem ich gegenüberstand, war, als ich versuchte, Analysen zwischen der aktuellen Menge und der vorherigen Menge durchzuführen und suche nach allen Knoten, die mit 'setx' gestartet wurden. Es dauerte eine lange Zeit als der Graph wuchs, also dachte ich an eine andere Lösung, die darin bestand, einen Knoten namens 'set1' zu erstellen und ihn mit allen Knoten für diese bestimmte Menge zu verbinden. Ich teste es, aber ich frage mich, ob es auf diese Weise einen effizienteren Weg oder einen eingebauten Umgang mit Datenstrukturen wie diesem gibt? Gibt es eine Möglichkeit, solche Daten irgendwie zu segmentieren?

Ich denke, eine allgemeine Lösung wäre die Anwendung, aber wenn es hilft, verwende ich neo4j (so wäre jede spezifische Lösung für diese Datenbank auch gut).

Answer 1

Sie haben eine sehr spezielle Art eines gerichteten Graphen, geschichteten Graph genannt.

Die Auswahl der Datenstruktur hängt hauptsächlich von der erwarteten Diagrammdichte (wie viele Knoten von einem vorherigen Satz/Layer normalerweise mit einem Knoten im aktuellen Satz/Layer verbunden sind) und von den Vorgängen ab, an denen Sie arbeiten müssen es die meiste Zeit. Es ist definitiv eine gute Idee, dass jeder Layer direkt durch einen numerischen Index repräsentiert wird (das heißt, die äußerste Struktur wird ein Array von Sätzen/Layern sein), und vermutlich können Sie auch ein Array von Scheitelpunkten pro Layer verwenden. Allerdings ist die Liste von Kanten pro Vertex (nur aus oder in und aus Sätzen von Kanten je nachdem, ob jemals die Schichten rückwärts durchlaufen) kann irgendeine der folgenden sein:

• verkettete Liste von Scheitelpunktkennungen; Das ist gut, wenn das Diagramm sehr spärlich ist und Kanten oft hinzugefügt/entfernt werden.
• Sortiertes Array von Scheitelpunktbezeichnern; Das ist gut, wenn das Diagramm ziemlich spärlich und unveränderlich ist.
• Array von booleschen Werten, indiziert durch Scheitelpunktbezeichner, um zu bestimmen, ob ein gegebener Scheitelpunkt durch eine Kante vom aktuellen Scheitelpunkt verbunden ist oder nicht; Das ist gut, wenn der Graph dicht ist.

Der "Vertex Identifier" kann viele Formen annehmen. Zum Beispiel kann es ein Index in das Array von Scheitelpunkten auf der nächsten Ebene sein.

Answer 2

Ihre zweite Lösung ist, was ich tun würde - Erstellen Sie einen SetX-Knoten und verbinden Sie alle Knoten, die zu diesem Set SetX gehören. Auf diese Weise werden Ihre Daten partitioniert und es ist einfacher, sie abzufragen.