CS35: Lab 9: Graph Algorithms and Applications

Due Friday, May 3 at 11:59pm.

Overview

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.

Starting Code

As usual, you can select your partner using Teammaker.

The URL for your repository will be

git@github.swarthmore.edu:CS35-S24/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.

Graph ADT

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.

New C++ features

The DirectedGraph class uses two new C++ features you haven’t seen before.

  • Default values to 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.

Calling parent class methods from child class

Sometimes, when you write methods for a child class, you’ll have need to explicltly call a method defined in a parent class. To do this, prepend the method name with the name of the parent class and double colons.

The following code snippet gives an example:

class Parent {
public:
  virtual void print();
};

void Parent::print() {
  cout << "parent" << endl;
}

class Child : public Parent {
public:
  void print();
};

void Child::print() {
  Parent::print(); // calls print method in Parent class
  cout << "child" << endl;
}

In this example, if you create a Child object and call it’s print method, then the output would be

parent
child

Graph Algorithms

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.

Graph Applications

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;
}

Kattis

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.

Advice

blueprints

OpenClipArt.org

  1. 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.

  2. 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.

  3. 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.

  4. 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?

Testing

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

Memory

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.

Extra Challenge Problems

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.

Summary of Requirements

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