Programming Assignment III: Minimum-cost Spanning Trees

Input	Correct Output	Description
Complete	Answer	A large complete graph. This test was the basis for the performance score. The fastest scores were in the 25-30ms range. Anything less than 50ms is excellent, and anything less than 100ms still earns "full credit" for performance.
Grid	Answer	A medium-sized grid graph, as from the provided tests.
Small	Answer	A very small, hand-made graph with 8 vertices and 13 edges. Tests performance on graphs with multiple edges with the same weight, and graphs with a wide range of weights. This is the only graph in the set with a non-unique solution.
Regular	Answer	A medium-sized |V|/2-regular graph, as from the provided tests.

Introduction

Files

makefile

A makefile for the project

mcst.cpp

The main program, which will time your routine. In order to use this file, you will have to fill in one routine, do_MCST(). This function should compute the minimum-cost spanning tree for the graph it is given. Exact details of the parameters are given in the file.

Note: The benchmark files are quite large. In order to prevent unnecessary copying, I have placed public copies in

          ~dfasulo/cse326/mcstbench

Instructions

1. Get the makefile and mcst.cpp above.

2. It is your responsibility to fill in the function do_MCST(). You can add any additional files to the project you want; for example, you will probably want to separately create a graph class to make writing the algorithm easier.

3. The graphs in this assignment have vertices labeled 0...(V-1), where V is the number of vertices in the graph. Thus, edges have the form (i, j, w) where 0 <= i, j < V and 0 <= w < E, with E being the number of edges. The graph is undirected, so the order of i and j are irrelevant.

4. The provided main program reads a graph from the standard input (cin) in the form

              V
              E
              i1 j1 w1
              i2 j2 w2
              ...
         

   For each edge, there is exactly one entry; hence, if there is an edge from vertex 1 to vertex 3 with weight 7 and there is an entry of the form

              1 3 7
         

   then there is no entry

              3 1 7
         

   After calling your algorithm, the program then prints out a list of edges in the MCST to standard out (cout) and also a message about the running time of the algorithm to the standard error device (cerr). This is convenient because you can run your program in the following way:

              mcst < mygraph > mygraph-result
         

   This will place the edges of the MCST into mygraph-result but print the running time of the algorithm to the console.

5. The table above has several benchmark graphs upon which to test your program. If the running time of your algorithm on sanjuan or orcas is faster than the one listed above and the output is correct (the MCST for each of these graphs is unique), then send me mail with the running time and a short description of your method (i.e., Kruskal's algorithm, Prim's algorithm, Smallest Component First, etc.) and I will publish the new result. My results were generated with a very basic, naive implementation and should be pretty easy to beat.

   The program will be judged partially on effort, so more sophisticated, faster algorithms will receive more credit than very naive implementations.

   Tip: Be more concerned with algorithmic improvements than hand-optimizing your C++ code (i.e., trying to eliminate assignment statements, etc.). Once you have a working program, you can compile with the g++ optimization flag -O2 to perform many source-level optimizations for you.

Turnin

1. As usual, you will submit your program electronically and turn in a hard copy on the due date. Your electronic submission is required to compile and run on sanjuan and orcas.

2. You will also turn in a short written description of your algorithm. Be sure to point out any enhancements you have made to make the program run more quickly.