CS35: Lab 9: Maps as Graphs

Due Wednesday, December 8th at 11:59pm.

Overview

In this lab, you will develop your understanding of graphs and graph algorithms. You will do this by implementing the three algorthims we discussed in class and apply them to exploring the map of Swarthmore College’s north campus. You will then provide written examples of how some of these graph algorithms work.

Map of Swarthmore College’s north campus

Part I: Implementing Graph Algorithms

As usual, you can find a link to your GitHub repository on Teammaker.

The URL for your repository will be

git@github.swarthmore.edu:cs35-f21/lab09-<your-teamname>

Your starting repository contains the following files. The bold files are the ones you will need to implement:

  • adjacencyListGraph.h and adjacencyListGraph-inl.h: An implementation of a directed, labeled, weighted graph in the form of a template class.

  • adjacencyListUndirectedGraph.h and adjacencyListUndirectedGraph-inl.h: An implementation of an undirected, labeled, weighted graph in the form of a template class.

  • adts/: As usual, this directory contains the definitions of ADT interfaces as well as supplied implementations of the ADTs we’ve previously discussed.

  • graphAlgorithms.h/graphAlgorithms-inl.h: The definitions of the graph search algorithms you will implement.

  • main.cpp: Where you will write the main program for this lab.

Make sure you have examined adts/graph.h to understand the interface you will be using in this lab.

Step 0: Main

For this final lab assignment of the semester, we are allowing you to design your main program as you see fit. However, you must have helper functions so that your main program is concise and easy to understand. You should declare your helper functions by using function prototypes above the definition of the main program. You should incrementally add to your main program as you make progress on implementing the graph algorithms.

In main.cpp create a graph to represent the college map as shown above. Do this by creating a new instance of the AdjacencyListUndirectedGraph class and then calling the graph’s insertVertex and insertEdge methods. For an undirected graph, you only need to insert the edge between any two vertices one time. There are 8 vertices and 10 edges in this graph.

Next, your main program should provide the user with a menu to allow them to interact with the graph associated with the College map:

$ ./main

Let's explore Swarthmore's north campus
1. Reachability from one building to another
2. Shortest length path from one building to another
3. Distances from one building to all others
0. Quit
Choice:

The menu should ensure that the user types in a valid integer 0-3. You may assume that the user always provides an integer. The menu should be repeatedly presented until the user chooses to quit.

Once your menu is working and your graph is created, start working on the graph algorithms.

Step 1: Depth-First Search

In graphAlgorithms-inl.h implement reachableDFS.

Then in your main program add the functionality to allow the user to call this function:

Let's explore Swarthmore's north campus
1. Reachability from one building to another
2. Shortest length path from one building to another
3. Distances from one building to all others
0. Quit
Choice: 1

Enter the first building: Martin
Martin is not a vaild building code
The building codes are: Par Trot Kohl Sing Ber LPAC Mar Sci

Let's explore Swarthmore's north campus
1. Reachability from one building to another
2. Shortest length path from one building to another
3. Distances from one building to all others
0. Quit
Choice: 1

Enter the first building: Mar
Enter the second building: Sing
Sing is reachable from Mar

You must ensure that the user provides a valid building code. If they make a mistake, you should list out all of the valid building codes, as shown above.

Step 2: Breadth-First Search

In graphAlgorithms-inl.h implement shortestLengthPathBFS.

Then in your main program add the functionality to allow the user to call this function:

Let's explore Swarthmore's north campus
1. Reachability from one building to another
2. Shortest length path from one building to another
3. Distances from one building to all others
0. Quit
Choice: 2

Enter the first building: Sci
Enter the second building: Trot
The shortest length path is: Sci Sing Trot

Again, you must ensure that the user provides a valid building code.

Remember that BFS will find the path with the fewest links, not the cheapest one.

Step 3: Single Source Shortest Path

In graphAlgorithms-inl.h implement singleSourceShortestPath.

Then in your main program add the functionality to allow the user to call this function:

Let's explore Swarthmore's north campus
1. Reachability from one building to another
2. Shortest length path from one building to another
3. Distances from one building to all others
0. Quit
Choice: 3

Enter the building to start from: Kohl
Distance from Kohl to all other buildings
Sci:6
Mar:5
LPAC:2
Trot:3
Par:4
Ber:2
Sing:4
Kohl:0

Again, you must ensure that the user provides a valid building code.

Once your main program is functioning correctly, you are ready to move on to the written portion of the assignment.

Part II: Written Assignment

Give your answers to the following questions in a file named WrittenLab.pdf. You may use the provided WrittenLab.tex file; running make WrittenLab.pdf will produce your document. You may also use some other program to generate the document.

Example graph

  1. Perform a breadth-first search of the graph starting from vertex A. Give the number of steps to reach every other vertex. Additionally, give the order in which the vertices are first witnessed; that is, give the order in which they first enter the queue (and not necessarily the order in which they are explored).

  2. Use Dijkstra’s algorithm (for finding single source shortest paths) on this graph starting from vertex A. Give the cost of the least-cost path to every other vertex. Additionally, give the order in which the vertices are first witnessed; that is, give the order in which they first enter the queue (and not necessarily the order in which they are explored).

  3. Give two valid topological sorts of this graph.

Summary of Requirements

When you are finished, you should have

  • An implementation of the three graph algorithms

  • A main.cpp program that meets the specifications detailed above

  • No memory errors or leaks

  • A write-up answering the above graph algorithm questions