Ordenação topológica

Sempre que instala software, compila um programa ou planeia um projeto, algo tem de descobrir o que fazer primeiro. Se a tarefa B precisa da tarefa A, A tem de vir antes. Uma ordenação topológica transforma uma teia de regras assim numa única linha reta.

Um grafo de nós ligados por setas de sentido único, os nós colocados a verde e a ordem até agora desenhada como uma fila por baixo
Um grafo de nós ligados por setas de sentido único, os nós colocados a verde e a ordem até agora desenhada como uma fila por baixo

A ideia

Desenhe cada tarefa como um nó e cada regra «A antes de B» como uma seta de A para B. Uma ordem topológica é uma fila com todos os nós em que cada seta aponta para a direita. Chama-se ordenação porque põe as coisas por ordem, mas, ao contrário de ordenar números, só tem de respeitar as setas: os nós que nenhuma cadeia de setas liga podem vir por qualquer ordem.

Quando é impossível

Se as setas formam um ciclo, por exemplo A antes de B, B antes de C e C antes de A, então A teria de vir antes de si próprio. Por isso, uma ordem topológica existe exatamente quando o grafo não tem ciclos dirigidos. Um grafo assim chama-se grafo acíclico dirigido, ou DAG. Os dois métodos abaixo encontram um ciclo se houver um, o que também os torna um teste de ciclos prático.

Um exemplo

Tome as setas A → C, B → C, B → D, C → E e D → E. O algoritmo de Kahn conta as setas de entrada: A e B não têm nenhuma, por isso A vai primeiro, depois B. Remover as setas de B liberta C e D, que se seguem, e depois E: a ordem A, B, C, D, E. O método DFS visita A, depois C, depois E; E fica concluído primeiro, depois C, depois A, e cada um vai para o início. Depois visita B e D, que ficam concluídos e vão para a frente deles: a ordem B, D, A, C, E. Ambas as ordens estão certas.

Kahn ou DFS?

O algoritmo de Kahn, publicado por Arthur Kahn em 1962, trabalha para a frente: sabe sempre que tarefas podem começar agora, o que convém ao escalonamento, e pode escolher entre as tarefas livres com qualquer regra, como a ordem alfabética. O método DFS, popularizado por Robert Tarjan em 1976, trabalha para trás a partir das pontas e só precisa de uma pesquisa em profundidade. Ambos levam um tempo que cresce com o número de nós mais arestas.

Robert Tarjan, que com John Hopcroft mostrou em 1972–73 que a pesquisa em profundidade resolve muitos problemas de grafos em tempo linear; receberam o prémio Turing de 1986 em parte por esse trabalho.
Robert Tarjan, que com John Hopcroft mostrou em 1972–73 que a pesquisa em profundidade resolve muitos problemas de grafos em tempo linear; receberam o prémio Turing de 1986 em parte por esse trabalho.

Aplicações

Ferramentas de compilação como o make compilam os ficheiros depois dos ficheiros de que dependem. Os gestores de pacotes instalam as bibliotecas pela ordem das dependências. As folhas de cálculo recalculam uma célula depois das células que a sua fórmula usa. As universidades verificam se os pré-requisitos das disciplinas podem ser cumpridos, os compiladores ordenam instruções e os pipelines de dados executam cada passo quando as suas entradas estão prontas. O comando Unix tsort faz sozinho uma ordenação topológica.

Experimente

Abra a aplicação e prima Avançar. As setas dizem que nó tem de vir antes de qual. Com o algoritmo de Kahn, o número em cada nó conta as setas de entrada que lhe restam, e os nós livres são azuis. Com o método DFS, os nós azuis estão em visita e os verdes estão colocados. A ordem cresce na fila por baixo do grafo. Marque Adicionar um ciclo e veja ambos os métodos descobrirem que não existe nenhuma ordem.

Perguntas frequentes

O que quer dizer topológico aqui?

O nome vem da topologia, o estudo de como as coisas estão ligadas e não da sua forma exata. A ordem só depende de que nós estão ligados por setas, não de onde estão desenhados.

Como encontro o ciclo quando não há ordem?

O método DFS mostra-o diretamente: a aresta para um nó ainda em visita, junto com o caminho dos nós em visita, é o ciclo. O algoritmo de Kahn só diz que nós estão presos; uma pesquisa entre eles encontra o ciclo.

Posso escolher uma ordem concreta entre as válidas?

Sim. No algoritmo de Kahn, quando há vários nós livres, escolha o que preferir, por exemplo a letra mais baixa ou a tarefa mais urgente. Usar uma fila de prioridade dá a ordem que vem primeiro alfabeticamente.

Como se usa a ordenação topológica com caminhos mais curtos?

Num grafo acíclico dirigido, relaxar as arestas de cada nó pela ordem topológica encontra todos os caminhos mais curtos a partir de uma origem numa só passagem, mesmo com arestas negativas, mais depressa do que Dijkstra ou Bellman–Ford.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Experimentar a ordenação topológica