Detalhes dos Anais Veja o resumo do trabalho

Publicado no Encontro de Saberes 2015

Evento: XXIII Seminário de Iniciação Científica

Área: CIÊNCIAS EXATAS E DA TERRA

Subárea: Ciência da Computação

Título
DIAGRAMAÇÃO DE GRAFOS UTILIZANDO INTELIGÊNCIA COMPUTACIONAL
Autores
CEZAR AUGUSTO NASCIMENTO E SILVA (Autor)
HAROLDO GAMBINI SANTOS (Orientador)
Resumo
A diagramação de grafos é um tópico conhecido no contexto de Ciência da Computação, grafos são utilizados em várias áreas do conhecimento devido à sua versatilidade e eficiência em modelar relacionamentos, procedimentos e dependências, por exemplo: bancos de dados, engenharia de software, autômatos, diagramas UML e de fluxo. A capacidade de se desenhar um grafo claramente de forma inteligível a um ser humano é tão importante quanto a informação contida no mesmo, pois a qualidade estética do diagrama tem efeitos diretos sobre a compreensão do leitor. Neste trabalho propomos um novo algoritmo de 2 fases para desenhar grafos sobre uma grade quadrangular. Em uma primeira fase, o posicionamento dos nós é feito por procedimentos de busca local. Na segunda fase são decididos os pontos de conexão e as ligações são realizadas resolvendo-se problemas de caminhos mínimos. Nosso algoritmo foi testado para desenhar diagramas de Entidade-Relacionamento(ER), onde cada vértice representa uma tabela de banco de dados e arestas indicam referências a outras tabelas. Uma bateria de testes foi realizada com o desenho de diagramas ER oriundos de aplicações cujo modelo de dados encontra-se publicamente disponível. Para avaliar as soluções produzidas e comparar com diagramas desenhados por outros softwares, utilizamos critérios amplamente aceitos, como o cruzamento de arestas e sobreposições entre arestas e entidades no diagrama. Observamos que vários diagramas catalogados, a maioria deles produzida com o software GraphViz da AT&T, eram soluções claramente sub-ótimas mesmo em instâncias com poucos nós. Na versão atual nosso método já produz soluções significativamente melhores: obtivemos soluções com menos cruzamentos em 12 das 17 instâncias testadas sendo que em uma das demais 5, mantivemos a qualidade. Um ponto que ainda deve ser melhorado no método é o seu tempo de processamento.
Voltar Visualizar PDF