Effiziente Suche in einem gerichteten Graphen

Question

Ich habe einen gerichteten Graphen mit Millionen von Eckpunkten und Kanten.Es wird eine Reihe von Eckpunkten angegeben. Nehmen wir an, dass sie „START_POINTS“ heißen.Ein weiterer Satz von Scheitelpunkten mit der Bezeichnung „END_POINTS“ ist ebenfalls angegeben.Das Problem besteht darin herauszufinden, welche END_POINTS von welchen START_POINTS aus erreichbar sind.

Hier ist ein Beispiel:

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

Der Algorithmus sollte Folgendes sagen können:

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 sind möglicherweise von keinem START_POINT aus erreichbar.

Die Frage ist nun:Wie lässt sich das am effizientesten umsetzen?

Ich habe versucht, bei jedem START_POINT einzeln zu beginnen und die erreichbaren END_POINTS mithilfe der Tiefensuche (oder BFS, das verändert die Laufzeit erheblich) zu finden.Allerdings nimmt es viel Zeit in Anspruch, da es so viele START_POINTS gibt (es gibt auch viele END_POINTS).

Die Suche kann optimiert werden, da es eine große Überschneidung zwischen den verfolgten Pfaden von START_POINTS gibt.Man muss sich merken, welche Pfade welche END_POINTS erreichen können.Was ist der effizienteste Weg, dies zu erreichen?Das ist vielleicht ein bekanntes Problem, aber ich konnte noch keine Lösung finden.

EDIT am 6. Januar:

Ich habe versucht, die Idee von highBandWidth umzusetzen (auf ähnliche Weise wie Keith Randall vorgeschlagen hat):Wenn dieser Knoten kein START- oder ENDpunkt ist, verbinden Sie für jeden Knoten alle Eingänge mit den Ausgängen und entfernen Sie dann 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

Dies beginnt sehr schnell und wird schnell sehr langsam, hauptsächlich weil die Ein-/Ausgabezahlen der verbleibenden Knoten sehr groß werden und verschachtelte for-Schleifen die Leistung beeinträchtigen.Irgendeine Idee, wie es effizienter gemacht werden kann?

Answer 1

Beschneiden Sie einfach das Diagramm, um alle Knoten zu entfernen, die nicht in den Startknoten oder Endknoten erscheinen, und ersetzen Sie sie durch Kanten von ihren eingehenden Knoten zu ihren ausgehenden Zielen.Sobald dies erledigt ist, gehen Sie alle anderen Knoten durch (die Start- oder Endknoten sind) und fügen Sie Kanten von ihren eingehenden Knoten zu ihren ausgehenden Knoten hinzu, ohne diese Knoten zu löschen.In einigen Djikstra-ähnlichen Iterationen sollten Sie mit den Start-End-Kanten zurückbleiben.

Answer 2

Das ist vielleicht übertrieben, aber Sie sollten es sich vielleicht ansehen Dijkstra.Ich habe es in der Vergangenheit verwendet, als ich meine eigene Routing-Tabelle für virtuelle Knoten erstellt habe.In diesem Fall hätten alle Ihre Knoten den Wert 1, was bedeutet, dass jeder Knoten in Bezug auf die Reise die gleichen Kosten verursacht.

Answer 3

Führen Sie zunächst a aus stark verbundene Komponenten Algorithmus.Ziehen Sie dann alle verbundenen Komponenten zu einem einzigen Knoten zusammen.Führen Sie dann a aus topologische Sortierung des Diagramms.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 dann eine Vereinigung der eingehenden Kanten an jedem Knoten in topologischer Reihenfolge durch).

Sie haben ein potenzielles Problem, da die Antwort so groß sein könnte wie # Startknoten * # Endknoten, was groß sein kann.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 die gleichen Orte erreichen, Sie müssen also nur einen Vertreter in Ihren Sätzen verwenden).