Algorithms + Data Structures = Programs

"Algorithms + Data Structures = Programs" é o nome de um livro de 1975 de Niklaus Wirth. Eu o li nos anos 80 (você pode ler também, "di gratís" baixando o PDF da página pessoal de Wirth no Swiss Federal Institute of Technology) e lembrei dele após algumas dificuldades em um exercício de curso de Algorítimos que estou seguindo.

Um grafo para teste (crédito: Gregor Ulm)

O curso de Algorítimos (que eu vou comentar com mais detalhes quando concluir) possui um exercício de programação para cada semana. O exercício da quarta semana diz respeito a grafos e tem como desafio adicional processar um grafo significativamente grande.

Sem entrar em detalhes na teoria (se quiser, veja as apresentações no curso), um grafo é composto por vértices (ou nós), interligados por arestas. No caso em questão, as arestas são direcionais, isto é, podem ser seguidos apenas em uma direção. O problema em estudo é encontrar no grafo conjuntos de nós fortemente conectados (isto é, de qualquer nó do conjunto é possível chegar a qualquer outro). A figura no início (feita por Gregor Ulm como caso de teste) resume visualmente o problema (cada cor indica um conjunto fortemente conectado).

Tradicionalmente, se usa n para indicar o número de nós e m o número de arestas. O curso apresenta o algorítimo de Kosaraju, que tem o potencial de ser extremamente rápido, com tempo proporcional à soma (n + m). E precisa mesmo ser rápido, pois o grafo a ser analisado tem quase 9000 mil nós e um pouco mais de 5 milhões de arestas. O algorítimo envolve analisar recursivamente todas as arestas que saem de cada nó (novamente, detalhes no material do curso). O arquivo de entrada possui uma linha para cada aresta, contendo o número do nó origem e do nó destino.

Comecei fazendo uma implementação direta do algorítimo (até agora estou resolvendo os problemas com C puro, sem nenhuma biblioteca especial). A estrutura para para representar o grafo foi uma imagem direta da entrada: um vetor com cada posição contendo a origem e destino de uma aresta. Após alguma briga, o programa processou com sucesso os casos de testes. Não conseguiu, entretanto, processar o grafo do exercício.

Lista de arestas do grafo

O meu passo seguinte foi retirar a chamada recursiva. No ponto em que era feita esta chamada, passei a salvar o contexto (que eram apenas duas variáveis) em uma pilha e prosseguir com os valores da nova chamada. Ao final do processamento de uma chamada, o contexto no alto da pilha é retirado e o processamento do contexto anterior prossegue (neste caso corresponde exatamente ao "backtracking" na análise das arestas). Quando a pilha fica vazia acabou o processamento. Esta mexida exigiu pensar um pouco mas não foi muito trabalhosa.

O processamento continuou muito lento. Em umas "contas de padaria" estimei umas 2 ou 3 horas de processamento no meu fiel Pentinum 4 2.8 HT. Foi quando me dei conta da bobagem que eu estava fazendo. Para processar as arestas de um nó eu examinava todas as arestas, portanto o meu processamento era proporcional a (n * m), não a (n + m).

Hora de mudar de estrutura de dados para representar o grafo. A nova estrutura consiste em um vetor onde os índices são os nós de origem e cada elemento é uma lista ligada de nós destino. Este mexida foi mais trabalhosa que a anterior, mas deu menos trabalho para debugar do que eu esperava.

Mesmo grafo, outra estrutura

Aí veio a hora da verdade: processar o grafo do exercício. Surpresa total: o processamento caiu para menos de 1 segundo (e os resultados estavam corretos)!

Obs: Além do exercício de programação, toda semana tem também uma provinha. Normalmente eu faço primeiro a prova e depois o exercício, mas desta vez resolvi fazer o contrário. Qual não foi minha surpresa ao ver que uma das questões era sobre a desvantagem de usar uma outra representação para o grafo. Se eu tivesse feito a prova primeiro, provavelmente teria percebido que ia usar uma estrutura inadequada.