(This page in english.)

(Clique aqui para uma breve introdução sobre o problema do teste de planaridade e seus principais algoritmos.)

Código fonte da implementação do algoritmo de Shih e Hsu

Recentemente, Shih e Hsu (SH) publicaram uma nova implementação do algoritmo de Lempel, Even e Cederbaum (LEC) que decide se um dado grafo é planar em tempo linear no número de vértices do grafo dado.

Desenvolvemos uma versão da implementação de SH sobre a plataforma LEDA. Ela foi testada na versão 4.4 do LEDA num PC com sistema GNU/Linux.

Para compilar o código fonte, é necessário possuir o LEDA instalado no seu sistema, além de um compilador C++.

A versão mais recente do LEDA (evaluation) pode ser obtida no endereço http://www.algorithmic-solutions.com/.

Clique aqui para obter o pacote compactado do código fonte da implementação de SH (arquivo 'planarity.tar.gz').

Para descompactar o arquivo no diretório ``meudir/'', utilize o comando

 meu_prompt> tar -zxvpf planarity.tar.gz -C meudir/

Após a descompactação, o diretório ``meudir/planarity/'' é criado. Dentro dele, estão os fontes da implementação de SH. Para obter os fontes da implementação de Boyer e Myrvold, entre em contato com John M. Boyer ou siga para https://github.com/graph-algorithms/edge-addition-planarity-suite.

Para compilar os programas ``planarity_time'' e ``sh_planar'', execute:

 meu_prompt> make


planarity_time. Este programa imprime na saída padrão uma tabela de comparação de tempos em formato LATEX, entre BM e SH e as duas implementações presentes na biblioteca do LEDA: Uma implementação de Booth e Lueker (BL) para o algoritmo de LEC e uma implementação de Hopcroft e Tarjan (HT) para o algoritmo de Auslander, Parter e Goldstein.

O programa pode ser rodado sobre grafos específicos ou sobre grafos aleatórios. Sobre grafos aleatórios, o programa testa as implementações sobre cinco tipos de grafos (conf. descritos no livro do LEDA [1]):

Após executar o programa ``planarity_time'', aparece a seguinte mensagem na tela

Please, type 1 for embedding:
Digite 1 para que o programa calcule uma justificativa para cada grafo testado (uma descrição combinatória plana se o grafo é planar; um subgrafo de Kuratowski, caso contrário), ou outro valor, caso contrário.

Após confirmar com ENTER, aparece a seguinte mensagem na tela

Please, specify a graph (gw file) or just press ENTER =
Digite o nome do arquivo que contém um grafo (arquivo gw) se deseja rodar o programa sobre um grafo específico, ou apenas tecle ENTER se deseja criar uma tabela de tempos com grafos gerados aleatoriamente.

Se nenhum grafo foi especificado ou o arquivo especificado é inválido, aparece a seguinte mensagem na tela

Random graphs selected...
number of nodes =
Digite o número de vértices inicial para a geração dos grafos aleatórios.

Após confirmar com ENTER, aparece a seguinte mensagem na tela

number of lines =
Digite o número de linhas na tabela para cada tipo de grafo usado nos testes. (Para cada tipo de grafo, grafos aleatórios são gerados em cada linha na tabela, duplicando o número de vértices na linha seguinte).

Após confirmar com ENTER, aparece a seguinte mensagem na tela

number of graphs per line =
Digite o número total de grafos a serem gerados em cada linha da tabela para cada tipo de grafo. (O tempo médio é impresso para cada linha da tabela.)


sh_planar. Este programa serve para depurar a implementação de SH. Ele roda tanto para grafos aleatórios quanto para grafos especificados na linha de comando. Para ver os detalhes da execução do programa, ativa-se o modo ``DEBUG'', conforme descrito no arquivo ``README'' contido no pacote ``planarity.tar.gz''.

Por exemplo, para testar a implementação de SH com grafos aleatórios e cálculo de justificativa, execute

 meu_prompt> ./sh_planar 1
Para mostrar a ajuda do programa, execute
 meu_prompt> ./sh_planar


Código fonte da dissertação

Para compilar a dissertação, é necessário possuir o LEDA (o diretório ".../LEDA-X.X/Manual/cmd/" deverá estar no PATH), o LATEX e o ``noweb'' (uma ferramenta para literate programming) devidamente instalados no seu sistema.

A versão mais recente do LEDA (evaluation) pode ser obtida no endereço http://www.algorithmic-solutions.com/

e o ``noweb'' em http://www.eecs.harvard.edu/~nr/noweb/.

Clique aqui para obter o pacote compactado da dissertação (arquivo 'dissertation.tar.gz').

Para descompactar o arquivo no diretório ``meudir/'', utilize o comando

 meu_prompt> tar -zxvpf dissertation.tar.gz -C meudir/

Após a descompactação, o diretório ``meudir/dissertation/'' é criado.

Para compilar a dissertação, execute

 meu_prompt> ./mkdissertation
O arquivo "dissertation.ps.gz" é criado.

Referências Bibliográficas

1
K. Mehlhorn e St. Näher, The LEDA Platform of Combinatorial and Geometric Computing, Cambridge University Press, 1999.


Envie suas dúvidas e sugestões para noma@ime.usp.br.