Program #3 Driving Directions Solution




This is a pair programming assignment. You and a partner can divide up the work. Although both of you may not work on all parts of the program you should understand and be able to fully explain every portion of the code. Outside of your team, it is permissible to consult with classmates to ask general questions about the assignment, to help discover and fix specific bugs, and to talk about high level approaches in general terms. It is not permissible to give or receive answers or solution details from fellow students.

You may research online for additional resources; however, you may not use code that was written specifically to solve the problem you have been given, and you may not have anyone else help you or your partner write the code or solve the problem. You may use code snippets found online, providing that they are appropriately and clearly cited, within your submitted code.

If you or your partner are found to have plagiarized any part of the assignment, both will receive a 0 and be reported.

*By submitting this assignment, you agree that you have followed the above guidelines regarding collaboration and research.*

For our final program you are going to create a library that reads in a file with a list a cities and the roads between the cities. The driver code will input a starting city and destination city, and you will return the shortest path between the two as a vector of cities along the path. Then we are going to test our path finding algorithm with a heap and without a heap.

:warning: Because this is a pair programming assignment, one of you will have to create the repo and team name. The other team member will join and select the team name as their team.

:no_entry_sign: __It is difficult to fix if you don’t pay attention. Do not select the wrong team. Do not create multiple teams.__

Part A: Making a Graph

For Part A you will read in a text containing cities and their x and y coordinates along a grid. The file format will be as follows:


mogadishu 6 7

fairbanks 3 5

nyc 4 7

paris 3 2


City names will not contain whitespace and will be uniquely named. Input files will be well-formed (no need for error checking). You will need to build an undirected, weighted graph using the x and y coordinates.

The user can only travel in straight lines, so paths are along the x and y grid. In other words, there is an edge between two cities if they have equal x coordinates or equal y coordinates and there is no city between them on the path. A city will have, at most, 4 adjacent cities. The adjacent city in any one direction is only the closest city in that direction. So the algorithm for building the adjacency list will be to find all cities in one direction, but set only the closest one as adjacent.

For example, if you have 3 cities along the same x axis A[5,3], B[5,6], and C[5,4], A is only adjacent to C; however, C is adjacent to B in the northern direction, and A in the southern direction.

You should use an array or vector to store the cities. To hold edges you will need to implement an adjacency list or an adjacency matrix (you may use the STL list or vector class).


* Public Methods

* `City(string cityName, int xCoor, int yCoor)`

* `std::string getName()`

* Returns the city name

* `int getXCoor()`

* Returns the x coordinate

* `int getYCoor()`

* Returns the y coordinate

* `list<City*> getAdjacent()`

* Returns an adjacency list for the city

* `bool operator<(City &c)`

* Compares cities by name using the string operator< method


* Public Methods

* `Map(string filename)`

* `City* findByName(string cityName)`

__Show your TA your working Part A code by the end of lab on May 3rd.__

_You may continue to work on the remainder of the lab on your own time or in lab_

Part B: Finding the Shortest Path

You will need to implement Dijkstra’s shortest path algorithm to determine the shortest path between two cities. If you want to implement a different shortest path algorithm, you must clear it with me first. You must travel in straight lines, and can only change directions at cities. In other words, if cityA has coordinates [5,7] and cityB has coordinates [6,2], there is no path between them. However, if you add cityC with coordinates [5,2], you now have a path between cityA and cityB through cityC.

You should add the following public method to your Map class:

* `vector<City *> shortestPath(City * start, City * dest)`

* The method should return the shortest path between two cities by returning a list of the cities you will need to travel through in order.

You will also need a second method that gives the distance between two cities on the graph:

* `unsigned int pathDistance(City * start, City * dest)`

* The method should return the total distance (based on the path you must take) between the two cities.

* The method should return -1 if there is no path.

Part C: Optimizing Dijkstra’s Algorithm

Part of the complexity of Dijkstra’s algorithm comes from finding the next closest, unvisited vertex. Typically, you can increase the speed of Dijkstra’s shortest path algorithm by storing the data in a simple priority queue, such as a heap. We will optionally store our cities in a heap to make accessing the closest city a constant time operation (_well, O(logn) if you count the time to re-heapify_). Add an additional Map constructor that takes a boolean as a second parameter in addition to the filename.

* `Map(string filename, bool heap)`

I recommend adding a method, ‘getNextCity’, that will iterate through the cities to find the next closest city if a heap is not used, otherwise will heapify your list of cities and return the priority value if a heap is used.

:warning: Remember to account for the `visited` flag when heapifying.

Part D: Code Organization and Submission

* Required code organization:

* program3.cpp

* Map.h/.cpp

* City.h/.cpp

* makefile

* You must have ‘checkmem’ and ‘run’ targets

* Your makefile must include c++11 or c++14 extensions

To submit, you only need to submit to your single group repo.

Below is just a reminder of the commands you should use to submit your code. If you cannot remember the exact process, please review lab 1.

*These commands all presume that your current working directory is within the directory tracked by `git`.*


git add Deck.h

git add Card.cpp

git commit -a -m “first commit”

git push


Lastly we are going to make our final commit. You will need to do this when your submission is ready for grading.


git commit –allow-empty -m “final commit”

git push


:warning: Remember, you __MUST__ make a submission with the comment “final commit” before the deadline to be considered on time.