Advertisement
Guest User

Untitled

a guest
Nov 28th, 2014
200
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.66 KB | None | 0 0
  1. public boolean contractEdge(V vertex1, V vertex2) {
  2. //First makes sure that both vertices are in the graph.
  3. if (!adjList.containsKey(vertex1) || !adjList.containsKey(vertex2))
  4. return false;
  5. //Then makes sure there is at least one edge between them.
  6. if (this.getEdge(vertex1, vertex2) != -1 ||
  7. this.getEdge(vertex2, vertex1) != -1) {
  8. //This checks to see which vertex is bigger.
  9. if (vertex1.compareTo(vertex2) < 0) {
  10. //The following for each loops handles the outgoing, then the
  11. //incoming edges for the vertices.
  12. for (V v : adjList.get(vertex2).keySet()) {
  13. //This if statement prevents the method from adding a self
  14. //reference.
  15. if (v.compareTo(vertex1) != 0) {
  16. //The next if statement picks the larger of the two
  17. //edges, if there are two of them present.
  18. if (this.getEdge(vertex2, v) >
  19. this.getEdge(vertex1, v)) {
  20. this.addEdge(vertex1, v, this.getEdge(vertex2, v));
  21. } else {
  22. this.addEdge(vertex1, v, this.getEdge(vertex1, v));
  23. }
  24. }
  25. }
  26. //Incoming block:
  27. for (V v : adjList.keySet()) {
  28. //If block to prevent self reference.
  29. if (adjList.get(v).keySet().contains(vertex2) &&
  30. v.compareTo(vertex1) != 0) {
  31. //If statement that checks the edge sizes to find the
  32. //larger of the two.
  33. if (this.getEdge(v, vertex2) >
  34. this.getEdge(v, vertex1)) {
  35. this.addEdge(v, vertex1, this.getEdge(v, vertex2));
  36. } else {
  37. this.addEdge(v, vertex1, this.getEdge(v, vertex1));
  38. }
  39. }
  40. }
  41. //Removes the smaller of the two parameter vertices and
  42. //returns true.
  43. this.removeVertex(vertex2);
  44. return true;
  45.  
  46. } else {
  47.  
  48. //These two for each loops handle the vertices if vertex2 is
  49. //larger than vertex1. It works in exactly the same way as
  50. //above, except the vertices are switched around.
  51. for (V v : adjList.get(vertex1).keySet()) {
  52. if (v.compareTo(vertex2) != 0) {
  53. if (this.getEdge(vertex1, v) >
  54. this.getEdge(vertex2, v)) {
  55. this.addEdge(vertex2, v, this.getEdge(vertex1, v));
  56. } else {
  57. this.addEdge(vertex2, v, this.getEdge(vertex2, v));
  58. }
  59. }
  60. }
  61. for (V v : adjList.keySet()) {
  62. if (adjList.get(v).keySet().contains(vertex1) &&
  63. v.compareTo(vertex2) != 0) {
  64. if (this.getEdge(v, vertex1) >
  65. this.getEdge(v, vertex2)) {
  66. this.addEdge(v, vertex2, this.getEdge(v, vertex1));
  67. } else {
  68. this.addEdge(v, vertex2, this.getEdge(v, vertex2));
  69. }
  70. }
  71. }
  72. this.removeVertex(vertex1);
  73. return true;
  74. }
  75. }
  76. //Final return false statement.
  77. return false;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement