búsqueda eficiente en un grafo dirigido

Question

I tiene un gráfico dirigido con millones de vértices y aristas. Un conjunto de vértices se dan, vamos a suponer que se les llama "START_POINTS". Otro conjunto de vértices, se dan también llamados "END_POINTS". El problema es encontrar el que END_POINTS se puede llegar desde la que START_POINTS.

Este es un ejemplo:

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

El algoritmo debe ser capaz de obtener la información siguiente:

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

Algunos de los END_POINTS podría no llegar desde cualquier punto_inicial.

Ahora, la pregunta es: ¿Cuál es la forma más eficiente para ponerlo en práctica

He intentado partir de cada punto_inicial uno por uno y encontrar los END_POINTS alcanzables mediante búsqueda en profundidad (o BFS, lo hace cambiar el tiempo de ejecución mucho). Sin embargo, se necesita mucho tiempo, porque hay tantas START_POINTS (también hay una gran cantidad de END_POINTS).

La búsqueda se puede optimizar, ya que hay una gran superposición entre los caminos trazados de START_POINTS. Uno tiene que recordar qué caminos puede llegar a que END_POINTS. ¿Cuál es la forma más eficaz de lograr esto? Esto podría ser un problema muy conocido, pero no pude encontrar una solución todavía.

EDITAR el 6 de Jan:

He intentado poner en práctica la idea de gran ancho de banda (de una manera similar a lo que Keith Randall propuso.): Para cada nodo, si este nodo no es punto inicial o final, conectar todas las entradas a las salidas, a continuación, eliminar el 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

Así se inicia muy rápido y rápidamente se convierte en muy lento, principalmente debido a los conteos de entrada / salida de los nodos restantes se ponen muy grandes y bucles for anidados mata el rendimiento. Cualquier idea de cómo se puede hacer más eficiente?

Answer 1

Sólo podar el gráfico para deshacerse de todos los nodos que no aparecen en el inicio nodos o nodos finales, sustituyéndolos por los bordes de sus nodos de entrada a sus objetivos salientes. Una vez hecho esto, pasar por todos los demás nodos (que son principio o al final nodos), y añadir bordes de sus nodos de entrada a sus nodos de salida, sin eliminar estos nodos. En un par de Djikstra-como iteraciones, se debe quedar con el principio hasta el final bordes.

Answer 2

Esto podría ser una exageración, pero es posible que desee revisar Dijkstra . Lo usé en el pasado la hora de crear mi propia tabla de encaminamiento de nodos virtuales. En este caso todos los nodos tendrían un valor de 1, lo que significa que cada nodo cuesta lo mismo recorrido sabia.

Answer 3

Primero, ejecute un fuertemente conectada componentes algoritmo. Entonces contraer todos los componentes conectados a un solo nodo. A continuación, realice una topológica tipo de la gráfica. Luego, en una sola pasada, se puede calcular que comienzan nodos pueden llegar a cada nodo en el gráfico (inicializar cada nodo de inicio s al conjunto {s}, a continuación, realizar la unión de los bordes entrantes en cada nodo en orden topológico).

tiene un problema potencial en que la respuesta podría ser tan grande como # inicia linfáticos * # nodos finales, que pueden ser grandes. Esperamos que tengan unas grandes SCC que contratar a los nodos individuales, ya que esto podría hacer que la respuesta mucho más concisos (todos los nodos de inicio de la misma SCC puede llegar a los mismos lugares, por lo que sólo necesitan utilizar un representante en sus conjuntos).