git@github.swarthmore.edu:CS35-F23/lab09-<your-teamname>
Due Wednesday, December 13 at 11:59pm .
The goals of this lab are to apply graph data structures to implement several graph algorithms and to use these graph algorithms to solve a number of sample applications. The objectives of this lab include:
implement a graph data structure for undirected graphs
implement graph algorithms
applying these algorithms to solve graph-based problems
This lab should reinforce the graph algorithms you learned in lecture and improve your programming skills.
As usual, you can select your partner using Teammaker.
The URL for your repository will be
git@github.swarthmore.edu:CS35-F23/lab09-<your-teamname>
The following is a description of the repository’s initial contents. Bolded files are those which you must change in completing this lab.
adts/
: As with your last two labs, the ADT interface declarations are stored here. The most notable additions for this lab are graph.h
and edge.h
.
directedGraph.h/directedGraph.cpp
: An implementation of the Graph
ADT representing a directed graph.
undirectedGraph.h/
undirectedGraph.cpp
: The UndirectedGraph
class that you will be implementing to represent an undirected graph.
graphAlgorithms.h/
graphAlgorithms.cpp
: A file containing the graph algorithms you’ll implement.
tests.cpp
: The unit testing program you will use to confirm that your UndirectedGraph
and your graph algorithms are correct.
manualTests.cpp
: A sandbox test program for you to use while you develop your programs.
wmi.cpp, oatp.cpp, cc.cpp, mst.cpp
: files for four simple applications of the graph algorithms that you’ll implement.
bat.cpp, ttp.cpp
: files for two optional extra challenge problems.
test_data/
: a directory containing several simple test files for your applications.
As usual, the adts/
directory contains the ADT declarations and
implementations for you to use in this assignment. The graph.h
and
edge.h
files are new; take a look at them.
The Graph
ADT assumes that vertices are labeled 0…n-1
. It has a
limited collection of methods: numVertices, insertEdge,
getNeighbors
, and getOutgoingEdges
. We hope this simple interface
allows you to focus on graph algorithms.
There are two implementations of the Graph ADT in your starter code:
DirectedGraph
and UndirectedGraph
. Both classes implement the
Graph ADT using adjacency lists. The latter is a subclass of the
former which changes the insertEdge
method to simulate an
undirected graph: each time an edge is added with insertEdge
, for
instance, another edge is also added in the opposite direction.
DirectedGraph
has been implemented for you. You’ll need to
implement UndirectedGraph
.
The DirectedGraph
class uses two new C++ features you haven’t seen before.
Default values to private data members. In C++
there’s a direct way to initialize values of data members in a
constructor. Example syntax from the Edge
constructor lies
below.
Edge(int src, int dest, int wt) : source(src),
destination(dest), weight(wt) {};
This code is equivalent to having the following in your constructor:
Edge(int src, int dest, int wt) {
this->source = src;
this->destination = dest;
this->weight = wt;
}
Default values for input parameters. In C++ it’s also possible to give default values for input parameters. Here is the signature for the insertEdge
method for the DirectedGraph
class:
virtual void insertEdge(int src, int dest, int weight=1);
when you insert an unweighted edge, it’s ok to just give the src and dest. g→insertEdge(4,19)
. A default weight of 1 will be assigned to this edge.
As part of this lab, you will write implementations of the following graph algorithms:
Depth-first search
Breadth-first search
Dijkstra’s algorithm
Prim’s algorithm
You will implement these algorithms in graphAlgorithms.cpp
. The
unit tests we provide in tests.cpp
are designed to help you verify
the graph algorithms are correct.
In order to motivate the graph algorithms you write and illustrate the diversity of applications that use graph algorithms, you will be implement the following programs:
Note: All of these problems come from Kattis, a popular site for competitive programming and for technical interview preparation. Kattis problem descriptions all have a particular format, and the way to call Kattis-style programs is a bit different from what you’ve been doing so far this semester, so it’s worth understanding the format before going into an implementation.
Each of the problem descriptions linked above have the same format:
Problem Description. This section provides some flavor text describing the problem you want to solve at a high level.
Input. This section defines exactly how the input is formatted.
Output. This section defines what your program is supposed to output.
Sample Input/Output. This section gives one or more sample inputs. Also, for each sample input this section shows what the program is to output.
Note: Instead of using file I/O, each application takes inputs from
standard input (i.e., cin
) and should output to standard output
(i.e., cout
). While not required, but when you are implementing
your applications, it might be useful to create a helper function
that reads the input in from standard input, creates a new Graph from
the data you read in, and returns a pointer to the Graph you create.
As an example, we’ve given you a loadGraph
helper function for the
"Where’s My Internet??" problem in wmi.cpp
:
Graph* loadGraph(int n, int m) {
int src,dest;
// Graph stores vertices 0...n-1, but input uses vertices 1...n
// so create a graph with an extra vertex
Graph *g = new UndirectedGraph(n+1);
for (int i =0; i<m; i++) {
cin >> src >> dest;
g->insertEdge(src,dest);
}
return g;
}
You are welcome but not required to have a Kattis account to complete this lab. One feature of Kattis is that you can submit solutions to Kattis problems, and it will be automatically tested by an "online judge" which provides a very limited range of feedback. The testing suite is much more extensive than the unit tests provided in your git repo.
A downside is that Kattis expects your entire program to consist of
a single .cpp
file. In order to test your lab solutions, you’d need
to merge all the files you use into a single .cpp
program.
When writing Dijkstra’s algorithm, you will need a min-heap. Although we haven’t used it before, such a heap is provided in the adts
directory in the file stlMinPriorityQueue.h
.
Once you’ve implemented and tested the graph algorithms, each application program should be pretty simple: read in the input, call one of the graph algorithms, and use that to print the correct output.
Read each application specification carefully. They tell you exactly what the input should look like and exactly what to output. Some of the applications assume vertices are numbered 0…n-1, but some assume 1…n. One way to handle vertices labeled starting from 1 is to create an n+1 vertex graph, and have a dummy vertex "0" which isn’t connected to anything.
For oatp
, understanding how many color changes Alice can force Bob to make can be subtle. Hint: Consider the BFS search tree. What would happen if Alice colored the edges in successive layers different colors?
While the applications you write must get input from cin
, it can be
helpful during testing to use files containing the input you want to
test, and to redirect the file’s contents to standard input using
the Unix redirect symbol '<'
. For example, to test your solution to
"Where’s My Internet??" on the first input file, run
./wmi < test_data/wmi-in1
Your code must run without any memory errors; make sure to use valgrind
to find them. Memory leaks, on the other hand, are acceptable in small amounts and will not significantly impact your grade. In particular, your application should not leak more memory the longer the game is played; applications which leak constant memory will not be penalized, while applications that leak non-constant memory (e.g. more memory after each move) will be penalized slightly.
For students looking for an extra challenge, we encourage you to implement the following additional applications:
Some notes for the extra challenge problems:
Both of these problems assume that vertices are labeled with strings
instead of being integers 0…n-1
. You’ll need to think creatively
how to handle this. One suggestion is to create a new graph class
which maintains a hash table mapping integers to string labels.
For these problems, you’ll need to think carefully on how to create the graph from the given input.
When you are finished, you should have
Implementation of the UndirectedGraph
class
Implementations of the four graph algorithms
Implementations for each of the four applications.
No memory errors
Code which conforms to the style requirements, which includes commenting all methods and data members for any classes that you create