lab_graphs Gory 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.
• Implement Kruskal’s minimum spanning tree algorithm.

Checking Out The Code

Get the code in the usual way.

After running svn up, copy your dsets from mp7 to lab_graphs:

cd lab_graphs
cp ../mp7/dsets.cpp .
cp ../mp7/dsets.h .

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. These are the only files that will be used for grading this lab. 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 included in the documentation above the functions you will write.

For a list of files and their descriptions, see the Doxygen for this lab.

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.

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?

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

To test your code, run:

./lab_graphs weight europe

to test on the Europe map (you can also use “us” or “japan”) or

./lab_graphs weight random

to test on a random graph or

./lab_graphs weight random 8 47

to test on a random graph with 8 vertices and random seed 47.

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?

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

To test your code, run

./lab_graphs path europe

to test on the Europe map (you can also use “us” or “japan”) or

./lab_graphs path random

to test on a random graph or

./lab_graphs path random 8 47

to test on a random graph with 8 vertices and random seed 47.

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 learn about two algorithms that accomplish this: Prim’s Algorithm and Kruskal’s Algorithm. 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.

To test your code, run:

./lab_graphs kruskal europe

to test on the Europe map (you can also use “us” or “japan”) or

./lab_graphs kruskal random

to test on a random graph or

./lab_graphs kruskal random 8 47

to test on a random graph with 8 vertices and random seed 47.

Grading Information

The following files (and ONLY these files!!) are used for grading this lab:

• graph_tools.h
• graph_tools.cpp
• dsets.h
• dsets.cpp

If you modify any other files, they will not be grabbed for grading and you may end up with a “stupid zero.”

Good luck!