Recorrido de gráfico cíclico dirigido

Question

Tengo un gráfico cíclico dirigido. Comenzando por las hojas, deseo propagar los datos adjuntos a cada nodo en sentido descendente a todos los nodos a los que se puede acceder desde ese nodo. En particular, necesito seguir presionando los datos alrededor de cualquier ciclo que se alcance hasta que los ciclos se estabilicen.

Estoy completamente seguro de que se trata de un problema transversal de gráfico de valores. Sin embargo, estoy teniendo un poco de dificultad tratando de encontrar un algoritmo adecuado, creo que me faltan algunas palabras clave de búsqueda cruciales.

Antes de intentar escribir mi propio algoritmo O (n^3) a medias, ¿alguien puede indicarme una solución adecuada? ¿Y qué es llamado este problema en particular?

Answer 1

Dado que el gráfico es cíclico (es decir, puede contener ciclos), primero lo dividiría en componentes fuertemente conectados. Un strongly connected component de un grafo dirigido es un subgrafo donde cada nodo es alcanzable desde cualquier otro nodo en el mismo subgrafo. Esto arrojaría un conjunto de subgrafos. Observe que un componente fuertemente conectado de más de un nodo es efectivamente un ciclo.

Ahora, en cada componente, cualquier información en un nodo eventualmente terminará en cada otro nodo del gráfico (ya que todos son accesibles). Por lo tanto, para cada subgráfico podemos simplemente tomar todos los datos de todos los nodos y hacer que cada nodo tenga el mismo conjunto de datos. No es necesario seguir los ciclos. Además, al final de este paso, todos los nodos en el mismo componente contienen exactamente los mismos datos.

El siguiente paso sería colapsar cada componente fuertemente conectado en un solo nodo. Como los nodos dentro del mismo componente tienen todos los mismos datos, y por lo tanto son básicamente los mismos, esta operación realmente no cambia el gráfico. El "super nodo" recién creado heredará todos los bordes que salen o que entran en los nodos del componente desde nodos fuera del componente.

Puesto que hemos colapsado todos los componentes fuertemente conectados, no habrá ciclos en la gráfica resultante (¿Por qué? Porque si hubiera habido un ciclo formado por los nodos resultantes, todos ellos se han colocado en el mismo componente en primer lugar). El gráfico resultante ahora es Directed Acyclic Graph. No hay ciclos, y un primer recorrido de profundidad simple desde todos los nodos con indegree = 0 (es decir, nodos que no tienen bordes entrantes), propagando datos de cada nodo a sus nodos adyacentes (es decir, sus "hijos"), debe hacer el trabajo .