Description
Overview
In this project, you must design and implement a graph data structure to store a weighted, undirected graph. In addition, you will
design and implement an efficient algorithm to find a Minimum Spanning Tree (MST) of the graph. You must implement this algorithm
in, at worst, O(|E|log(|V|)) time, where |E| is the number of edges in the graph and |V| is the number of vertices.
Datasets
We have provided some datasets for your use and a python script to generate more. A video has been uploaded to Learn to show you
how to read the datasets and use the python script. These datasets represent power stations, which are numbered from 1 to N, and
the cost of connecting those power stations to neighbouring stations. The datasets all have the same format as following:
• On the first line is N, the number of power stations in the dataset.
• On next lines are edges between power stations, one edge per line. These edges are given in a space-separated values format
like: i j W where i is the number of the first power station, j is the number of the second, and W is the weight between
them representing the cost of connecting the two stations. You may assume that i, j, and W are all integers greater than 0
(so 0 is not included). You may assume that the “int” data type is sufficient to store them.
By computing an MST on this graph, your design and implementation produce a minimum-cost power grid.
Program Design and Documentation
You must use proper Object-Oriented design principles to implement your solution. You will create a design using classes which have
appropriately private/protected data members and appropriately public services (member functions). It is not acceptable to simply
make all data members public. Structs are not permitted. You may notice that you are writing a generic graph implementation for
this project. A Tree is a graph without a cycle. Therefore, it may be a good idea to use a single graph class to represent both the power
grid and the MST. This is not a requirement, but it is a nice design decision to simplify your code.
Write a short description of your design to be submitted along with your C++ solution files for marking according to the template
posted to Learn. You may use the following libraries from the STL and all of their associated functionality: vector and tuple.
Input/Output Requirements
In this project, you must create a test program that must read commands from standard input and write the output to standard output.
The commands are described below.
Note: In order for the MST to be unique, the graph must be connected with unique edge weights. You may assume that the LOAD
command always produces such a graph. However, the INSERT command may not, and the DELETE command may change the graph
so that the unique MST conditions are not met. The MST command below will only be called on connected graphs with unique weights.
Command Parameters Description Expected Runtime (worst case) Output
LOAD filename Load a dataset into a graph.
This command may not be present in all
input files. If it is, you may assume that it
is the first command in the input file. You
may assume there are no illegal
arguments in the datasets. You may
assume that, if this command is used, it
will be used only once per input file.
N/A – this depends on your
implementation and the
dataset size. Do not analyze
this function.
success
Note: This command
should output “success”
no matter what. It
should not output one
“success” per vertex.
2
Command Parameters Description Expected Runtime (worst case) Output
INSERT a b w Insert a new edge into the graph from
vertex a to vertex b with weight w. If
either a or b are not in the graph, add
them. Valid values a and b will be positive
integers between 1 and 50000 inclusive
and valid values of w will be a positive
integer weight greater than 0
Depends on your
implementation. Analysis is
expected. See below.
success
if the insertion was
successful
failure
if the edge is already in
the graph, regardless of
weight
illegal argument (see
below the table)
PRINT a Print all vertices adjacent to vertex a.
Valid values for a will be a positive
integer between 1 and 50000. The order
in which you print the vertices is not
important. The Autograder will be
programmed to handle any ordering.
O(degree(a)) b c d …
Print all vertex numbers
adjacent to a on a single
line with spaces
between them, followed
by a newline character.
failure
if vertex a is not in the
graph
illegal argument (see
below the table)
DELETE a Delete the vertex a and any edges
containing a. Note that this means you
will need to remove the vertex a from the
edge set of all vertices adjacent to a. This
command may produce an unconnected
graph.
Depends on your
implementation
success
if the vertex is in the
graph and was erased
failure
if the vertex is not in the
graph, including the case
where the graph is
empty
illegal argument (see
below the table)
MST Find the MST of the graph. You may
assume that the graph is connected.
Note: This command must output the
list of edges in the MST. The output
should contain all the edges on a single
line, separated by spaces. Each edge
should be displayed in the format of
vertex 1, vertex 2, and weight. The order
in which the edges are printed is not
important, as long as each edge is
displayed in the correct format, the
autograder will figure it out.
O(|E|log(|V|)) to find the
MST. Do not consider printing
as part of this algorithm.
|E|= number of edges in the
graph
|V|=number of vertices in the
graph
V1 V2 W12 V3 V4 W34
V1 V4 W14…
where Vi, Vj, and Wij are
the integers
representing the
vertices and weight of
the edge.
failure
if the graph is empty.
COST Determine the cost (the sum of the
weights) of the power grid computed via
the MST. You may assume the cost will
never overflow an int on eceubuntu.
O(|E|log(|V|)) (why?) cost is x
where “x” is the cost of
the grid. Note that x may
be 0 if the graph is
empty
3
Command Parameters Description Expected Runtime (worst case) Output
END Last command for all input files. This command does not
print any output
Illegal arguments: For the commands INSERT, PRINT, and DELETE, you must handle invalid input. A vertex is invalid if it is larger than
50000 or less than or equal to 0. A weight is invalid if it is less than or equal to 0. No other types of invalid input will be tested. All
invalid input will fit into an “int” datatype. Your code must throw an illegal_argument exception, catch it, and output “illegal
argument” (without quotes) if it is caught. You may assume that the only type of invalid input will be integers outside of the range. To
do this, you will need to:
a. Define a class for this exception, call it illegal_exception
b. Throw an instance of this class when the condition is encountered using this line:
throw illegal_exception();
c. Use a try/catch block to handle this exception and print the desired output of the command
You must analyze the worst-case runtime of your algorithms in your design document. Prove that your implementation achieves these
runtimes. For vertex insertion and deletion, this runtime is dependent on your implementation. Analyze your own implementation
and discuss the worst-case runtime.
Valgrind and Memory Leaks
20% of your grade in this project will be allocated to memory leaks. We will be using the Valgrind utility to do this check. The expected
behaviour of Valgrind is to indicate 0 errors and 0 leaks possible, with all allocated bytes freed. To test your code with Valgrind,
presuming you are using an input file test01.in, you would use the following command:
valgrind ./a.out < test01.in
Test Files
Learn contains some sample input files with the corresponding output. The files are named test01.in, test02.in and so on with their
corresponding output files named test01.out etc. All test files are provided as-is. Your code must be able to parse them.
Submitting your Program
Once you have completed your solution and tested it comprehensively on your own computer or the lab computers, you should
transfer your files to the eceUbuntu server and test there. We perform automated tested on this platform, so if your code works on
your own computer but not on eceUbuntu it will be considered incorrect. A makefile is required for this project since the exact source
structure you use will be unique to you. Do not submit the dataset or precompiled binaries.
Once you are done your testing you must create a compressed file in the tar.gz format, that contains:
– A typed document, maximum of four pages, describing your design. Submit this document in PDF format. The name of this
file should be xxxxxxxx_design_pn.pdf where xxxxxxxx is your maximum 8-character UW user ID (for example, I would use my
ID “mstachow”, not my ID “mstachowsky”, even though both are valid UW IDs), and n is the project number. In my case, my
file would be mstachow_design_p4.pdf.
– A test *.cpp file that contains your main function that reads the commands and writes the output
– Required header files that you created.
– Any additional support files that you created. Do not submit any input files.
– A makefile, named Makefile, with commands to compiler your solution and creates an executable. Do not use the -o output
flag in your makefile. The executable’s name must be a.out.
The name of your compressed file should be xxxxxxxx_p4.tar.gz, where xxxxxxxx is your UW ID as above.
