Bester Weg zum Speichern / Zugang zu einem gerichteten Graphen

Question

Ich habe etwa 3500 Hochwasserschutzeinrichtungen, die Ich mag würde als ein Netzwerk darzustellen Strömungswege, um zu bestimmen (im wesentlichen ein gerichteter Graph). Ich bin derzeit mit SqlServer und einen CTE rekursiv alle Knoten und ihre Upstream-Komponenten zu prüfen und dies funktioniert, solange der Upstream-Pfad nicht Gabel alot. Allerdings nehmen einige Abfragen exponentiell länger als andere, auch wenn sie nicht viel weiter physisch auf dem Weg (das heißt zwei oder drei Segmente „downstream“) wegen der zusätzlichen Komplexität stromaufwärts; in einigen Fällen habe ich es vor der Tötung der Abfrage gehen über 10 Minuten lassen. Ich verwende eine einfache Tabelle mit zwei Spalten, eine Spalte, die die Anlage selbst ist und das andere die Einrichtung ist, die stromaufwärts von dem in der ersten Spalte aufgelistet ist.

Ich habe versucht, einen Index Hinzufügen die aktuelle Anlage mit Geschwindigkeit Dingen zu helfen, aber das machte keinen Unterschied. Und wie für die möglichen Verbindungen in der grafischen Darstellung, alle Knoten mehr Upstream-Verbindungen haben könnten und könnten von mehrere „downstream“ Knoten angeschlossen werden.

Es ist durchaus möglich, dass es Zyklen in den Daten, aber ich habe noch nicht einen guten Weg gefunden, dies zu überprüfen (außer wenn die CTE-Abfrage eines maximalen rekursive Zählung Treffer gemeldet, das war einfach zu beheben)

Also, meine Frage ist, bin Speicherung ich diese Informationen falsch? Gibt es eine bessere Art und Weise andere als ein CTE die Upstream-Punkte abfragen?

Answer 1

Ich weiß nichts über Hochwasserschutzeinrichtungen. Aber ich würde die erste Anlage übernehmen. Und verwenden Sie eine temporäre Tabelle und eine while-Schleife den Pfad zu erzeugen.

-- Pseudo Code
TempTable (LastNode, CurrentNode, N)


DECLARE @intN INT
SET @intN = 1

INSERT INTO TempTable(LastNode, CurrentNode, N)
  -- Insert first item in list with no up stream items...call this initial condition
  SELECT LastNode, CurrentNode, @intN
  FROM your table
  WHERE node has nothing upstream

WHILE @intN <= 3500
BEGIN
     SEt @intN = @intN + 1
    INSERT INTO TempTable(LastNode, CurrentNode, N)
      SELECT LastNode, CurrentNode, @intN
      FROM your table
      WHERE LastNode IN (SELECT CurrentNode FROM TempTable WHERE N = @intN-1)

IF @@ROWCOUNT = 0
     BREAK


END

Wenn wir, dass alle Knotenpunkte auf ein Kind übernehmen. Dann sollten diese nicht länger als 3500 Iterationen. Wenn mehrere Knoten den gleichen Upstream-Provider haben, dann wird es weniger nehmen. Aber noch wichtiger ist, auf diese Weise können Sie dies tun ...

SELECT LastNode, CurrentNode, N VON TempTable ORDER BY N

Und das können Sie sehen, ob es irgendwelche Schleifen oder andere Probleme mit Ihrem Provider sind. Übrigens 3500 Zeilen ist nicht so sehr, auch im schlimmsten Fall der einzelnen Anbieter zu einem anderen Upstream-Provider zeigt, ist dies nicht so lange dauern sollte.

Answer 2

Der beste Weg, Graphen zu speichern, ist natürlich eine native Graph db zu verwenden: -)

Hier finden Sie aktuelle Neo4j . Es ist in Java implementiert und verfügt über Python und Ruby-Bindungen als auch.

Ich schrieb bis zwei Wiki-Seiten mit einfachen Beispielen von Domänenmodellen als Graphen dargestellt mit Neo4j: Montag und Rollen . Weitere Beispiele sind auf dem Domain-Modellierung Galerie Seite gefunden.

Answer 3

Traditionell werden Graphen entweder durch eine Matrix oder einen Vektor dargestellt. Die Matrix nimmt mehr Platz, ist aber einfacher zu verarbeiten (3500x3500 Einträge in Ihrem Fall); der Vektor nimmt weniger Platz (3500 Einträge, jeweils eine Liste, die sie verbinden zu).

Hilft Ihnen?

Answer 4

Ich denke, Ihre Datenstruktur in Ordnung ist (für SQL Server), sondern ein CTE kann nicht die effizienteste Lösung für Ihre Fragen sein. Sie können eine gespeicherte Prozedur versuchen zu machen, die das Diagramm unter Verwendung einer temporären Tabelle als eine Warteschlange stattdessen durchläuft, sollte dies effizienter sein.

die temporäre Tabelle kann auch verwendet werden Zyklen in der Grafik zu beseitigen, obwohl es sollte nicht sein

Answer 5

Ja (vielleicht). Ihr Datensatz klingt relativ klein ist, könnten Sie die Grafik-Speicher als Adjazenzmatrix oder Adjazenzliste laden und die Grafik direkt abfragen - vorausgesetzt, Sie programmieren.

Was On-Disk-Format, DOT unter anderem ziemlich portable / beliebt ist. Es scheint auch ziemlich üblich, eine Liste von Kanten in einem flachen Dateiformat zu speichern, wie:

vertex1 vertex2 {edge_label1}+

Wenn die erste Zeile der Datei, die Anzahl der Scheitelpunkte in dem Diagramm enthält, und jede Zeile danach Kanten beschreibt. Ob die Kanten gerichtet oder ungerichtet sind, ist an den Implementierer auf. Wenn Sie explizit gerichtete Kanten wollen, dann beschreiben sie gerichtete Kanten unter Verwendung von wie:

vertex1 vertex2
vertex2 vertex1

Answer 6

Meine Erfahrungen mit der Speicherung von so etwas wie Sie in einer SQL Server-Datenbank beschrieben:

Ich war eine Distanzmatrix zu speichern, zu sagen, wie lange dauert es, um von Punkt A reisen nach Punkt B. ich die naive Darstellung getan habe und sie direkt in eine Tabelle namens Entfernungen mit Spalten A, B, Entfernung, Zeit gespeichert.

Das ist sehr langsam auf einfache retreival. Ich fand es viel besser ist meine ganze Matrix als Text zu speichern. Dann retreive es in den Speicher vor den Berechnungen, eine Matrix struxture im Speicher erstellen und dort mit ihm arbeiten.

ich mit einigem Code zur Verfügung stellen könnte, aber es wäre C # sein.