Ordenação topológica
Em teoria dos grafos, uma ordenação topológica de um digrafo acíclico (DAG) é uma ordem linear de seus nós em que cada nó vem antes de todos nós para os quais este tenha arestas de saída. Cada DAG tem uma ou mais ordenações topológicas.
Mais formalmente, define-se a relação acessibilidade R sobre os nós do DAG tal que xRy se e somente se existe um caminho dirigido de x para y. Então, R é uma ordem parcial, e uma ordenação topológica é uma extensão linear desta ordem parcial, isto é, uma ordem total compatível com a ordem parcial.
Exemplos
[editar | editar código-fonte]A aplicação canônica da ordenação topológica (ordem topológica) está na programação de uma sequência de trabalhos ou tarefas; tem uso potencial todas as vezes em que o problema abordado envolve uma ordem parcial;[1] algoritmos de ordenação topológica começaram a ser estudados no início dos anos 1960 no contexto da técnica PERT para a agendamento de tarefas em gerenciamento de projetos.[2] Os trabalhos são representados por vértices, e existe uma aresta de x para y se o trabalho x deve estar concluído antes do trabalho y poder ser iniciado (por exemplo, ao lavar roupas, a máquina de lavar deve terminar antes de se poder colocar as roupas para secar). Em seguida, uma ordenação topológica dá uma ordem na qual se possa realizar os trabalhos.
Em informática, as aplicações deste tipo surgem em agendamentos de instruções, ordenação de fórmulas de avaliação de células quando recalculando os valores de fórmulas em planilhas, síntese lógica, determinação da ordem das tarefas de compilação para executar em arquivos "make", e resolução de dependências de símbolos em ligadores.
 |
O grafo mostrado à esquerda tem muitas ordenações topológicas, incluindo:
|
Algoritmos
[editar | editar código-fonte]Os algoritmos usuais de ordenação topológica tem tempo de execução linear no número de nós, mais o número de arestas (O(|V|+|E|)).
Um desses algoritmos, descrito pela primeira vez por Kahn,[3] trabalha escolhendo vértices na mesma ordem da eventual ordenação topológica. Primeiro, encontra uma lista de nós "íniciais", que não tem arestas de entrada e os insere em um conjunto S; pelo menos um nó devem existir se o grafo é acíclico. Então:
L ← Lista vazia que irá conter os elementos ordenados
S ← Conjunto de todos os nós sem arestas de entrada
enquanto S é não-vazio faça
remova um nodo n de S
insira n em L
para cada nodo m com uma aresta e de n até m faça
remova a aresta e do grafo
se m não tem mais arestas de entrada então
insira m em S
se o grafo tem arestas então
escrever mensagem de erro (grafo tem pelo menos um ciclo)
senão
escrever mensagem (ordenação topológica proposta: L)
Se o grafo é um digrafo acíclico (DAG), a solução está contida na lista L (a solução não é única). Caso contrário, o grafo tem pelo menos um ciclo e, portanto, uma ordenação topológica é impossível.
Note-se que, reflectindo a não-exclusividade da ordenação resultante, a estrutura S pode ser simplesmente um conjunto ou uma fila ou uma pilha. Dependendo da ordem em que os nodos n são removidos do conjunto S, uma solução diferente é criada.
Um algoritmo alternativo para a ordenação topológica é baseado em uma busca em profundidade. Para este algoritmo, as arestas apontam na direção oposta, como o algoritmo anterior (e no sentido oposto ao mostrado no diagrama na seção de exemplos acima). Existe uma aresta de x para y se a tarefa x depende da tarefa y (em outras palavras, se a tarefa y deve ser concluída antes da tarefa x poder ser iniciada). O algoritmo faz um loop através de cada nó do grafo, em uma ordem arbitrária, iniciando uma busca em profundidade que termina quando se atinge qualquer nó que já foi visto desde o início da ordenação topológica:
L ← Lista vazia que irá conter os elementos ordenados S ← Conjunto de todos os nós sem arestas de entrada
função visita(nodo n)
se n não foi visitado ainda então
marque n como visitado
para cada nodo m com uma aresta de n para m faça
visite(m)
adicione n em L
para cada nodo n em S faça
visite(n)
Note que cada nodo n é adicionado à lista de saída L somente após considerar todos os outros nodos dos quais n depende (todos os nodos descendentes de n no grafo). Especificamente, quando o algoritmo acrescenta o nodo n, temos a garantia que todos os nodos dos quais n depende já estão na lista de saída L: eles foram adicionados a L tanto pela chamada recursiva anterior à visite(), ou por uma chamada anterior à visite(). Uma vez que cada aresta e nodo é visitado uma vez, o algoritmo executa em tempo linear. Note que o simples pseudocódigo acima não consegue detectar o caso de erro, onde o grafo de entrada contém ciclos. O algoritmo pode ser refinado para detectar os ciclos, observando nodos que são visitados mais de uma vez durante toda a seqüência de chamadas recursivas aninhadas à visite() (por exemplo, passar uma lista adiante como um argumento extra para visite(), indicando que nodos já foram visitados na pilha de chamada corrente).
Este algoritmo de busca em profundidade é o descrito por Cormen, Leiserson, Rivest e Stein;[4] parece ter sido descrito pela primeira vez em artigo por Tarjan[5]
Unicidade
[editar | editar código-fonte]Se uma ordenação topológica tem a propriedade de todos os pares de vértices consecutivos na ordem de classificação serem conectados por arestas, essas arestas formam um caminho hamiltoniano dirigido no DAG. Se existe um caminho Hamiltoniano, a ordenação topológica é única, nenhuma outra ordem respeita as arestas caminho. Inversamente, se uma ordenação topológica não formar um caminho Hamiltoniano, o DAG terá duas ou mais ordenações topológicas válidas, porque neste caso, é sempre possível formar-se uma segunda ordenação válida ao se trocar dois vértices consecutivos, que não são ligados por uma aresta, uns com os outros. Portanto, é possível testar em tempo polinomial se existe uma única ordenação, e se existe um caminho hamiltoniano, apesar da característica NP-hard do problema do caminho hamiltoniano para grafos dirigidos mais gerais[6]
Ver também
[editar | editar código-fonte]Ligações externas
[editar | editar código-fonte]Referências
- ↑ Markenzon, Lilian; Szwarcfiter, Jayme Luiz (1997). Estruturas de Dados e seus Algoritmos. Rio de Janeiro: LTC. ISBN 85-2161-014-9
- ↑ Jarnagin, M. P. (1960), Automatic machine methods of testing PERT networks for consistency, Technical Memorandum No. K-24/60, Dahlgren, Virginia: U. S. Naval Weapons Laboratory.
- ↑ *Kahn, A. B. (1962), «Topological sorting of large networks», Communications of the ACM, 5 (11): 558–562, doi:10.1145/368996.369025.
- ↑ CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST Ronald L.; STEIN, Clifford (2001). «Topological sort( seção 22.4)». Introduction to Algorithms 2ª ed. [S.l.]: MIT Press/McGraw-Hill. pp. 549–552. ISBN 0-262-03293-7
- ↑ Tarjan, Robert E. (1976), «Edge-disjoint spanning trees and depth-first search», Algorithmica, 6 (2): 171–185, doi:10.1007/BF00268499.
- ↑ Vernet, Oswaldo; Markenzon, Lilian (1997), «Hamiltonian problems for reducible flowgraphs», Proc. 17th International Conference of the Chilean Computer Science Society (SCCC '97), pp. 264–267, doi:10.1109/SCCC.1997.637099.