| 1. Motivação.
Grafos são entidades algébricas
utilizadas na modelagem e solução
por computador de inúmeros problemas,
em especial aqueles em que sistemas de relações
estejam envolvidos. Embora definidos em termos
algébricos, grafos admitem uma representação
geométrica através de pontos (vértices)
e linhas (arestas) desenhados sobre uma superfície,
normalmente um plano. Esta representação
visual não apenas facilita a percepção
das relações expressas, mas também
dá origem a novos problemas de cunho
puramente geométrico.
Este aspecto pictórico é tão
proeminente que, quem esteja a elaborar um algoritmo
que processe grafos, irá decerto concebê-lo
tendo em mente as representações
geométricas. O tratamento computacional,
no entanto, distancia-se em muito desta abordagem
visual, em particular nos seguintes pontos:
· A descrição
em alto nível dos algoritmos utiliza
sentenças específicas, como: “Para
todos os vizinhos do vértice v, efetue...”;
ou ainda: “Inicialize peso(v) = 0, para
todo vértice v”. Estas sentenças
devem ser traduzidas em comandos da linguagem
de programação eleita para a implementação,
obscurecendo as idéias essenciais do
algoritmo.
· A geração
manual ou automática de grafos para servirem
de entrada a programas obriga a conversões
tediosas, porquanto as representações
geométrica e em memória principal
em nada se assemelham. O mesmo se dá
no momento de analisar os resultados finais,
após a execução do programa,
quando informações numéricas
precisam ser interpretadas no contexto original
do grafo que foi processado.
· A abordagem
tradicionalmente usada para depuração
– monitorar continuamente valores das
variáveis do programa – torna-se
inviável quando o algoritmo em questão
possui certo grau de complexidade.
Um ambiente para programação
em grafos procura minimizar os inconvenientes
ocasionados por esta discrepância entre
o apelo visual e o tratamento computacional.
A disponibilidade de uma biblioteca de funções
que manipulem grafos auxilia a tarefa do programador,
permitindo que este se despreocupe da manutenção
de estruturas específicas para o armazenamento
de dados. Esta biblioteca deve prover recursos
para leitura/escrita de grafos, além
de permitir a associação de atributos
(rótulos) aos vértices e arestas
do grafo, indispensáveis a aplicações
reais. É fundamental poder trabalhar
com a representação geométrica
durante algumas etapas da implementação,
principalmente entrada, saída e depuração;
facilidades para edição de grafos
e animação de algoritmos vêm
de encontro a esta necessidade. O desafio maior,
no entanto, permanece: resolver estes problemas
de forma integrada e confortável ao usuário.
O ambiente KineGraph auxilia a implementação
de algoritmos em grafos em todas as etapas,
destinando-se a programadores C que necessitem
de uma maneira simples, rápida e eficiente
de tratar grafos em seus programas. Em sua versão
atual, foi desenvolvido integralmente na linguagem
de programação ANSI C e pode ser
instalado em plataformas de filosofia Unix,
como Linux e Solaris, em que a interface gráfica
X-Window esteja disponível. Dois módulos
integram o ambiente:
· A bibioteca KineLib, que provê
um conjunto de funções que permitem
manipular grafos em memória. Estas funções
estão divididas em cinco grupos:
- Grupo A: criação de grafos,
vértices e arestas; leitura/escrita de
grafos de/em arquivos;
- Grupo B: percursos;
- Grupo C: relações de incidência
e adjacência;
- Grupo D: manipulação de atributos;
- Grupo E: manipulação de subgrafos.
· O aplicativo KineGed, um editor
gráfico com facilidades específicas
para edição de grafos.
2. Histórico.
A primeira versão do ambiente KineGraph
data de 1991. Escrita em Turbo Pascal 6.0, executava
sobre o sistema operacional DOS e constava de
três módulos: uma biblioteca básica
de funções, um construtor de grafos
e uma biblioteca de funções para
animação. A aplicação
a que visamos na época foi o traçado
automático de grafos [4,9], uma área
então emergente de pesquisa, hoje consolidada,
que se ocupa em produzir bons desenhos para
um grafo, segundo critérios estéticos
diversos, além de procurar responder
a diversas indagações teóricas
sobre tais desenhos.
A principal característica do ambiente
era a forte integração entre os
seus módulos. Assim, um grafo editado
através do construtor era armazenado
em um arquivo e servia de entrada a programas
que utilizassem as funções da
biblioteca básica. Através delas,
o programador podia explorar o sistema de relações
expresso, bem como alterar informações
associadas aos vértices e arestas (atributos).
Com o uso da biblioteca de animação,
essas modificações eram visualizadas
diretamente sobre a imagem do grafo desenhada
na tela, mediante variações gráficas
convencionadas pelo programador e exibidas sucessivamente,
como em um desenho animado. O produto final
– um grafo possivelmente modificado pelo
programa – podia ser escrito em um arquivo
para posterior processamento ou exame.
O ambiente KineGraph mostrou-se, de
pronto, aplicável a outras áreas
de pesquisa, como o planejamento de redes de
energia elétrica [5], bem como ao ensino,
em disciplinas de graduação e
pós-graduação que objetivam
a construção de algoritmos em
grafos [2,8].
Seguiram-se as versões 2.0 (1993) e
3.0 (1998) [3,6,7], igualmente implementadas
em Turbo Pascal sobre DOS, em que os módulos
foram revistos com agregação de
novas facilidades, sem que, no entanto, a funcionalidade
e integração originais tenham
sido afetadas.
3. Estado Atual e Etapas Futuras.
Em 2003, iniciou-se uma completa revisão
do ambiente KineGraph, que deu origem à
versão 4.0. Dentre as principais motivações
para empreender tal processo de reestruturação,
podemos destacar:
· Tendo sido
as versões anteriores escritas em Turbo
Pascal para executarem exclusivamente em PCs
sobre o sistema operacional DOS, o ambiente
tornou-se rapidamente obsoleto e necessitou
sofrer abrangente revisão, objetivando
principalmente a portabilidade.
· A recente disponibilidade
de sistemas operacionais de filosofia Unix para
PCs sugeriu-nos o transporte para essas plataformas,
em que a portabilidade é facilmente assegurada
através dos padrões ANSI C e X-Window,
amplamente aceitos.
· Embora nenhuma
limitação houvesse quanto ao tamanho
dos grafos manipulados, não existia a
preocupação em suportar grafos
gigantes, o que constitui uma demanda atual
em diversas áreas de aplicação.
A revisão teve em conta esta necessidade
e, atualmente, é possível tratar
grafos com milhões de vértices
e arestas.
Em sua versão 4.1 atual, o ambiente
KineGraph encontra-se disponível
apenas para plataformas Unix, tendo sido testado
nos sistemas operacionais Linux e Tropix. A
implementação consta, por enquanto,
apenas dos dois módulos já citados:
a biblioteca básica de funções
KineLib e o construtor de grafos KineGed.
O manual do usuário, bem como os programas-fonte,
encontram-se disponíveis para download
na home page do projeto [1].
No presente momento, a biblioteca de animação
sofre (ou deleita-se com) uma completa reconcepção,
procurando tirar proveito de facilidades como
comunicação entre processos e
memória compartilhada disponíveis
em plataformas Unix. Planejamos também,
para o futuro, uma versão para Windows.
4. Bibliografia do Projeto.
[1] Markenzon, L., Vernet, O., KineGraph Version
4.1 – User’s Guide, disponível
na home page do Projeto (http://kinegraph.nce.ufrj.br),
fevereiro de 2005.
[2] Markenzon, L., Vernet, O., Teaching Graphs
with Real-Life Problems, Proceedings of the
ICECE’99 (International Conference on
Engineering and Computer Education), pp. 104-107,
Rio de Janeiro, RJ, agosto de 1999.
[3] Markenzon, L., Vernet, O., The Design and
Implementation of Graph Algorithms, Proceedings
of the IV JCIS’98 (Joint Conference on
Information Sciences), vol. III, pp. 138-141,
Research Triangle Park, North Carolina, USA,
outubro de 1998.
[4] Markenzon, L., Vernet, O., Nowosad, M. G.,
Traçado Automático de Árvores:
Critérios Estéticos e Algoritmos,
Anais do XXVI SBPO, pp. 461 a 466, Florianópolis,
SC, novembro de 1994.
[5] Markenzon, L., Vernet, O., Paciornik, N.,
Um Ambiente de Trabalho para Planejamento de
Redes de Energia Elétrica, Anais do XII
Seminário Nacional de Distribuição
de Energia Elétrica, Recife, PE, outubro
de 1994.
[6] Markenzon, L., Vernet, O., KineGraph: Um
Ambiente para Animar Algoritmos em Grafos, Anais
do XXV SBPO, pp. 391 a 395, Campinas, SP, novembro
de 1993.
[7] Markenzon, L., Vernet, O., KineGraph: A
Computer System for Graph Algorithm Animation,
Journées de l’Optimisation 1993,
Montréal, Canadá, maio de 1993.
[8] Markenzon, L., Vernet, O., O Uso de um Ambiente
no Ensino de Grafos, Anais do II EDUC, pp. 69
a 78, Rio de Janeiro, RJ, outubro de 1992.
[9] Markenzon, L., Vernet, O., Um Ambiente para
Implementação de Algoritmos de
Traçado Automático de Grafos,
Investigación Operativa, vol. 2, nº
2, pp. 147 a 158, dezembro de 1991.
|
