Advertisement
dcndrd

Untitled

Nov 23rd, 2014
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.19 KB | None | 0 0
  1. package br.uefs.ecomp.Game.util;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.LinkedList;
  5.  
  6. /**
  7. * Classe que implementa um grafo
  8. *
  9. * @author Daniel Andrade
  10. * @author Cássio Santos
  11. * @see br.uefs.ecomp.Game.util.Vertex
  12. * @see br.uefs.ecomp.Game.util.GraphPathSearch
  13. */
  14. public class Graph {
  15.  
  16. private final int totalVertex;
  17. private final double aMatrix[][];
  18. private int actualVertex;
  19. private final Vertex[] vertex;
  20.  
  21. public Graph(int numberOfVertex) {
  22. this.totalVertex = numberOfVertex;
  23. this.aMatrix = new double[this.totalVertex][this.totalVertex];
  24. this.vertex = new Vertex[this.totalVertex];
  25. this.actualVertex = 0;
  26. }
  27.  
  28. /**
  29. *
  30. * @param label Label do vértice
  31. * @param x Coordenada x
  32. * @param y Coordenada y
  33. * @return O vértice criado
  34. * @throws DuplicateVertexException
  35. */
  36. public Vertex addVertex(String label, int x, int y) throws DuplicateVertexException {
  37. if (!this.containsVertex(label)) {
  38. Vertex v = new Vertex(label, this.actualVertex, x, y);
  39. this.vertex[this.actualVertex++] = v;
  40. return v;
  41. }
  42. throw new DuplicateVertexException();
  43. }
  44.  
  45. /**
  46. * Busca um vértice através da Label.
  47. *
  48. * @param label Label do vértice a ser buscado
  49. * @return O vértice que corresponde a label ou null caso ele não existir.
  50. */
  51. public Vertex getVertexByLabel(String label) {
  52. for (Vertex v : this.vertex) {
  53. if (v != null && v.getLabel().equals(label)) {
  54. return v;
  55. }
  56. }
  57. return null;
  58. }
  59.  
  60. /**
  61. * Busca um vértice através da id
  62. *
  63. * @param id Id do vértice a ser buscado
  64. * @return O vértice que corresponde a ID ou null caso ele não existir
  65. */
  66. public Vertex getVertexById(int id) {
  67. for (Vertex v : this.vertex) {
  68. if (v != null && v.getId() == id) {
  69. return v;
  70. }
  71. }
  72. return null;
  73. }
  74.  
  75. /**
  76. * Cria uma nova aresta
  77. *
  78. * @param a Vértice que deve ser ligada a vértice b
  79. * @param b Vértice que deve ser ligada a vértice a
  80. */
  81. public void addEdge(String a, String b) {
  82. if (this.containsVertex(a) && this.containsVertex(b)) {
  83. Vertex va = this.getVertexByLabel(a);
  84. Vertex vb = this.getVertexByLabel(b);
  85.  
  86. this.aMatrix[va.getId()][vb.getId()] = this.getWeigth(va, vb);
  87. this.aMatrix[vb.getId()][va.getId()] = this.getWeigth(va, vb);
  88. }
  89. }
  90.  
  91. /**
  92. * Verifica se dois vétices estão ligados por uma aresta
  93. *
  94. * @param a Vértice 1
  95. * @param b Vértice 2
  96. * @return
  97. */
  98. public boolean isConnected(String a, String b) {
  99. if (this.containsVertex(a) && this.containsVertex(b)) {
  100. Vertex va = this.getVertexByLabel(a);
  101. Vertex vb = this.getVertexByLabel(b);
  102.  
  103. return this.aMatrix[va.getId()][vb.getId()] != 0;
  104. }
  105. return false;
  106. }
  107.  
  108. /**
  109. * Verifica se o vértice com a label correspondente já existe.
  110. *
  111. * @param s Label do vértice
  112. * @return True caso exista, false caso contrário.
  113. */
  114. private boolean containsVertex(String s) {
  115. for (Vertex v : this.vertex) {
  116. if (v != null && v.getLabel().equals(s)) {
  117. return true;
  118. }
  119. }
  120. return false;
  121. }
  122.  
  123. /**
  124. * Verifica todos os vértices adjacentes a um dado vértice.
  125. *
  126. * @param s Vértice a ser analisado
  127. * @return Uma coleção de todos os vétices adjacentes.
  128. */
  129. public LinkedList<String> adjacentNodes(String s) {
  130. LinkedList<String> adj = new LinkedList<>();
  131. if (this.containsVertex(s)) {
  132. Vertex v = this.getVertexByLabel(s);
  133. for (int i = 0; i < this.totalVertex; i++) {
  134. if (this.aMatrix[v.getId()][i] != 0) {
  135. adj.add(this.getVertexById(i).getLabel());
  136. }
  137. }
  138. }
  139. return adj;
  140. }
  141.  
  142. /**
  143. * Verifica quais os caminhos possíveis partindo do vértice A e chegando no
  144. * vértice B
  145. *
  146. * @param a Vértice de origem
  147. * @param b Vértice de destino
  148. * @return Uma coleção de caminhos possíveis
  149. * @throws VertexNotFoundException
  150. */
  151. public ArrayList<ArrayList<String>> getAllPossiblePaths(String a, String b) throws VertexNotFoundException {
  152. if (this.containsVertex(a) && this.containsVertex(b)) {
  153. return new GraphPathSearch(a, b, this).getAllPossiblePaths();
  154. }
  155. throw new VertexNotFoundException();
  156. }
  157.  
  158. /**
  159. * Calcula o menor caminho do vértice A até o vértice B
  160. *
  161. * @param a Vértice de origem
  162. * @param b Vértice de destino
  163. * @return O menor caminho entre os dois vértices
  164. * @throws PathlessException
  165. */
  166. public ArrayList<String> smallerPath(String a, String b) throws PathlessException {
  167. if (this.containsVertex(a) && this.containsVertex(b)) {
  168. ArrayList<ArrayList<String>> paths = new GraphPathSearch(a, b, this).getAllPossiblePaths();
  169.  
  170. ArrayList<String> lowerCostPath = null;
  171. double costOfLowerPath = Double.MAX_VALUE;
  172.  
  173. for (ArrayList<String> p : paths) {
  174. double actualCost = 0;
  175. for (int i = 0; i < p.size(); i++) {
  176. Vertex va = this.getVertexByLabel(p.get(i));
  177. Vertex vb;
  178. if (i == p.size() - 1) {
  179. vb = this.getVertexByLabel(p.get(0));
  180. } else {
  181. vb = this.getVertexByLabel(p.get(i + 1));
  182. }
  183. actualCost += this.aMatrix[va.getId()][vb.getId()];
  184. }
  185. if (costOfLowerPath > actualCost) {
  186. costOfLowerPath = actualCost;
  187. lowerCostPath = p;
  188. }
  189. }
  190.  
  191. if (lowerCostPath != null) {
  192. return lowerCostPath;
  193. }
  194. }
  195. throw new PathlessException();
  196. }
  197.  
  198. /**
  199. * Calcula o peso de uma aresta com base na distância euclidiana entre os
  200. * vértices.
  201. *
  202. * @param a Label do vértice de origem
  203. * @param b Label do vértice de destino
  204. * @return O peso da aresta
  205. */
  206. private double getWeigth(Vertex a, Vertex b) {
  207. double x = Math.pow((b.getX() - a.getX()), 2);
  208. double y = Math.pow((b.getY() - a.getY()), 2);
  209.  
  210. return Math.sqrt(x + y);
  211. }
  212.  
  213. /**
  214. * Calcula a distância euclidiana entre dois vértices
  215. *
  216. * @param a Label do vértice de origem
  217. * @param b Label do vértice de destino
  218. * @return A distância entre os dois vértices
  219. * @throws VertexNotFoundException
  220. */
  221. public double LinearDistance(String a, String b) throws VertexNotFoundException {
  222. if (this.containsVertex(a) && this.containsVertex(b)) {
  223. return this.getWeigth(this.getVertexByLabel(a), this.getVertexByLabel(b));
  224. }
  225. throw new VertexNotFoundException();
  226. }
  227.  
  228. public double[][] getAMatrix() {
  229. return this.aMatrix;
  230. }
  231.  
  232. /**
  233. * Calcula o peso total de um caminho.
  234. *
  235. * @param p Caminho percorrido
  236. * @return O peso.
  237. */
  238. public double getPathWeigth(ArrayList<String> p) {
  239. double actualCost = 0;
  240. for (int i = 0; i < p.size(); i++) {
  241. Vertex va = this.getVertexByLabel(p.get(i));
  242. Vertex vb;
  243. if (p.size() > 2) {
  244. if (i == p.size() - 1) {
  245. vb = this.getVertexByLabel(p.get(0));
  246. } else {
  247. vb = this.getVertexByLabel(p.get(i + 1));
  248. }
  249. actualCost += this.aMatrix[va.getId()][vb.getId()];
  250. }
  251. else{
  252. try {
  253. actualCost = this.LinearDistance(p.get(0), p.get(1));
  254. } catch (VertexNotFoundException ex) {}
  255. }
  256. }
  257.  
  258. return actualCost;
  259. }
  260. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement