uopspop

Untitled

Sep 22nd, 2019
186
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. // shortest path
  4. public class GraphAdjacentMatrix_MST_kruskal {
  5.     public static int empty = -1;
  6.  
  7.     private int adjMatrix[][];
  8.     private int numVertices;
  9.     private boolean addedForMst[];
  10.  
  11.     public GraphAdjacentMatrix_MST_kruskal(int numVertices) {
  12.         this.numVertices = numVertices;
  13.  
  14.         adjMatrix = new int[numVertices][numVertices];
  15.         for (int i = 0; i < adjMatrix.length; i++) {
  16.             for (int j = 0; j < adjMatrix[i].length; j++) {
  17.                 adjMatrix[i][j] = empty;
  18.             }
  19.         }
  20.  
  21.         addedForMst = new boolean[numVertices];
  22.     }
  23.  
  24.     public int getNumVertices(){
  25.         return numVertices;
  26.     }
  27.  
  28.     public int getWeight(int i, int j){
  29.         return adjMatrix[i][j];
  30.     }
  31.  
  32.     public void setEdge(int i, int j, int weight) {
  33.         adjMatrix[i][j] = weight;
  34. //        adjMatrix[j][i] = true; // directed
  35.  
  36.         addedForMst[i] = true;
  37.         addedForMst[j] = true;
  38.     }
  39.  
  40.     public void delEdge(int i, int j) {
  41.         adjMatrix[i][j] = empty;
  42. //        adjMatrix[j][i] = false; // directed
  43.     }
  44.  
  45.     public boolean isEdge(int i, int j) {
  46.         return (adjMatrix[i][j] != -1);
  47.     }
  48.  
  49.     public int first(int v1){
  50.         int[] ary = this.adjMatrix[v1];
  51.         int firstNeighborIndex = this.numVertices; // return n if none
  52.         for (int i = 0; i < ary.length; i++) {
  53.             if (ary[i] != empty){
  54.                 firstNeighborIndex = i;
  55.                 break;
  56.             }
  57.         }
  58.         return firstNeighborIndex;
  59.     }
  60.  
  61.     public int next(int v1, int v2){
  62.         int[] ary = this.adjMatrix[v1];
  63.         int nextNeighborIndex = this.numVertices; // return n if none
  64.         for (int i = v2 + 1; i < ary.length; i++) {
  65.             if (ary[i] != empty){
  66.                 nextNeighborIndex = i;
  67.                 break;
  68.             }
  69.         }
  70.         return nextNeighborIndex; // return n if none
  71.     }
  72.  
  73.     public class EdgeElemnt implements Comparable{
  74.         public Integer v1;
  75.         public Integer v2;
  76.         public Integer edgeWeight;
  77.  
  78.         public EdgeElemnt(Integer v1, Integer v2, Integer edgeWeight) {
  79.             this.v1 = v1;
  80.             this.v2 = v2;
  81.             this.edgeWeight = edgeWeight;
  82.         }
  83.  
  84.         @Override
  85.         public boolean equals(Object obj)
  86.         {
  87.             if(this == obj)
  88.                 return true;
  89.             if(obj == null || obj.getClass()!= this.getClass())
  90.                 return false;
  91.  
  92.             // type casting of the argument.
  93.             EdgeElemnt geek = (EdgeElemnt) obj;
  94.             return  (geek.v1 == this.v1 && geek.v2 == this.v2) || (geek.v1 == this.v2 && geek.v2 == this.v1);
  95.         }
  96.  
  97.         @Override
  98.         public int hashCode() {
  99.             return Objects.hash(v1 + v2);
  100.         }
  101.  
  102.         @Override
  103.         public int compareTo(Object o) {
  104.             EdgeElemnt o1 = (EdgeElemnt) o;
  105.             return this.edgeWeight.compareTo(o1.edgeWeight);
  106.         }
  107.  
  108.         @Override
  109.         public String toString() {
  110.             return " " + edgeWeight;
  111. //            return "EdgeElemnt{" +
  112. //                    "fromV=" + fromV +
  113. //                    ", toV='" + toV +
  114. //                    ", edgeWeight=" + edgeWeight +
  115. //                    '}';
  116.         }
  117.     }
  118.  
  119.  
  120.  
  121.     private boolean isReachable(int vDest){
  122.  
  123.         for (int i = 0; i < numVertices; i++) {
  124.             if (this.isEdge(i, vDest)) return true;
  125.         }
  126.  
  127.         return false;
  128.  
  129.     }
  130.  
  131.     private Set<EdgeElemnt> extractEdgeElement(int vStart){
  132.         boolean[] visitedTmp = new boolean[numVertices];
  133.         Queue<Integer> queue = new LinkedList<>();
  134.         Set<EdgeElemnt> set = new HashSet<>();
  135.  
  136.         queue.add(vStart);
  137.  
  138.         while(queue.peek() != null){
  139.             Integer currV = queue.remove();
  140.  
  141.             if (visitedTmp[currV]) continue;
  142.             visitedTmp[currV] = true;
  143.  
  144.             for (int nextV = this.first(currV); nextV < this.numVertices; nextV = this.next(currV, nextV)) {
  145.                 set.add(new EdgeElemnt(currV, nextV, this.getWeight(currV, nextV))); // go check how equals() and hash() are defined for the EdgeElemnt class
  146.                 queue.add(nextV);
  147.             }
  148.         }
  149.  
  150.         return set;
  151.     }
  152.  
  153.     private boolean contains(Integer v) {
  154.         return addedForMst[v];
  155.     }
  156.  
  157.     public static class EdgeWeightComparrator implements Comparator<EdgeElemnt> {
  158.         @Override
  159.         public int compare(EdgeElemnt ee1, EdgeElemnt ee2) {
  160.             return ee1.edgeWeight.compareTo(ee2.edgeWeight);
  161.         }
  162.     }
  163.  
  164.     static <E extends Comparable<? super E>> void heapsort(E[] ary) { // Heapsort
  165.         MaxHeap<E> H = new MaxHeap<>(ary, ary.length, ary.length);
  166.     }
  167.  
  168.     public String toString() {
  169.         StringBuilder s = new StringBuilder();
  170.         for (int i = 0; i < numVertices; i++) {
  171.             s.append(i + ": ");
  172.             for (int j : adjMatrix[i]) {
  173.                 s.append((j != empty?1:0) + " ");
  174.             }
  175.             s.append("\n");
  176.         }
  177.         return s.toString();
  178.     }
  179.  
  180.     //////////// MST: kruskal algo ////////////
  181.  
  182.     public static GraphAdjacentMatrix_MST_kruskal kruskal(GraphAdjacentMatrix_MST_kruskal gam) {
  183.  
  184.         Set<EdgeElemnt> edgeElemnts = gam.extractEdgeElement(1);
  185.  
  186.         GraphAdjacentMatrix_MST_kruskal MST = kruskal(edgeElemnts, gam.getNumVertices());
  187.         return MST;
  188.     }
  189.  
  190.     // calculate the shortest distances between the startingVertice to all other vertices
  191.     public static GraphAdjacentMatrix_MST_kruskal kruskal(Set<EdgeElemnt> edgeElemnts, int numOfVertices) {
  192.  
  193.         // result
  194.         GraphAdjacentMatrix_MST_kruskal MST = new GraphAdjacentMatrix_MST_kruskal(numOfVertices);
  195.         int totalWeight = 0;
  196.  
  197.         // use minHeap to kick out the smallest edge each round
  198.         PriorityQueue<EdgeElemnt> minHeap = new PriorityQueue<>(new EdgeWeightComparrator());
  199.         minHeap.addAll(edgeElemnts);
  200.  
  201.         // Remove items from the Priority Queue (DEQUEUE)
  202.         while (!minHeap.isEmpty()) {
  203.             EdgeElemnt ee = minHeap.remove();
  204.  
  205.             // check if vertices are in the MST already
  206.             if (MST.contains(ee.v1) && MST.contains(ee.v2)) {
  207.                 if (MST.isEdge(ee.v1, ee.v2)) continue; // if the direct edge is already added in MST, skip it.
  208.                 // check if they are connected indirectly
  209.                 if (MST.isReachable(ee.v2)) continue; // no need to add as long as they are connected indirectly
  210.             }
  211.  
  212.             // add vertices to the MST
  213.             MST.setEdge(ee.v1, ee.v2, ee.edgeWeight);
  214.             MST.setEdge(ee.v2, ee.v1, ee.edgeWeight);
  215.  
  216.             totalWeight += ee.edgeWeight;
  217.  
  218.             System.out.printf("MST(total_w: %d):%n%s %n", totalWeight, MST);
  219.         }
  220.  
  221.         System.out.printf("MST(total_w: %d):%n%s %n", totalWeight, MST);
  222.         return MST;
  223.     }
  224.  
  225.  
  226.     ////////// UTIL ///////////
  227.  
  228.     private static void printArray(int[] ary){
  229.         for (int i = 0; i < ary.length; i++) {
  230.             System.out.printf("%4d" , ary[i]);
  231.         }
  232.         System.out.println();
  233.     }
  234.  
  235.  
  236.  
  237.     public static void main(String[] args) {
  238.         GraphAdjacentMatrix_MST_kruskal gam = new GraphAdjacentMatrix_MST_kruskal(7);
  239.         // undirected graph
  240.         gam.setEdge(1,2, 5); gam.setEdge(2,1, 5);
  241.         gam.setEdge(1,3, 6); gam.setEdge(3,1, 6);
  242.         gam.setEdge(1,4, 4); gam.setEdge(4,1, 4);
  243.         gam.setEdge(2,3, 1); gam.setEdge(3,2, 1);
  244.         gam.setEdge(2,4, 2); gam.setEdge(3,4, 2);
  245.         gam.setEdge(3,4, 2); gam.setEdge(4,3, 2);
  246.         gam.setEdge(3,5, 5); gam.setEdge(5,3, 5);
  247.         gam.setEdge(3,6, 3); gam.setEdge(6,3, 6);
  248.         gam.setEdge(4,6, 4); gam.setEdge(6,4, 4);
  249.         gam.setEdge(5,6, 4); gam.setEdge(6,5, 4);
  250.  
  251.  
  252.         gam.kruskal(gam);
  253.  
  254.         System.out.println();
  255.     }
  256.  
  257. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×