Program 2 - Sample Data Available Now
Topic: Union-Find and Kruskal's Minimal Spanning Tree Algorithm
A model train layout is being constructed. At various locations around the layout, lights are required. Power must be supplied to each of these locations via a pair of wires. Wire is a bit expensive, however, so we need to devise a scheme to use the least amount of wire. Rather than running a separate wire (pair) from the power source to each individual light, we decide to economize, relying on the fact that once power is received at point A, we can run a wire from point A to point B to power the light at the new point. Essentially, we need to determine what pairs of points need wires run between them so they are all interconnected in an optimal way. This is a graph problem called finding a spanning tree; in this case, a minimal weight spanning tree, where the weights correspond to the cost of the wire joining two points.
The input to your program will be a file containing all of the connection information. The first line will be a single integer, N - the number of connection points (one of which will be the power supply). The next N lines will each contain N integers representing the costs to run wires between points. This is essentially an N x N matrix. The entry in row i and column j is the cost to run a wire from point i and point j. The diagonal elements will always be 0 and the matrix will be symmetric (cost from a to b == cost from b to a).
You must determine which points to connect so there is a single path between any two points, and the overall cost of the connections is the least possible. Kruskal's algorithm is to be used to accomplish this task.
Kruskal's algorithm requires the ability to select an edge of minimum weight from a collection of remaining edges. You should use a heap structure to do this. During the execution of the algorithm, the vertices are grouped into a collection of non-empty disjoint sets (a partition). Each step of the algorithm selects an edge that connects two of the sets from this partition and unions them. This requires a disjoint set class implementing the union-find algorithm.
Create a separate class to implement the union-find structure. Actually, three separate classes will be needed as you will be implementing it three different ways and comparing efficiencies and run-times for each implementation. All implementations use the same public interface. The first implementation is the basic quick-find approach which simply associates a number with each item to identify the set to which it belongs. The second implementation is an improved quick-find that uses linked lists and list sizes to obtain better performance. The third implementation is an improved quick-union that implements path compression and union-by-size.
Your classes should have built-in record keeping capabilities. Log every step used in the find and union operations as well as the number of finds and unions that are performed. Include methods for extracting this data from the object and display it as part of the output.
Test your program on the sample data sets. Determine execution times and operation counts for each of the union-find implementations. Submit a one page report (plus supporting graphs) describing your empirical results with explanations. The output for a sample data set should display on the screen the total cost for the connections (and may report the statistics for the operation). Produce a list of the pairs of vertices that are to be connected in an output file named "wires.txt". This file will contain N-1 lines, each line a pair of integers representing a connection to be made. List edges with the smaller vertex first (3,5 not 5,3); sort the list of edges in increasing order (2,6 is before 3,4 and 2,4 is before 2,5).
Your finished project must be zipped and submitted via email by the due date. Mail the project to my grader manjeera_m@hotmail.com and CC to me margush@uakron.edu and use the subject line: DSAII Program 2 Submission. All project files must be in one folder named your_name_2. Delete or empty the Debug folder before zipping. Zip the entire project folder and contents so when I unzip it, everything is in a single folder named with your name and the project number. Please submit a printed copy of the program along with your report.