¿Cómo encuentro todas las rutas a través de un conjunto de nodos dados en un DAG?

Question

Tengo una lista de elementos (nodos azules a continuación) que están categorizados por los usuarios de mi aplicación. Las categorías en sí se pueden agrupar y clasificar por sí mismas.

La estructura resultante se puede representar como un Gráfico acíclico dirigido (DAG) donde los elementos son sumideros en la parte inferior de la topología del gráfico y las principales categorías son fuentes. Tenga en cuenta que si bien algunas de las categorías pueden estar bien definidas, muchas serán definidas por el usuario y pueden ser muy desordenadas.

Ejemplo:

_{(fuente: theuprightape.net )}

En esa estructura, quiero realizar las siguientes operaciones:

• buscar todos los elementos (sumideros) debajo de un nodo en particular (todos los elementos en Europa)
• encuentra todas las rutas (si las hay) que pasan a través de un conjunto de n nodos (todos los elementos enviados a través de SMTP desde example.com)
• encuentre todos los nodos que se encuentran debajo de todo un conjunto de nodos (intersección: alimentos marrón goyish)

El primero parece bastante sencillo: comience en el nodo, siga todos los caminos posibles hacia la parte inferior y recoja los elementos allí. Sin embargo, ¿hay un enfoque más rápido? Recordar los nodos por los que ya pasé probablemente ayuda a evitar repeticiones innecesarias, pero ¿hay más optimizaciones?

¿Cómo hago para el segundo? Parece que el primer paso sería determinar la altura de cada nodo en el conjunto, como determinar en cuál (es) comenzar y luego encontrar todas las rutas por debajo de las que incluyen el resto del conjunto. ¿Pero es este el mejor (o incluso un buen) enfoque?

Los algoritmos de recorrido del gráfico enumerados en Wikipedia parecen preocuparse por encontrar un particular nodo o la ruta más corta o más efectiva entre dos nodos. Creo que ambas cosas no son lo que quiero, ¿o simplemente no pude ver cómo esto se aplica a mi problema? ¿Dónde más debería leer?

Answer 1

Me parece que es esencialmente la misma operación para las 3 preguntas. Siempre está preguntando "Buscar todos los X debajo de los nodos Y, donde X es de tipo Z". Todo lo que necesita es un mecanismo genérico para 'localizar todos los nodos debajo del nodo' (resuelve Q3) y luego puede filtrar los resultados para 'nodetype = sink' (resuelve Q1). Para Q2, tiene el punto de inicio (su conjunto de nodos) y su punto final (cualquier sumidero debajo del punto de inicio), por lo que su conjunto de soluciones son todas las rutas desde el nodo de inicio especificado hasta el sumidero. Por lo tanto, sugeriría que lo que básicamente tiene es un árbol, y los algoritmos básicos de recorrido del árbol serían el camino a seguir.

Answer 2

A pesar de que su gráfico es acíclico, las operaciones que cita me recuerdan aspectos similares del análisis de gráficos de flujo de control. Existe un amplio conjunto de algoritmos basados ??en dominio que pueden ser aplicables. Por ejemplo, su tercera operación me recuerda a las fronteras de computación de dominio; Creo que el algoritmo funcionaría directamente si introduces temporalmente "entrada". y "salir" nodos El nodo de entrada conecta el " conjunto de nodos dado " y los nodos de salida conectan los sumideros.

Consulte también los algoritmos básicos de Robert Tarjan .