Programa de desenho de grafos



|Alunos: Alexandre Marinho Ferreira |N.º 3163 |

|Filipe Vieira da Silva | |

| |Eng. da Comunicação 4º Ano. |

|Disciplinas: Teoria dos Grafos | |

|Paradigmas da Computação | |

|Docentes: Eng. José Torres | |

|Eng. Rui Silva Moreira | |

Programa de desenho de grafos

Descrição do trabalho realizado

Índice

Índice 2

Especificação do problema 4

Modelo Orientado aos objectos do Protótipo 5

Estrutura do Protótipo 7

Conclusão 11

Bibliografia 12

Introdução

Este relatório pretende descrever o trabalho realizado para as disciplinas de Teoria dos Grafos e Paradigmas da Computação.

O objectivo é a descrição e implementação de um protótipo de geração e manipulação de Grafos.

No capitulo de especificação do problema será feita uma especificação funcional dos objectivos a atingir com este trabalho.

Os capítulos de modelo OO associado e estrutura do protótipo constituem a maior parte deste relatório.

No modelo OO será feita a descrição dos diagramas UML criados na fase de concepção do protótipo.

Na estrutura do protótipo será feita uma descrição da fase de implementação, com a descrição especifica dos métodos e algoritmos implementados.

Finalmente será feita uma conclusão sobre as mais valias que este trabalho proporcionou e possíveis melhoramentos futuros.

Especificação do problema

Neste projecto era pretendida a implementação de um programa que permitisse desenho e manipulação de grafos.

Genericamente, a aplicação desenvolvida consegue desenhar qualquer tipo de grafo, graças á abordagem de concepção usada. Por insuficiência de tempo não conseguimos implementar um interface do utilizador que permitisse uma verdadeira interactividade com a aplicação, podendo dessa forma haver uma manipulação mais eficiente dos grafos.

Como este projecto inseria-se no âmbito de uma disciplina que estuda o modelo de programação orientado aos objectos e a linguagem de programação Java, o desenvolvimento da aplicação foi feito usando uma abordagem orientada aos objectos e utilizando a linguagem de programação Java.

Para a concepção do modelo de classes da aplicação foi usada a ferramenta de modelação gráfica, Rational Rose para Java baseada na Unified Modelling Language (UML), linguagem sucessora da Object Modelling Technique(OMT) dos mesmos autores.

Esta ferramenta CASE(computer assisted software engeneering) permite fazer a concepção orientada a objectos, de alto nível do modelo de classes da aplicação, dos seus atributos, inter-relacionamentos (relacionamentos simples, agregações, heranças, etc) e métodos, gerando posteriormente o código correspondente constituído pelo esqueleto das classes e dos seus métodos.

Na fase seguinte passamos á implementação propriamente dita da aplicação, utilizando, como já foi referido, a linguagem Java.

Foram implementadas funcionalidades para conseguir um controlo total sobre as propriedades dos grafos a desenhar.

Nomeadamente foram consideradas aspectos como cores, conteúdo dos nós, suporte para grafos pesados e digrafos, etc...

Foram posteriormente feitos testes para avaliar as funcionalidades da aplicação.

Modelo Orientado aos objectos do Protótipo

Na figura seguinte apresenta-se o diagrama UML de classes da aplicação, que será descrito pormenorizadamente a seguir:

[pic]

As 3 classes principais são:

• a classe Grafo, que contem todas as propriedades e operações que podem ser feitas num grafo. Basicamente é constituído por um identificador, métodos para adicionar/remover nós e ramos, e métodos adicionais para desenhar ou gravar o grafo. Contem duas relações fundamentais entre a classe Ramo e a classe No. Um grafo é constituído por agregações de Ramos e Nós representadas aqui pelas associações listaRamos e listaNos.

• A classe No, que contem igualmente todas as suas propriedades e operações possíveis que um nó pode ter. Tal como as outras 2 classes principais, um nó também tem o seu próprio identificador, tendo adicionalmente coordenadas de localização na área de desenho, cor própria e opcionalmente armazena dados. A maior parte dos métodos desta classe servem para operar as suas variáveis membro, tendo tal como as outras classes, o seu próprio método desenhar. Existe ainda a possibilidade de mover um nó graças ao respectivo método.

• Finalmente a classe Ramo tem atributos e métodos semelhantes ao Nó. Tem uma relação que posteriormente na implementação, torna-se muito importante: um ramo é uma ligação entre 2 nós, havendo pois uma relação de N para 2 entre ramos e nós.

Tem ainda dois atributos adicionais importantes, peso e seta. O atributo peso é usado para determinar se estamos perante um grafo pesado, ou seja, é o peso de um determinado ramo. Se o peso for igual a 0, trata-se de um grafo convencional.

A seta é usada para determinar se o ramo tem um sentido, ou seja, se é o ramo de um digrafo. Caso seja, o sentido é de No1 para No2.

Existem ainda duas classes secundarias:

• AreaDesenho, que é responsável pela interacção entre as classes anteriores e a área de desenho, conhecida em java por canvas. Tem, para alem do construtor, um único método paint, responsável pelo desenho de figuras geométricas, propriamente dito. Do ponto de vista da nossa aplicação, essas figuras geométricas, vão ser pequenas circunferências, no caso dos nós, e segmentos de rectas no caso dos ramos.

• TesteApp que não tem atributos nem construtor, possuindo apenas um método main(). Esta classe é responsável por executar toda a aplicação usando as outras classes.

Uma 3ª classe a implementar seria a UserInterface, responsável pelo interface do utilizador e pela interactividade com o mesmo, respondendo a eventos. Esta classe teria relações com TesteApp e Grafo e provavelmente com AreaDesenho. Infelizmente por falta de tempo, foi inviável esta implementação.

Estrutura do Protótipo

Tendo em conta que a linguagem de programação usada foi Java, tivemos de considerar alguns aspectos particulares desta linguagem.

Uma das características particulares mais evidentes foi a utilização do Canvas.

Em java o Canvas é uma classe do AWT(Abstract Window Tookit) que corresponde a uma área de desenho .

O Canvas tem relativamente poucos métodos associados e não pode ser acedido directamente.

Para o utilizar temos que criar uma classe (neste caso AreaDesenho), que redefine um dos métodos mais importantes do Canvas, o paint(). Este método é responsável por definir as propriedades do Canvas a usar e todas as operações (métodos invocados dentro do paint()) que podem ser realizadas no Canvas.

Na nossa classe AreaDesenho, o paint() é redefinido para desenhar o Canvas e invocar o método Grafo.desenharGrafo() que irá desenhar o grafo propriamente dito.

Especificamente, para que as operações de desenho possam ser feitas usa-se uma classe independente do Canvas, a Graphics que é uma abstracção de todo o conjunto de operações que pode ser feito num canvas através do paint(), entretanto já redefinido e usado implicitamente.

No nosso projecto usamos o Graphics para desenhar circunferências e segmentos de recta, correspondentes aos nós e grafos.

Estes métodos são invocados quando pretendemos especificamente usar os métodos No.desenharNo() e Ramo.desenharRamo(), que podem ser acedidos directamente, ou mais frequentemente através do método Grafo.desenharGrafo().

Na classe Grafo (tal como nas classes No e Ramo), existem muitos métodos bastante simples que pura e simplesmente resumem-se a leitura das suas variáveis membro.

No entanto há alguns mais complexos.

Quer os nós, quer os ramos, estão armazenados em 2 vectores de objectos respectivamente m_listaNos e m_listaRamos

Para criar nós e ramos podemos optar por duas soluções.

Podemos criar os nós e os ramos invocando os construtores das respectivas classes e depois invocarmos respectivamente os métodos inserirNo() e inserirRamo(), ou então usarmos estes métodos para fazer tudo numa única chamada.

Como cada um destes 2 métodos tem duas implementações, estamos perante um exemplo de polimorfismo em Java.

Se fizermos tudo numa única chamada, o inserirRamo() invoca o Grafo.encontrarNo() para determinar a quais nós irá estar ligado.

O Grafo.encontrarNo() e o Grafo.encontrarRamo() procuram ciclicamente, nos respectivos vectores de nos/ramos qual o ramo/no que está associado á id que foi passada como parâmetro.

Estes algoritmos são conseguidos á custa dos métodos da classe Vector para manipular objectos dessa classe.

Os métodos apagarNo() e apagarRamo() seguem algoritmos semelhantes. Primeiro invocam o Grafo.encontrarNo() ou Grafo.encontrarRamo() para encontrarem o nó ou ramo correspondente á id que foi passada inicialmente como parâmetro.

Depois simplesmente executam o método removeElementAt() da classe vector para remover o objecto encontrado.

Se soubermos a localização dos nos ou ramos a apagar nos vectores respectivos, podemos usar os métodos Grafo.removeNo() e Grafo.removeRamo(), que passam como parâmetro o índice na lista de ramos/nos do objecto a apagar.

Nesta classe existem ainda dois métodos importantes e independentes dos anteriores que são o Grafo.desenharGrafo() e o Grafo.gravarGrafo().

No primeiro vamos desenhar o grafo em 2 passos.

No primeiro passo vamos percorrer ciclicamente o vector de nos e por cada passagem invocar o método No.desenharNo().

No segundo passo vamos seguir exactamente o mesmo procedimento para os ramos: percorrer o vector de ramos e por cada passagem invocar Ramo.desenharRamo().

O Grafo.gravarGrafo() grava num ficheiro de texto todo o conteúdo do Grafo no momento em que é invocado por TesteApp.main().

Este método invoca o método createfile() utiliza métodos da package java.io (contem todas os métodos e classes necessários para gestão de ficheiros) para escrever sequencialmente o conteúdo do grafo no ficheiro, novamente de forma cíclica.

Este conteúdo é passado como parâmetro para o createfile() através de uma string que contem os dados estruturados do grafo.

A organização desses dados é feita previamente pelo Grafo.gravarGrafo() através de dois ciclos que percorrem o vector de nos e o vector de ramos lendo as variáveis membro desses nos e ramos e colocando-as na string final, que irá ser passada como parâmetro.

Na classe No a maior parte dos métodos resume-se á leitura/escrita simples das variáveis membro. Os dois métodos mais importantes são No.desenharNo() e o No.moverNo().

O No.desenharNo() utiliza os métodos do objecto da classe Graphics (passado como parâmetro) para atribuir-lhe uma cor e desenhar-lhe uma Elipse de eixos iguais (uma circunferência).

O No.moverNo() move o No para a nova posição (x,y) passada como parâmetro e invoca o Grafo.desenharGrafo(), redesenhando o grafo, para que as alterações sejam visíveis.

Para que o No se possa associar ao grafo, utiliza a variável membro m_pertenceGrafo que é inicializada pelo construtor do No como o Grafo ao qual o No pertence.

Na classe Ramo existem dois aspectos importantes a salientar.

O construtor ao inicializar as variáveis membro utiliza um vector com 2 elementos m_ligaNos que é constituído pelos 2 nós ao qual o ramo está ligado. Estes nós são passados como parâmetro pelo construtor.

O outro aspecto importante a descrever, é obviamente o método Ramo.desenharRamo().

Tal como no No.desenharNo(), este método utiliza métodos do objecto da classe Graphics (passado como parâmetro) para atribuir uma cor ao ramo e desenha-lo.

Do ponto de vista de algoritmia o ramo é um segmento de recta de um nó de origem para um nó de destino (podemos falar em “origem” e “destino” para uma implementação de digrafos).

Tudo o que o método que desenha o segmento de recta (ramo) faz é desenhar um segmento de recta das coordenadas do no de origem para as coordenadas do nó de destino).

Em java e noutras linguagens de programação OO, tem que existir um método main() numa classe qualquer para executar a aplicação. Neste caso essa classe é a TesteApp.

Devido á inexistência de um interface de utilizador é aqui que temos que definir o que a nossa aplicação de desenho de grafos deverá fazer.

Para efeitos de teste foram criados alguns nós e ramos entre esses nós, sendo depois criado um frame ao qual adicionamos o nosso canvas com os ramos e nós desenhados.

Invocou-se ainda o método Grafo.gravarGrafo() também para efeitos de teste de gravação do ficheiro de texto com a informação do Grafo.

Todos os testes foram bem sucedidos.

Conclusão

O programa de desenho de grafos, é uma demonstração simples da resolução de um problema, utilizando a modelação orientada aos objectos, e demonstrando as potencialidades da linguagem Java como linguagem OO e algumas das suas características especificas como o Canvas.

Por outro lado, as vantagens da utilização de uma ferramenta CASE num projecto de software ficaram bem demonstradas com a utilização do Rational Rose para java.

A modelação OO fica muito mais facilitada com esta ferramenta estruturando melhor o modelo da aplicação a desenvolver.

A aplicação resultante é flexível ao ponto de conseguir englobar diversas características dos grafos, tomando como base muitas noções de teoria dos grafos, tais como os grafos pesados, ou os digrafos.

Espera-se pois, que este projecto possa ser usado como base para uma aplicação mais eficaz a nível de funcionalidades disponibilizadas. Por exemplo, o passo seguinte que seria correcto tomar, poderia ser a implementação de um interface de utilizador interactivo.

A nível de teoria dos grafos, o programa possui uma estrutura base que permite que futuramente sejam introduzidas melhorias tais como, por exemplo, calculo de caminhos em digrafos, usando os algoritmos estudados (que seriam praticamente o único código adicional a implementar).

A nível pessoal o trabalho proporcionou-nos um melhor entendimento do modelo OO e abordagens respectivas, com um exemplo pratico bem como um melhor entendimento dos tipos de grafos existentes.

Bibliografia

Eckel, Bruce: Thinking in Java , 1998 Prentice Hall

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download