Lab Graphs

Assignment Description

In this lab you will:

• Use a traversal to find a particular edge in a graph.
• Find the shortest path between two vertices.
• Optional: Implement Kruskal’s minimum spanning tree algorithm.

Checking Out The Code

Download the zip file here: lab_graphs.zip and upload to the remote Linux servers.

This lab has a graph library already implemented for you; it is your job to write some functions that make use of it. These functions are contained in the namespace GraphTools, and you can implement them by editing graph_tools.h and graph_tools.cpp.

The file demo.cpp shows you how that graph class can be used, and tests.cpp calls your functions and creates output images. Some code to create some specific graphs is located in premade_graphs.cpp. The functions there will create graphs that represent maps of the United States, Europe, and Japan. You can have tests.cpp call your functions on these map graphs, or on random graphs.

The source code in this lab is documented heavily. Use this to your advantage. Above each function (including the ones you need to write), is a comment describing what the function does, its inputs, and its outputs. Hints and notes are also included in the documentation above the functions you will write.

The Graph Library

demo.cpp shows several ways that the Graph class and its functions can be used. Use this opportunity to familiarize yourself with the available functions. All functions are very similar (if not identical) to those described in lecture. By default, running

make graphdemo
./graphdemo

will print two graphs to your terminal and put additional graph image files in the images/ directory.

Recall that you can open png images from the terminal using the command: xdg-open image.png where image.png is the name of the png you want to open.

To help you debug your code, each edge is colored according to its edge label when graphs are printed as PNGs. Edge labels can be set with the setEdgeLabel() function. The coloring scheme is as follows:

"UNEXPLORED" -> black (default)
"MIN"        -> blue  (solution)
"MST"        -> blue  (solution)
"MINPATH"    -> blue  (solution)
"CROSS"      -> red
"DISCOVERY"  -> green
"VISITED"    -> grey

So if this line appears in your code, graph.setEdgeLabel(u, v, "MIN"), the edge between vertices u and v would appear blue to denote that the edge is the minimum weighted edge (i.e., if you were doing findMinWeight()).

Please note that the default edge label and vertex label is empty string. If you are doing a traversal or need to rely on the labels for any reason, you should initialize them to some value or consider empty string as "UNEXPLORED".

Another useful function for debugging is snapshot(), a member function of the Graph class. By default, tests.cpp print out a picture of your graph after you’re done with it, but what if you wanted to see how your graph labels are changing as you traverse it? For example,

// do a BFS on the graph g

// setup snapshot feature with your image title
g.initSnapshot("myBFS");

while(...)
{
    // traverse the graph
    g.snapshot();
    // label edges, etc
    // ...
}

will create a PNG for each iteration of the while loop, so you can see how the traversal progresses. Ideally, edges will change from "UNEXPLORED" to "DISCOVERY", "CROSS", or "VISITED". You will be able to see this by watching the edges change color while flipping through the generated files myBFS0.png, myBFS1.png, myBFS2.png, etc in images/.

One last bit of information: if you run

make tidy

all the PNG files in images/ will be deleted. This is useful because they can accumulate fast, especially if you are liberally using snapshot().

int GraphTools::findMinWeight(Graph & graph)

Given the map graphs of the U.S., Europe, and Japan, which two cities are closest in each one?

Useful functions: - In graph.h the only functions you should need are: getVertices, getEdges, setVertexLabel, setEdgeLabel. - In graph_tools.h: BFS. - You should also take a look at the definition of an Edge object (edge.h), some fields will be useful to you.

(Note traversal edges are also colored in this solution).

int GraphTools::findShortestPath(Graph & graph, Vertex start, Vertex end)

What is the minimum number of layovers/train exchanges between two cities if the only flights/routes possible are represented by edges on the graph?

Hints - You will need to do a modified BFS. - You should keep track of the ‘parents’ using an unordered set. You don't have to worry about the edge weights because we are only interested in the number of hops between the vertices, not their costs.

For this task, you must return the length of the shortest path (in edges) between two vertices. You must also color the edges in the shortest path blue by labeling them "MINPATH".

Optional: void GraphTools::findMST(Graph & graph)

What path can you create between all cities in each graph with the minimum total distance?

For this task, you must label the edges of the minimum spanning tree as "MST" in the Graph g using Kruskal’s Algorithm.

A spanning tree connects all vertices of a graph, without creating cycles. A minimum spanning tree does the same thing, but the edges it uses to connect the vertices are of minimal weight. In other words, a minimal spanning tree uses the lightest edges possible to connect all the vertices in a graph.

In class we learned about two algorithms that accomplish this: Prim’s Algorithm Links to an external site. and Kruskal’s Algorithm Links to an external site.. For this lab, we will use Kruskal’s algorithm, because we already have the tools necessary to implement it. Incredibly, we can find and label the minimum spanning tree in less than 40 lines of code! Let’s take a look at the algorithm:

1. Get a list of all edges in the graph and sort them by increasing weight.
2. Create a disjoint sets structure where each vertex is represented by a set.
3. Traverse the list from the start (i.e., from lightest weight to heaviest).
   • Inspect the current edge. If that edge connects two vertices from different sets, union their respective sets and mark the edge as part of the MST. Otherwise there would be a cycle, so do nothing.
   • Repeat this until n-1  edges have been added, where n is the number of vertices in the graph.

Testing Your Work

The given test.cpp file contains test cases (the same ones we’ll deploy on PrairieLearn). Compile your code by typing make and then execute the test cases by typing ./test.

Marking Your Work

You will let us know you’ve worked on the lab by submitting your work to the autograder in PrairieLearn Links to an external site.. Autograder will run 10 tests (one for submission) and your code needs to pass 7 of them (including the submission) for you to get full marks. In other words, 7/10 means full marks.

Submitting the lab is as simple as dragging your completed code into the PrarieLearn interface for the 

lab_graphs assignment.

Please submit the following file:

• graph_tools.h
• graph_tools.cpp

Good luck!