Project 4 Minimum Spanning Tree (MST)

1
ECE250: Lab Project 4

1. Project Description
The goal of this project is to write a C++ implementation for the Minimum Spanning Tree
(MST) on a weighted undirected graph, using Kruskal’s Algorithm. We consider the n
nodes in the graph to be numbered from 0 to n – 1. This means a graph with 4 nodes has
nodes named 0, 1, 2 and 3. Each edge has a weight (a positive number of double type)
associated with it. You can represent the graph as an adjacency matrix or an adjacency list.
In order to build the minimum spanning tree T, the Kruskal’s algorithm adds one edge to the
T (initialized with an empty graph) in each step. To make sure that this procedure does not
form loops in the tree, we need to keep track of the connected components of T. In your
implementation you will write a Disjoint sets class to assist you with this task. Disjoint sets is
a well-known data structure for grouping n elements (nodes) into a collection of disjoint sets
(connected components). You can read more information on disjoint sets from the
corresponding course slides (week 12) as well as Chapter 21 of CLRS book. It is recommend to
write the disjoint sets using linked lists.
2. Program Design
Write a short description of your design. You will submit this document along with your C++
solution files for marking. This document must include your design decisions. Please refer to
the course website for “Programming Guidelines” and the expected content for your design
document.
3. Project Requirements
Write a test program (named msttest.cpp) that will read commands from standard input
and write the output to standard output. The program will respond to the commands
described in this section.
Command Parameters Description Output
n m m is the number of nodes.
Note: This is always the
first command and never is
called again.
success
failure*
If m < 0.
i u;v;w Inserts an edge between
nodes u and v with weight
w (a double type).
success
If the insertion was
successful. If there is already
an edge connecting u and v,
this command will update
the weight for the edge.
failure*
If u or v are outside the valid
range, or w <= 0.
2
Command Parameters Description Output
d u;v Deletes the edge between
nodes u and v.
success
If the deletion was
successful.
failure
If there is no edge
connecting u and v.
failure*
If u or v are outside the valid
range.
degree u Returns the degree of
vertex u.
degree of u is d_u
If node u is a valid node.
failure*
If u is outside the valid
range.
edge_count Returns the total number of
edges in the graph.
edge count is n_edges
For an empty graph, the edge
count is 0.
clear Removes all the edges from
the graph.
success
mst Calculates the minimum
spanning tree and returns
its total weight.
mst weight
not connected
If the graph is not connected.
* Failure must be detected by handling an exception. That is, the tree function will “throw” an
exception and the driver will “catch” the exception, creating the output “failure” for these
cases. You can define an exception class called “illegal_argument” to be used for these cases.
The time complexity of Kruskal’s algorithm depends on the implementation of the disjoint-set
data structure. Implement mst command with the best possible running time based on your
disjoint-set data structure. You can refer to Chapters 21 and 23.2 from CLRS for the running
time that you need to add to your design document.
• Test Files
The course website contains example input files for the corresponding output files. The files
are named test01.in, test02.in and so on with the output files named test01.out, test02.out
and so on.
4. How to Submit Your Program
Once you have completed your solution and tested it comprehensively on your computer, you 
3
have to transfer your files to the eceUbuntu server and test there since we perform the
automated testing using this environment. Once you finish testing in the eceUbuntu server,
you will create a compressed file (tar.gz) that should contain:
• A typed document (maximum three pages) describing your design. A document beyond
3 pages will not be marked. Submit this document in PDF format. The name of this file
should be:
xxxxxxxx _design_ pn.pdf in which xxxxxxxx is your UW user id (e.g., jsmith) and n
is the project number that is 4 (four) for this submission.
• A test program (msttest.cpp) that reads the commands and writes the output.
• Required header files and classes (ending in .h .hpp .cpp).
• A make file (named Makefile), with instructions on how to compile your solution and
create an executable file named mstdriver
The name of your compressed file should be xxxxxxxx_pn.tar.gz, where xxxxxxxx is your
UW user id (e.g., jsmith) and n is the project number that is 4 (four) for this submission.