Effiziente Suche in einem gerichteten Graphen

Question

Ich habe einen gerichteten Graphen mit Millionen von Ecken und Kanten. Es wird eine Reihe von Vertices angegeben, angenommen, sie heißen "START_POINTS". Eine weitere Gruppe von Vertices, "END_POINTS" genannt, wird ebenfalls angegeben. Das Problem besteht darin herauszufinden, welche END_POINTS von welchen START_POINTS aus erreicht werden können. Hier

ein Beispiel:

START_POINTS: S1 S2 S3 S4 S5 S6 S7 ... 
END_POINTS : E1 E2 E3 E4 E5 E6 E7 ... 

Der Algorithmus sollte folgende Lage sein, sagen:

S1 can reach to E1, E2, E6 
S2 can reach to E9, E10 
S3 cannot reach any END_POINT 
S4 can reach to ..... 
.... 

Einige der END_POINTS vielleicht nicht von jedem START_POINT erreicht werden.

Jetzt ist die Frage: Was ist der effizienteste Weg, um es zu implementieren?

Ich habe versucht, von jedem START_POINT eins nach dem anderen zu starten und die erreichbaren END_POINTS mit Tiefensuche (oder BFS, es ändert die Laufzeit viel) zu finden. Es kostet jedoch viel Zeit, da es so viele START_POINTS gibt (es gibt auch viele END_POINTS).

Die Suche kann optimiert werden, da sich die verfolgten Pfade von START_POINTS stark überschneiden. Man muss sich merken, welche Pfade welche END_POINTS erreichen können. Was ist der effizienteste Weg, dies zu erreichen? Dies könnte ein bekanntes Problem sein, aber ich konnte noch keine Lösung finden.

EDIT am 6. Januar:

Ich versuchte highBandWidth Idee (in einer Weise, ähnlich dem, was Keith Randall vorgeschlagen) zu implementieren: Für jeden Knoten, wenn dieser Knoten wird Punkt nicht beginnen oder enden, schließen Sie alle Eingänge zu Ausgängen, dann entfernen Sie den Knoten.

foreach NODE in NODES 
    Skip if NODE is START_POINT or END_POINT 
    foreach OUTPUT_NODE of NODE 
     Disconnect NODE from INPUT_NODE 
    end 
    foreach INPUT_NODE of NODE 
     Disconnect NODE from INPUT_NODE 
     foreach OUTPUT_NODE of NODE 
      Connect INPUT_NODE to OUTPUT_NODE 
     end 
    end 
    Remove NODE from NODES 
end 

Das beginnt sehr schnell und wird schnell sehr langsam, vor allem weil die Eingabe/Ausgabe-Zählungen verbleibenden Knoten sehr groß werden und für Schleifen verschachtelt tötet die Leistung. Irgendeine Idee, wie es effizienter gemacht werden kann?

Answer 1

Schneiden Sie das Diagramm einfach ab, um alle Knoten zu entfernen, die nicht in Startknoten oder Endknoten angezeigt werden, und ersetzen sie durch Kanten von ihren eingehenden Knoten zu ihren ausgehenden Zielen. Sobald dies geschehen ist, gehen Sie durch alle anderen Knoten (die Start- oder Endknoten sind) und fügen Sie den Knoten für ausgehende Knoten Kanten hinzu, ohne diese Knoten zu löschen. In einigen Djikstra-ähnlichen Iterationen sollten Sie die Kanten vom Anfang bis zum Ende beibehalten.

Answer 2

Dies könnte Overkill sein, aber Sie möchten vielleicht Dijkstra überprüfen. Ich habe es in der Vergangenheit beim Erstellen meiner eigenen Routing-Tabelle von virtuellen Knoten verwendet. In diesem Fall würden alle Ihre Knoten den Wert 1 haben, was bedeutet, dass jeder Knoten die gleiche Reise kostet.

Answer 3

Führen Sie zuerst einen strongly connected components Algorithmus aus. Dann kontrahiere alle verbundenen Komponenten zu einem einzigen Knoten. Führen Sie dann einen topological sort des Graphen aus. Dann können Sie in einem einzigen Durchgang berechnen, welche Startknoten jeden Knoten im Diagramm erreichen können (initialisieren Sie jeden Startknoten s mit der Menge {s}, und führen Sie anschließend die Vereinigung der eingehenden Kanten an jedem Knoten in topologischer Reihenfolge durch).

Sie haben ein potenzielles Problem darin, dass die Antwort so groß sein könnte wie # Startknoten * # Endknoten, die groß sein können. Hoffentlich haben Sie einige große SCCs, die sich zu einzelnen Knoten zusammenziehen, da dies die Antwort viel prägnanter machen könnte (alle Startknoten im selben SCC können dieselben Orte erreichen, Sie brauchen also nur einen Repräsentanten in Ihren Sätzen).