Universidade regional de blumenau



Baixar 1,07 Mb.
Página11/12
Encontro01.07.2018
Tamanho1,07 Mb.
1   ...   4   5   6   7   8   9   10   11   12

IMPLEMENTAÇÃO


São apresentadas nesta seção as técnicas e ferramentas utilizadas na implementação do FGA, a descrição do desenvolvimento do trabalho e por fim a operacionalidade da ferramenta.

      1. Técnicas e ferramentas utilizadas


A implementação do FGA e aplicação de teste foram feitas utilizando a linguagem de programação Java versão 6, a qual permite a portabilidade do FGA para diversas plataformas que suportam a linguagem. Durante o desenvolvimento também foi utilizada a biblioteca Document Object Model (DOM) para criação e leitura de arquivos eXtensible Markup Language (XML).

Para a codificação do FGA, bem como para a aplicação de teste, foi utilizado o ambiente de programação Fedora Eclipse 3.4.1. Por fim, para gerar a documentação do FGA, foi utilizado o Javadoc.


        1. DOM


O Document Object Model (DOM) é um padrão desenvolvido pela World Wide Web Consortium (W3C) e define uma forma padrão para criar, acessar e manipular documentos XML. O DOM define os objetos e propriedades de todos os elementos do documento, e os métodos para acessá-los. Para trabalhar com os arquivos XML o DOM representa os documentos como uma estrutura baseada em árvores (WORLD WIDE WEB CONSORTIUM, 2010). O uso da biblioteca DOM, no FGA, permite disponibilização de funções para persistir e carregar grafos de arquivos.
        1. Javadoc


O Javadoc é uma ferramenta que analisa as declarações e os comentários de documentação em um conjunto de arquivos-fonte e produz um conjunto de páginas HyperText Markup Language (HTML), descrevendo as classes, interfaces, construtores, métodos e campos (ORACLE TEAM, 2005).

O Quadro 19 mostra um exemplo de código com comentários para o Javadoc.



/**
 * Carrega um grafo a partir de um arquivo
 * @param arquivo Arquivo onde está o grafo
 * @return Grafo
 * @throws ParserConfigurationException
 * @throws FileNotFoundException
 * @throws SAXException
 * @throws IOException
 */
public static Grafo carregaGrafo(String arquivo) throws ParserConfigurationException, FileNotFoundException, SAXException, IOException {...}

Quadro 19 – Exemplo de código com comentários para o Javadoc
      1. Desenvolvimento do FGA


O desenvolvimento do trabalho foi dividido em cinco etapas principais, a implementação da estrutura do grafo, o desenvolvimento da persistência, a implementação dos geradores de grafos, o desenvolvimento dos algoritmos e por fim a implementação da aplicação de exemplo. A seguir é descrita a implementação de cada uma das etapas.
        1. Desenvolvimento da estrutura do grafo


A estrutura básica do grafo é responsável por manter o conjunto de vértices e os identificadores das arestas existentes. A partir desta estrutura básica é possível que a mesma seja estendida tanto para um grafo dirigido como para um grafo não dirigido.

Como boa parte dos métodos e atributos de um grafo dirigido e um grafo não dirigido são os mesmos, estes dados acabam ficando como responsabilidade da classe Grafo, deixando as implementações específicas para as classes GrafoDirigido e GrafoNaoDirigido. Parte do código da classe Grafo é exibida no Quadro 20.



public abstract class Grafo {

protected ArrayList vertices;

private HashMap
adjacente;

protected HashMap idVertices;

protected HashMap idArestas;
/**

* Retorna se existe uma conexão u -> v

* @param u Vértice de origem

* @param v Vértice de destino

* @return true ou false

*/

public boolean ehAdjacente(Vertice u, Vertice v) {



Pair par = new Pair(u, v);

return adjacente.get(par) != null;

}
/**

* Retorna se o grafo é conexo.


* Um grafo é conexo se for possível visitar qualquer vértice, partindo de um outro e passando por arestas.

* @return true ou false

*/

Public abstract Boolean ehConexo();



Quadro 20 – Classe Grafo

Os métodos abstratos existentes na classe Grafo são métodos que necessitam de implementações específicas para grafos dirigidos e não dirigidos. Tais implementações estão nas classes GrafoDirigido e GrafoNaoDirigido que estendem a classe Grafo.

Para um melhor desempenho na busca da existência de conexões entre dois vértices foi criado o atributo adjacente, o qual é utilizado para verificar se existe alguma conexão entre um vértice de origem e outro de destino. Esta informação pode ser obtida chamando o método ehAdjacente passando como argumentos os vértices de origem e destino.

Outra característica importante desta classe é a forma de obter vértices e arestas de uma forma rápida. Para que seja possível tal desempenho foi necessária a criação de um identificador único para cada vértice e para cada aresta. Este valor é um número inteiro e é feito um mapeamento com as classes Vertice e Aresta.

A classe GrafoDirigido implementa os métodos específicos para os grafos dirigidos. Parte do seu código é apresentado no Quadro 21. Já a classe GrafoNaoDirigido é responsável pelos métodos com implementação específica para grafos não dirigidos, sendo que um trecho do seu código é exposto no Quadro 22.

O conjunto de arestas do grafo também é mantido nas classes GrafoDirigido e GrafoNaoDirigido, já que as arestas podem ser dirigidas ou não dirigidas.



public class GrafoDirigido extends Grafo {

private ArrayList arestas;

/**

* Retorna se o grafo é conexo.


* Um grafo é conexo se for possível visitar qualquer vértice, partindo de um outro e passando por arestas.


* Em grafos dirigidos é feito o teste se o grafo é fortemente conexo, ou seja, possui apenas uma componente


* fortemente conexa.

* @return true ou false

*/

public boolean ehConexo() {



AlgoritmoBuscaLargura alg = new AlgoritmoBuscaLargura();

alg.executar(this, getUmVertice());


AlgoritmoBuscaLarguraResultado res = alg.getResultado();
int tamanhoGrafo = getTamanho();

for (int i = 0; i < tamanhoGrafo; i++) {

Vertice v = getVertice(i);

if (res.getVisitado(v) != true) return false;

}

//executa no grafo transposto



Grafo g = getTransposto();
alg = new AlgoritmoBuscaLargura();

alg.executar(g, g.getUmVertice());


res = alg.getResultado();

for (int i = 0; i < tamanhoGrafo; i++) {

Vertice v = g.getVertice(i);

if (res.getVisitado(v) != true) return false;

}

return true;



}

Quadro 21 – Classe GrafoDirigido

public class GrafoNaoDirigido extends Grafo {

private ArrayList arestas;

/**

* Retorna se o grafo é conexo.


* Um grafo é conexo se for possível visitar qualquer vértice, partindo de um outro e passando por arestas.

* @return true ou false

*/

public boolean ehConexo() {



AlgoritmoBuscaLargura alg = new AlgoritmoBuscaLargura();

alg.executar(this, getUmVertice());


AlgoritmoBuscaLarguraResultado res = alg.getResultado();

int tamanhoGrafo = getTamanho();

for (int i = 0; i < tamanhoGrafo; i++) {

Vertice v = getVertice(i);

if (res.getVisitado(v) != true) return false;

}

return true;



}

Quadro 22 – Classe GrafoNaoDirigido

Todas as verificações das propriedades do grafo têm seus métodos chamados a partir da classe Grafo. Algumas propriedades necessitam de cálculos diferenciados para grafos dirigidos e não dirigidos, portanto tais métodos são abstratos na classe Grafo. O Quadro 21 e o Quadro 22 exemplificam a propriedade que diz respeito a conexidade de um grafo, enquanto que o Quadro 23 mostra exemplos de métodos que testam outras propriedades.



/**

* Retorna se o grafo é trivial.


* Um grafo é trivial se contém apenas um vértice e nenhuma aresta.

* @return true ou false

*/

public boolean ehTrivial() {



return getTamanho() == 1 && getQtdeArestas() == 0;

}

/**



* Retorna se o grafo é nulo.

* Um grafo é nulo se o conjunto de arestas é vazio.

* @return true ou false

*/

public boolean ehNulo() {



return getQtdeArestas() == 0;

}
/**

* Retorna se o grafo é denso.

* Um grafo é denso se o total de arestas é maior ou igual ao quadrado da quantidade de vértices.

* @return true ou false

*/

public boolean ehDenso() {



int m = getQtdeArestas();

int n = getTamanho();

return m >= (n * n);

}

/**



* Retorna se o grafo é esparso.

* Um grafo é esparso se o total de arestas é menor que o quadrado da quantidade de vértices.

* @return true ou false

*/

public boolean ehEsparso() {



return !ehDenso();

}
/**

* Retorna se o grafo é simples.

* Um grafo é simples se não possui arestas paralelas e laços.

* @return true ou false

*/

public boolean ehSimples() {



return !ehMultigrafo();

}


Quadro 23 – Métodos que testam propriedades de grafos

Um grafo é constituído por vértices e arestas. Da mesma forma que as classes relacionadas com as características do grafo, são implementadas as classes para trabalhar com as arestas.

A classe abstrata Aresta disponibiliza os métodos comuns para as arestas dirigidas e não dirigidas. Uma parte do seu código é exibida no Quadro 24.


public abstract class Aresta {

private int id;

private Object dado;

private double valor;

private double capacidade;

private Vertice vi;

private Vertice vj;

private Grafo g;


/**

* Retorna o dado da aresta

* @return dado

*/

public Object getDado() {



return dado;

}
/**

* Retorna o valor/custo da aresta

* @return valor

*/

public double getValor() {



return valor;

}


Quadro 24 – Classe Aresta

Os métodos getVi e getVj, que são utilizados para retornar os vértices que formam uma determinada aresta, são escritos nas classes ArestaDirigida e ArestaNaoDirigida. Um trecho da classe ArestaDirigida é exibido no Quadro 25, enquanto que parte do código da classe ArestaNaoDirigida é mostrado no Quadro 26.



public class ArestaDirigida extends Aresta {

/**


* Retorna o vértice de origem da aresta

* @return vi

*/

public Vertice getVi() {



return vi;

}

/**



* Retorna o vértice de destino da aresta

* @return vj

*/

public Vertice getVj() {



return vj;

}


Quadro 25 – Classe ArestaDirigida

public class ArestaNaoDirigida extends Aresta {

/**


* Retorna o vértice de origem da aresta

* @return vi

*/

public Vertice getVi() {



return vi;

}

/**



* Retorna o vértice de destino da aresta

* @param u Um vértice

* @return vj

*/

public Vertice getVj(Vertice u) {



if (vi.equals(u))

return vj;

return vi;

}


Quadro 26 – Classe ArestaNaoDirigida

Por fim, a classe Vertice disponibiliza os métodos para trabalhar com os vértices do grafo. Um dos atributos da classe é a lista de arestas em que o vértice é o ponto de partida. A partir deste atributo é possível descobrir os vértices adjacentes sem que seja necessário percorrer todo o grafo. Um trecho do seu código é exposto no Quadro 27.



public abstract class Vértice {

private int id;

private Object dado;

private Color cor;

private ArrayList arestas;

private HashMap idArestas;


/**

* Adiciona uma aresta ao vértice

* @param a Aresta

*/

protected void addAresta(Aresta a) {



idArestas.put(a.getId(), a);

arestas.add(a);

}
/**

* Retorna o grau do vértice

* @return grau

*/

public int getGrau() {



return arestas.size();

}


Quadro 27 – Classe Vertice
        1. Implementação da persistência de grafos


Para a gravação e recuperação de grafos foi optado pelo formato de arquivo XML, pois é um formato aberto e de implementação relativamente simples.

A estrutura do formato do grafo no arquivo requer que seja informado se o tipo grafo que está sendo armazenado é dirigido ou não dirigido. O campo responsável por este controle é o Tipo. Se nele contiver o valor 1 então o grafo é dirigido, enquanto que, se contiver o valor 2 será um grafo não dirigido. Informado o tipo do grafo segue-se a lista de vértices e arestas.

Para os vértices estão disponíveis um campo obrigatório para informar o identificador, chamado Id, outro campo chamado Cor para a cor do vértice, a qual está no formado Red Green Blue (RGB), e por fim um campo chamado Dado, responsável por armazenar um objeto qualquer que pode estar vinculado ao vértice.

Para as arestas é necessário informar um identificador, representado pelo campo Id, um identificador de um vértice de origem para o campo Vi e outro identificador de um vértice de destino para o campo Vj. Além destes campos estão disponíveis um campo chamado Valor, do tipo numérico com ponto flutuante, que representa o custo ou peso de uma aresta, outro campo chamado Capacidade, também do tipo numérico com ponto flutuante, responsável pelo fluxo de dados que pode ser transmitido pela aresta e por fim, um campo chamado Dado, que pode conter um objeto qualquer para estar vinculado na aresta.

Um exemplo de arquivo que demonstra uma configuração de um grafo utilizando este formato pode ser observado no Quadro 28.




1





1

25500

A





2

02550

B







3

00255



C









1

1

2

1442.44

6.3

Trilha 1





2

1

3



13.45

5.0

Trilha 2







Quadro 28 – Exemplo de um arquivo com um grafo

O FGA utiliza a biblioteca DOM para trabalhar com XML, sendo que a interação com este formato de arquivo ocorre somente por meio da classe Persistencia. Através do método carregaGrafo é possível passar um endereço de arquivo como parâmetro e obter como retorno o grafo nele persistido. Neste método é feito o teste do tipo de grafo e é chamada uma função auxiliar carregaGrafoDirigido para o caso de um grafo dirigido ou a função carregaGrafoNaoDirigido para um grafo não dirigido.

O método carregaGrafo tem seu código exposto no Quadro 29, enquanto que um trecho do método carregaGrafoDirigido está no Quadro 30 e, um trecho do método carregaGrafoNaoDirigido no Quadro 31.


/**

* Carrega um grafo a partir de um arquivo

* @param arquivo Arquivo onde está o grafo

* @return Grafo

* @throws ParserConfigurationException

* @throws FileNotFoundException

* @throws SAXException

* @throws IOException

*/

public static Grafo carregaGrafo(String arquivo) throws ParserConfigurationException, FileNotFoundException, SAXException, IOException {



DocumentBuilderFactory fabrica = DocumentBuilderFactory.newInstance();

DocumentBuilder construtor = fabrica.newDocumentBuilder();

Document documento = construtor.parse(retornaDadosXML(arquivo));

Element elementoGrafo =

(Element) documento.getElementsByTagName("Grafo").item(0);

Node nodeTipo =

elementoGrafo.getElementsByTagName("Tipo").item(0).getFirstChild();

if (nodeTipo.getNodeValue().equals("1"))

return carregaGrafoDirigido(documento);

else


return carregaGrafoNaoDirigido(documento);

}


Quadro 29 – Método carregaGrafo

private static GrafoDirigido carregaGrafoDirigido(Document documento) {

GrafoDirigido g = new GrafoDirigido();

Element elementoGrafo = (Element)

documento.getElementsByTagName("Grafo").item(0);

//Vertices

Element elementoVertices = (Element)

elementoGrafo.getElementsByTagName("Vertices").item(0);

NodeList nodelistVertices =

elementoVertices.getElementsByTagName("Vertice");
for (int i = 0; i < nodelistVertices.getLength(); i++) {

{...}


Vertice v = new

Vertice(Integer.parseInt(nodeId.getNodeValue()));

v.setCor(new Color(Integer.valueOf(nodeR.getNodeValue()),

Integer.valueOf(nodeG.getNodeValue()),

Integer.valueOf(nodeB.getNodeValue())));

v.setDado(nodeDado.getNodeValue());

g.addVertice(v);

}
//Arestas

Element elementoArestas = (Element)

elementoGrafo.getElementsByTagName("Arestas").item(0);

NodeList nodelistArestas =

elementoArestas.getElementsByTagName("Aresta");


for (int i = 0; i < nodelistArestas.getLength(); i++) {

{...}


Vertice u =

g.getVerticeById(Integer.valueOf(nodeVi.getNodeValue()));

Vertice v =

g.getVerticeById(Integer.valueOf(nodeVj.getNodeValue()));

ArestaDirigida a = new

ArestaDirigida(Integer.valueOf(nodeId.getNodeValue()), u, v);

a.setValor(Double.valueOf(nodeValor.getNodeValue()));

a.setCapacidade(Double.valueOf(nodeCapacidade.getNodeValue()));

a.setDado(nodeDado.getNodeValue());

g.addAresta(a);

}

return g;



}

Quadro 30 – Método carregaGrafoDirigido

private static GrafoNaoDirigido carregaGrafoNaoDirigido(Document documento) {

GrafoNaoDirigido g = new GrafoNaoDirigido();

Element elementoGrafo = (Element)

documento.getElementsByTagName("Grafo").item(0);

//Vertices

Element elementoVertices = (Element)

elementoGrafo.getElementsByTagName("Vertices").item(0);

NodeList nodelistVertices =

elementoVertices.getElementsByTagName("Vertice");
for (int i = 0; i < nodelistVertices.getLength(); i++) {

{...}


Vertice v = new

Vertice(Integer.parseInt(nodeId.getNodeValue()));

v.setCor(new Color(Integer.valueOf(nodeR.getNodeValue()),

Integer.valueOf(nodeG.getNodeValue()),

Integer.valueOf(nodeB.getNodeValue())));

v.setDado(nodeDado.getNodeValue());

g.addVertice(v);

}
//Arestas

Element elementoArestas = (Element)

elementoGrafo.getElementsByTagName("Arestas").item(0);

NodeList nodelistArestas =

elementoArestas.getElementsByTagName("Aresta");


for (int i = 0; i < nodelistArestas.getLength(); i++) {

{...}


Vertice u =

g.getVerticeById(Integer.valueOf(nodeVi.getNodeValue()));

Vertice v =

g.getVerticeById(Integer.valueOf(nodeVj.getNodeValue()));

ArestaNaoDirigida a = new

ArestaNaoDirigida(Integer.valueOf(nodeId.getNodeValue()), u, v);

a.setValor(Double.valueOf(nodeValor.getNodeValue()));

a.setCapacidade(Double.valueOf(nodeCapacidade.getNodeValue()));

a.setDado(nodeDado.getNodeValue());

g.addAresta(a);

}

return g;



}

Quadro 31 – Método carregaGrafoNaoDirigido

O FGA também disponibiliza os métodos geraXMLGrafo, que é responsável por converter um objeto da classe Grafo em formato XML, e persisteGrafo que faz a gravação do XML em um arquivo informado.

No Quadro 32 está mostrado o código do método persisteGrafo, enquanto que no Quadro 33 é exibida parte do código do método geraXMLGrafo.


/**

* Persiste uma grafo em arquivo

* @param g Grafo

* @param arquivo Arquivo de destino

* @throws IOException

*/

public static void persisteGrafo(Grafo g, String arquivo) throws IOException {



String texto = getXMLGrafo(g);

Comandos.salvar(arquivo, texto, false);

}


Quadro 32 – Método persisteGrafo

/**

* Retorna uma String com o grafo convertido em XML

* @param g Grafo

* @return String XML que representa o grafo

*/

public static String getXMLGrafo(Grafo g) {



DocumentBuilderFactory fabrica = DocumentBuilderFactory.newInstance();

DocumentBuilder construtor = null;

try {

construtor = fabrica.newDocumentBuilder();



} catch (ParserConfigurationException e) {

e.printStackTrace();

}

Document documento = construtor.newDocument();



Element elementoGrafo = documento.createElement("Grafo");

documento.appendChild(elementoGrafo);

Element elementoTipo = documento.createElement("Tipo");

Text nodeTipo = documento.createTextNode(String.valueOf(g.getTipo()));

elementoTipo.appendChild(nodeTipo);

elementoGrafo.appendChild(elementoTipo);

//Percorre vertices e arestas

{...}
//Gera xml

try {

trans = transfac.newTransformer();



} catch (TransformerConfigurationException e) {}

trans.setOutputProperty(OutputKeys.OMIT_XML_DECLARATION, "yes");

trans.setOutputProperty(OutputKeys.INDENT, "yes");

StringWriter sw = new StringWriter();

StreamResult result = new StreamResult(sw);

DOMSource source = new DOMSource(documento);

try {

trans.transform(source, result);



} catch (TransformerException e) {}

return sw.toString();

}


Quadro 33 – Método geraXMLGrafo

        1. Desenvolvimento dos algoritmos de grafos


Para cada algoritmo desenvolvido existem duas classes que disponibilizam métodos para serem trabalhados. Uma classe é específica para a execução do algoritmo, enquanto a outra é o resultado da sua execução. A classe de resultado armazena todos os dados importantes obtidos durante a execução do algoritmo escolhido.

Toda classe de execução de algum algoritmo possui dois métodos principais sendo eles o executa, ao qual cabe a tarefa de executar o algoritmo sobre o grafo passado como parâmetro, e getResultado, responsável por retornar o resultado da execução do algoritmo.

Uma mesma classe de algoritmo pode conter mais de um método executa, ou seja, é permitido que haja uma maneira de executar o algoritmo utilizando parâmetros diferentes. Um exemplo para o caso mencionado é o algoritmo de busca em profundidade. Nele é possível chamar a execução da busca apenas passando um grafo como informação, sendo que para todo vértice não visitado uma nova execução do algoritmo é feita, ou também é válido informar qual é o vértice de origem para que seja feita a busca. Neste caso o algoritmo pára quando não há mais nenhum vértice possível de ser atingido a partir do vértice de origem.

No Quadro 34 é apresentada parte do código da classe AlgoritmoBuscaProfundidade, que contém a implementação dos métodos executa e getResultado para o algoritmo de busca em profundidade. Já, no Quadro 35 é mostrado um trecho do código fonte da classe AlgoritmoBuscaProfundidadeResultado, que disponibiliza métodos para acessar as conclusões obtidas pelo algoritmo.



public class AlgoritmoBuscaProfundidade {

private AlgoritmoBuscaProfundidadeResultado resultado;


/**

* Retorna o resultado do algoritmo

* @return AlgoritmoBuscaProfundidadeResultado

*/

public AlgoritmoBuscaProfundidadeResultado getResultado() {



return resultado;

}
private void dfs(Vertice pred, Vertice u) {

branco.put(u, false);

resultado.setTempoAbertura(u, tempo);

resultado.addDescendente(pred, u);

resultado.setPredecessor(u, pred);

resultado.setVisitado(u, true);

resultado.incrementaAtingidos();

tempo++;

ArrayList adjU = g.getAdjacentes(u);

for (Vertice v: adjU) {

if (branco.get(v))

dfs(u, v)

}

resultado.setTempoFechamento(u, tempo);



tempo++;

}

/**



* Método que executa o algoritmo sobre um grafo

* @param g Grafo

*/

public void executar(Grafo g) {



{...}

for (int i = 0; i < tamanhoGrafo; i++) {

Vertice v = g.getVertice(i);

if (branco.get(v))

dfs(null, v);

}

}



/**

* Método que executa o algoritmo sobre um grafo a partir de um vértice de origem

* @param g Grafo

* @param s Vértice de origem

*/

public void executar(Grafo g, Vertice s) {



{...}

dfs(null, v);

}


Quadro 34 – Classe AlgoritmoBuscaProfundidade

À medida que o algoritmo de busca em profundidade é executado há uma sequência de interações com a classe AlgoritmoBuscaProfundidadeResultado, que é notificada com os eventos ocorridos durante a execução. No exemplo da classe AlgoritmoBuscaProfundidade estas interações podem ser vistas no método dfs, que invoca os métodos setTempoAbertura, addDescendente, setPredecessor, setVisitado e setTempoFechamento da classe resultado. É desta forma que, ao término da execução, o resultado final é construído.



public class AlgoritmoBuscaProfundidadeResultado {

private HashMap tempoAbertura;

private HashMap tempoFechamento;

private HashMap predecessor;

private HashMap> descendentes;

private HashMap visitado;

/**

* Atribui um tempo de abertura para o vértice



* @param v Vértice

* @param t Tempo de abertura

*/

public void setTempoAbertura(Vertice v, int t) {



tempoAbertura.put(v, t);

}

/**



* Retorna o tempo de abertura do vértice

* @param v Vértice

* @return Tempo de abertura

*/

public int getTempoAbertura(Vertice v) {



return tempoAbertura.get(v);

}

/**



* Atribui um predecessor para um vértice

* @param v Vértice

* @param pai Vértice pai

*/

public void setPredecessor(Vertice v, Vertice pai) {



predecessor.put(v, pai);

}

/**



* Retorna o predecessor de um vértice

* @param v Vértice

* @return Predecessor do vértice

*/

public Vertice getPredecessor(Vertice v) {



return predecessor.get(v);

}


Quadro 35 – Classe AlgoritmoBuscaProfundidadeResultado

Para o usuário do FGA apenas os métodos da classe ficam disponíveis, sendo que a partir deles é possível construir outras estruturas de dados implícitas nos atributos da classe AlgoritmoBuscaProfundidadeResultado. Como exemplo é possível citar uma árvore construída através das leituras dos predecessores de cada vértice. Esta informação pode ser obtida invocando o método getPredecessor.

Outro exemplo de algoritmo implementado é o algoritmo de Prim. Parte da classe AlgoritmoPrim é mostrada no Quadro 36 enquanto que um trecho da classe AlgoritmoPrimResultado é mostrado no Quadro 37.

Para a implementação do algoritmo foi necessária a utilização de uma fila de prioridades, que é responsável por armazenar, em ordem, as distâncias dos vértices para que sejam adicionados na árvore geradora de custo mínimo. Além disso, é utilizada uma HashMap para identificar se um vértice já está presente na árvore.

Na classe dos resultados foram utilizadas uma HashMap para armazenar os predecessores de cada vértice, outra para a lista de vértices descendentes e outra, cujo objetivo é armazenar o custo até cada vértice. Por fim, uma lista foi usada para manter as arestas que fazem parte da árvore. Todos os demais detalhes da implementação do algoritmo foram feitos conforme descrito em pseudocódigo no Quadro 8.


public class AlgoritmoPrim {

private HashMap naArvore;

private PriorityQueue
> fila;
public void executar(GrafoNaoDirigido g) {

for (int i = 0; i < tamanhoGrafo; i++) {

Vertice v = g.getVertice(i);

naArvore.put(v, false);

resultado.setCusto(v, Constante.INF);

resultado.setPredecessor(v, null);

}

Vertice x = g.getUmVertice();



fila.offer(new PairPriority(x, 0));

while (fila.size() > 0) {

PairPriority p = fila.peek();

fila.poll();

Vertice u = p.getDado();

if (naArvore.get(u)) continue;

naArvore.put(u, true);

resultado.addCustoTotal(p.getCusto());

int qtdeArestas = u.getQtdeArestas();

for (int i = 0; i < qtdeArestas; i++) {

ArestaNaoDirigida a = (ArestaNaoDirigida) u.getAresta(i);

Vertice v = a.getVj(u);

if (naArvore.get(v) == false && a.getValor() < resultado.getCusto(v)) {

resultado.setCusto(v, a.getValor());

resultado.setPredecessor(v, u);

fila.offer(new PairPriority(v, a.getValor()));

}

}

}



for (int i = 0; i < tamanhoGrafo; i++) {

Vertice v = g.getVertice(i);

Vertice pred = resultado.getPredecessor(v);

if (pred != null) {

resultado.addDescendente(pred, v);

resultado.addAresta(g.getArestaCustoMinimo(pred, v));

}

}

}



}

Quadro 36 – Classe AlgoritmoPrim

public class AlgoritmoPrimResultado {

private HashMap predecessor;

private HashMap> descendentes;

private HashMap custo;

private ArrayList arestas;

private double custoTotal = 0;

/**

* Atribui um predecessor para um vértice



* @param v Vértice

* @param pai Vértice pai

*/

public void setPredecessor(Vertice v, Vertice pai) {



predecessor.put(v, pai);

}

/**



* Retorna o predecessor de um vértice

* @param v Vértice

* @return Predecessor do vértice

*/

public Vertice getPredecessor(Vertice v) {



return predecessor.get(v);

}


Quadro 37 – Classe AlgoritmoPrimResultado
        1. Desenvolvimento dos geradores de grafos


Outra funcionalidade do FGA é a capacidade de gerar grafos com diversas propriedades especiais. A parte do FGA que fica responsável por isso está na classe GeradorGrafos. Nela estão, para cada tipo de grafo que pode ser gerado, um método para gerar um grafo dirigido e outro para gerar um grafo não dirigido. No Quadro 38 é exibido o método getGrafoCompletoDirigido, para construir um grafo completo dirigido, enquanto que no Quadro 39 é exposto o método getGrafoCompletoNaoDirigido que constrói um grafo completo não dirigido. Nota-se que, pelas características particulares do grafo dirigido e do não dirigido, o algoritmo que os gera é sempre diferente.

/**

* Gera um grafo dirigido completo.


* Um grafo é completo se ele é simples e existe uma aresta ligando cada par de vértices distintos.

* @param qtdeVertices Quantidade de vértices

* @return GrafoDirigido completo

*/

public static GrafoDirigido getGrafoCompletoDirigido(int qtdeVertices) {



GrafoDirigido g = new GrafoDirigido();

for (int i = 1; i <= qtdeVertices; i++) {

Vertice v = new Vertice (i);

v.setDado(i);

g.addVertice(v);

}

int cArestas = 1;



for (int i = 0; i < qtdeVertices; i++) {

Vertice u = g.getVertice(i);

for (int j = 0; j < qtdeVertices; j++) {

if (i == j) continue;

Vertice v = g.getVertice(j);

ArestaDirigida a = new ArestaDirigida(cArestas, u, v);

a.setValor(Comandos.getDoubleNumeroAleatorio(0.0, 100.0));

a.setDado(cArestas);

a.setCapacidade(Comandos.getDoubleNumeroAleatorio(0.0, 100.0));

g.addAresta(a);

cArestas++;

}

}



return g;

}


Quadro 38 – Método getGrafoCompletoDirigido

/**

* Gera um grafo não dirigido completo.


* Um grafo é completo se ele é simples e existe uma aresta ligando cada par de vértices distintos.

* @param qtdeVertices Quantidade de vértices

* @return GrafoNaoDirigido completo

*/

public static GrafoNaoDirigido getGrafoCompletoNaoDirigido(int qtdeVertices) {



GrafoNaoDirigido g = new GrafoNaoDirigido();

for (int i = 1; i <= qtdeVertices; i++) {

Vertice v = new Vertice (i);

v.setDado(i);

g.addVertice(v);

}

int cArestas = 1;



for (int i = 0; i < qtdeVertices; i++) {

Vertice u = g.getVertice(i);

for (int j = i + 1; j < qtdeVertices; j++) {

Vertice v = g.getVertice(j);

ArestaNaoDirigida a = new ArestaNaoDirigida(cArestas, u, v);

a.setValor(Comandos.getDoubleNumeroAleatorio(0.0, 100.0));

a.setDado(cArestas);

a.setCapacidade(Comandos.getDoubleNumeroAleatorio(0.0, 100.0));

g.addAresta(a);

cArestas++;

}

}

return g;



}

Quadro 39 – Método getGrafoCompletoNaoDirigido

Dependendo do tipo de grafo, dirigido ou não dirigido, e da propriedade que precisa ser atingida, muitas configurações de parâmetros de entrada para os geradores podem ser inválidas.

Não é possível, por exemplo, gerar um grafo regular não dirigido com uma quantidade de vértices ímpar e exigir que o mesmo tenha todos seus vértices com grau também ímpar. Se uma entrada for dada da maneira mencionada o FGA retorna uma exceção, garantindo que não fique tentando gerar um grafo inválido.

Outro exemplo pode ser verificado quando se tenta gerar um grafo desconexo de apenas um vértice. O retorno para esta entrada também é de uma configuração inválida. No Quadro 40 é mostrado o exemplo do tratamento feito ao gerar um grafo regular não dirigido, bem como o tratamento feito ao gerar um grafo desconexo dirigido, nos métodos getGrafoRegularNaoDirigido e getGrafoDesconexoDirigido, respectivamente.



/**

* Gera um grafo não dirigido regular.


* Um grafo é regular se todos os vértices possuem o mesmo grau.

* @param qtdeVertices Quantidade de vértices

* @param grau Grau dos vértices

* @return GrafoNaoDirigido regular

* @throws Exception caso a quantidade de vértices e o grau seja ímpar

*/

public static GrafoNaoDirigido getGrafoRegularNaoDirigido(int qtdeVertices, int grau) throws Exception {



if (qtdeVertices % 2 != 0 && grau % 2 != 0)

throw new Exception("Nao e possivel gerar um grafo dessa configuracao");


/**

* Gera um grafo dirigido desconexo.


* Um grafo é desconexo se não for possível visitar qualquer vértice, partindo de um outro e passando por arestas.

* @param qtdeVertices Quantidade de vértices

* @return GrafoDirigido desconexo

* @throws Exception caso a quantidade de vértices seja 1

*/

public static GrafoDirigido getGrafoDesconexoDirigido(int qtdeVertices) throws Exception {



if (qtdeVertices == 1)

throw new Exception("Nao e possivel gerar um grafo dessa configuracao");



Quadro 40 – Métodos getGrafoRegularNaoDirigido e getGrafoDesconexoDirigido
        1. Desenvolvimento da aplicação de exemplo


Como aplicação de teste, foi desenvolvida uma ferramenta simples que utiliza todos os recursos que o FGA oferece. A aplicação é constituída por três menus, sendo um para a execução de algoritmos de grafos, outro para o teste de propriedades de grafos e por fim, um menu que contém as funções de gerar grafos, criar, salvar e carregar um grafo.

Além disto, está disponível uma interface para editar o grafo, ou seja, adicionar e remover vértices e arestas. Com isto é possível testar também os métodos básicos da estrutura do grafo, sendo eles addAresta, addVertice, delAresta e delVertice.



A Figura 21 mostra a interface gráfica da aplicação de teste, com o resultado da execução do algoritmo de Hopcroft-Tarjan.

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

No Quadro 41 é mostrada uma parte do código que chama a execução do algoritmo de ordenação topológica. O modo de obter o resultado da execução do algoritmo também está exemplificado no mesmo quadro.


public void executaOrdenacaoTopologica() {

if (g == null) {

JOptionPane.showMessageDialog(null, "Nenhum grafo criado...");

return;


}

if (!g.ehDirigido() || !g.ehAciclico()) {

JOptionPane.showMessageDialog(null, "O grafo precisa ser dirigido e acíclico...");

return;


}

imprimeln("*** Executando algoritmo de Ordenacao Topologica ***");

AlgoritmoOrdenacaoTopologica alg = new AlgoritmoOrdenacaoTopologica();

try {


alg.executar((GrafoDirigido)g);

} catch (Exception e) {

imprimeln(e.getMessage());

return;


}
imprimeln("*** FIM DA EXECUCAO ***");

imprimeln("*** RESULTADOS ***");

AlgoritmoOrdenacaoTopologicaResultado res = alg.getResultado();

int tamanhoLista = res.getTamanho();

Vertice v = res.getVertice(0);

String seq = v.getDado() + "[" + res.getTempoAbertura(v) + "/" + res.getTempoFechamento(v) + "]";

for (int i = 1; i < tamanhoLista; i++) {

v = res.getVertice(i);

seq = v.getDado() + "[" + res.getTempoAbertura(v) + "/" + res.getTempoFechamento(v) + "]" + " -> " + seq;

}


imprimeln(seq);

}


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

O Quadro 42 exibe um trecho do código que chama os métodos que trabalham com a persistência do grafo, ou seja, o método persisteGrafo e o carregaGrafo da classe Persistencia.



private void salvaGrafo() {

String arquivo = javax.swing.JOptionPane.showInputDialog("Informe o endereco do arquivo do grafo para salvar...");


try {

Persistencia.persisteGrafo(g, arquivo);

} catch (IOException e) {}

}
private void carregaGrafo() {

String arquivo = javax.swing.JOptionPane.showInputDialog("Informe o endereco do arquivo do grafo...");

File file = new File(arquivo);


if (! file.exists()) {

JOptionPane.showMessageDialog(null, "Arquivo inexistente");

return;

}

cboArestas.removeAllItems();



cboVertices.removeAllItems();

g = null;

try {

g = Persistencia.carregaGrafo(arquivo);



carregaVertices();

carregaArestas();

} catch (Exception e) {}

}


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

Um exemplo da chamada de uma função para gerar um grafo bipartido, bem como testar se o grafo é bipartido pode ser visto no Quadro 43.



private void gerarGrafoDirigidoBipartido() {

String strQtdeX = javax.swing.JOptionPane.showInputDialog("Informe a quantidade de vertices do conjunto X...");

if (strQtdeX == null || strQtdeX.equals("")) {

JOptionPane.showMessageDialog(null, "Quantidade inválida...");

return;

}

String strQtdeY = javax.swing.JOptionPane.showInputDialog("Informe a quantidade de vertices do conjunto Y...");



if (strQtdeY == null || strQtdeY.equals("")) {

JOptionPane.showMessageDialog(null, "Quantidade inválida...");

return;

}

g = GeradorGrafos.getGrafoBipartidoDirigido(Integer.parseInt(strQtdeX), Integer.parseInt(strQtdeY));



carregaVertices();

carregaArestas();

}
public void actionPerformed(ActionEvent e) {

JOptionPane.showMessageDialog(null, "Bipartido: " + g.ehBipartido());

}


Quadro 43 – Métodos que exemplificam uso da geração de grafos e teste de propriedades
      1. Operacionalidade da implementação


Esta seção apresenta a operacionalidade do FGA através da execução de um estudo de caso. Para a demonstração do FGA foi construída uma aplicação simples que desenha um grafo na tela, mostra algumas propriedades e a execução dos algoritmos de busca em profundidade e de Kruskal.

Inicialmente é necessário estender a classe Vertice para que seja possível criar novos métodos e atributos. Portanto é apresentada a classe VerticeGeometrico (Quadro 44), que é uma extensão da classe Vertice, e contém como atributos o raio de um círculo e a posição x e y. Esta classe é utilizada para desenhar os vértices do grafo na tela.




import base.Vertice;

public class VerticeGeometrico extends Vertice {

private int x;

private int y;

private int raio;

public VerticeGeometrico(int id) {

super(id);

}

public VerticeGeometrico(int id, int x, int y, int raio) {



super(id);

this.x = x;

this.y = y;

this.raio = raio;

}

public int getX() {



return x;

}
public void setX(int x) {

this.x = x;

}


Quadro 44 – Classe VerticeGeometrico

Terminada a classe VerticeGeometrico, é necessário instanciar um grafo, conforme ilustrado no Quadro 45.



GrafoNaoDirigido grafo = new GrafoNaoDirigido();

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

O próximo passo é instanciar alguns vértices e arestas. O Quadro 46 mostra um exemplo da instanciação de vértices geométricos e arestas não dirigidas.

Para os vértices são informados um identificador, uma posição x e y e um raio. Além disso, é definida uma cor específica para cada vértice.

Para as arestas são informados um identificador, um vértice de origem e um vértice de destino. Outro atributo dado para a aresta é um peso, no caso acessado pelo método setValor. Tal atributo é necessário para que mais tarde possa ser executado o algoritmo de Kruskal e descobrir a árvore ou floresta geradora de custo mínimo.



VerticeGeometrico v1 = new VerticeGeometrico(1, 10, 3, 20);

VerticeGeometrico v2 = new VerticeGeometrico(2, 100, 150, 30);

VerticeGeometrico v3 = new VerticeGeometrico(3, 58, 300, 50);

VerticeGeometrico v4 = new VerticeGeometrico(4, 300, 200, 40);

VerticeGeometrico v5 = new VerticeGeometrico(5, 400, 100, 20);

VerticeGeometrico v6 = new VerticeGeometrico(6, 450, 200, 30);

VerticeGeometrico v7 = new VerticeGeometrico(7, 30, 500, 20);

VerticeGeometrico v8 = new VerticeGeometrico(8, 400, 520, 40);

v1.setCor(Color.green);

v2.setCor(Color.yellow);

v3.setCor(Color.orange);

v4.setCor(Color.red);

v5.setCor(Color.black);

v6.setCor(Color.blue);

v7.setCor(Color.gray);

v8.setCor(Color.cyan);

ArestaNaoDirigida a1 = new ArestaNaoDirigida(1, v1, v2);

ArestaNaoDirigida a2 = new ArestaNaoDirigida(2, v2, v3);

ArestaNaoDirigida a3 = new ArestaNaoDirigida(3, v2, v4);

ArestaNaoDirigida a4 = new ArestaNaoDirigida(4, v4, v1);

ArestaNaoDirigida a5 = new ArestaNaoDirigida(5, v5, v6);

ArestaNaoDirigida a6 = new ArestaNaoDirigida(6, v3, v4);

ArestaNaoDirigida a7 = new ArestaNaoDirigida(7, v3, v7);

ArestaNaoDirigida a8 = new ArestaNaoDirigida(8, v4, v7);

ArestaNaoDirigida a9 = new ArestaNaoDirigida(9, v7, v8);

ArestaNaoDirigida a10 = new ArestaNaoDirigida(10, v8, v4);

a1.setValor(100);

a2.setValor(5);

a3.setValor(40);

a4.setValor(50);

a5.setValor(14);

a6.setValor(3);

a7.setValor(15);

a8.setValor(7);

a9.setValor(2);

a10.setValor(1);



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

Para que os vértices e arestas componham o grafo, eles precisam ser explicitamente adicionados ao grafo. O Quadro 47 mostra um exemplo de como adicionar vértices e arestas em um grafo.



grafo.addVertice(v1);

grafo.addVertice(v2);

grafo.addVertice(v3);

grafo.addVertice(v4);

grafo.addVertice(v5);

grafo.addVertice(v6);

grafo.addVertice(v7);

grafo.addVertice(v8);


grafo.addAresta(a1);

grafo.addAresta(a2);

grafo.addAresta(a3);

grafo.addAresta(a4);

grafo.addAresta(a5);

grafo.addAresta(a6);

grafo.addAresta(a7);

grafo.addAresta(a8);

grafo.addAresta(a9);

grafo.addAresta(a10);



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

Com o grafo criado, contendo vértices e arestas, é possível executar algoritmos e verificar propriedades. O Quadro 48 mostra como executar e obter o resultado dos algoritmos de busca em profundidade e Kruskal.



AlgoritmoBuscaProfundidade algDFS = new AlgoritmoBuscaProfundidade();

algDFS.executar(grafo);

AlgoritmoBuscaProfundidadeResultado resDFS = algDFS.getResultado();

AlgoritmoKruskal algKruskal = new AlgoritmoKruskal();

algKruskal.executar(grafo);

AlgoritmoKruskalResultado resKruskal = algKruskal.getResultado();



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

Terminada a execução dos dois algoritmos e de posse dos resultados obtidos pode-se desenhar o grafo na tela e destacar as soluções obtidas. O Quadro 49 mostra o desenho das arestas. Inicialmente são desenhadas todas as arestas do grafo e, em seguida, são pintadas em verde apenas as arestas que fazem parte da floresta de custo mínimo encontrada pelo algoritmo de Kruskal. Por fim, a última iteração desenha na tela o conteúdo do atributo valor de cada aresta.



for (int i = 0; i < grafo.getQtdeArestas(); i++) {

ArestaNaoDirigida a = grafo.getAresta(i);

VerticeGeometrico u = (VerticeGeometrico) a.getVi();

VerticeGeometrico v = (VerticeGeometrico) a.getVj(u);


g.setColor(Color.black);

g.drawLine(u.getX() + u.getRaio() / 2, u.getY() + u.getRaio() / 2,

v.getX() + v.getRaio() / 2, v.getY() + v.getRaio() / 2);

}
for (int i = 0; i < resKruskal.getArestas().size(); i++) {

ArestaNaoDirigida a = (ArestaNaoDirigida)

resKruskal.getArestas().get(i);

VerticeGeometrico u = (VerticeGeometrico) a.getVi();

VerticeGeometrico v = (VerticeGeometrico) a.getVj(u);

g.setColor(Color.green);

g.drawLine(u.getX() + u.getRaio() / 2, u.getY() + u.getRaio() / 2,

v.getX() + v.getRaio() / 2, v.getY() + v.getRaio() / 2);

}
for (int i = 0; i < grafo.getQtdeArestas(); i++) {

ArestaNaoDirigida a = grafo.getAresta(i);
VerticeGeometrico u = (VerticeGeometrico) a.getVi();

VerticeGeometrico v = (VerticeGeometrico) a.getVj(u);

g.setColor(Color.white);

g.fillRect((u.getX() + v.getX()) / 2, (u.getY() + v.getY()) / 2,

String.valueOf(a.getValor()).length() * 7, 10);

g.setColor(Color.blue);

g.drawString(""+a.getValor(), (u.getX() + v.getX()) / 2,

(u.getY() + v.getY()) / 2 + 10);

}


Quadro 49 – Desenho de arestas

O Quadro 50 mostra o desenho dos vértices do grafo. Junto ao vértice são destacados o atributo id e o tempo de abertura e fechamento encontrados pela execução do algoritmo de busca em profundidade.



for (int i = 0; i < grafo.getTamanho(); i++) {

VerticeGeometrico v = (VerticeGeometrico) grafo.getVertice(i);

g.setColor(v.getCor());

g.fillOval(v.getX(), v.getY(), v.getRaio(), v.getRaio());

g.setColor(Color.black);

g.drawString("{Id = " + v.getId() + "}

[" + resDFS.getTempoAbertura(v) + "/" +

resDFS.getTempoFechamento(v) + "]",

v.getX() + v.getRaio(),

v.getY() + v.getRaio() / 2);

}


Quadro 50 – Desenho de vértices

As propriedades que são mostradas na tela são desenhadas como texto, que aparece como true, caso a propriedade esteja satisfeita ou false, caso a propriedade não seja satisfeita. O Quadro 51 apresenta como é trabalhado com as propriedades de um grafo.



g.setColor(Color.black);

g.drawString("Conexo: " + grafo.ehConexo(), 480, 250);

g.drawString("Simples: " + grafo.ehSimples(), 480, 270);

g.drawString("Acíclico: " + grafo.ehAciclico(), 480, 290);

g.drawString("Denso: " + grafo.ehDenso(), 480, 310);

g.drawString("Bipartido: " + grafo.ehBipartido(), 480, 330);

g.drawString("Completo: " + grafo.ehCompleto(), 480, 350);

g.drawString("Regular: " + grafo.ehRegular(), 480, 370);

g.drawString("Ciclo: " + grafo.ehCiclo(), 480, 390);

g.drawString("Nulo: " + grafo.ehNulo(), 480, 410);

g.drawString("Trivial: " + grafo.ehTrivial(), 480, 430);

g.drawString("Árvore: " + grafo.ehArvore(), 480, 450);

g.drawString("Floresta: " + grafo.ehFloresta(), 480, 470);


Quadro 51 – Teste de propriedades

Por fim, a Figura 22 apresenta o resultado final da implementação. Nela é possível ver as arestas atingidas pelo algoritmo de Kruskal, bem como os tempos de abertura e fechamento dos vértices atingidos pelo algoritmo de busca em profundidade.



Figura 22 – Visualização do grafo




1   ...   4   5   6   7   8   9   10   11   12


©livred.info 2017
enviar mensagem

    Página principal