Traversal do gráfico direcionado cíclico

Question

Eu tenho um gráfico direcionado cíclico. Começando nas folhas, desejo propagar dados anexados a cada nó a jusante para todos os nós que são acessíveis a partir desse nó. Em particular, preciso continuar pressionando os dados em torno de qualquer ciclos alcançados até que os ciclos se estabilizem.

Tenho certeza de que este é um problema de travessia de gráfico de ações. No entanto, estou tendo bastante dificuldade em tentar encontrar um algoritmo adequado-acho que estou perdendo algumas palavras-chave de pesquisa cruciais.

Antes de tentar escrever meu próprio algoritmo O (n^3), alguém pode me apontar para uma solução adequada? E o que é Este problema em particular chamado?

Answer 1

Como o gráfico é cíclico (o IE pode conter ciclos), eu o dividiria primeiro em componentes fortemente conectados. UMA componente fortemente conectado de um gráfico direcionado é um subgrafileiro em que cada nó é acessível de todos os outros nó no mesmo subgraf. Isso produziria um conjunto de subgrafos. Observe que um componente fortemente conectado de mais de um nó é efetivamente um ciclo.

Agora, em cada componente, qualquer informação em um nó acabará por acabar em todos os outros nó do gráfico (pois todos são acessíveis). Assim, para cada subgrafista, podemos simplesmente pegar todos os dados de todos os nós e fazer com que todos os nó tenham o mesmo conjunto de dados. Não há necessidade de continuar passando pelos ciclos. Além disso, no final desta etapa, todos os nós no mesmo componente contêm exatamente os mesmos dados.

A próxima etapa seria colapsar cada componente fortemente conectado em um único nó. Como os nós dentro do mesmo componente têm os mesmos dados e, portanto, são basicamente os mesmos, essa operação não altera o gráfico. O recém -criado "Super Node" herdará todas as bordas que saem ou entram nos nós do componente de nós fora do componente.

Como colapsamos todos os componentes fortemente conectados, não haverá ciclos no gráfico resultante (por quê? Porque havia um ciclo formado pelos nós resultantes, todos teriam sido colocados no mesmo componente em primeiro lugar). O gráfico resultante é agora um Gráfico acíclico direcionado. Não há ciclos, e uma simples traseira de profundidade de todos os nós com indegredos = 0 (isto é, nós que não têm bordas de entrada), propagando dados de cada nó para seus nós adjacentes (ou seja, seus "filhos"), devem fazer o trabalho .