¿Cómo puedo encontrar 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 mismas pueden agruparse y categorizarse.

La estructura resultante se puede representar como Directed Acyclic Graph (DAG) donde los elementos se hunden en la parte inferior de la topología del gráfico y las categorías superiores son fuentes. Tenga en cuenta que si bien algunas de las categorías pueden estar bien definidas, mucho será definido por el usuario y podría ser muy complicado.

Ejemplo:

example data http://theuprightape.net/dag.png

En esa estructura, que desea llevar a cabo las siguientes operaciones:

• buscar todos los elementos (sumideros) por debajo de un nodo particular (todos los artículos en Europa)
• buscar 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)
• f ind todos los nodos que se encuentran por debajo de todos un conjunto de nodos (intersección: alimentos marrones goyish)

La primera parece bastante sencillo: comienzan en el nodo, siguen todos los caminos posibles a la parte inferior y recoger los artículos allí. Sin embargo, ¿hay un enfoque más rápido? Recordar los nodos que ya pasé probablemente ayuda a evitar la repetición innecesaria, pero ¿hay más optimizaciones?

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

Todos los graph traversal algorithms listed at Wikipedia parecen estar relacionados con la búsqueda de un nodo en particular o la ruta más corta o más efectiva entre dos nodos. Creo que ninguno de los dos es lo que quiero o simplemente no veo 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ás preguntando "Encontrar todos los X debajo del nodo (s) Y, donde X es del 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 partida (su conjunto de nodos) y su punto final (cualquier receptor debajo del punto de inicio), por lo que su conjunto de soluciones es todas las rutas desde el nodo de inicio especificado hasta el receptor. Así que sugeriría que lo que tienes básicamente es un árbol, y los algoritmos básicos de cruce de árboles serían el camino a seguir.

Answer 2

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

Ver también Robert Tarjan's algoritmos básicos.