Updated by Chris Gregg and Chris Piech. Thanks to Julie Zelenski, Nick Parlante, Jerry Cain, Eric Roberts, Keith Schwarz, Dawson Zhou, Leonid Shamis (UC Davis) and Marty Stepp.
March 10th, 2017
This assignment focuses on graphs, specifically on searching for paths in a graph. You will write several path finding algorithms.
We provide you with several support files, but you should not modify them. Turn in the following files;
trailblazer.cpp, code to perform graph path searches
map-custom.txt, a world map of your own creation.
map-custom.jpg, a world map of your own creation.
This is an individual assignment. Write your own solution and do not work in a pair/group on this program.
This program displays various road maps and allows users to find the shortest path between any two nodes. For example, if the user loaded the Stanford map and selected a node at the top of the Oval and another node at FroSoCo, your program should display the best route:
If you click on any two nodes in the world, the program will find a path from the starting position to the ending position. As it does so, it will color the vertexes green and yellow based on the colors assigned to them by the algorithm. Once the path is found, the program will highlight it and display information about the path cost in the console. The user can select one of four path-searching algorithms in the top menu:
The window contains several controls. You can load world maps by selecting them from the bottom drop-down menu and then clicking the "Load" button.
In your trailblazer.cpp file, you must write the following 4 functions for finding paths and creating mazes in a graph:
Path breadthFirstSearch(RoadGraph& graph, Vertex* start, Vertex* end)
Path dijkstrasAlgorithm(RoadGraph& graph, Vertex* start, Vertex* end)
Path aStar(RoadGraph& graph, Vertex* start, Vertex* end)
Path alternativeRoute(RoadGraph& graph, Vertex* start, Vertex* end)
Each of the first three implements a path-searching algorithm taught in class. You should search the given graph for a path from the given start vertex to the given end vertex. If you find such a path, the path you return should be a list of all vertexes along that path, with the starting vertex first (index 0 of the vector) and the ending vertex last.
Path is a typedef of a
Vector<Vertex *>. It is an alias for the same exact type.
If no path is found, return an empty path. If the start and end vertexes are the same, return a one-element vector containing only that vertex. Though some graphs may be undirected (all edges go both ways), your code should not assume this. You may assume that the graph passed in is not corrupt.
Our provided main client program will allow you to test each algorithm one at a time before moving on to the next. You can add more functions as helpers if you like, particularly to remove redundancy between some algorithms containing similar code.
The road network world is represented by a RoadGraph, which is a thin wrapper around the BasicGraph we saw in class. Each vertex represents a specific location on the world. An edge between two verticies means that there is a direct road between the two. The cost of the path is the time it takes to traverse that road.
Your algorithm should work on any RoadGraph instance, such as this map of Middle Earth that can help Frodo get from the Shire to Mount Doom:
We provide you with a lot of starter code for this assignment. Here is a quick breakdown of what each file contains, though you do not need to examine or know about each file or its contents in order to complete the assignment.
trailblazer.h/.cpp:We provide a skeleton version of these files where you will write your path-searching code for the assignment.
Color.h/.cppConstants representing colors of verticies
TrailblazerGUI.h/.cppThe app's graphical user interface.
trailblazermain/.cppThe main function that initializes the GUI and launches the application.
World(Abstract,Map).h/.cppHierarchy of types of world graphs.
Each vertex in the graph is represented by an instance of the Vertex structure, which has the following members:
||vertex's name, such as "r34c25" or "vertex17"|
||edges outbound from this vertex|
||sets this vertex to be drawn in the given color in the GUI, one of UNCOLORED, WHITE, GRAY, YELLOW, or GREEN|
||returns a printable string representation of the vertex for debugging|
When you call setColor on a Vertex, the GUI is automatically updated, the programs internal count of the number of verticies that you touch is increased, and a delay is added (so you can see your algorithm animate). All vertex colors are reset before each of your path-searching algorithms is called.
Each edge in the graph is represented by an instance of the Edge structure, which has the following members:
||the starting vertex of this edge|
||the ending vertex of this edge (i.e., finish is a neighbor of start)|
||cost to traverse this edge|
||returns a printable string representation of the vertex for debugging|
The vertexes and edges are contained inside a RoadGraph object passed to each of your algorithm functions.
||get all Verticies that can be reached by a single edge from v|
||return the edge that connects start to end|
||the fastest speed of any edge in the graph|
||the distance between two nodes as the crow flies.|
Coloring: In addition to searching for a path in each algorithm, we also want you to add some code to give colors to various vertexes at various times. This coloring information is used by the GUI to show the progress of your algorithm and to provide the appearance of animation. To give a color to a vertex, call the color member function on that vertex's Vertex object, passing it a global color constant such as GRAY, YELLOW, or GREEN. For example:
// set the start vertex's color to green start->setColor(GREEN);
Here is a listing of colors available and when you should use them:
The provided GUI has an animation slider that you can drag to set a delay between coloring calls. If the slider is not all the way to its left edge, each call to setColor on a vertex will pause the GUI briefly, causing the appearance of animation so that you can watch your algorithms run.
See the expected output files for reference on what your program should do. For Dijkstra's and A* you should get the same path costs as shown in the expected outputs. But you do not need to exactly match our path itself, nor its "locations visited", so long as your path is a correct one
Check out the search handout for an example of the search algorithms. Each of the three search algorithms (BFS, Dijkstra, A*) follow the general paradigm:
Breadth-first search implementation notes: Implement the version of the algorithm pseudo-code from lecture. Make sure to keep track of nodes that you have already visited.
Dijkstra's algorithm implementation notes: The version of Dijkstra that we talk about in class is slightly different than the version in the book. Your implementation of Dijkstra's algorithm can follow any version. The one we talked about in lecture is probably the easiest. The priority queue should store paths, and once you find a path that ends in the destination, you should reconstruct the shortest path back. See the lecture slides for more details.
A* implementation notes: As discussed in class, the A* search algorithm is essentially a variation of Dijkstra's algorithm that uses heuristics to fine-tune the order of elements in its priority queue to explore more likely desirable elements first. So when you are implementing A*, you need a heuristic function to incorporate into the algorithm.
You can compare the behavior of Dijkstra's algorithm and A* (or any pair of algorithms). First try performing a search between two points using Dijkstra's algorithm, then select A* and press the "Run" button at the top of the GUI window. This will repeat the same search using the currently selected algorithm. Run a search using Dijkstra's algorithm, switch the algorithm choice to "A*," then run that search to see how much more efficient A* is.
In order for A* to work, you need to define a heuristic function which under-estimates the cost of travelling between two vertices.
For a road map (where cost is travel time), a simple heuristic is to calculate the time it would take to get between the nodes assuming that there was a direct super highway between the two nodes. If the speed of a super highway is as fast or faster than the speed on any road then the algorithm will underestimate the true graph distance (which makes it an admissable heuristic). To calculate how long it would take to travel along a super highway between two nodes use the two RoadGraph functions:
Recall that traveTime = distance / speed.
Your A* search algorithm should always return a path with the same length and cost as the path found by Dijkstra's algorithm. If you find that the algorithms give paths of different costs, it probably indicates a bug in your solution.
When travelling between two points on a road map, you may want to take the fastest route, but if there is a reasonable alternative you might prefer that instead. For example, though highway 101 is often slightly faster way to get to San Francisco, highway 280 is more beautiful (Chris Gregg thinks that you should also consider going all the way to highway 1). Your final task is to implement the
In this example the shortest path between the oval and the back of MemChu is shown in red, and a next best alternative is shown in blue:
We already know how to find a shorest path from a start to a goal. How do we find an alternate route?
To find an alternate path from a start node to an end node, first we are going to calculate the best (aka shortet) path between start and end. Then, for each edge in the best path we are going to calculate the shortest path from start to end that ignores that edge. Each search will return a candidate "alternate route". Your function should return the lowest cost alternate route that is sufficiently different from the original best path.
The difference of an alternate path P from the best path B is defined to be the number of nodes that are in B, but are not in P divided by the number of nodes in P:
For each edge in the best path you will produce one candidate alternate route. Your function should choose, from those candidates, the shortest path that has a difference score greater than 0.2 when compared to the the original best path (see the constant SUFFICIENT_DIFFERENCE).
The shortest alternate route is the path Start -> D -> A -> B -> C -> End. However it has a difference score of 0.2 (recall that we are looking for a path with difference score greater than 0.2). The shortest alternative that also has a difference greater that 0.2 is:
Start -> A -> E -> F -> C -> End
That is the path that your alternative path algorithm returns.
There are different ways to accomplish the modification to your path algorithm. One option is to simply write a separate and modified Dijkstra or A* function that has the ability to ignore an edge. While this option is allowed for your project, it does duplicate a lot of code. A better option would be to refactor your code and write a modified function that performs Dijstra or A* and can either perform the standard algorithm or can ignore a given edge. Then, modify your original Dijkstra or A* function to simply call your new function.