Guest User

Untitled

a guest
Oct 24th, 2017
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.26 KB | None | 0 0
  1. package exercise3;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Iterator;
  5. import java.util.List;
  6.  
  7. public class AdjacencyMatrixGraph<V, E> implements Graph<V, E> {
  8. private List<Vertex<V>> vertices; //the vertices of the graph
  9. private List<Edge<E>> edges; //the edges of the graph
  10. private int vertexNo;
  11.  
  12. public AdjacencyMatrixGraph() {
  13. vertices = new ArrayList<Vertex<V>>();
  14. edges = new ArrayList<Edge<E>>();
  15. vertexNo = 0;
  16. }
  17.  
  18. @Override
  19. public Iterator<Vertex<V>> adjacentVertices(Vertex<V> v) {
  20. Iterator<Edge<E>> it = incidentEdges(v);
  21. ArrayList<Vertex<V>> vertices = new ArrayList<Vertex<V>>();
  22.  
  23. while (it.hasNext()) {
  24. ELEdge e = (ELEdge) it.next();
  25.  
  26. Vertex<V> vertex = e.getEndpoint1().equals((ELVertex) v) ? e.getEndpoint2() : e.getEndpoint1();
  27. vertices.add(vertex);
  28. }
  29.  
  30. return vertices.iterator();
  31. }
  32.  
  33. @Override
  34. public boolean areAdjacent(Vertex<V> v, Vertex<V> w) {
  35. ELVertex v1 = check(v);
  36. ELVertex v2 = check(w);
  37.  
  38. int[] numbers = indexes(v1.getNumber(), v2.getNumber());
  39.  
  40. if (edges.get(numbers[1] * (numbers[0] + 1)) != null) {
  41. return true;
  42. }
  43.  
  44. return false;
  45. }
  46.  
  47. @Override
  48. public int degree(Vertex<V> v) {
  49. Iterator<Edge<E>> it = incidentEdges((ELVertex) v);
  50. int count = 0;
  51. while (it.hasNext()) {
  52. it.next();
  53. count++;
  54. }
  55. return count;
  56. }
  57.  
  58. @Override
  59. public Iterator<Edge<E>> edges() {
  60. return edges.iterator();
  61. }
  62.  
  63. @Override
  64. public Vertex<V>[] endVertices(Edge<E> e) {
  65. Vertex<V>[] vertices = new Vertex[2];
  66. ELEdge edge = check(e);
  67. vertices[0] = edge.getEndpoint1();
  68. vertices[1] = edge.getEndpoint2();
  69. return vertices;
  70. }
  71.  
  72. @Override
  73. public Iterator<Edge<E>> incidentEdges(Vertex<V> v) {
  74. ArrayList<Edge<E>> incidents = new ArrayList<Edge<E>>();
  75. ELVertex v1 = check(v);
  76.  
  77. for (Vertex<V> vertex : vertices) {
  78. ELVertex v2 = (ELVertex) vertex;
  79.  
  80. int[] numbers = indexes(v1.getNumber(), v2.getNumber());
  81.  
  82. if (edges.get(numbers[1] * (numbers[0] + 1)) != null) {
  83. incidents.add(edges.get(numbers[1] * (numbers[0] + 1)));
  84. }
  85. }
  86.  
  87. return incidents.iterator();
  88. }
  89.  
  90. private int[] indexes(int n1, int n2) {
  91. int[] out = new int[2];
  92.  
  93. if (n1 > n2) {
  94. out[0] = n2;
  95. out[1] = n1;
  96. }
  97. else if (n1 < n2) {
  98. out[0] = n1;
  99. out[1] = n2;
  100. }
  101. else {
  102. out[0] = n1;
  103. out[1] = n2;
  104. }
  105.  
  106. return out;
  107. }
  108.  
  109. @Override
  110. public Edge<E> insertEdge(Vertex<V> v, Vertex<V> w, E element) {
  111. ELVertex v1 = check(v);
  112. ELVertex v2 = check(w);
  113.  
  114. int[] numbers = indexes(v1.getNumber(), v2.getNumber());
  115.  
  116. ELEdge edge = new ELEdge(element, v1, v2);
  117. edges.add(numbers[1] * (numbers[0] + 1), edge);
  118. v1.incNumIncidentEdges();
  119. v2.incNumIncidentEdges();
  120. return edge;
  121. }
  122.  
  123. @Override
  124. public Vertex<V> insertVertex(V element) {
  125. ELVertex v = new ELVertex(element);
  126. vertices.add(v);
  127. return v;
  128. }
  129.  
  130. @Override
  131. public int numEdges() {
  132. return edges.size();
  133. }
  134.  
  135. @Override
  136. public int numVertices() {
  137. return vertices.size();
  138. }
  139.  
  140. @Override
  141. public Vertex<V> opposite(Vertex<V> v, Edge<E> e) {
  142. ELVertex v1 = check(v);
  143. ELEdge edge = check(e);
  144. return edge.getEndpoint1().equals(v1) ? check(edge.getEndpoint2()) : check(edge.getEndpoint1());
  145. }
  146.  
  147. @Override
  148. public void removeEdge(Edge<E> e) {
  149. edges.remove(e);
  150. }
  151.  
  152. @Override
  153. public void removeVertex(Vertex<V> v) {
  154. vertices.remove(v);
  155. }
  156.  
  157. @Override
  158. public Iterator<Vertex<V>> vertices() {
  159. return vertices.iterator();
  160. }
  161.  
  162. private ELVertex check(Vertex<V> v)
  163. {
  164. if (v == null)
  165. throw new RuntimeException("Vertex can't be null.");
  166. else if (!(v instanceof AdjacencyMatrixGraph.ELVertex))
  167. throw new RuntimeException("Vertex is not of the right type.");
  168.  
  169. return (ELVertex) v;
  170. }
  171.  
  172. private ELEdge check(Edge<E> e)
  173. {
  174. if (e == null)
  175. throw new RuntimeException("Edge can't be null.");
  176. else if (!(e instanceof AdjacencyMatrixGraph.ELEdge))
  177. throw new RuntimeException("Edge is not of the right type.");
  178.  
  179. return (ELEdge) e;
  180. }
  181.  
  182. private class ELEdge implements Edge<E> {
  183. private E element;
  184. private ELVertex endPoint1; //the vertex at one end of the edge
  185. private ELVertex endPoint2; //the vertex at the other end of the edge
  186.  
  187. public ELEdge(E element, ELVertex v1, ELVertex v2)
  188. {
  189. this.element = element;
  190. endPoint1 = v1;
  191. endPoint2 = v2;
  192. }
  193.  
  194. @Override
  195. public E element()
  196. {
  197. return element;
  198. }
  199.  
  200. public ELVertex getEndpoint1()
  201. {
  202. return endPoint1;
  203. }
  204.  
  205. public ELVertex getEndpoint2()
  206. {
  207. return endPoint2;
  208. }
  209. }
  210.  
  211. private class ELVertex implements Vertex<V>
  212. {
  213. private V element;
  214. private int numIncidentEdges; //count of edges incident to this vertex
  215. int number;
  216.  
  217. public ELVertex(V element)
  218. {
  219. this.element = element;
  220. numIncidentEdges = 0;
  221. number = vertexNo;
  222. vertexNo++;
  223. }
  224.  
  225. @Override
  226. public V element()
  227. {
  228. return element;
  229. }
  230.  
  231. public int getNumber() {
  232. return number;
  233. }
  234.  
  235. public int getNumIncidentEdges()
  236. {
  237. return numIncidentEdges;
  238. }
  239.  
  240. public void incNumIncidentEdges()
  241. {
  242. numIncidentEdges++;
  243. }
  244.  
  245. public void decNumIncidentEdges()
  246. {
  247. numIncidentEdges--;
  248. }
  249.  
  250. @Override
  251. public String toString()
  252. {
  253. return element.toString();
  254. }
  255.  
  256. }
  257. }
Add Comment
Please, Sign In to add comment