uopspop

Untitled

Sep 28th, 2019
141
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_UNIONFIND {
  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_UNIONFIND(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_UNIONFIND kruskal(GraphAdjacentMatrix_MST_kruskal_UNIONFIND gam) {
  183.  
  184.         Set<EdgeElemnt> edgeElemnts = gam.extractEdgeElement(1);
  185.  
  186.         GraphAdjacentMatrix_MST_kruskal_UNIONFIND 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_UNIONFIND kruskal(Set<EdgeElemnt> edgeElemnts, int numOfVertices) {
  192.  
  193.         // result
  194.         GraphAdjacentMatrix_MST_kruskal_UNIONFIND MST = new GraphAdjacentMatrix_MST_kruskal_UNIONFIND(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.         // prepare the subsets for the UNION-FIND strcuture
  202.         int[] subsets_parent = new int[numOfVertices];
  203.         int[] subsets_rank = new int[numOfVertices];
  204.         for (int i = 0; i < numOfVertices; i++) {
  205.             subsets_parent[i] = i; // in the very beginning, every vertice is its own subset
  206.             subsets_rank[i] = 0;
  207.         }
  208.  
  209.         // Remove items from the Priority Queue (DEQUEUE)
  210.         while (!minHeap.isEmpty()) {
  211.             EdgeElemnt ee = minHeap.remove();
  212.  
  213.             // check if vertices are in the MST already - use UNION-FIND structure
  214.             int parentV1 = MST.find(subsets_parent, ee.v1); // O(log(|E|))
  215.             int parentV2 = MST.find(subsets_parent, ee.v2); // O(log(|E|))
  216.             if (parentV1 == parentV2) {
  217.                 System.out.printf("FIND: %d and %d have the same parent %d  %n", ee.v1, ee.v2, parentV1); // debug purpose only
  218.                 continue;
  219.             }
  220.  
  221.             // add vertices to the MST
  222.             MST.setEdge(ee.v1, ee.v2, ee.edgeWeight);
  223.             MST.setEdge(ee.v2, ee.v1, ee.edgeWeight);
  224.  
  225.             // update the UNION-FIND structure
  226.             MST.union(subsets_parent, subsets_rank, parentV1, parentV2); // O(1)
  227.  
  228.             totalWeight += ee.edgeWeight;
  229.  
  230. //            System.out.printf("MST(total_w: %d):%n%s %n", totalWeight, MST);
  231.         }
  232.  
  233.         System.out.printf("MST(total_w: %d):%n%s %n", totalWeight, MST);
  234.         return MST;
  235.     }
  236.  
  237.     private void union(int[] subsets_parent, int[] subsets_rank, int parentV1, int parentV2) {
  238.  
  239.         int from = 0; // debug purpose only
  240.         int to = 0; // debug purpose only
  241.  
  242.         if (subsets_rank[parentV1] == subsets_rank[parentV2]) {
  243.             // randomly pick one as the parent
  244.             subsets_parent[parentV2] = parentV1;
  245.             subsets_rank[parentV1]++;
  246.             from = parentV1; to = parentV2;
  247.  
  248.         } else if (subsets_rank[parentV1] > subsets_rank[parentV2]){
  249.             subsets_parent[parentV2] = parentV1;
  250.             from = parentV1; to = parentV2;
  251.         } else if (subsets_rank[parentV1] < subsets_rank[parentV2]) {
  252.             subsets_parent[parentV1] = parentV2;
  253.             from = parentV2; to = parentV1;
  254.         }
  255.  
  256.         System.out.printf("UNION: %d -> %d  %n", from, to); // debug purpose only
  257.     }
  258.  
  259.     private int find(int[] subsets_parent, Integer v1) {
  260.  
  261.         if (subsets_parent[v1] == v1) return v1;
  262.  
  263.         return find(subsets_parent, subsets_parent[v1]);
  264.  
  265.     }
  266.  
  267.  
  268.     ////////// UTIL ///////////
  269.  
  270.     private static void printArray(int[] ary){
  271.         for (int i = 0; i < ary.length; i++) {
  272.             System.out.printf("%4d" , ary[i]);
  273.         }
  274.         System.out.println();
  275.     }
  276.  
  277.  
  278.  
  279.     public static void main(String[] args) {
  280.         GraphAdjacentMatrix_MST_kruskal_UNIONFIND gam = new GraphAdjacentMatrix_MST_kruskal_UNIONFIND(7);
  281.         // undirected graph
  282.         gam.setEdge(1,2, 5); gam.setEdge(2,1, 5);
  283.         gam.setEdge(1,3, 6); gam.setEdge(3,1, 6);
  284.         gam.setEdge(1,4, 4); gam.setEdge(4,1, 4);
  285.         gam.setEdge(2,3, 1); gam.setEdge(3,2, 1);
  286.         gam.setEdge(2,4, 2); gam.setEdge(3,4, 2);
  287.         gam.setEdge(3,4, 2); gam.setEdge(4,3, 2);
  288.         gam.setEdge(3,5, 5); gam.setEdge(5,3, 5);
  289.         gam.setEdge(3,6, 3); gam.setEdge(6,3, 6);
  290.         gam.setEdge(4,6, 4); gam.setEdge(6,4, 4);
  291.         gam.setEdge(5,6, 4); gam.setEdge(6,5, 4);
  292.  
  293.  
  294.         gam.kruskal(gam);
  295.  
  296.         System.out.println();
  297.     }
  298.  
  299. }
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.

×