Numeração topológica

Este capítulo está intimamente relacionado com o anterior: encontrar uma numeração topológica é essencialmente o mesmo que decidir se um grafo é acíclico.

Numeração topológica

Uma numeração topológica (= ordenação topológica = topological order) dos vértices de um grafo é uma atribuição de um número t a cada vértice v de tal modo que

v–>t > w–>t para cada arco (v,w).

Se dois vértices não são adjacentes, não há mal em permitir que recebam o mesmo número. Mas usualmente vértices diferentes recebem números diferentes, todos no intervalo 1..n, onde n é o número de vértices do grafo.

Se um grafo tem uma numeração topológica então ele é acíclico; isto é evidente. A recíproca é menos óbvia mas não menos verdadeira.

Para que serve uma numeração topológica? Se os vértices de seu grafo são tarefas e um arco (v,w) significa que a tarefa v deve ser executada antes da tarefa w, então uma numeração topológica dá uma programação seqüencial das tarefas (a primeira tarefa a ser executada é a tiver o maior número).

Eis outra aplicação: Suponha que você foi incumbido de encontrar um ciclo em um grafo. Depois de uma noite de trabalho frustrante, você está convencido de que o grafo não tem ciclo algum. Como você pode convencer o seu chefe, no dia seguinte, de que o grafo não tem ciclos? Resposta: basta exibir uma numeração topológica dos vértices. O seu chefe terá um pouco de trabalho braçal para verificar que a numeração é de fato topológica, mas depois disso estará convencido de que não há ciclos. [A coisa também pode ser entendida ao contrário. Se o seu chefe quer uma numeração topológica e você precisa convencê-lo de que tal numeração não existe, basta exibir um ciclo.]

Exercícios

Suponha que f é uma atribuição de números aos vértices tal que v–>f < w–>f para cada arco (v,w). Transforme f em numeração topológica.
Suponha que f é uma atribuição de números aos vértices tal que v–>f > w–>f para cada arco (v,w). É possível garantir que o grafo tem uma numeração topológica?
Suponha que x[0], x[1], . . . , x[n] é uma seqüência de vértices em que cada vértice aparece uma e uma só vez tal que para todo arco (x[i],x[j]) tem-se i > j. Obtenha uma numeração topológica dos vértices do grafo.
Suponha que cada vértice v de um grafo g tem um número v–>t (o campo t é um utility field). Escreva uma função que receba g e devolva 1 se a numeração dos vértices for topológica e 0 em caso contrário.
Prove, por indução no número de vértices, que todo grafo acíclico tem uma numeração topológica. Comece mostrando que todo grafo acíclico tem pelo menos um sorvedouro.
Suponha que um grafo tem vértices 1, 2, . . . , n e que não existem arcos da forma (i,j) com i < j. Mostre que a matriz de adjacências do grafo é triangular inferior (ou seja, só tem zeros acima da diagonal).

Um algoritmo simples: eliminação de sorvedouros

Eis o esboço de um algoritmo simples de numeração topológica. Para descrever o algoritmo, diremos que um vértice v é branco se v–>t == –1 e preto em caso contrário. Diremos também que o grau de saída branco de um vértice v é o número de arcos da forma (v,w) tais que w é branco.

enquanto o grafo tem sorvedouros brancos
escolha um vértice v cujo grau de saída branco seja 0
faça v–>t = k
faça k = k+1
se todos os vértices são pretos
então t é uma numeração topológica
senão o grafo tem um ciclo

Uma implementação descuidada do algoritmo pode ser muito ineficiente. Uma implementação inteligente pode ser bastante eficiente (mas o algoritmo da próxima seção é ainda melhor). O algoritmo tem um defeito: ele não devolve um ciclo explicitamente se tal existir. (Mas veja o exercício do grafo sem sorvedouros no capítulo anterior.)

Exercícios

Mostre que no início de cada iteração do algoritmo acima o conjunto dos vértices pretos é um sorvedouro acíclico.
Implemente o algoritmo acima usando as estruturas de dados do SGB. Ao receber um grafo, sua função deve devolver 0 se o grafo tem uma numeração topológica ou 1 em caso contrário. No primeiro caso, a função deve gravar uma numeração topológica em um utility field. [Sugestão: Use um utility field para armazenar o grau de saída branco de cada vértice.]
Faça uma versão mais completa, que produza um ciclo z, z–>próx, z–>próx–>prox, . . . , z no segundo caso.

Um algoritmo sofisticado: busca em profundidade

Nosso algoritmo definitivo é muito eficiente e faz um serviço completo. A função num_topológica que implementa o algoritmo é um aperfeiçoamento da função temciclo. Ela recebe um grafo g e devolve 0 se g admite uma numeração topológica e 1 em caso contrário. No primeiro caso, a função grava a numeração topológica no utility field t de cada vértice (os números são 1, . . , g–>n). No segundo caso, ela usa o mesmo utility field t para marcar com CINZA os vértices de um "6" (que contém um ciclo).

#define BRANCO –1
#define CINZA  0
#define t   u.I

Não há PRETO explícito, mas você pode imaginar que são PRETOs todo os vértices que têm t > 1.

int num_topológica (Graph* g) {
   Vertex* v0 = g–>vertices, * vn = g–>vertices+g–>n;
   for (v = v0; v < vn; v++)   
      v–>t = BRANCO;
   for (y = v0; y < vn; y++) {
      if (y–>t >= 1) continue;
      y–>t = CINZA;
      if (dfs(y) == 1) return 1;
   }
   return 0;
}

(É claro que falta declarar as variáveis v e y.) A função dfs, que é o coração do algoritmo, é quase igual à do capítulo anterior; ela faz uma busca em profundidade a partir do vértice y e marca com CINZA todos os vértices encontrados. A variável estática k é inicializada apenas na primeira execução de dfs e incrementada a cada execução subseqüente; ela administra a numeração topológica.

int dfs (Vertex* y) {
   static int k = 1;
   for (a = y–>arcs; a != NULL; a = a–>next) {
      z = a–>tip;
      if (z–>t >= 1) continue;
      if (z–>t == CINZA) return 1; 
      z–>t = CINZA;
      if (dfs(z) == 1) return 1;
   }
   y–>t = k++;
   return 0;
}

Exercícios

Por que não trocar o corpo da função num_topológica pelo que está abaixo?

   for (v = v0; v < vn; v++)   
      v–>t = BRANCO;
   v0–>t = CINZA;
   if (dfs(v0) == 1) return 1;
   return 0;

Mostre que ao longo da execução dos algoritmos num_topológica e dfs o conjuntos dos vértices PRETOs é um sorvedouro acíclico.
Considere a função num_topológica. Mostre que não há vertices CINZA no início de cada uma das iterações do for controlado por y.
Diga o que, exatamente, a função dfs faz.
Escreva uma versão iterativa da função dfs.
Escreva uma versão mais completa da função num_topológica: ela deve devolver o vértice z de um ciclo ou NULL se o grafo for acíclico. No primeiro caso, o ciclo será z, z–>prox, z–>prox–>prox, . . . , z, onde prox é um utility field. No segundo caso, a numeração topológica é dada por um utility field t.
Escreva uma versão da função num_topológica que decida se o grafo é acíclico e em caso afirmativo imprima uma matriz de adjacências do grafo com vértices ordenados de tal forma que a matriz seja triangular inferior (ou seja, só zeros acima da diagonal).
Prove o seguinte teorema: Todo grafo tem um ciclo ou uma numeração topológica; e nunhum grafo tem ambos.
[Bom!] Escreva uma variante da função num_topológica que ignora os ciclos de comprimento 1 e 2.
Implemente a função temciclo e aplique-a aos grafos
```
               board(8,8,0,0,1,0,1)
               board(8,8,0,0,1,-1,1)
                econ(79,2,100,0)
```
Para saber se sua implementação é realmente eficiente, aplique-a aos grafos
```
              binary(10,5,1)
       partial_gates(prod(20,80),20,0,0,NULL)
           all_trees(10,1)
```
(Você precisa incluir gb_econ.h para usar econ, gb_gates.h para usar partial_gates e gb_basic.h para usar qualquer uma das demais.)

Mais exercícios

Desafio: Dado um grafo arbitrário, encontrar uma numeração tão próxima quanto possível da topológica, ou seja, uma numeração t tal que v–>t > w–>t para o maior número possível de arcos (v,w). Este problema é conhecido como minimum feedback arc set. O módulo ECON_ORDER do SGB tenta resolver um problema ligeiramente mais geral no grafo da economia americana gerado pela função econ. [Um bom exercício preliminar: Retire do código de ECON_ORDER as peculiaridades de econ, deixando somente uma função que recebe um grafo g arbitrário e tenta calcular uma numeração t dos vértices que maximize o número de arcos (v,w) para os quais v–>t > w–>t.]
Escreva um algoritmo para encontrar um caminho de comprimento máximo em um grafo acíclico. Suponha que uma numeração topológica dos vértices é dada. (O módulo FOOTBALL do SGB tenta resolver o problema num grafo arbitrário.)
Suponha que cada arco a de um grafo acíclico tem um peso a–>len que pode ser negativo. Encontrar um caminho de peso mínimo de um vértice dado r a um vértice dado s. Compare com o algoritmo de Dijkstra. Qual a relação desse problema com o anterior (caminho de comprimento máximo)?