(This page in english.)
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/.
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 1Para mostrar a ajuda do programa, execute
meu_prompt> ./sh_planar
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> ./mkdissertationO arquivo "dissertation.ps.gz" é criado.