In this lab you will:
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.
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.
Note to students working locally! The graphviz library is required for graphdemo to work, so please install it on your machine with your architecture's package manager.
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:
graph.h the only functions you should need are: getVertices, getEdges, setVertexLabel, setEdgeLabel.graph_tools.h: BFS.edge.h), some fields will be useful to you.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:
Note Your graph may differ (say, KansasCity->StLouis->Cincinnati->WashingtonDC), but the minimum number of edges is the same: 3.
We will take it into consideration when grading that there may be multiple paths of minimum length.
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".
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 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:
graph_tools.cpp
/**
* @file graph_tools.cpp
* This is where you will implement several functions that operate on graphs.
* Be sure to thoroughly read the comments above each function, as they give
* hints and instructions on how to solve the problems.
*/
#include "graph_tools.h"
/**
* Finds the minimum edge weight in the Graph graph.
*
* @param graph - the graph to search
* @return the minimum edge weight
*
* @todo Label the minimum edge as "MIN". It will appear blue when
* graph.savePNG() is called in minweight_test.
*
* @note You must do a traversal.
* @note You may use the STL stack and queue.
* @note You may assume the graph is connected.
*/
int GraphTools::findMinWeight(Graph& graph)
{
// TODO
// 1. Label all edges and vertices as unexplored. You will need
// to look in graph.h for the right functions.
vector<Vertex> vertices = graph.getVertices();
for (Vertex v : vertices) {
graph.setVertexLabel(v, "UNEXPLORED");
}
if (vertices.empty()) {
return -1;
}
// 2. Find the minimum weight edge by checking all edges.
Edge minEdge;
minEdge.weight = INT_MAX;
vector<Edge> edges = graph.getEdges();
for (auto e : edges) {
if (e.weight < minEdge.weight) {
minEdge = e;
}
}
graph.setEdgeLabel(minEdge.source, minEdge.dest, "MIN");
return minEdge.weight;
}
/**
* Returns the shortest distance (in edges) between the Vertices
* start and end.
*
* @param graph - the graph to search
* @param start - the vertex to start the search from
* @param end - the vertex to find a path to
* @return the minimum number of edges between start and end
*
* @todo Label each edge "MINPATH" if it is part of the minimum path
*
* @note Remember this is the shortest path in terms of edges,
* not edge weights.
* @note Again, you may use the STL stack and queue.
* @note You may also use the STL's unordered_map, but it is possible
* to solve this problem without it.
*
* @hint In order to draw (and correctly count) the edges between two
* vertices, you'll have to remember each vertex's parent somehow.
*/
int GraphTools::findShortestPath(Graph& graph, Vertex start, Vertex end)
{
unordered_map<Vertex, Vertex> parent;
// TODO
// 1. Set all vertices as unexplored
vector<Vertex> vertices = graph.getVertices();
for (Vertex v : vertices) {
graph.setVertexLabel(v, "UNEXPLORED");
}
// 2. Do a modified BFS. See the BFS function below as a guideline, but
// your BFS here only needs to populate the "parent" map and stop once the short-
// est path has been found.
queue<Vertex> q;
graph.setVertexLabel(start, "VISITED");
q.push(start);
parent[start] = start; // Start has no parent
bool found = false;
while (!q.empty() && !found) {
Vertex v = q.front();
q.pop();
vector<Vertex> adj = graph.getAdjacent(v);
for (size_t i = 0; i < adj.size(); ++i) {
int isUnexplored = graph.getVertexLabel(adj[i]) == "UNEXPLORED";
int isConnectedToExplored = graph.getEdgeLabel(v, adj[i]) == "UNEXPLORED";
if (isConnectedToExplored && !isUnexplored) {
graph.setEdgeLabel(v, adj[i], "CROSS");
continue;
}
if (!isUnexplored) continue;
graph.setEdgeLabel(v, adj[i], "DISCOVERY");
graph.setVertexLabel(adj[i], "VISITED");
parent[adj[i]] = v; // Set parent
q.push(adj[i]);
if (adj[i] == end) {
found = true;
break;
}
}
}
// 3. Use the unordered map to trace from a path from the end to the start,
// counting edges. You should set edges to "minpath" here too.
int edgeCount = 0;
Vertex current = end;
while (current != start) {
Vertex par = parent[current];
graph.setEdgeLabel(par, current, "MINPATH");
current = par;
edgeCount++;
}
return edgeCount;
}
/**
* Finds a minimal spanning tree on a graph.
*
* @param graph - the graph to find the MST of
*
* @todo Label the edges of a minimal spanning tree as "MST"
* in the graph. They will appear blue when graph.savePNG() is called.
*
* @note Use your disjoint sets class given in dsets.cpp to help you with
* Kruskal's algorithm.
*
* @note You may call std::sort instead of creating a priority queue.
*/
void GraphTools::findMST(Graph& graph)
{
DisjointSets forest = DisjointSets();
vector<Vertex> vertices = graph.getVertices();
forest.addelements(vertices.size());
vector<Edge> edges = graph.getEdges();
sort(edges.begin(), edges.end());
for (auto e : edges) {
int setU = forest.find(e.source);
int setV = forest.find(e.dest);
if (setU == setV) {
continue;
}
graph.setEdgeLabel(e.source, e.dest, "MST");
forest.setunion(setU, setV);
}
}
/**
* Does a BFS of a graph, keeping track of the minimum
* weight edge seen so far.
* @param g - the graph
* @param start - the vertex to start the BFS from
* @return the minimum weight edge
*/
Edge GraphTools::BFS(Graph& graph, Vertex start)
{
queue<Vertex> q;
graph.setVertexLabel(start, "VISITED");
q.push(start);
Edge min;
min.weight = INT_MAX;
while (!q.empty()) {
Vertex v = q.front();
q.pop();
vector<Vertex> adj = graph.getAdjacent(v);
for (size_t i = 0; i < adj.size(); ++i) {
if (graph.getVertexLabel(adj[i]) == "UNEXPLORED") {
graph.setEdgeLabel(v, adj[i], "DISCOVERY");
graph.setVertexLabel(adj[i], "VISITED");
q.push(adj[i]);
int weight = graph.getEdgeWeight(v, adj[i]);
if (weight < min.weight) {
min.source = v;
min.dest = adj[i];
min.weight = weight;
}
} else if (graph.getEdgeLabel(v, adj[i]) == "UNEXPLORED") {
graph.setEdgeLabel(v, adj[i], "CROSS");
int weight = graph.getEdgeWeight(v, adj[i]);
if (weight < min.weight) {
min.source = v;
min.dest = adj[i];
min.weight = weight;
}
}
}
}
return min;
}
graph_tools.h
/**
* @file graph_tools.h
* This is the declaration of the tasks you will write for this lab.
*/
#ifndef _GRAPH_TOOLS_
#define _GRAPH_TOOLS_
#include <algorithm>
#include <stack>
#include <queue>
#include <unordered_map>
#include "graph.h"
#include "dsets.h"
using std::stack;
using std::queue;
using std::unordered_map;
/**
* This is a namespace that provides various functions for
* operations on the Graph class. Your assignment this lab
* will be to implement these three functions.
*/
namespace GraphTools
{
/**
* Finds the minimum edge weight in the Graph graph.
*/
int findMinWeight(Graph& graph);
/**
* Returns the shortest distance (in edges) between the Vertices
* start and end.
*/
int findShortestPath(Graph& graph, Vertex start, Vertex end);
/**
* Finds a minimal spanning tree on a graph.
*/
void findMST(Graph& graph);
// define any helper functions here:
/// @cond SOL
/**
* Does a BFS of a graph, keeping track of the minimum
* weight edge seen so far.
*/
Edge BFS(Graph& graph, Vertex start);
/// @endcond
}
#endif