ricerca efficiente in un grafo orientato

Question

Ho un grafo orientato con milioni di vertici e spigoli. Un insieme di vertici è dato, supponiamo che essi sono chiamati "START_POINTS". Un'altra serie di vertici, sono anche dato chiamati "END_POINTS". Il problema è quello di trovare quale END_POINTS può essere raggiunta da cui START_POINTS.

Ecco un esempio:

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

L'algoritmo dovrebbe essere in grado raccontare il seguente:

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

Alcuni dei END_POINTS potrebbero non essere raggiunti da qualsiasi start_point.

Ora, la domanda è: Qual è il modo più efficace per la sua attuazione

Ho provato a partire da ogni start_point uno per uno e trovare le END_POINTS raggiungibili utilizzando ricerca in profondità (o BFS, lo fa cambiare il run-time molto). Tuttavia, ci vuole un sacco di tempo perché ci sono così tanti START_POINTS (ci sono anche un sacco di END_POINTS).

La ricerca può essere ottimizzato, perché c'è una grande sovrapposizione tra i percorsi tracciati di START_POINTS. Uno ha bisogno di ricordare quali percorsi possono raggiungere che END_POINTS. Qual è il modo più efficace per raggiungere questo obiettivo? Questo potrebbe essere ben noto problema, ma non sono riuscito a trovare una soluzione ancora.

Modifica il 6 gen:

ho cercato di realizzare l'idea di bandwidth (in modo analogo a quanto Keith Randall proposto):. Per ciascun nodo, se questo nodo non punto iniziale o finale, collegare tutti gli ingressi alle uscite, quindi rimuovere il nodo

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

Questo inizia molto veloce e diventa rapidamente molto lento, soprattutto perché i conteggi di ingresso / uscita dei nodi rimanenti diventano molto grandi e nidificati per i loop uccide le prestazioni. Qualsiasi idea di come può essere reso più efficiente?

Answer 1

Proprio potare il grafico di sbarazzarsi di tutti i nodi che non appaiono in Start Nodi o di fine nodi, sostituendole con bordi dai loro nodi in entrata ai loro obiettivi in ??uscita. Una volta fatto ciò, passare attraverso tutti gli altri nodi (che sono i nodi di inizio o fine), e aggiungere bordi dai loro nodi in entrata ai loro nodi in uscita, senza cancellare questi nodi. In un paio di Djikstra-come iterazioni, si dovrebbe essere lasciato con lo Start a Fine bordi.

Answer 2

Questo potrebbe essere eccessivo, ma si potrebbe voler controllare Dijkstra . L'ho usato in passato, quando la creazione di mia propria tabella di routing dei nodi virtuali. In questo caso tutti i nodi dovrebbero avere un valore di 1, il che significa ogni nodo costa lo stesso viaggio saggia.

Answer 3

In primo luogo, eseguire un fortemente connesso componenti algoritmo. Poi contrarre tutti i componenti collegati ad un singolo nodo. Quindi eseguire un topologica sorta del grafico. Poi, in un singolo passaggio, si può calcolare che partono nodi possono raggiungere ciascun nodo del grafo (inizializza ciascun nodo di partenza s all'insieme {s}, quindi eseguire l'unione degli archi entranti in ogni nodo in ordine topologico).

Hai un potenziale problema in quanto la risposta potrebbe essere grande come # iniziano nodi * # nodi finali, che possono essere grandi. Speriamo che si dispone di alcuni grandi SCC che si contraggono a singoli nodi, in quanto ciò potrebbe rendere la risposta molto più conciso (tutti i nodi di partenza nella stessa SCC può raggiungere gli stessi luoghi, quindi è necessario utilizzare un solo rappresentante nel vostro set).