CPSC 035: Lab 9: Maps as Graphs

Due on Wednesday, April 27th (by the end of the day, U.S. Eastern Time).

Overview

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

Map of Swarthmore College’s 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-s22/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 make a graph to represent the college map. Your graph should contain the following vertices:

SCI
SING
TROT
BER
KOHL
PAR
LPAC
MAR
SHAR
CLOT
WHAR

And, the following edges:

{SCI, SING} weight 3
{SING, TROT} weight 5
{SCI, BER} weight 4
{SING, BER} weight 2
{SCI, MAR} weight 6
{MAR, LPAC} weight 3
{LPAC, KOHL} weight 2
{BER, KOHL} weight 2
{PAR, KOHL} weight 4
{TROT, KOHL} weight 3
{SHAR, CLOT} weight 4
{WHAR, SHAR} weight 5
{CLOT, WHAR} weight 4

Make the graph 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 11 vertices and 13 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 campus
1. Reachability from one building to another
2. Shortest length path from one building to another
3. Distances from one building to all other reachable buildings
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.

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 campus
1. Reachability from one building to another
2. Shortest length path from one building to another
3. Distances from one building to all other reachable buildings
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 SHAR CLOT WHAR

Let's explore Swarthmore's campus
1. Reachability from one building to another
2. Shortest length path from one building to another
3. Distances from one building to all other reachable buildings
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.

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 campus
1. Reachability from one building to another
2. Shortest length path from one building to another
3. Distances from one building to all other reachable buildings
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.

If no such path exists, then you must print "NO PATH EXISTS".

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 campus
1. Reachability from one building to another
2. Shortest length path from one building to another
3. Distances from one building to all other reachable buildings
0. Quit
Choice: 3

Enter the building to start from: KOHL
Distance from KOHL to all other reachable 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 priority 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

Website created by Zachary Palmer and Michael Wehar, Swarthmore College, 2022