Melhor algoritmo para detectar ciclos em um grafo direcionado

Qual é o algoritmo mais eficiente para detectar todos os ciclos dentro de um gráfico direcionado?

Eu tenho um gráfico direcionado representando um cronograma de tarefas que precisam ser executadas, um trabalho sendo um nó e uma dependência sendo uma vantagem. Eu preciso para detectar o caso de erro de um ciclo dentro deste gráfico levando a dependencies cíclicas.

O algoritmo de componentes fortemente conectados do Tarjan possui complexidade de tempo O(|E| + |V|) .

Para outros algoritmos, consulte Componentes fortemente conectados na Wikipedia.

Dado que esta é uma agenda de trabalhos, suspeito que, em algum momento, você irá classificá- los em uma ordem proposta de execução.

Se esse for o caso, uma implementação de sorting topológica pode, em qualquer caso, detectar ciclos. tsort UNIX certamente faz. Eu acho que é provável que seja mais eficiente detectar ciclos ao mesmo tempo que tsorting, em vez de em uma etapa separada.

Assim, a questão pode se tornar “como eu tsort mais eficientemente”, em vez de “como eu detecto mais eficientemente loops”. Para o qual a resposta é provavelmente “usar uma biblioteca”, mas na falta do seguinte artigo da Wikipedia:

http://en.wikipedia.org/wiki/Topological_sorting

tem o pseudo-código para um algoritmo e uma breve descrição de outro da Tarjan. Ambos possuem complexidade de tempo O(|V| + |E|) .

Comece com um DFS: um ciclo existe se e somente se um back-edge for descoberto durante o DFS . Isto é provado como resultado do teorema do caminho branco.

A maneira mais simples de fazer isso é fazer um primeiro detalhamento de profundidade (DFT) do gráfico .

Se o grafo tiver n vértices, este é um algoritmo de complexidade de tempo O(n) . Já que você possivelmente terá que fazer um DFT a partir de cada vértice, a complexidade total se tornará O(n^2) .

Você precisa manter uma pilha contendo todos os vértices na primeira profundidade atual , com seu primeiro elemento sendo o nó raiz. Se você se deparar com um elemento que já está na pilha durante a DFT, então você tem um ciclo.

Na minha opinião, o algoritmo mais compreensível para detectar o ciclo em um grafo direcionado é o algoritmo de coloração de grafos.

Basicamente, o algoritmo de coloração do gráfico percorre o gráfico de maneira DFS (Depth First Search, o que significa que ele explora um caminho completamente antes de explorar outro caminho). Quando encontra um back edge, ele marca o gráfico como contendo um loop.

Para uma explicação detalhada do algoritmo de coloração do gráfico, leia este artigo: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

Além disso, forneço uma implementação de coloração de charts em JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

Se você não puder adicionar uma propriedade “visitada” aos nós, use um conjunto (ou mapa) e adicione todos os nós visitados ao conjunto, a menos que eles já estejam no conjunto. Use uma chave única ou o endereço dos objects como a “chave”.

Isso também fornece informações sobre o nó “raiz” da dependência cíclica, que será útil quando o usuário tiver que corrigir o problema.

Outra solução é tentar encontrar a próxima dependência a ser executada. Para isso, você deve ter alguma pilha onde possa se lembrar de onde está agora e o que precisa fazer a seguir. Verifique se uma dependência já está nessa pilha antes de executá-la. Se for, você encontrou um ciclo.

Embora isso pareça ter uma complexidade de O (N * M), você deve lembrar que a pilha tem uma profundidade muito limitada (de modo que N é pequena) e que M fica menor com cada dependência que você pode marcar como “executada” mais você pode parar a busca quando encontrou uma folha (para que você nunca tenha que verificar cada nó -> M será pequeno também).

No MetaMake, criei o gráfico como uma lista de listas e, em seguida, excluí todos os nós enquanto os executava, o que naturalmente reduzia o volume de pesquisa. Eu nunca tive que executar uma verificação independente, tudo aconteceu automaticamente durante a execução normal.

Se você precisar de um modo “somente teste”, basta adicionar um sinalizador de “execução a seco” que desabilita a execução dos trabalhos reais.

Não há algoritmo que possa encontrar todos os ciclos em um gráfico direcionado em tempo polinomial. Suponha que o grafo direcionado tenha n nós e cada par de nós tenha conexões entre si, o que significa que você tem um grafo completo. Portanto, qualquer subconjunto não vazio desses n nós indica um ciclo e há um número 2 ^ n-1 de tais subconjuntos. Portanto, nenhum algoritmo de tempo polinomial existe. Portanto, suponha que você tenha um algoritmo eficiente (não estúpido) que possa informar o número de ciclos direcionados em um gráfico. Você pode primeiro encontrar os componentes fortes conectados e, em seguida, aplicar seu algoritmo nesses componentes conectados. Desde ciclos existem apenas dentro dos componentes e não entre eles.

Eu tinha implementado este problema em sml (programação imperativa). Aqui está o esboço. Encontre todos os nós que possuem um indegree ou outdegree de 0. Esses nós não podem fazer parte de um ciclo (portanto, remova-os). Em seguida, remova todas as bordas de input ou saída desses nós. Aplique recursivamente este processo ao gráfico resultante. Se no final você não tiver nenhum nó ou borda, o gráfico não terá nenhum ciclo, senão ele tem.

Se o DFS encontrar uma aresta que aponte para um vértice já visitado, você terá um ciclo lá.

https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length Eu gosto desta solução o melhor especialmente para 4 comprimento 🙂

Também o feiticeiro diz que você tem que fazer O (V ^ 2). Eu acredito que precisamos apenas de O (V) / O (V + E). Se o gráfico estiver conectado, o DFS visitará todos os nós. Se o grafo tiver conectado subcharts, cada vez que executarmos um DFS em um vértice deste subgráfico, encontraremos os vértices conectados e não teremos que considerá-los para a próxima execução do DFS. Portanto, a possibilidade de correr para cada vértice é incorreta.

A maneira que eu faço é fazer uma sorting topológica, contando o número de vértices visitados. Se esse número for menor que o número total de vértices no DAG, você terá um ciclo.

Como você disse, você tem um conjunto de trabalhos, ele precisa ser executado em determinada ordem. Topological sort deu a ordem necessária para o agendamento de tarefas (ou para problemas de dependência, se for um direct acyclic graph ). Execute o dfs mantenha uma lista e comece a adicionar o nó no início da lista, e se você encontrou um nó que já é visitado. Então você encontrou um ciclo em determinado gráfico.

Se um gráfico satisfizer essa propriedade

 |e| > |v| - 1 

então o gráfico contém pelo menos no ciclo.