| |
| Acadêmico(a): Maicon Rafael Zatelli |
| Título: Um Framework para Algoritmos Baseados na Teoria dos Grafos |
| |
| Introdução: |
Grafo é um tipo de estrutura de dados utilizada para representar relacionamentos entre pares de objetos. Basicamente é formado por um conjunto de vértices e uma coleção de conexões entre pares de vértices, chamadas de arestas (GOODRICH; TAMASSIA, 2007, p. 508). Ao longo do tempo a teoria dos grafos evoluiu muito e diversos problemas práticos e teóricos podem ser reduzidos a um modelo de grafos, que, com o auxílio de teoremas e algoritmos, podem levar a conclusões e soluções acerca destas questões. Segundo Skiena e Revilla (2003, p. 237), a chave para solucionar problemas consiste em identificar o grafo fundamental oculto àquela situação e utilizar algoritmos clássicos para resolver a questão resultante.
Porém, há uma enorme gama de propriedades e algoritmos de grafos a serem estudados e implementados. Muitas implementações são simples, outras são mais complexas e podem demandar horas de pesquisa, especificação e desenvolvimento. Em termos de desenvolvimento de aplicações isso pode desviar o objetivo do desenvolvedor, que não é de realizar tais implementações, mas sim, por meio de um conhecimento prévio, apenas utilizar chamadas de funções de bibliotecas já prontas. Sendo assim, alguém que eventualmente sabe a aplicabilidade de determinado algoritmo envolvendo grafos pode não querer implementá-lo, mas sim apenas modelar o grafo, chamar a execução do algoritmo e trabalhar com a resposta fornecida. Hoje isto é possível graças a orientação a objetos, que tem como uma de suas características a reusabilidade de código, permitindo a integração de classes desenvolvidas por terceiros em uma aplicação.
Nesse momento aparece um outro desafio: a criação de casos de teste utilizando instâncias de grafos contendo muitos vértices e arestas, ou um tipo específico com base em algumas restrições. Muitas vezes é necessário gerar tais grafos a fim de testar mais profundamente a aplicação e avaliar seu desempenho e bom funcionamento.
Diante da falta de uma ferramenta que contemple todos estes requisitos, surge a ideia de desenvolver um framework de grafos, que permita gerar grafos mediante critérios, editar os existentes e que seja capaz de extrair diversas propriedades importantes e executar algoritmos clássicos. Além disso, faz-se necessário ter uma boa documentação, bem como uma aplicação exemplo para demonstrar a utilização dos recursos oferecidos pelo framework.
|
| |
|
