Universidade regional de blumenau



Baixar 1,07 Mb.
Página1/12
Encontro01.07.2018
Tamanho1,07 Mb.
  1   2   3   4   5   6   7   8   9   ...   12


UNIVERSIDADE REGIONAL DE BLUMENAU

CENTRO DE CIÊNCIAS EXATAS E NATURAIS

CURsO DE CIÊNCIA DA COMPUTAÇÃO – BACHARELADO

UM FRAMEWORK PARA ALGORITMOS BASEADOS NA TEORIA DOS GRAFOS

maicon rafael zatelli

bLUMENAU

2010

2010/2-20

maicon rafael zatelli

UM FRAMEWORK PARA ALGORITMOS BASEADOS NA TEORIA DOS GRAFOS

Trabalho de Conclusão de Curso submetido à Universidade Regional de Blumenau para a obtenção dos créditos na disciplina Trabalho de Conclusão de Curso II do curso de Ciência da Computação — Bacharelado.

Prof. Paulo César Rodacki Gomes, Dr. – Orientador


bLUMENAU

2010

2010/2-20

UM FRAMEWORK PARA ALGORITMOS BASEADOS NA TEORIA DOS GRAFOS

Por


maicon rafael zatelli

Trabalho aprovado para obtenção dos créditos na disciplina de Trabalho de Conclusão de Curso II, pela banca examinadora formada por:



______________________________________________________

Presidente: Prof. Paulo César Rodacki Gomes, Dr. – Orientador, FURB



______________________________________________________

Membro: Prof. Antônio Carlos Tavares, Esp. – FURB



______________________________________________________

Membro: Prof. Roberto Heinzle, Ms. – FURB



Blumenau, 08 de dezembro de 2010

Dedico este trabalho a todos os amigos, especialmente aqueles que me ajudaram diretamente na realização deste.

AGRADECIMENTOS

A Deus, pelo seu imenso amor e graça.

À minha família, pelo apoio de sempre.

À minha irmã, Gabriele Andressa Zatelli, pela ajuda para resolver alguns problemas com formatações.

Ao meu orientador, Paulo César Rodacki Gomes, por ter auxiliado na conclusão deste trabalho.

Ao professor José Roque Voltolini da Silva, pelo esclarecimento de diversas dúvidas durante o trabalho.


A coisa mais bela que podemos experimentar é o mistério. Essa é a fonte de toda a arte e ciências verdadeiras.

Albert Einstein



RESUMO

Este trabalho apresenta o desenvolvimento do FGA, um framework de algoritmos baseados na teoria dos grafos implementado na linguagem Java. O FGA disponibiliza uma série de verificações de propriedades de grafos, bem como um subconjunto de funções capazes de gerar grafos com base em certas características tais como grafos completos, bipartidos, regulares entre outros. Além disso, é disponibilizado um conjunto de classes para a execução e manipulação de resultados obtidos com algoritmos clássicos da teoria dos grafos. Tais algoritmos são úteis para modelar e resolver diversos problemas práticos e teóricos. Por fim, uma aplicação de exemplo é construída aproveitando todos os recursos oferecidos pelo FGA. Como item adicional do trabalho, o framework Java também foi portado para linguagem Objective-C.

Palavras-chave: Algoritmos. Estuturas de dados. Framework. Teoria dos grafos.

ABSTRACT

This work presents the development of FGA, a Java framework for algorithms based on graph theory concepts. The FGA provides features for inspections of graph properties and a set of functions for automatic graph construction based on certain characteristics such as complete graphs, bipartite graphs, regular graphs and others. The FGA also provides several classes for execution of classic graph theory algorithms which can be used to model and solve both practical and theoretical problems. Finally, an example application is developed using all the resources offered by the FGA. As an additional feature, the framework also has been ported from Java to Objective-C.

Key-words: Algorithms. Data structures. Framework. Graph theory.

LISTA DE ilustrações


Figura 1 – Exemplo de um grafo dirigido (a) e um grafo não dirigido (b) 18

Figura 1 – Exemplo de um grafo dirigido (a) e um grafo não dirigido (b) 18

Figura 2 – Exemplo de base (A e B) e antibase (F, G, H e I) 19

Figura 2 – Exemplo de base (A e B) e antibase (F, G, H e I) 19

Figura 3 – Exemplo de uma ponte (a) e três nós de articulação (b) 19

Figura 3 – Exemplo de uma ponte (a) e três nós de articulação (b) 19

Figura 4 – Exemplos de grafos 22

Figura 4 – Exemplos de grafos 22

Quadro 1 – Algoritmo busca em profundidade 23

Quadro 2 – Algoritmo busca em largura 24

Quadro 3 – Algoritmo ordenação topológica 25

Quadro 4 – Algoritmo de Dijkstra 26

Quadro 5 – Algoritmo de Floyd-Warshall 27

Quadro 6 – Algoritmo de Bellman-Ford 28

Figura 5 – Exemplo de um grafo e suas componentes fortemente conexas 28

Figura 5 – Exemplo de um grafo e suas componentes fortemente conexas 28

Quadro 7 – Algoritmo de Hopcroft-Tarjan 29

Quadro 8 – Algoritmo de Prim 30

Quadro 9 – Algoritmo de Kruskal 31

Quadro 10 – Algoritmo de Ford-Fulkerson 32

Figura 6 – Interface gráfica da ferramenta 33

Figura 6 – Interface gráfica da ferramenta 33

Quadro 11 – Exemplo de integração da biblioteca JgraphT e Jgraph 34

Figura 7 – Interface gráfica da ferramenta 35

Figura 7 – Interface gráfica da ferramenta 35

Quadro 12 – Comparação entre trabalhos correlatos 35

Figura 8 – Diagrama de casos de uso 37

Figura 8 – Diagrama de casos de uso 37

Quadro 13 – Caso de uso Criar grafo 38

Quadro 14 – Caso de uso Gerar grafo 38

Quadro 15 – Caso de uso Carregar grafo de arquivo 39

Quadro 16 – Caso de uso Salvar grafo em arquivo 39

Quadro 17 – Caso de uso Executar algoritmos 39

Quadro 18 – Caso de uso Testar propriedades 39

Figura 9 – Diagrama de pacotes 40

Figura 9 – Diagrama de pacotes 40

Figura 10 – Diagrama de classes resumido do pacote Base 41

Figura 10 – Diagrama de classes resumido do pacote Base 41

Figura 11 – Diagrama de classes detalhado do pacote Base 42

Figura 11 – Diagrama de classes detalhado do pacote Base 42

Figura 12 – Diagrama de classes detalhado do pacote Algoritmos 43

Figura 12 – Diagrama de classes detalhado do pacote Algoritmos 43

Figura 13 – Diagrama de classes resumido do pacote Algoritmos 44

Figura 13 – Diagrama de classes resumido do pacote Algoritmos 44

Figura 14 – Diagrama de classes do pacote Persistencia 44

Figura 14 – Diagrama de classes do pacote Persistencia 44

Figura 15 – Diagrama de classes do pacote GeradorGrafos 45

Figura 15 – Diagrama de classes do pacote GeradorGrafos 45

Figura 16 – Diagrama de classes do pacote Auxiliar 46

Figura 16 – Diagrama de classes do pacote Auxiliar 46

Figura 17 – Diagrama de atividades 47

Figura 17 – Diagrama de atividades 47

Figura 18 – Diagrama de sequência da operação salvar grafo 48

Figura 18 – Diagrama de sequência da operação salvar grafo 48

Figura 19 – Diagrama de sequência da operação executar algoritmo 49

Figura 19 – Diagrama de sequência da operação executar algoritmo 49

Figura 20 – Diagrama de sequência da operação testar propriedade 50

Figura 20 – Diagrama de sequência da operação testar propriedade 50

Quadro 19 – Exemplo de código com comentários para o Javadoc 52

Quadro 20 – Classe Grafo 53

Quadro 21 – Classe GrafoDirigido 54

Quadro 22 – Classe GrafoNaoDirigido 55

Quadro 23 – Métodos que testam propriedades de grafos 56

Quadro 24 – Classe Aresta 57

Quadro 25 – Classe ArestaDirigida 57

Quadro 26 – Classe ArestaNaoDirigida 58

Quadro 27 – Classe Vertice 58

Quadro 28 – Exemplo de um arquivo com um grafo 60

Quadro 29 – Método carregaGrafo 61

Quadro 30 – Método carregaGrafoDirigido 62

Quadro 31 – Método carregaGrafoNaoDirigido 63

Quadro 32 – Método persisteGrafo 64

Quadro 33 – Método geraXMLGrafo 64

Quadro 34 – Classe AlgoritmoBuscaProfundidade 66

Quadro 35 – Classe AlgoritmoBuscaProfundidadeResultado 67

Quadro 36 – Classe AlgoritmoPrim 69

Quadro 37 – Classe AlgoritmoPrimResultado 70

Quadro 38 – Método getGrafoCompletoDirigido 71

Quadro 39 – Método getGrafoCompletoNaoDirigido 72

Quadro 40 – Métodos getGrafoRegularNaoDirigido e getGrafoDesconexoDirigido 73

Figura 21 – Interface gráfica da aplicação de exemplo 74

Figura 21 – Interface gráfica da aplicação de exemplo 74

Quadro 41 – Método que exemplifica uso do algoritmo de ordenação topológica 74

Quadro 42 – Métodos que exemplificam uso da persistência de grafos 75

Quadro 43 – Métodos que exemplificam uso da geração de grafos e teste de propriedades 76

Quadro 44 – Classe VerticeGeometrico 77

Quadro 45 – Instanciação de um grafo não dirigido 77

Quadro 46 – Instanciação de vértices e arestas 78

Quadro 47 – Adicionar vértices e arestas em um grafo 79

Quadro 48 – Execução algoritmos de busca em profundidade e Kruskal 79

Quadro 49 – Desenho de arestas 80

Quadro 50 – Desenho de vértices 80

Quadro 51 – Teste de propriedades 81

Figura 22 – Visualização do grafo 82

Figura 22 – Visualização do grafo 82

Quadro 52 – Comparação entre trabalhos correlatos e o FGA 87

Quadro 53 – Arquivo AlgoritmoPrim.h 88

Quadro 54 – Arquivo AlgoritmoPrim.m 89

Quadro 55 – Arquivo AlgoritmoPrimResultado.h 90

Quadro 56 – Arquivo AlgoritmoPrimResultado.m 90

Quadro 57 – Execução do algoritmo de Prim 91


Lista de tabelas

Tabela 1 – Comparação entre o algoritmo de Dijkstra e busca em profundidade 83

Tabela 2 – Comparação entre algoritmos de busca 84

Tabela 3 – Comparação entre algoritmos de geração de árvore de custo mínimo 84

Tabela 4 – Comparação entre algoritmos de menor caminho em uma consulta 85

Tabela 5 – Comparação entre os algoritmos com várias consultas tendo mesma origem 85

Tabela 6 – Comparação entre os algoritmos com várias consultas tendo origens diferentes 86


LISTA DE SIGLAS

BFS – Breadth First Search

CSV – Comma-separated Values

DFS – Depth First Search

DOM – Document Object Model

FGA – Framework for Graph Algorithms

GB – GBytes

GHz – GigaHertz

HTML – HiperText Markup Language

RGB – Red Green Blue

UML – Unified Modeling Language

XML – eXtensible Markup Language

W3C – World Wide Web Consortium

SUMÁRIO


1 Introdução 18

1.1 OBJETIVOS DO TRABALHO 19

1.2 estrutura do trabalho 19

2 FUNDAMENTAÇÃO TEÓRICA 21

2.1 conceitos básicos da teoria DOS grafos 21

Fonte: adaptado de Gross e Yellen (2006, p. 2). 22

Figura 1 – Exemplo de um grafo dirigido (a) e um grafo não dirigido (b) 22

Fonte: adaptado da definição de Rabuske (1992, p. 32). 23

Figura 2 – Exemplo de base (A e B) e antibase (F, G, H e I) 23

Fonte: adaptado de Cormen et al. (2001, p. 559). 23

Figura 3 – Exemplo de uma ponte (a) e três nós de articulação (b) 23

2.2 Propriedades dos grafos 23

Figura 4 – Exemplos de grafos 26

2.3 Algoritmos clássicos de grafos 26

2.3.1 Busca em profundidade 27

Fonte: adaptado de Gross e Yellen (2006, p. 132). 27

Quadro 1 – Algoritmo busca em profundidade 27

2.3.2 Busca em largura 27

Fonte: adaptado de Gross e Yellen (2006, p. 134). 28

Quadro 2 – Algoritmo busca em largura 28

2.3.3 Ordenação topológica 28

Fonte: adaptado de Cormen et al. (2001, p. 550). 29

Quadro 3 – Algoritmo ordenação topológica 29

2.3.4 Algoritmo de Dijkstra 29

Fonte: adaptado de Gross e Yellen (2006, p. 148). 30

Quadro 4 – Algoritmo de Dijkstra 30

2.3.5 Algoritmo de Floyd-Warshall 30

Fonte: adaptado de Cormen et al. (2001, p. 635). 31

Quadro 5 – Algoritmo de Floyd-Warshall 31

2.3.6 Algoritmo de Bellman-Ford 31

Fonte: adaptado de Cormen et al. (2001, p. 588). 32

Quadro 6 – Algoritmo de Bellman-Ford 32

2.3.7 Algoritmo de Hopcroft-Tarjan 32

Fonte: adaptado de Cormen et al. (2001, p. 553). 32

Figura 5 – Exemplo de um grafo e suas componentes fortemente conexas 32

Fonte: adaptado de Eppstein (2001). 33

Quadro 7 – Algoritmo de Hopcroft-Tarjan 33

2.3.8 Algoritmo de Prim 33

Fonte: adaptado de Gross e Yellen (2006, p. 146). 34

Quadro 8 – Algoritmo de Prim 34

2.3.9 Algoritmo de Kruskal 34

Fonte: adaptado de Cormen et al. (2001, p. 569). 35

Quadro 9 – Algoritmo de Kruskal 35

2.3.10 Algoritmo de Ford-Fulkerson 35

Fonte: adaptado de Cormen et al. (2001, p. 658). 36

Quadro 10 – Algoritmo de Ford-Fulkerson 36

2.4 Trabalhos correlatos 37

Fonte: Braun (2009, p. 23). 37

Figura 6 – Interface gráfica da ferramenta 37

Fonte: JgraphT Team (2005). 38

Quadro 11 – Exemplo de integração da biblioteca JgraphT e Jgraph 38

Fonte: Braun (2009, p. 62). 39

Figura 7 – Interface gráfica da ferramenta 39

Quadro 12 – Comparação entre trabalhos correlatos 39

3 DESENVOLVIMENTO 40

3.1 requisitos principais do problema a ser trabalhado 40

3.2 ESPECIFICAÇÃO 41

3.2.1 Casos de uso 41

Figura 8 – Diagrama de casos de uso 41

Quadro 13 – Caso de uso Criar grafo 42

Quadro 14 – Caso de uso Gerar grafo 42

Quadro 15 – Caso de uso Carregar grafo de arquivo 43

Quadro 16 – Caso de uso Salvar grafo em arquivo 43

Quadro 17 – Caso de uso Executar algoritmos 43

Quadro 18 – Caso de uso Testar propriedades 43

3.2.2 Diagrama de classes 44

Figura 9 – Diagrama de pacotes 44

Figura 10 – Diagrama de classes resumido do pacote Base 45

Figura 11 – Diagrama de classes detalhado do pacote Base 46

Figura 12 – Diagrama de classes detalhado do pacote Algoritmos 47

Figura 13 – Diagrama de classes resumido do pacote Algoritmos 48

Figura 14 – Diagrama de classes do pacote Persistencia 48

Figura 15 – Diagrama de classes do pacote GeradorGrafos 49

Figura 16 – Diagrama de classes do pacote Auxiliar 50

3.2.3 Diagrama de atividades 50

Figura 17 – Diagrama de atividades 51

3.2.4 Diagrama de sequência 51

Figura 18 – Diagrama de sequência da operação salvar grafo 52

Figura 19 – Diagrama de sequência da operação executar algoritmo 53

Figura 20 – Diagrama de sequência da operação testar propriedade 54

3.3 IMPLEMENTAÇÃO 54

3.3.1 Técnicas e ferramentas utilizadas 55

3.3.1.1 DOM 55

3.3.1.2 Javadoc 55

Quadro 19 – Exemplo de código com comentários para o Javadoc 56

3.3.2 Desenvolvimento do FGA 56

3.3.2.1 Desenvolvimento da estrutura do grafo 56

Quadro 20 – Classe Grafo 57

Quadro 21 – Classe GrafoDirigido 58

Quadro 22 – Classe GrafoNaoDirigido 59

Quadro 23 – Métodos que testam propriedades de grafos 60

Quadro 24 – Classe Aresta 61

Quadro 25 – Classe ArestaDirigida 61

Quadro 26 – Classe ArestaNaoDirigida 62

Quadro 27 – Classe Vertice 62

3.3.2.2 Implementação da persistência de grafos 63

Quadro 28 – Exemplo de um arquivo com um grafo 64

Quadro 29 – Método carregaGrafo 65

Quadro 30 – Método carregaGrafoDirigido 66

Quadro 31 – Método carregaGrafoNaoDirigido 67

Quadro 32 – Método persisteGrafo 68

Quadro 33 – Método geraXMLGrafo 68

3.3.2.3 Desenvolvimento dos algoritmos de grafos 69

Quadro 34 – Classe AlgoritmoBuscaProfundidade 70

Quadro 35 – Classe AlgoritmoBuscaProfundidadeResultado 71

Quadro 36 – Classe AlgoritmoPrim 73

Quadro 37 – Classe AlgoritmoPrimResultado 74

3.3.2.4 Desenvolvimento dos geradores de grafos 74

Quadro 38 – Método getGrafoCompletoDirigido 75

Quadro 39 – Método getGrafoCompletoNaoDirigido 76

Quadro 40 – Métodos getGrafoRegularNaoDirigido e getGrafoDesconexoDirigido 77

3.3.2.5 Desenvolvimento da aplicação de exemplo 77

Figura 21 – Interface gráfica da aplicação de exemplo 78

Quadro 41 – Método que exemplifica uso do algoritmo de ordenação topológica 78

Quadro 42 – Métodos que exemplificam uso da persistência de grafos 79

Quadro 43 – Métodos que exemplificam uso da geração de grafos e teste de propriedades 80

3.3.3 Operacionalidade da implementação 80

Quadro 44 – Classe VerticeGeometrico 81

Quadro 45 – Instanciação de um grafo não dirigido 81

Quadro 46 – Instanciação de vértices e arestas 82

Quadro 47 – Adicionar vértices e arestas em um grafo 83

Quadro 48 – Execução algoritmos de busca em profundidade e Kruskal 83

Quadro 49 – Desenho de arestas 84

Quadro 50 – Desenho de vértices 84

Quadro 51 – Teste de propriedades 85

Figura 22 – Visualização do grafo 86

3.4 RESULTADOS E DISCUSSÃO 86

3.4.1 Comparação entre algoritmos de fluxo 87

Tabela 1 – Comparação entre o algoritmo de Dijkstra e busca em profundidade 87

3.4.2 Comparação entre algoritmos de busca 87

Tabela 2 – Comparação entre algoritmos de busca 88

3.4.3 Comparação entre algoritmos de geração de árvore de custo mínimo 88

Tabela 3 – Comparação entre algoritmos de geração de árvore de custo mínimo 88

3.4.4 Comparação entre algoritmos de menor caminho 88

Tabela 4 – Comparação entre algoritmos de menor caminho em uma consulta 89

Tabela 5 – Comparação entre os algoritmos com várias consultas tendo mesma origem 89

Tabela 6 – Comparação entre os algoritmos com várias consultas tendo origens diferentes 90

3.4.5 Comparação entre trabalhos correlatos 90

Quadro 52 – Comparação entre trabalhos correlatos e o FGA 91

3.4.6 O framework em Objective-C 91

Quadro 53 – Arquivo AlgoritmoPrim.h 92

Quadro 54 – Arquivo AlgoritmoPrim.m 93

Quadro 55 – Arquivo AlgoritmoPrimResultado.h 94

Quadro 56 – Arquivo AlgoritmoPrimResultado.m 94

Quadro 57 – Execução do algoritmo de Prim 95

4 CONCLUSÕES 96

4.1 EXTENSÕES 97

Referências bibliográficas 98






  1   2   3   4   5   6   7   8   9   ...   12


©livred.info 2017
enviar mensagem

    Página principal