Embed Size (px)
Citation preview
Curso de Engenharia de Computação
PROPOSTA DE FERRAMENTA GRÁFICA PARA
REPRESENTAÇÃO DE GRAFOS COM APLICAÇÃO DE
MÉTODOS DE BUSCA
Campinas
2009
Alan Thiago do Prado
RA: 004200500387
ii
PROPOSTA DE FERRAMENTA GRÁFICA PARA
REPRESENTAÇÃO DE GRAFOS COM APLICAÇÃO DE
MÉTODOS DE BUSCA
Campinas
2009
Monografia apresentada à disciplina de
Trabalho de conclusão de curso de
Engenharia de Computação da
Universidade São Francisco campus
de Campinas, sob orientação do Prof.
Ms. Raimundo Claudio Vasconcelos
como requisito para obtenção do título
de Bacharel em Engenharia de
Computação.
iii
Monografia defendida e aprovada em 18 de junho de 2009 pela banca examinadora
constituída pelos professores:
Prof. Ms. Raimundo Claudio Vasconcelos – Orientador
Prof. Ms. José Aparecido Carrilho
Prof. Ms. Sidney Pio de Campos
iv
“Faça tudo o mais simples
possível, mas não simples”.
Albert Einstein
Mateus 5:6
v
AGRADECIMENTOS
À Deus, pela força saúde e perseverança que me propiciou;
À minha namorada, Ruty, por dividir sua sagaz alegria, ávido apoio, e singela confiança;
Ao meu orientador e professor, Ms. Claudio, por partilhar de sua vasta sabedoria e
conhecimento instruindo-me para que fosse possível realizar este trabalho de estudo;
À minha família, por tudo;
Aos meus amigos e colegas, Rubia e Marcio, por sua presença, apoio, e inspiração;
Aos Professores e colegas da Universidade São Francisco pela amizade, e aprendizado
tanto profissional como social;
Ao professor Luiz Arturo Perez Lozada, pelo suporte e esclarecimentos bem como sua
predisposição a fazê-lo;
Aos meus amigos, por acreditar, e esperar.
vi
SUMÁRIO
LISTA DE SIGLAS ............................................................................................................... viii
LISTA DE FIGURAS .............................................................................................................. ix
RESUMO ................................................................................................................................... x
ABSTRACT .............................................................................................................................. x
1. INTRODUÇÃO .................................................................................................................. 1 1.1 Contextualização ........................................................................................................... 2
1.2 Definição do problema a ser tratado ............................................................................. 2 1.3 Estrutura do Texto ......................................................................................................... 2
2. FERRAMENTAS E MATERIAS .................................................................................... 3 2.1 Java ................................................................................................................................ 3
2.2 IDE Eclipse ................................................................................................................... 3 2.3 Graphical Editor Framework (GEF) ............................................................................ 3
2.4 JUDE ............................................................................................................................. 3 2.5 UML .............................................................................................................................. 4 2.6 Materiais necessários..................................................................................................... 4
3. GEF ..................................................................................................................................... 5 3.1 MVC .............................................................................................................................. 5
3.2 Draw2d .......................................................................................................................... 6
4. GRAFOS ............................................................................................................................. 9 4.1 Representação computacional dos grafos ................................................................... 10 4.2 Algoritmos de Busca ................................................................................................... 14
4.2.1 Busca em Largura (BFS) ...................................................................................... 14 4.2.2 Busca em Profundidade (DFS) ............................................................................. 15 4.2.3 Aplicação .............................................................................................................. 16
5. PROJETO DESENVOLVIDO ....................................................................................... 18 5.1 Abordagem .................................................................................................................. 18 5.2 Descrição da interface ................................................................................................. 18 5.3 Diagrama de classes .................................................................................................... 22 5.4 Diagrama de eventos ................................................................................................... 24 5.5 Diagrama de caso e uso ............................................................................................... 30
5.6 Diagrama de estados.................................................................................................... 31 5.7 Scalable Vector Graphics (SVG) ................................................................................ 32
5.7.1 Exemplo de SVG .................................................................................................. 33
6. CONCLUSÃO .................................................................................................................. 34 6.1 Resultados obtidos....................................................................................................... 34 6.2 Contribuições .............................................................................................................. 36
6.3 Trabalhos futuros......................................................................................................... 36
vii
7. BIBLIOGRAFIA ............................................................................................................. 38 7.1 Livros .......................................................................................................................... 38
7.2 Sites ............................................................................................................................. 38 7.3 Bibliografia Consultada............................................................................................... 39
viii
LISTA DE SIGLAS
BFS Breath-First-Search
DFS Depth-First-Search
FIFO First-In-First-Out
GB Giga Byte
GEF Graphical Editor Framework
Ghz Giga hertz
GUI Graphical User Interfaces
IBM International Business Machines
JDK Java Development Kit
MB Mega Byte
MHz Mega Hertz
MVC Model, view e controller
PC Personal Computer
RAM Random Access Memory
SVG Scalable Vector Graphics
UML Unified Model Language
ix
LISTA DE FIGURAS
FIGURA 1. MODELO MVC ........................................................................................................... 5
FIGURA 2. GRAFO ORIENTADO DE 4 VÉRTICES E 5 ARESTAS. ...................................................... 9
FIGURA 3. GRAFO NÃO ORIENTADO DE 4 VÉRTICES E 4 ARESTAS .............................................. 10
FIGURA 4. MATRIZ DE ADJACÊNCIA PARA GRAFO ORIENTADO ................................................. 11
FIGURA 5 MATRIZ DE ADJACÊNCIA PARA GRAFO NÃO-ORIENTADO ........................................... 11
FIGURA 6. MATRIZ DE INCIDÊNCIA PARA GRAFO ORIENTADO ................................................... 12
FIGURA 7. MATRIZ DE INCIDÊNCIA PARA GRAFO NÃO-ORIENTADO .......................................... 12
FIGURA 8. LISTA DE ADJACÊNCIA PARA GRAFO ORIENTADO .................................................... 12
FIGURA 9. LISTA DE ADJACÊNCIA PARA GRAFO NÃO-ORIENTADO ............................................ 13
FIGURA 10. ILUSTRAÇÃO DAS PROPRIEDADES TOPOLÓGICAS DO GRAFO. .................................. 13
FIGURA 11. JANELA GRAFO ....................................................................................................... 19
FIGURA 12. JANELA MENSAGEM ............................................................................................... 19
FIGURA 13. MATRIZ JANELA ..................................................................................................... 20
FIGURA 14. JANELA BUSCA ....................................................................................................... 20
FIGURA 15. JANELA PRINCIPAL ................................................................................................. 21
FIGURA 16. FIGURA DESENHAR ................................................................................................. 22
FIGURA 17. DIAGRAMA DE CLASSES: TOPOLOGIA ..................................................................... 23
FIGURA 18. DIAGRAMA DE SEQÜÊNCIA - SELECIONAR GRAFO NÃO ORIENTADO CASO 1 .......... 24
FIGURA 19. DIAGRAMA DE SEQÜÊNCIA - SELECIONAR GRAFO NÃO ORIENTADO CASO 2 .......... 25
FIGURA 20. DIAGRAMA DE SEQÜÊNCIA - SELECIONAR GRAFO ORIENTADO CASO 1 .................. 26
FIGURA 21. DIAGRAMA DE SEQÜÊNCIA - SELECIONAR GRAFO NÃO ORIENTADO CASO 2 .......... 27
FIGURA 22. PALETA DE DESENHOS - CRIAR ARESTA ................................................................. 28
FIGURA 23. PALETA DE DESENHOS - CRIAR AUTOLOOP ............................................................ 28
FIGURA 24. PALETA DE DESENHO - CRIAR LABEL ..................................................................... 29
FIGURA 25. PALETA DE DESENHO - CRIAR VÉRTICE .................................................................. 29
FIGURA 26. DIAGRAMA CASO USO - VISÃO GERAL ................................................................... 31
FIGURA 27. DIAGRAMA DE ESTADO - EXECUTAR BUSCA .......................................................... 32
FIGURA 28. REPRESENTAÇÃO DE GRAFO NÃO ORIENTADO ATRAVÉS DO GEF ........................... 36
x
PRADO, Alan Thiago do: Proposta de ferramenta gráfica para apresentação de grafos
com aplicação de métodos de busca. 49 fs. Monografia – Curso de Graduação em
Engenharia de Computação da Universidade São Francisco, Campinas/SP.
RESUMO
Esta monografia aborda a elaboração de uma ferramenta gráfica que seja permite a
manipulação de grafos. A interface deve possuir informações relativas às propriedades dos
grafos além de suportar a execução de algoritmos de busca sobre o grafo representado na
interface. Java foi a plataforma utilizada para a elaboração do protótipo. O protótipo suporta
grafos orientados ou não-orientados bem como ponderados ou não-ponderados. O protótipo
permite a execução dos algoritmos BFS e DFS, de grande valia nos estudos acadêmicos de
computação.
Palavras Chave: GRAFOS, ALGORITMOS DE BUSCA, INTERFACE GRÁFICA, BFS,
DFS.
ABSTRACT
This monograph approaches a graphical tool capable to manipulate graphs. The interface
should have information concerning the proprieties of graphs addition to supporting the
implementation of the search algorithms on the graph represented in the interface. Java was
used as platform to the development of the prototype. The prototype supports oriented or non-
oriented as well as weighted or non-weighted graphs. The prototype has the implementation
of algorithms BFS and DFS, very helpful in academic studies of computer.interface.
KEY WORDS: GRAPHS, SEARCH ALGORITHMS, GRAPHICAL INTERFACE, BFS,
DSF.
1
1. INTRODUÇÃO
Grafo pode ser entendido como um elemento matemático baseado em dois
conjuntos, onde o segundo conjunto realiza uma função binária entre os elementos do
primeiro para obter seus elementos. O primeiro conjunto denominado vértice, e o
segundo conjunto denominado aresta, [Cormen, 2002].
Para entender a importância deste estudo é necessário conhecer um pouco sobre a
capacidade de representação de um Grafo. Através de um Grafo é possível representar
qualquer tipo de conjunto de elementos concretos ou abstratos.
Alguns exemplos comuns de representação de grafos de elementos concretos estão
ligados a representação de cidades, componentes de redes, pontes. Enquanto outras
representações de grafos baseiam-se em elementos abstratos e normalmente estão
ligadas a máquinas de estado descrevendo ação de objetos como carros, pessoas,
ampulhetas, copos, ou então ligados a outros elementos matemáticos como pontos
descrevendo um objeto real.
Grafos são tão comuns a nós que estamos cercados por eles. É tão comum que
qualquer professor(a) do ensino fundamental utiliza grafos para descrever o modelo
atômico sem ao mesmo saber o que é um grafo. Agora, observe a capacidade de
representação de um grafo, visto que foi possível representar um modelo de átomos
através de grafos mesmo a partir de poucas informações de maneira clara e simplificada.
Segundo [Ziviani, 1999], algoritmos de busca estão intimamente ligados às
estruturas de dados. Isso pode ser explicitado ao se fazer a análise dos métodos de
busca.
Os métodos de busca mais adequados a uma aplicação são dependentes de dois
aspectos principais: quantidade de dados envolvidos; e quantidade de inserções e
remoções desses dados.
Tais fatores devem ser levados em conta para que seja possível oferecer um
software adequado a uma determinada aplicação para decidir qual algoritmo será
utilizado.
2
1.1 Contextualização
O objetivo principal dessa proposta é criar um ambiente gráfico bidimensional
onde grafos possam ser visualizados e explorados através de algoritmos de busca com
intuito de auxiliar os estudos acadêmicos de computação.
Para o desenvolvimento deste projeto foi escolhida a linguagem de programação
JAVA para representar computacionalmente os grafos, implementar métodos de busca e
Interfaces Gráficas voltadas ao Usuário (Graphical User Interfaces - GUI), utilizando
recursos do framework Graphical Editor Framework (GEF) para implementar a
interface gráfica e atingir os objetivos propostos neste trabalho de conclusão de curso.
1.2 Definição do problema a ser tratado
Desenvolvimento de um aplicativo capaz de apresentar a execução de algoritmos
de percurso em grafos orientados e não orientados através de interfaces gráficas com
intuito de auxiliar a compreensão de estudos acadêmicos em computação.
1.3 Estrutura do Texto
O texto foi dividido em introdução, contextualização, objetivo e estrutura do texto
desenvolvido (Seção 1); ferramentas e materiais necessários para desenvolvimento deste
projeto (Seção 2); seção GEF trata apresentação do framework (Seção 3); seção que faz
uma descrição sobre grafos, seus elementos e algumas de suas propriedades (Seção 4);
Projeto Desenvolvido é a seção que trata o desenvolvimento propriamente dito do
protótipo, incluindo abordagem, e modelagem (Seção 5); Conclusão (Seção 6).
3
2. FERRAMENTAS E MATERIAS
2.1 Java
Segundo [Sun 1, 2009], java é um ambiente de programação orientada a objeto,
independente de plataforma, e multithread, propiciando uma tecnologia versátil,
eficiente, portável e segura, tal como exposto por [Sun 2, 2009].
2.2 IDE Eclipse
Segundo [Burnette, 2006] o Eclipse é um ambiente de desenvolvimento integrado,
que pode ser utilizado para desenvolver softwares em qualquer linguagem e não apenas
em Java.
O código-fonte do Eclipse era de propriedade da IBM, que posteriormente
disponibilizou o seu código-fonte e hoje o Eclipse é administrado por uma instituição
sem fins lucrativos, denominada Eclipse Foundation.
2.3 Graphical Editor Framework (GEF)
GEF é um framework que facilita a construção de interfaces gráficas baseado em
dois plug-ins:
Draw2d: toolkit utilizado para renderização e layout;
GEF: framework que usa os princípios do antigo MVC do Smalltalk (linguagem
de programação orientada a objeto).
2.4 JUDE
Para gerar os diagramas de classe e diagramas de eventos foi o utilizado o
software JUDE/Community como se pode observar a partir de [Jude 1, 2008].
JUDE/Community é uma edição livre de um ambiente gráfico capaz de gerar
diagramas UML1.4, importar ou exportar códigos-fonte do java, geração de autolayout,
além de outras funcionalidades.
4
2.5 UML
A UML (Linguagem de Modelagem Unificada) propõe a padronização para a
construção de softwares. Sua utilização é realizada com o intuito de minimizar os
problemas que podem ocorrer durante o desenvolvimento de um software minimizando
custos e tempo de desenvolvimento.
Para a padronização dos processos utiliza conceitos de engenharia de software.
Ela utiliza diagramas padronizados permitindo que os desenvolvedores possam
visualizar o software antes de realizar sua implementação.
2.6 Materiais necessários
Requisitos de software:
- O projeto será desenvolvido utilizando a plataforma JDK 6.0 (Java 2
SE Development Kit). Através da plataforma da JDK será utilizado o
framework GEF para implementar a interface gráfica juntamente com
o framework Visual Editor;
- IDE Eclipse versão 3.2 ou superior.
Requisitos de hardware:
A partir de [Sun 3, 2009] é possível observar que para a instalação do JDK 6.0
será necessário computadores que atendam pelo menos os requisitos relacionados a
seguir:
- Windows Installer 2.0 ou conexão com internet;
- Memória RAM dependerá das aplicações;
- 132 MB de espaço em disco disponível.
Para o Eclipse, [Burnette, 2006] especifica que será necessário computadores
que atendam pelo menos os seguintes requisitos:
Requisito Mínimo Recomendado
Versão
1.4.0 5.0 ou posterior
Memória 512 MB 1 GB ou mais
Espaço livre em disco 300 MB 1 GB ou mais
Velocidade do processador 800 Mhz 1,5 Ghz ou mais
5
3. GEF
GEF é baseado no modelo MVC (model, view, e controller) conforme ilustrado na
Figura 1, contudo é função do programador entender como organizar e montar as
estruturas conforme descrito através de [GEF 1, 2009].
A figura a seguir descreve o modelo MVC:
Figura 1. Modelo MVC
3.1 MVC
MVC é um modelo utilizado pela arquitetura de software para descrever
interfaces gráficas.
Model - Modelo
É responsável por armazenar quaisquer dados persistentes devendo conter
qualquer tipo de dado que seja conveniente armazenar sendo que os dados persistentes
devem ser contidos apenas no Modelo.
O modelo não deve conhecer ou manter referências com nenhuma estrutura da
Visão ou qualquer parte do Editor e deve ser utilizado somente como um contêiner de
dados que poderá ter suas propriedades alteradas através de mecanismos de notificação.
6
Ele deve implementar alguns tipos de mecanismos de notificação para adicionar
ou remover os listeners das propriedades a fim de mapear suas alterações.
GEF suporta qualquer tipo de modelo, contudo é necessário prover os
mecanismos de notificação.
View - Visão
A visão é responsável por fazer a apresentação de qualquer figura para o usuário
não devendo conter nenhum dado que não fora armazenado pelo modelo. Também não
deve conhecer ou manter referências com nenhuma estrutura do Modelo ou qualquer
parte do Editor. Ela é uma espécie de mapa usada como algoritmo de pintura para
desenhar as figuras da interface gráfica definida pelo plug-in Draw2d.
Controller – Controlador
Elo entre o Modelo e a Visão. No GEF o Controlador é representado pela
subclasse da classe EditPart. Existe um EditPart em cada objeto do Modelo que deverá
ser renderizado através da visão.
O EditPart mantém referência sobre o Modelo e a Visão, sendo capaz de atualizar
a visão de acordo com o estado que se encontra o objeto do Modelo, por isso, cada
objeto do Modelo que necessite ser renderizado deve ser registrado como listeners.
Conforme ocorre alguma mudança no modelo, os listeners notificam o EditPart que
atualiza a Visão.
3.2 Draw2d
Plug-in que consiste em diversos componentes gráficos seguindo o mesmo padrão
do SWING, contudo diferente do swing que possui sua arquitetura MVC o Draw2d é
praticamente todo gráfico.
Draw2d suporta duas estruturas de desenhos: figuras e as árvores de figuras.
Também é composto por uma grande quantidade de figuras prontas, úteis para criação
de uma GUI.
Árvores de Figuras
A classe da figura implementa a interface IFigure onde definirá o uso das
diversas funções relativas as propriedades das figuras.
7
Para adicionar uma referência de parentesco entre uma figura e outra basta
realizar a chamada do método parent,add(child) e para remover a referência deve-se
fazer a chamada do método parent.remove(child).
Pintura das Figuras
As figuras possuem a habilidade de se pintar através do método
Figure.paint(Graphics) seguindo a seguinte ordem:
As figuras pintam a si próprias através do método
paintFigure(Graphics);
As figuras que são derivadas da primeira camada de figuras são
pintadas na ordem em que aparecem recursivamente através do método
paint(Graphics);
As bordas das figuras são pintadas.
Pintura de Bordas
O algoritmo de pintura de borda realiza a pintura das bordas do elemento mais
especifico para o mais genérico.
Todas as figuras devem ter borda, então mesmo que o elemento mais específico
não possua toda sua área desenhada, ele deverá possuir toda sua borda na região
desenhada que não poderá ser sobrescrita pela figura que está acima na hierarquia da
árvore de figuras.
Recursos Interessantes
Layout managers: é possível criar um layout para cada figura. São
objetos responsáveis por ajustar as bordas, propriedades geométricas,
propriedades relacionadas à movimentação e tamanho das figuras filhas;
Hit – testing: algoritmo recursivo capaz de determinar o valor mais alto
que poderá ser atribuído para o ponto inicial que desenhará uma figura,
possibilitando sobrescrever o método IFigure.containsPoint();
Events: permite criar diferentes tipos de listeners para as figuras;
8
Predifined types of Figures: figures para exibir textos, figures para
mostrar imagens, formas geométricas, scroll panes, poligonos, labels,
botões, checkboxes, entre outros;
Predifined types of Borders: existem diferentes tipos de bordas capazes
de compor bordas com estilo bem complexo, muito similar ao swing;
Connections: possui um grande suporte para criar conectores de figuras;
Cursors and tooltips: permite configurar diferentes tipos de cursores para
o mouse e tooltips text;
Layers: fornecem dados transparentes ao hit-testing permitindo figuras
diferentes em diferentes níveis.
9
4. GRAFOS
Segundo [Cormen, 2002], grafos podem ser orientados e não-orientados.
Um grafo orientado é um par de conjuntos (V, E) onde V é um conjunto finito de
elementos e E é um conjunto que estabelece relações binárias em V. V é conhecido
como conjunto de vértices e E conjunto de arestas e seus elementos respectivamente,
vértices e arestas.
Para grafos não orientados G = (V, E), onde E consiste num conjunto de arestas não
ordenadas e o primeiro vértice é diferente do segundo vértice para cada aresta.
Para um grafo orientado a aresta α = (a, b), onde “a” e “b” são vértices, α é
“incidente do” ou “sai do” vértice “a” e é “incidente no” ou “entra no” vértice “b”. Para
grafo não orientado a aresta α = (a,b) é incidente nos vértices “a” e “b”.
A Figura 2 ilustra o conceito de grafo orientado. Seja G o grafo orientado, definido
por, G=(V,E), onde V={a,b,c,d} e E={(a,b),(b,c),(c,d),(d,a),(c,c)}.
Figura 2. Grafo Orientado de 4 vértices e 5 arestas.
Observe-se que o grafo dirigido G constitui um multigrafo, uma vez que a arestas
e3 constitui um laço, isto é, um ciclo de tamanho 1.
10
A Figura 3 ilustra o conceito de grafo não-orientado. Seja G o grafo não-orientado,
definido por, Grafo Não-Orientado: H=(V,E), onde V={a,b,c,d} e
E={(a,b),(b,c),(c,d),(d,a)}.
Figura 3. Grafo Não Orientado de 4 vértices e 4 arestas
Na implementação dessa ferramenta foram considerados os critérios a seguir para a
representação geométrica dos grafos e de seus resultados:
vértices: representados por círculos;
arestas não-orientadas: representadas por uma reta que une os dois vértices;
arestas orientadas: representadas por uma reta unindo dois vértices e possui
em uma de suas extremidades uma seta para indicar sua incidência no vértice
destino;
4.1 Representação computacional dos grafos
Todo e qualquer grafo, independente da sua topologia e de sua versão orientada ou
não, pode ser representado e manipulado computacionalmente através de matrizes e de
listas ligadas.
Matriz de adjacência: matriz quadrada cujas linhas e colunas representam os
vértices do grafo. Caso haja incidência no elemento e[i,j], o índice é demarcado
com 1 (um), caso contrário 0 (zero). Salientando que se o grafo é não orientado,
a matriz de adjacência é simétrica (uma matriz é simétrica quando ela e sua
transposta são a mesma). Se o grafo é orientado a matriz de adjacência não é
mais simétrica.
11
Considerando o grafo orientado G da Figura 2, sua matriz de adjacência
corresponde à seguinte apresentada na Figura 4.
a b c d
a 0 1 0 0
b 0 0 1 0
c 0 0 1 1
d 1 0 0 0
Figura 4. Matriz de adjacência para Grafo orientado
Considerando o grafo não-orientado H da Figura 3, a matriz de adjacência é
representada pela matriz da Figura 5.
a b c d
a 0 1 0 1
b 1 0 1 0
c 0 1 0 1
d 1 0 1 0
Figura 5 Matriz de adjacência para Grafo não-orientado
Matriz de incidência: Outra maneira de representar computacionalmente um
grafo é através da matriz de incidência. Nessa representação as linhas e colunas
representam vértices e as arestas, respectivamente. Se uma aresta incide nos
vértices i e j, o elemento b[i,j] é demarcado com um (1), caso contrário zero (0).
12
Considerando o grafo orientado G da Figura 2, a matriz de incidência é
representada pela matriz da Figura 6.
e1 e2 e3 e4 e5
a 1 0 0 0 0
b 0 1 0 0 0
c 0 0 1 1 0
d 0 0 0 0 1
Figura 6. Matriz de Incidência para Grafo Orientado
Considerando o grafo não-orientado H da Figura 3, a matriz de adjacência é
representada pela matriz da Figura 7.
e1 e2 e3 e4
a 1 0 0 1
b 1 1 0 0
c 0 1 1 0
d 0 0 1 1
Figura 7. Matriz de Incidência para Grafo Não-Orientado
Lista de adjacências: representação que associa a entrada de cada vértice a
uma lista de vértices, que podem ser alcançáveis através do vértice entrada.
Considerando o grafo orientado G da Figura 2, a matriz de adjacência é
representada na Figura 8.
Entrada
a b Nill
b c Nill
c d c Nill
d a Nill
Figura 8. Lista de Adjacência para Grafo Orientado
13
Considerando o grafo não-orientado H conforme na Figura 3 a lista de adjacência é
representada pela na Figura 9.
Entrada
a b d Nil
b a c Nill
c b d Nill
d c a Nill
Figura 9. Lista de Adjacência para Grafo Não-Orientado
Propriedades para Grafos Orientados:
o adjacência: dados dois vértices “a” e “b”, “a” é adjacente a “b” se, e somente
se, “a” é incidente em “b” e “b” é incidente em “a” (E={(a,b),(b,a)});
o vizinhos de um vértice v: é o conjunto de vértices adjacentes, representado
N(v);
o grau de entrada: quantidade de arestas incidentes num vértice;
o grau de saída: quantidade de arestas incidentes dum vértice;
o grau de um vértice: é a soma do grau de entrada e grau de saída de um
vértice.
Considere novamente o grafo orientado G. O vértice a, por exemplo, tem como
vértices adjacentes apenas o vértice b, o vértice c tem como vértices adjacentes o vértice
d e ele próprio. N(a)={b}
Figura 10. Ilustração das propriedades topológicas do grafo.
14
Grafos Não-Orientados
o adjacência: dados dois vértices “a”, “b”. Como “a” e “b” são incidentes
aos vértices “a” e “b”, então “a” é adjacente a “b” assim como “b” é
adjacente a “a” (E={(a,b)});
o grau: quantidade de arestas incidentes num vértice;
Grafos Orientados e Grafos Não-Orientados
o caminho: conjunto alternado de vértices e arestas compreendidos entre
um vértice origem e um vértice destino;
o peso de uma aresta: atributo atribuído a uma aresta podendo ser
negativo. Quando uma aresta não possui peso é dito aresta não ponderada
caso contrário é dita ponderada.
4.2 Algoritmos de Busca
Após a definição de um grafo é possível aplicar um algoritmo de busca que tem
por função percorrer sistematicamente caminhos contidos num grafo procurando
padrões de interesse.
Existem diversos algoritmos de busca, mas neste trabalho de conclusão de curso
foram abordados os algoritmos:
Busca em Largura (Breadth-First Search – BFS);
Busca em Profundidade (Depth-First Search – DFS).
4.2.1 Busca em Largura (BFS)
Consiste na exploração de arestas a partir de um vértice origem com o intuito de
calcular a distância da origem a partir de cada vértice visitado. O algoritmo tem por
característica expandir a fronteira dos vértices descobertos e não-descobertos
uniformemente, ou seja, a partir da origem, visitam-se todos os vértices cuja distância
seja igual a “x” antes de visitar vértices cuja distância seja “x+1”.
A busca em largura como seu próprio nome sugere, explora as arestas de um
grafo sistematicamente. Esse algoritmo baseia-se na estrutura de dados Fila e de suas
operações de enfileiramento (enqueue) e “desenfileramento” (dequeue).
15
A seguir está descrito o código da busca em largura:
BFS(G, s)
for cada vértice u pertencente V[G] – {s}
do cor [u] <= BRANCO
d [u] <= infinito
α [u] <= nulo
cor [s] <= CINZA
d [u] <= 0
α [u] <= nulo
FILA <= 0
ENQUEUE(FILA, s)
while FILA != 0
do v <= DEQUEUE(FILA)
for cada cor [v] <= Adj [u]
do if cor [v] == BRANCO
then cor [v] <= CINZA
d [v] <= d [u] + 1
π [v] <= u
ENQUEUE(FILA, v)
cor [u] <= PRETO
4.2.2 Busca em Profundidade (DFS)
Consiste na exploração de arestas a partir do vértice descoberto mais
recentemente, de um vértice origem, que ainda possui arestas inexploradas. A partir do
momento que todas as arestas são descobertas a busca regressa para explorar as arestas
do vértice predecessor àquele que fora mais recentemente descoberto, a origem. Então,
o vértice origem buscará uma nova aresta a fim de encontrar outro vértice para que o
ciclo de busca se reinicie. Caso não haja nenhuma aresta a ser explorada através do
vértice origem, será definida outra origem e o algoritmo será reiniciado até que
finalmente todas as arestas e vértices sejam visitados.
16
Algoritmo de natureza recursivo que utiliza atributos de tempo e coloração (ou
estado) para os vértices. A partir da iniciação do algoritmo os vértices mais próximos da
origem são visitados pela primeira vez a coloração é alterada de branco para cinza. Ao
passo que os vértices são novamente visitados, a coloração cinza é alterada para preto.
A seguir está descrito o código da Busca em Profundidade:
DFS(G)
for cada vértice u pertencente V[G]
do cor [u] <= BRANCO
π [u] <= nulo
tempo <= 0
for cada vértice u pertencente V[G]
do if cor [u] == BRANCO
then DFS-VISIT(u)
DFS-VISIT(u)
cor [u] <= CINZA //Branco, o vértice u acabou de ser descoberto
tempo <= tempo + 1
for cada cor [v] <= Adj [u] //Explora a aresta(u,v)
do if cor [v] == BRANCO
then π [v] <= u
DFS-VISIT(v)
cor [u] <= PRETO //Enegrece u, terminado
f [u] <= tempo <= tempo + 1
4.2.3 Aplicação
Conforme [Krishnamoorthy, Rajeev, 1996], busca em largura, busca em
profundidade e heurísticas, são técnicas que podem ser utilizadas para solucionar
alguns problemas que podem ser causados quando a árvore de busca da solução
torna-se muito extensa e passa a consumir muitos recursos como tempo e
espaço, ou quando é gerado conflito na escolha de regras a serem testadas.
17
Diversos problemas de domínios complexos bastante abrangentes estão
no âmbito da Inteligência Artificial, com isso podem-se observar suas diversas
aplicações de algoritmos de busca.
Os problemas possuem as mais diversas naturezas, desde soluções de
problemas relacionados a jogos, enigmas lógicos, até sistemas complexos.
18
5. PROJETO DESENVOLVIDO
5.1 Abordagem
Existem dois aspectos que devem ser considerados para a implementação do
projeto:
topologia: forma abstrata de representação dos elementos do grafo, ou seja,
estruturas dos vértices com suas relações de incidência e adjacência, o
modelo de representação computacional utilizado será o de listas de
adjacências;
geometria: forma de representação visual dos elementos do grafo, ou seja,
desenhos de círculos para vértices e retas para arestas.
Para a simplificação do protótipo, a geometria pode ser obtida através da
especificação do usuário, ou seja, o usuário escolhe onde cada elemento do grafo deve
ficar com o intuito de evitar problemas de desenho de grafos (graph drawing).
Em relação à topologia foram abordados os seguintes aspectos:
Orientação: orientado e não-orientado;
Custo: ponderado e não-ponderado;
Algoritmos de Busca: DFS, BFS.
5.2 Descrição da interface
A interface contém seis janelas.
1. A janela com o nome de Grafo tem a função de auxiliar o usuário na
escolha do grafo pretendido e possui dois pares de botões, sendo um para
escolha da orientação e o outro para a escolha da ponderação. Quando o
grafo for alterado de orientado para não orientado ou vice-versa, todas as
arestas serão removidas, a visualização da imagem pode ser observada
conforme Figura 11;
19
Figura 11. Janela Grafo
2. A janela chamada Mensagem é uma área de texto com objetivo de exibir
as mensagens de texto referentes à construção e atualização do grafo, a
janela de Mensagem pode ser observada conforme Figura 12;
Figura 12. Janela Mensagem
3. A janela designada Matriz é capaz de exibir a representação do grafo
através de JTable para uma matriz de incidência e adjacêcia, por isso terá
referência dinâmica com o grafo corrente desenhado na janela descrita
através do item 6. A janela conta com uma aba para dividir a matriz de
incidência da matriz de adjacência como pode ser observado através da
Figura 13;
20
Figura 13. Matriz Janela
4. A janela designada Busca, tem por objetivo iniciar o algoritmo de busca.
Contém um botão de opções BFS, outro DFS e um botão comum para
iniciar a execução. Possui mais três botões para desabilitados (Visitar,
Parar e Voltar) que tem por função auxiliar na execução do algoritmo de
busca. Após iniciada a execução, esses botões são desabilitados e outros
três botões são habitados. O botão Visitar é utilizado para avançar a busca,
o botão Voltar serve para retroceder ao estado anterior, e o botão Parar
finaliza a busca. Finalizada a execução do algoritmo os botões voltam ao
estado inicial, como pode ser observado na Figura 14;
Figura 14. Janela Busca
21
5. A janela principal, contém um menu para criar um novo arquivo, abrir,
salvar e fechar; outro menu para configurar as cores do ambiente e um
terceiro para abrir ou reabrir qualquer uma das outras cinco janelas
mencionadas. A figura de conter ter todas as outras janelas cinco janelas e
pode ser visualizada conforme Figura 15;
Figura 15. Janela Principal
6. Janela cujo titulo será o nome do arquivo tem por função realizar o
desenho do grafo através de cinco botões: BtnDesenharVertice,
BtnDesenharAresta, BtnDesenharAutoloop, BtnInserirTexto,
BtnSelecionar. Sendo suas funções respectivamente, desenhar um vértice,
desenhar uma aresta (orientada ou não orientada), desenhar autoloop
(habilitado somente para grafo orientado), inserir caixa de texto e
selecionar objeto. Essa janela conta com uma paleta de cinco botões uma
para cada tipo de função da janela descrita, e pode ser visualizada através
da Figura 16.
22
Figura 16. Figura Desenhar
5.3 Diagrama de classes
O protótipo foi organizado em três pacotes:
topologia: pacote responsável por armazenar a estrutura para gerar um grafo
orientado ou não-orientado, com seus respectivos elementos mantendo suas
propriedades;
buscas: pacote responsável por armazenar as buscas BFS e DFS;
geometria: pacote responsável por armazenar as estruturas de janelamento e
seus eventos.
23
Figura 17. Diagrama de Classes: topologia
A Figura 17 faz a representação do diagrama de classes do pacote topologia. Abaixo
pode ser observado uma breve descrição da principais classes envolvidas.
public abstract class Aresta: classe abstrata que define a base para criar arestas
orientadas e não-orientadas;
public class ArestaNaoOrientada extends Aresta: classe que define a criação de
arestas não-orientadas e herda seus atributos e métodos da classe Aresta;
public class ArestaOrientada extends Aresta: classe que define a criação de
arestas orientadas e herda seus atributos e métodos da classe Aresta;
public abstract class Grafo: classe abstrata que define a base para criar grafos
orientados e não-orientados;
public class GrafoNaoOrientado extends Grafo: classe que define a criação de
grafos não-orientados e herda seus atributos e métodos da classe Grafo;
public class GrafoOrientado extends Grafo: classe que define a criação de
grafos orientados e herda seus atributos e métodos da classe Grafo;
public class Vertice: classe que define um vértice.
24
5.4 Diagrama de eventos
Abaixo é possível verificar alguns dos diagramas de seqüência previstos para o
protótipo.
Conforme a Figura 18, é possível observar que a classe GrafoFrame enviará uma
mensagem ao objeto DesenharFrame que por sua vez criará um objeto da classe
GrafoNaoOrientado e enviará uma mensagem para a classe MensagemFrame. Por fim, o
botão AutoLoop da classe PaletaDesenhoFrame será desabilitado visto que no modelo
previsto por [Cormen, 2002] grafos não orientados não suportam autoloop.
Figura 18. Diagrama de Seqüência - Selecionar Grafo Não Orientado caso 1
Quando houver um grafo criado, ocorrerão as etapas descritas na Figura 19. É
possível observar que a classe GrafoFrame enviará uma mensagem ao objeto
DesenharFrame. DesenharFrame enviará a mensagem criarGrafoNaoOrientado() para a
classe Grafo e esta enviará a mensagem limpaArestas() para a classe Vertices que terá a
função de remover todas as arestas de todos os vértices. O botão para criar AutoLoop
será desabilitado e será efetuado um cast (conversão) do tipo do grafo para o tipo
GrafoNaoOrientado, em seguida as arestas do desenho serão removidas e as classes que
fazem a representação gráfica das matrizes de adjacência e incidência serão atualizadas,
e a classe MensagemFrame será notificada para que exiba as mensagens referentes as
atualizações.
25
Figura 19. Diagrama de Seqüência - Selecionar Grafo Não Orientado caso 2
26
Conforme a Figura 20, é possível observar que a classe GrafoFrame enviará uma
mensagem ao objeto DesenharFrame que por sua vez criará um objeto da classe
GrafoOrientado e enviará uma mensagem para a classe MensagemFrame; por fim o
botão da classe PaletaDesenhoFrame será habilitado.
Figura 20. Diagrama de Seqüência - Selecionar Grafo Orientado caso 1
Quando houver um grafo criado, ocorrerão as ações descritasnda Figura 21. É
possível observar que a classe GrafoFrame enviará uma mensagem ao objeto
DesenharFrame. DesenharFrame enviará a mensagem criarGrafoOrientado() para a
classe Grafo e esta enviará a mensagem limpaArestas() para a classe Vertices que terá a
função de remover todas as arestas de todos os vértices. O botão para criar AutoLoop
será habilitado e efetuará um cast (conversão) do tipo do grafo para o tipo
GrafoOrientado, em seguida as arestas do desenho serão removidas e as classes que
fazem a representação gráfica das matrizes de adjacência e incidência serão atualizadas,
e a classe MensagemFrame será notificada para que exiba as mensagens referentes as
atualizações.
27
Figura 21. Diagrama de Seqüência - Selecionar Grafo Não Orientado caso 2
28
A partir da classe PatelaDesenhoFrame é possível criar uma aresta. Para isso é
necessário que seja enviada uma mensagem para DesenharFrame que deverá criar um
novo objeto Aresta e notificar a classe MensagemFrame, além de atualizar as matrizes
de incidência e adjacências e notificar a classe MensagemFrame. Finalmente deve, criar
o desenho da nova Aresta.
O comportamento da criação de uma aresta pode ser observado conforme Figura 22.
Figura 22. Paleta de Desenhos - Criar Aresta
A partir da classe PatelaDesenhoFrame, também é possível criar um AutoLoop.
Da mesma forma, é necessário que seja enviada uma mensagem para DesenharFrame
que deverá criar um novo objeto Aresta e notificar a classe MensagemFrame, além de
atualizar as matrizes de incidência e adjacências e notificar a classe MensagemFrame e
finalmente, criar o desenho do AutoLoop, como pode ser observado na Figura 23.
Figura 23. Paleta de Desenhos - Criar Autoloop
29
A classe PatelaDesenhoFrame pode criar uma caixa de texto. Basta enviar a
mensagem clicarLabel(...) para a classe DesenharFrame que por sua vez adicionará o
rótulo à sua área, como descrito pelo diagrama da Figura 24.
Figura 24. Paleta de Desenho - Criar Label
A classe PaletaDesenhoFrame também é responsável por iniciar os eventos para
criação do desenho do vértice, como exemplificado pela Figura 25.
DesenharFrame criará um novo objeto Vertice e notificará a classe
MensagemFrame. Atualizará as matrizes de incidência e adjacências e notificará
novamente a classe MensagemFrame a respeito das novas mudanças. Por fim, criará o
desenho do Vertice.
Figura 25. Paleta de Desenho - Criar Vértice
30
5.5 Diagrama de caso e uso
Abaixo é possível observar o funcionamento da interface gráfica, conforme segue
o diagrama de caso e uso ilustrado através da Figura 26. O usuário pode abrir, salvar e
fechar o arquivo, além de selecionar o tipo de grafo quanto à orientação (orientado e não
orientado) e à ponderação (ponderado e não ponderado). Também é possível inserir
componentes tais como arestas, vértices, Autoloops (para arestas orientadas) e caixas de
texto.
O usuário tem como opção a escolha cores que a interface deve exibir, assim
como a execução de busca BFS ou DFS, e efetuar as seguintes ações: visitar, parar, ou
voltar.
O sistema deve ler os comandos enviados através da interface gráfica do usuário,
e interpretá-los para que sejam desenhadas as novas estruturas que farão a composição
do grafo.
A partir do momento que usuário optar por iniciar a busca, o sistema deve ser
capaz de interpretar o algoritmo de forma a representá-lo na GUI, passo a passo.
31
Figura 26. Diagrama Caso Uso - Visão Geral
5.6 Diagrama de estados
A Figura 27 mostra o funcionamento da execução de um algoritmo de busca.
Ao executar o algoritmo é possível visitar, parar e voltar.
O estado visitar empilha o próximo objeto a ser visitado numa pilha de objetos
encaminhando-o para o estado desenhar, para que seja pintado. O estado desenhar,
realizar a pintura do objeto empilhado retornando à execução da busca.
32
O estado voltar desempilha o último objeto da pilha de objetos encaminhando-o
para o estado desenhar que possuirá comportamento análogo ao descrito para o estado
visitar.
O estado parar finaliza a execução da busca.
Quando não houver mais vértices a serem visitados a busca será finalizada.
Figura 27. Diagrama de Estado - Executar Busca
5.7 Scalable Vector Graphics (SVG)
O formato para salvar as informações pertinentes ao projeto é o SVG. Este padrão
descreve gráficos bidimensionais baseados no padrão XML. O SVG permite o
desenvolvimento de interfaces dinâmicas e iterativas que podem ser interpretadas pelo
browser assim como descrito através de [SVG 1, 2009].
33
O SVG pode ser executado através do Firefox e do Internet Explorer, contudo
para a execução no Internet Explorer é necessário a instalação de um programa do
Adobe chamado SVGview.exe ou SVGViewer.exe.
5.7.1 Exemplo de SVG
Abaixo pode ser verificado um exemplo escrito a partir do modelo SVG
representando uma esfera vermelha com borda azul inscrita em retângulo de proporções
maiores.
<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg width="12cm" height="4cm" viewBox="0 0 1200 400" version="1.1"
xmlns="http://www.w3.org/2000/svg" preserveAspectRatio="xMidYMid meet"
zoomAndPan="magnify">
<desc>Example circle01 - circle filled with red and stroked with blue</desc>
<!-- Show outline of canvas using 'rect' element -->
<rect x="1" y="1" width="1198" height="398" fill="none" stroke="blue" stroke-
width="2"/>
<circle cx="600" cy="200" r="100" fill="red" stroke="blue" stroke-width="10"/>
</svg>
34
6. CONCLUSÃO
Grafos possuem diversas aplicações e podem ser utilizados para resolução de
problemas no domínio complexo através da execução de algoritmos de busca.
Para a criação da ferramenta foi necessário conhecer tecnologias como UML e
JAVA, contribuindo para a complementação dos estudos deste acadêmico.
Foi possível entender o conceito de programação orientada a objetos e a
dificuldade existente na modelagem de uma interface gráfica para usuário dada à
quantidade de detalhes e componentes existentes.
A criação do protótipo envolveu a utilização e a manipulação das seguintes
estruturas de dados: pilhas, listas, filas, e mapas. Além das estruturas de dados o
protótipo contou com o recurso de genéricos proposto por JAVA.
O padrão SVG é capaz de fazer a representação de uma figura através de sua
descrição e pode ser interpretado através do browser.
O GEF é um poderoso instrumento de criação de interfaces gráficas de usuário.
Contudo, ele é composto de diversos design partners sendo necessário ter um bom
conhecimento a respeito do assunto. Possui diversos recursos para tratar eventos, e
oferece suporte para criação de plug-ins. É baseado no modelo MVC facilitando a
extensibilidade.
6.1 Resultados obtidos
Não foi possível realizar a implementação da interface gráfica em virtude de não
ter sido possível fazer o desenho do vértice e da aresta serem selecionáveis, contudo os
algoritmos de busca funcionam normalmente com uma saída em formato de texto a
partir de um grafo estático como pode ser observado a seguir:
public static void main(String[] args) { final int nV=4; Grafo g = new GrafoNaoOrientado(); for(int i=0;i<nV;i++) g.criaVertice(i);
35
g.criaAresta(0, 1); g.criaAresta(1, 2); g.criaAresta(2, 3); g.criaAresta(3, 0); BFS a = new BFS(g); a.busca_BFS(g,g.getVertice(0)); a.reportar(g); DFS b = new DFS(g); b.busca_DFS(g, g.getVertice(0)); b.reportar(g); } //Saida: //Busca em Largura vertice predecessor distancia estado 0 0 Visitado 1 0 1 Visitado 2 3 2 Visitado 3 0 1 Visitado //Busca em profundidade vertice predecessor distancia tempo_volta Estado 0 1 8 Visitado 1 0 2 7 Visitado 2 1 3 6 Visitado 3 2 4 5 Visitado
Para desenhar um vértice dentro de um JPanel e torná-lo selecionável existe uma
série de etapas que devem ser seguidas como pode ser observado em [Davison, 2009].
Através de pesquisas foram encontradas duas ferramentas capazes de representar
grafos. A primeira chama-se JGraphX e a segunda é um plug-in baseado em GEF
denominado Direct Graph Example. Porém nenhuma das duas ferramentas dá suporte à
execução de algoritmos de busca.
Foi possível realizar uma adaptação do exemplo Shapes Diagram Editor proposto
por Elias Volanakis, e foi possível obter o comportamento desejado. Entretanto, houve
duvida com relação à inserção de outras janelas em virtude do plug-in ser executado
sobre o Eclipse. Outra duvida existe é com relação ao formato de salvamento utilizado
por GEF. O resultado pode ser observado através da Figura 28.
36
Figura 28. Representação de grafo não orientado através do GEF
6.2 Contribuições
Através deste trabalho de conclusão de curso foi possível realizar as seguintes
contribuições:
Oferecer ao acadêmico suporte no estudo de grafos;
Exposição do GEF e SVG como ferramentas capazes de compor uma
interface gráfica;
Complementar os estudos deste acadêmico.
6.3 Trabalhos futuros
Entre as várias extensões a este trabalho, pode-se destacar as seguintes:
Realizar a criação da interface gráfica visto que não fora uma etapa
concluída;
Introdução de outros algoritmos de busca tais como Dijkstra, A*, Kruskal e
Prim, Spannig-Tree, entre outros.
37
Criar mecanismo para que o usuário possa habilitar a escolha de uma nova
origem caso o algoritmo executado possua mais de uma origem. Após a
busca ser executada a partir da primeira origem a execução pararia e
habilitaria ao usuário clicar sobre um vértice não visitado. Através do clique
a busca continuaria e o recurso se tornaria ativo para caso houvesse novas
origens a serem tratadas até que todos os vértices fossem visitados.
Introduzir conceitos de componentes conexos e fortemente conexos, sub-
grafo, sub-caminho e ciclo.
Adaptar a interface para combinar a execução de um ou mais métodos de
busca ao mesmo tempo.
Alterar a estrutura da interface para o modelo MVC.
Permitir ao protótipo exportar uma animação no padrão SVG do algoritmo
de busca sendo executando. A animação pode possuir botões tais como
visitar e voltar.
Criar artifício para que o programa possa habilitar ao usuário importar
vértices através de outra representação como o símbolo para roteadores, por
exemplo.
Adaptação do grafo para aplicação de autômatos.
38
7. BIBLIOGRAFIA
7.1 Livros
[Burnette, 2006] – Burnette, Ed “Eclipse IDE: Guia de bollso”: tradução João
Tortello, Editora Porto Alegre: Bookman, 2006.
[Cormen, 2002] – Cormen, Thomas H., “Algoritmos: teoria e prática”: Rio de
Janeiro: Elsevier, 2a Edição 5a reimpressão, 2002.
[Deitel & Deitel, 2005] – Deitel, Harvey M. / Deitel, Paul J., “Java: como
programar”: tradução Edson Furmankiewicz, Editora Person Prentice Hall, 6a. Edição,
2005.
[Medeiros, 2004] – Medeiros, Ernani Sales de: “Desenvolvendo software com
UML 2.0”: Editora São Paulo: Pearson Makron Books, 2004.
[Krishnamoorthy, Rajeev, 1996] - C.S. Krishnamoorthy, S. Rajeev, “Artificial
Intelligence and Expert Systems for Engineers”: Ed. CRC Press, 1996.
[Ziviani, 1999] – Ziviani, Nivio, “Projeto de algoritmos com implementação
em Pascal e C / Nivio Ziviani”: Editora São Paulo: Pioneira, 1999.
7.2 Sites
[Davison, 2009] - http://fivedots.coe.psu.ac.th/~ad/jg/ch1/ch1.pdf - [05.06.2009]
[GEF 1, 2009] - http://wiki.eclipse.org/GEF_Description - [21.04.2009]
[Jude 1, 2008] – http://jude.change-vision.com/jude-web/product/community.html -
[13.11.2008]
[Sun 1, 2009] – http://br.sun.com/java/about/ - [03.04.2009]
[Sun 2, 2009] – http://www.java.com/pt_BR/about/ - [03.04.2009]
[Sun 3, 2009] – http://java.sun.com/javase/6/webnotes/install/jdk/install-
windows.html#requirements - [03.04.2009]
[SVG 1, 2009] – http://www.w3.org/2000/svg - [18.04.2009]
39
7.3 Bibliografia Consultada
http://dev.eclipse.org/viewcvs/indextools.cgi/org.eclipse.ve.examples/org.eclipse.ve.exa
mple.customwidget/WebContent/index.html - [10.02.2009]
http://www.eclipse.org/gef/reference/documentation.php - [20.04.2009]
http://java.sun.com/docs/books/tutorial/2d/index.html - [21.04.2009]
http://java.sun.com/javase/6/docs/api/java/util/package-summary.html - [25.04.2008]
http://java.sun.com/javase/technologies/desktop/media/2D/ - [25.04.2008]
http://jeez.sourceforge.net/ereport/howto/index.html - [17.04.2009]
http://w3.ualg.pt/~hshah/algoritmos/aula1/aula1.htm - [20.10.2008]
http://www.deitel.com/articles/java_tutorials/20050923/IntroductionToJava2D.html -
[23.04.2009]
http://www.eclipse.org/articles/article.php?file=Article-Understanding-
Layouts/index.html - [27.04.2009]
http://www.ebookee.com/Professional-Java-User-Interfaces_7.html - [14.03.2009]
http://www.ibm.com/developerworks/opensource/library/os-gef/ - [15.10.2008]
http://www.inf.ufsc.br/grafos/teo-prov/teoremas-de-grafos.htm - [21.09.2008]
http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/grafos.html - [21.09.2008]
http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/bfs.html - [21.09.2008]
http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/grafos.html - [21.09.2008]
http://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/bfs.html - [21.09.2008]
http://www.jgraph.com/jgraphx.html - [05.06.2009]
