English version at the following link:
enprogramminghome.blogspot.comOlá pessoal,
Em
link está um uma classe que programei que possui um único método search(type::TypeSearchEnum, v:int, cost:Graph<Double,Double>):SearchInfo
Vamos discutir a O.O deste método:
Esse método foi projetado para que diferentes tipos de buscas pudessem ser realizadas. A enumeração
TypeSearchEnum tem somente o tipo "DIJKSTRA", pois somente programei
esse tipo de busca. Posteriormente, podemos inserir "BFS", "DFS","KRUSKAL",...
Se "TypeSearchEnum" é "DIJKSTRA" é chamado o método privado
-dijkstra(v:int, cost:Graph<Double,Double>):SearchInfo
Obviamente, este último método faz busca de Dijkstra em um grafo definido pela interface Graph&lK,V> (K = V = Double). Porque um objeto Graph<K,V>?
Eu poderia ter criado uma assinatura para cada tipo de grafo ex: "double[][] custos",
"LinkedList<LinkedList<Double>> custos", "ArrayList<ArrayList<Double>> custos", "ArrayList<LinkedList<Double>> custos"...
É possível pensar em uma quantidade enorme de assinaturas, o que implica em multiplicação de código. Agora, imagine que todos esses exemplos de grafos acima implementem uma interface "Graph<K,V>" que contém métodos de acesso apropriados a estrutura de dados. Assim, criando uma única assinatura podemos lidar com esse problema!!! (Polimorfismo pela interface)
Com essa aplicação percebe-se que nós saímos daquela idéia simplista de que uma interface é apenas um contrato. O que vimos acima é a vantagem das interfaces, um
polimorfismo inigualável.
O método acima retorna um objeto SearchInfo (explicarei esse objeto daqui a pouco) que contém os resultados da busca. Quais são esses resultados?
Evidentemente, cada vértice é representado por um inteiro. O resultado de uma busca a partir de um vertice "v" são os menores caminhos dele para TODOS os demais vértices. Um menor caminho não é baseado no número de vértices e sim na menor distância, então, é interessante que também sejam as menores distâncias. E são essas informações que SearchInfo armazena. Esta classe disponibiliza dois métodos públicos para consulta.
getPathFrom(vertex:int):LinkedList{Integer}
Este método retorna o menor caminho do vértice "v" para um vértice "vertex" do grafo. Uma linkedlist é usada devido as diferenças que podem existir no número de elementos em um caminho e também porque os elementos são inseridos por addFirst(e:E) (esse método executa em O(1)).
getPathFrom(vertex:int):double
Este método retorna a menor distância do vértice "v" para um vértice "vertex" do grafo.
A classe SearchInfo é interna a SearchGraphAlgorithms, pública e com construtor privado. Isso foi pensado da seguinte maneira:
Essa classe deveria conter um método que contruisse os caminhos a partir de um vetor de vértices anteriores gerado pelo método de dijkstra. Mas as pessoas não devem acessar esse método externamente, então, ele deveria ser privado. Contudo, a classe SearchGraphAlgorithms deve ser capaz de usar esse método de construção de caminhos, assim, a classe SearchInfo deve ser interna a SearchGraphAlgorithms.
SearchInfo deve ser pública para que código externo seja capaz de acessar os resultados da busca, contudo, o contrutor é criado a partir de uma vetor de menores distâncias gerado pelo método "dijkstra", então, o construtor deve ser privado a código externo e vísivel a SearchGraphAlgorithms, o que é possível pois SearchInfo é interno.
A interface
Graph contém somente dois métodos:
+ get(i:int, j:int):V
+ size():int
Como aplicação, criei uma classe
MatGraph que monta uma matriz de adjacência a partir de um arquivo formatado:
Ex:
8
0 * * * * * * *
30 0 * * * * * *
100 80 0 * * * * *
* * 120 0 * * * *
* * * 150 0 25 * *
* * * 100 * 0 90 140
* * * * * * 0 100
170 * * * * * * 0
A primeira linha deve conter o número de vértices. As demais linhas contêm as distâncias das adjacências. Quando não existir conexão o símbolo "*" deve ser inserido.
Na Classe
Main está a aplicação desses códigos.
A numeração dos vértices começam a partir do zero.
Espero que tenham gostado!
Considerações finais:
Seja correto, caso você copie esse código no seu trabalho/projeto não deixe de indicar a minha autoria. Lembre-se que esse post é muito fácil de achar na internet e possui uma Orientação a Objetos um tanto peculiar, não seja uma pessoa tola.
