Compare the performance of weighted quick union, weighted quick union with path

Question

Compare the performance of weighted quick union, weighted quick union with path compression, and connected component implementation.  

a) Implement the following method inside DataGenerator, which generate the required number of vertices and edges, and save the data to the provided output file.   The format of the output file is this: the first line is number of vertices, the second line is number of edges, and the rest are vertex pairs separate by space. Please make sure there are not duplicated edges generated.

public static void generate(int numVertices, int numEdges, String outputFilePath)

8

8

0 3 1 3 1 4 2 7

3 5 3 6 3 7 4 6

b)Provide implementation for two unimplemented method in UnionClient

c)Run UnionClient and put your results in the following table.

Input

Weighted Quick Union

Weighted Quick Union with Path Compression

Connected Component

V=100, E=100

V=100, E=2500

V=100, E=4800

V=1000, E=1000

V=1000, E=250000

V=1000, E=480000

V=10000, E=10000

V=10000, E=25000000

V=10000, E=48000000

public class DataGenerator {
  
   /**
   * Given number of vertices and edges as well as output file path as inputs,
   * this method use some random algorithm to generate vertex pairs (edges)
   * and save the data to the output file. The results should not have duplicated
   * vertex pairs (edges). input_1.txt is an example output file, where first line
   * contains the number of vertices, and it is followed by numEdges vertex pairs (edges).
   * Only space or new line should be used as delimiters.
   */
   public static void generate(int numVertices, int numEdges, String outputFilePath) {
      
   }

}

Input

Weighted Quick Union

Weighted Quick Union with Path Compression

Connected Component

V=100, E=100

V=100, E=2500

V=100, E=4800

V=1000, E=1000

V=1000, E=250000

V=1000, E=480000

V=10000, E=10000

V=10000, E=25000000

V=10000, E=48000000

Explanation / Answer

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.util.Random;

public class DataGenerator {
public static void main(String[] argv){
   generate(8,8,"edges.txt");
}
/**
* Given number of vertices and edges as well as output file path as inputs,
* this method use some random algorithm to generate vertex pairs (edges)
* and save the data to the output file. The results should not have duplicated
* vertex pairs (edges). input_1.txt is an example output file, where first line
* contains the number of vertices, and it is followed by numEdges vertex pairs (edges).
* Only space or new line should be used as delimiters.
*/
public static void generate(int numVertices, int numEdges, String outputFilePath) {
   BufferedWriter bw = null;
       FileWriter fw = null;

int[][] edges = new int [numEdges][2];
int count=0;
Random rand = new Random();
  
while(true){
   int x = Math.abs(rand.nextInt())%numVertices;
   int y = Math.abs(rand.nextInt())%numVertices;
   if(x==y)
       continue;
   boolean isExit = false;
   for(int i=0;i<count; i++){
       if((edges[i][0]==x && edges[i][1]==y)||(edges[i][0]==y && edges[i][1]==x)){
           isExit = true;
           break;
       }
   }
   if(isExit)
       continue;
   edges[count][0] = x;
   edges[count][1] = y;
   count++;
   //System.out.println(count+"="+x+" "+y);
  
   if(count>=numEdges)
       break;
}
try {
   fw = new FileWriter(outputFilePath);
           bw = new BufferedWriter(fw);
          
   bw.write(""+numVertices+" ");
   bw.newLine();
   bw.write(""+numEdges+" ");
   bw.newLine();
   for(int i=0; i<numEdges; i++){
           bw.write(edges[i][0]+" ");
       }
       bw.write(" ");
       bw.newLine();
       for(int i=0; i<numEdges; i++){
           bw.write(edges[i][1]+" ");
       }
       if (bw != null)
               bw.close();

           if (fw != null)
               fw.close();
}
catch(Exception e){
  
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.