CS235-Project 5 Find Route in Map (Backtracking using a Stack) Solved

For this project you will design and implement two classes (City and RouteMap) to find a route, if one exists, from origin to destination city, given a particular map.

This project will build on ideas we have worked with already (reading input from a file, working with abstractions - i.e. a City and a RouteMap). 

However this time you will be responsible for the design!                  

The idea: In a map, as the one pictured above, we say that R is reachable from P because there is an arrow going from P to R (you can go from P to R). However, P is NOT reachable from R because you cannot go from R to P following a single arrow. A route from an origin city to a destination city is a sequence of cities s.t. each city in the sequence is reachable from the previous one. As we discussed in lecture, it is possible to find out if there is a route from an origin city to a destination city  by implementing backtracking using a stack 

•          Starting from the origin, push reachable cities that have not yet been visited onto the stack, and mark them as having been visited.

•          If you reach a dead end (no more unvisited reachable cities available from the city at the top of the stack), pop the stack to backtrack.

•          Stop when you either have the destination at the top of the stack (found route!) or the stack is empty (there is no route)

The input: The input will be in the following format:


•          The first line will be a comma-separated list of city names in alphabetical order. For example, for the RouteMap pictured above, the first line in the corresponding input file will be:

P,Q,R,S,T,W,X,Y,Z\n
• The remainder of the file will be a comma separated list of city pairs separated by ‘-‘, where the second city in the pair is reachable from the first. For example, for the RouteMap pictured above, the remainder of the file will be:

P-R,P-W,Q-X,R-X,S-T,T-W,W-Y,W-S,Y-R,Y-Z\n
You may assume that the city names are unique (no two cities have the same name) but not necessarily single letters, and that the input file is in the correct format.

Design and Implementation:

You will design and implement the two classes: City (City.hpp and City.cpp) and RouteMap (RouteMap.hpp and RouteMap.cpp)  




Design Requirements - to successfully implement backtracking using a stack you need to:

•          Be able to mark a city as having been visited

•          Find out what cities are reachable from any given city





























Furthermore
• The RouteMap class must have the following 3 public methods (you may and should add any public and private members that you deem necessary to implement and support the following)

/**

@param input_file_name of a csv file representing a route map where the first     line is a comma-separated list of city names, and the remainder is a        comma-separated list of city-pairs of the form A-B, indicating that B    is reachable from A 


       (i.e. there is an arrow in the map going from A to B)

@post this depends on your design, the input data representing the map must      have been stored. Reachable cities must be stored and explored in the           same order in which they are read from the input file  

**/

bool readMap(std::string input_file_name);


   

/**

@return a pointer to the city found at position, where         0 <= position <= n-1, and n is the number of cities, 
    and cities are stored in the same order in which they appear      in the input file. Returns nullptr if city not found at position.

**/

const City* getCity(size_t position);

    

/**

@return true if there is a route from origin to destination, false otherwise @post if a route is found from origin to destination, it will print it to         standard output in the form “ORIGIN - ... - DESTINATION\n”

**/

bool isRoute(City* origin, City* destination);

 

For example, with the map in the above example,  isRoute(T_ptr, Z_ptr);  will return true and print