algorithm - prim - ¿Cómo puedo encontrar todas las rutas a través de un conjunto de nodos dados en un DAG?
prim''s algorithm (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 el dominio 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.
También vea los algoritmos básicos de Robert Tarjan .
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 un Gráfico Acíclico Dirigido (DAG) donde los artículos 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:
datos de ejemplo http://theuprightape.net/dag.png
En esa estructura, quiero realizar las siguientes operaciones:
- encuentre todos los artículos (fregaderos) debajo de un nodo particular (todos los artículos en Europa)
- encuentre 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 un conjunto de nodos (intersección: alimentos marrones goyish)
La primera parece bastante sencilla: comience en el nodo, siga todos los caminos posibles hasta el fondo y recoja los elementos 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 voy sobre 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?
Los algoritmos de cruce de gráficos enumerados en Wikipedia parecen estar relacionados con la búsqueda de un nodo 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?
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.