| |
| Acadêmico(a): Maicon Rafael Zatelli |
| Título: Um Framework para Algoritmos Baseados na Teoria dos Grafos |
| |
| Conclusão: |
Os resultados obtidos com o desenvolvimento do FGA foram considerados satisfatório, pois os requisitos propostos foram cumpridos, e, além disso, o FGA conta com uma série de outros recursos não mencionados inicialmente na proposta. O objetivo final do trabalho foi atingido, que é a disponibilização de um framework de algoritmos de grafos que contivesse desde algoritmos clássicos, funções de geração de grafos com base em restrições e por fim, verificação de propriedades.
Com a utilização do FGA foi possível comparar o desempenho dos algoritmos implementados. Foram feitas diversas baterias de testes com diferentes tipos de problemas a fim de verificar qual é a melhor situação para utilizar cada algoritmo.
Com o recurso de gerar grafos aleatórios foi possível criar instâncias de grafos com mais vértices e arestas. As instâncias geradas puderam ser facilmente verificadas se estão corretas utilizando o recurso de testar propriedades dos grafos.
Além disso, a persistência permite ao usuário salvar o grafo em que está trabalhando. Tal recurso facilita o transporte do grafo de um lugar para outro. Por ser um framework, é possível que o grafo possa ser persistido em outros formatos, já que para isso basta implementar a função de persistência para acessar os atributos de vértices e arestas. A biblioteca DOM apresentou grande importância na persistência do grafo, sendo que a partir dela é feito todo o controle de geração e recuperação de dados no modelo XML.
Como principal limitação do trabalho tem-se o fato de não haver uma maneira de ver a representação de um grafo na forma gráfica. No entanto, a aplicação de teste mostra de maneira simples o conjunto de vértices e arestas, tendo disponíveis funções para adicionar e remover os mesmos.
Outra limitação encontrada é o baixo desempenho da linguagem Java. Para instâncias grandes de grafos há uma demora demasiada tanto na geração de grafos como na execução de algum algoritmo sobre o grafo em questão. Cabe uma investigação mais profunda sobre este problema, podendo ser feita a comparação entre as implementações em Java e em Objective-C.
O grande consumo de memória também foi outro fator crítico enfrentado principalmente nos algoritmos de geração de grafos. Um exemplo é na geração de grafos densos de mais de 1000 vértices. Para que ele seja considerado denso é necessário que ele contivesse no mínimo 1000000 arestas. Tanto para arestas como vértices há atributos em questão, portanto este grafo pode consumir mais de 100Mb de memória.
Por fim, está aberto um horizonte para trabalhos futuros, desde implementação de novos algoritmos, verificação de outras propriedades, além de gerar um novo módulo para visualização gráfica dos grafos criados.
|
| |
|
