This lab will have you and your lab partner implement a graph representation, and several graph algorithms.
As usual, you can get the initial files for this lab from Github. The new files are listed here, and the files that you will need to edit are highlighted in blue:
You are responsible for the following deliverables:
The only data member for Graph has been provided: an adjacency list that maps from vertices to outgoing edges. Graph represents graphs that are weighted and directed. An edge is described by the Edge class, which stores a label to identify the edge (e.g., the flight number of the edge represents airline routes), a source vertex, a destination vertex, and a weight (uniform for unweighted graphs).
You will implement all the provided methods on the Graph class, and be sure to test them thoroughly.
As mentioned, the Graph class represents graphs as being weighted and directed. This is the most general representation of a graph: unweighted graphs can be simulated by simply ignoring the edge weights (i.e., assigning the same cost to each). Similarly, we can simulate an undirected graph by simply ensuring each inserted edge has a complement. That is, for every edge A-->B, there must be a B-->A with matching weight and label.
We could simply rely on a user of the Graph class to maintain this property, but it would be better to write a new class that encapsulates this behavior.
In ugraph.h, you will find the declaration for UGraph, an undirected graph class. This class inherits most of its features from the Graph class. In fact, most of the methods will remain unchanged since their behavior does not depend on whether the graph is directed or undirected. Only three methods need to be over-ridden - insertEdge, removeEdge, and getEdges. You must implement removeEdge and getEdges. You are also responsible for understanding this fact: our use of inheritance and polymorphism allows us to write graph methods (e.g., Dijkstras, breadth-first search) that work the same regardless of whether we are working with a directed or undirected graph.
Note: You can call the parent class implementation of a method by using the scope operator (e.g., Graph<V,E,W>::). For example, in the provide insertEdge, we simply add two directed edges using the Graph implementation of insertEdge. If we omitted the scope operator, C++ would call the UGraph implementation, leading to infinite recursion. removeEdge will be as simple as insertEdge (i.e., simply call the parent method twice). getEdges will be slightly more complicated: you must call the parent method, but ensure that each edge appears only once in the vector (i.e., only one of A-->B or B-->A should be in the list since they are the same exact edge).
Please complete each function declared in graph-algorithms.h to ensure you understand three traversal algorithms we discussed in class - depth-first search, bread-first search, and Dijkstra's. You must test each function you implement using the testGraph program. I suggest starting with simple graphs we drew in class, but you should also come up with much larger examples to ensure that you cover interesting cases.
Feel free to add additional methods, although you will need to ensure you add their declaration in the header file. At a minimum, your functions are:
reachableDFS(G, source, dest) : dictionary VISITED, each vertex is false toReturn = recursiveDFS(G,source, dest, VISITED) return toReturn } recursiveDFS(G, current, dest, VISITED) if current == dest return true mark current as visited for each neighbor w of current if w not visited if recursiveDFS(g, w, dest, visited) return true return false
A summary of dijkstra's algorithm is below for reference.
Dijkstras(source, G): empty priority queue PQ empty dictionary DIST dictionary COMPLETED, each vertex is false PQ.insert(0, source) DIST[source] = 0 while( !PQ.empty() ): u = PQ.removeMin() if( COMPLETED[u] ) // been there done that continue COMPLETED[u] = true for each (u,v) in E //for each neighbor of u if DIST does not contain v: // new priority DIST[v] = DIST[u] + cost(u,v) PQ.insert(DIST[v], v) else if DIST[v] > DIST[u] + cost(u,v) //updating priority DIST[v] = DIST[u] + cost(u,v) //update distance PQ.insert(DIST[v],v) return DIST
Here is pseudocode for a topological sort algorithm; we'll talk about it more in class on Thursday. The underlying idea is to “count down” the number of incoming edges into each vertex. When each incoming edge is accounted for, the vertex has no remaining dependencies and can be output. You need to adapt the “output” to make sense for the given signature of topsort in your graph algorithm.
topologicalSort(G) depend = new hashtable S = new stack for each v in V depend[v] = count-in-edges(v) if depend[v] == 0 S.push(v) while(!S.isEmpty()) u = S.pop() output u for each (u,v) in E depend[v] = depend[v] - 1 if depend[v] == 0 S.push(v)
As an example, you could construct a graph to represent, say, the search problem of trying to get from Parrish Hall to The Ville. If you do this correctly, your test may look like this (with added print statements).
$ ./testGraph Let's build a map of Swarthmore! The graph: Softball: {Ville, Soccer, Tunnel, Train} Bridge: {Tennis, Wharton} Sharples: {Clothier, Tunnel} Soccer: {Softball, Tennis} Wharton: {Bridge, Clothier} Magill: {Parrish, Train} Tennis: {Soccer, Bridge, Tunnel} Parrish: {Magill, Clothier} Train: {Magill, Ville, Softball} Ville: {Train, Softball} Tunnel: {Softball, Sharples, Tennis} Clothier: {Wharton, Parrish, Sharples} Can I get from Parrish to the Ville? DFS: yes! How do I get from Parrish to the Ville? Using BFS: Parrish Magill Train Ville The shortest path length is: 3Other examples to try are maze inputs expressed as graphs, flight plan examples from class, a map of Crum woods, a map of your hometown, a partial map of your Facebook friends...
You might find the following hints more or less helpful:
Graph <string, string, int>* graph = new Graph <string, string, int>; graph->insertVertex("Parrish"); //do some more inserts, code is looking good! //now let's do something interesting shortestLengthPathBFS("Parrish","Ville", graph); //Compiler errorThe error might look like:
./graph-algorithms-inl.h:21:11: note: candidate template ignored: deduced conflicting types for parameter 'V' ('const char *' vs. 'std::__1::basic_stringC++ interprets "Parrish" as a c-string and doesn't like that you are trying to send that in for a string. Simply modify your call by casting it as a string explicitly.') vector<V> shortestLengthPathBFS(V src, V dest, Graph<V,E,W>* g){
bfs(string("Parrish"), string("Ville"), graph);