Phase 1 submission: Monday, April 11 by 23:59 pm

Phase 2 submission: Wednesday, April 20 by 23:59 pm

Phase 3 submission: Sunday, May 1 by 23:59 pm

Video Presentation: Friday, April 29

This project focuses on using data structures in C++ and implementing various graph algorithms to build a map application.

• Please clone the repository, look through README.md and fill up functions to finish in the project.
• Please make sure that your code can run bazel run/test.
• In this project, you will need to fill up trojanmap.cc and add unit tests in the tests directory.

Each point on the map is represented by the class Node shown below and defined in trojanmap.h.

class Node {
  public:
    Node(){};
    Node(const Node &n){id = n.id; lat = n.lat; lon = n.lon; name = n.name; neighbors = n.neighbors; attributes = n.attributes;};
    std::string id;    // A unique id assign to each point
    double lat;        // Latitude
    double lon;        // Longitude
    std::string name;  // Name of the location. E.g. "Bank of America".
    std::vector<std::string> neighbors;  // List of the ids of all neighbor points.
    std::unordered_set<std::string> attributes;  // List of the attributes of the location.
};

For visualization, we use OpenCV library. You will use this library as a black box and don't need to worry about the graphic details.

Use the following commands to install OpenCV and other libarary.

For MacOS:

$ brew install cmake
$ brew install opencv
$ brew install ncurses

For Ubuntu:

$ cd **your project folder**
$ git clone https://github.com/opencv/opencv.git
$ sudo apt-get install cmake libgtk2.0-dev pkg-config
$ sudo apt install libcanberra-gtk-module libcanberra-gtk3-module
$ sudo apt-get install libncurses5-dev libncursesw5-dev
$ cp ubuntu/* ./

Next, type the following, but make sure that you set the path_to_install_folder to be the absolute path to the install folder under opencv.

$ cd opencv/
$ mkdir build install
$ cd build
$ cmake -D CMAKE_INSTALL_PREFIX=**path_to_install_folder** -D BUILD_LIST=core,highgui,imgcodecs,imgproc,videoio ..
$ make install

For example, if cloned this repo under "/Users/ari/github/TrojanMap", you should type:

$ cd opencv/
$ mkdir build install
$ cd build
$ cmake -D CMAKE_INSTALL_PREFIX=/Users/ari/github/TrojanMap/opencv/install -D BUILD_LIST=core,highgui,imgcodecs,imgproc,videoio ..
$ make install

Please run:

For MacOS,

$ bazel run src/main:main

For Ubuntu, you need to use the following command to prevent errors.

$ bazel run --cxxopt='-std=c++17' src/main:main

If everything is correct, this menu will show up.

TrojanMap
**************************************************************
* Select the function you want to execute.                    
* 1. Autocomplete                                             
* 2. Find the location                                        
* 3. CalculateShortestPath                                    
* 4. Travelling salesman problem                              
* 5. Cycle Detection                                          
* 6. Topological Sort                                         
* 7. Find Nearby                                              
* 8. Exit                                                     
**************************************************************
Please select 1 - 8:

We created some tests for you to test your program, please run

$ bazel test tests:trojanmap_test

Please add you test in the trojanmap_test_student.cc and run

$ bazel test tests:trojanmap_test_student

std::vector<std::string> Autocomplete(std::string name);

We consider the names of nodes as the locations. Implement a method to type the partial name of the location and return a list of possible locations with partial name as prefix. Please treat uppercase and lower case as the same character.

Example:

Input: "Chi"
Output: ["Chick-fil-A", "Chipotle", "Chinese Street Food"]

Example:

**************************************************************
* 1. Autocomplete                                             
**************************************************************

Please input a partial location:ch
*************************Results******************************
Chinese Street Food
Cheebos Burger
Chick-fil-A
Chase
Chevron 1
Chipotle
Chase Plaza Heliport
Chevron 2
Church of Christ
Chucks Chicken & Waffles
Chevron
**************************************************************
Time taken by function: 2 ms

std::pair<double, double> GetPosition(std::string name);

Given a location name, return the latitude and longitude. There are no duplicated location names. You should mark the given locations on the map. If the location does not exist, return (-1, -1). The algorithm is case-sensitive.

Example:

Input: "Target"
Output: (34.0257016, -118.2843512)

**************************************************************
* 2. Find the position                                        
**************************************************************

Please input a location:Target
*************************Results******************************
Latitude: 34.0257 Longitude: -118.284
**************************************************************
Time taken by function: 1 ms

int CalculateEditDistance(std::string name1, std::string name2);

When entering a location name that does not exist in the map, the map will determine whether the input can be replaced with a "similar name" or not. Similar names refer to the names that exist in the map with a smallest distance from the original input. The distance between two names A and B is the minimum number of operations required to convert A to B. There are 3 operations:

• Insert a character
• Delete a character
• Replace a character

If the exact match is found, it will be shown on the map. Otherwise, the map will show the most similar name by using FindClosestName and print a warning. For example, if I type Rolphs, I should get a warning like "Did you mean Ralphs instead of Rolphs?"

You can use dynamic programming to calculate edit distance.

Example:

Input: "Rolphs", "Ralphs"
Output: 1

std::string FindClosestName(std::string name);

Example:

Input: "Rolphs"
Output: "Ralphs"

**************************************************************
* 2. Find the location                                        
**************************************************************

Please input a location:Rolphs
*************************Results******************************
No matched locations.
Did you mean Ralphs instead of Rolphs? [y/n]y
Latitude: 34.0318 Longitude: -118.291
**************************************************************
Time taken by function: 2 ms

std::vector<std::string> CalculateShortestPath_Dijkstra(std::string &location1_name,
                                               std::string &location2_name);
std::vector<std::string> CalculateShortestPath_Bellman_Ford(std::string &location1_name,
                                               std::string &location2_name);

Given 2 locations A and B, find the best route from A to B. The distance between 2 points is the euclidean distance using latitude and longitude. You should use both Dijkstra algorithm and Bellman-Ford algorithm. Compare the time for the different methods. Show the routes on the map. If there is no path, please return empty vector.

Please report and compare the time spent by these 2 algorithms.

Example:

Input: "Ralphs", "ChickfilA"
Output: ["2578244375", "5559640911", "6787470571", "6808093910", "6808093913", "6808093919", "6816831441", "6813405269", "6816193784", "6389467806", "6816193783", "123178876", "2613117895", "122719259", "2613117861", "6817230316", "3642819026", "6817230310", "7811699597", "5565967545", "123318572", "6813405206", "6813379482", "544672028", "21306059", "6813379476", "6818390140", "63068610", "6818390143", "7434941012", "4015423966", "5690152766", "6813379440", "6813379466", "21306060", "6813379469", "6813379427", "123005255", "6807200376", "6807200380", "6813379451", "6813379463", "123327639", "6813379460", "4141790922", "4015423963", "1286136447", "1286136422", "4015423962", "6813379494", "63068643", "6813379496", "123241977", "4015372479", "4015372477", "1732243576", "6813379548", "4015372476", "4015372474", "4015372468", "4015372463", "6819179749", "1732243544", "6813405275", "348121996", "348121864", "6813405280", "1472141024", "6813411590", "216155217", "6813411589", "1837212103", "1837212101", "6820935911", "4547476733"]

**************************************************************
* 3. CalculateShortestPath                                    
**************************************************************

Please input the start location:Ralphs
Please input the destination:Target
*************************Dijkstra*****************************
*************************Results******************************
"2578244375","5559640911","6787470571","6808093910","8410528464","8410528457","6808093913","6808093919","6816831441","6813405269","6816193784","6389467806","6816193783","123178876","2613117895","122719259","6807243574","6807243576","213332111","441895337","441895335","122719255","2613117893","6813405231","6813405237","6813405235","6047197523","6813379584","5237417650",
The distance of the path is:0.823773 miles
**************************************************************
Time taken by function: 23 ms

*************************Bellman_Ford*************************
*************************Results******************************
"2578244375","5559640911","6787470571","6808093910","8410528464","8410528457","6808093913","6808093919","6816831441","6813405269","6816193784","6389467806","6816193783","123178876","2613117895","122719259","6807243574","6807243576","213332111","441895337","441895335","122719255","2613117893","6813405231","6813405237","6813405235","6047197523","6813379584","5237417650",
The distance of the path is:0.823773 miles
**************************************************************
Time taken by function: 3484 ms

In this section, we assume that we are using a UAV which means we can fly directly from 1 point to another point. Given a vector of location ids, assume every location can reach all other locations in the vector (i.e. assume that the vector of location ids is a complete graph). Find the shortest route that covers all the locations exactly once and goes back to the start point.

You will need to return the progress to get the shortest route which will then be converted to an animation.

We will use the following algorithms:

• Brute-force (i.e. generating all permutations, and returning the minimum)

std::pair<double, std::vector<std::vector<std::string>>> TravellingTrojan_Brute_force(
      std::vector<std::string> location_ids);

• Brute-force enhanced with early backtracking

std::pair<double, std::vector<std::vector<std::string>>> TravellingTrojan_Backtracking(
      std::vector<std::string> location_ids);

• 2-opt Heuristic. Also see this paper

std::pair<double, std::vector<std::vector<std::string>>> TravellingTrojan_2opt(
      std::vector<std::string> location_ids);

We use early backtracking when the current cost is higher than current minimum.

Please report and compare the time spent by these 3 algorithms. 2-opt algorithm may not get the optimal solution. Please show how far your solution is from the optimal solution.

Show the routes on the map. For each intermediate solution, create a new plot. Your final video presentation should include the changes to your solution.

We will randomly select N points in the map and run your program.

**************************************************************
* 4. Travelling salesman problem                              
**************************************************************

In this task, we will select N random points on the map and you need to find the path to travel these points and back to the start point.

Please input the number of the places:8
"8201681442","6197156485","7786565237","6820972477","6807600525","1832234142","6819144993","1873055949",
Calculating ...
*************************Results******************************
TravellingTrojan_Brute_force
"8201681442","1873055949","6197156485","1832234142","6807600525","6819144993","7786565237","6820972477","8201681442",
The distance of the path is:7.94756 miles
**************************************************************
You could find your animation at src/lib/output.avi.          
Time taken by function: 59 ms

Calculating ...
*************************Results******************************
TravellingTrojan_Backtracking
"8201681442","6820972477","7786565237","6819144993","6807600525","1832234142","6197156485","1873055949","8201681442",
The distance of the path is:7.94756 miles
**************************************************************
You could find your animation at src/lib/output_backtracking.avi.
Time taken by function: 20 ms

Calculating ...
*************************Results******************************
TravellingTrojan_2opt
"8201681442","1873055949","6197156485","1832234142","6807600525","6819144993","7786565237","6820972477","8201681442",
The distance of the path is:7.94756 miles
**************************************************************
You could find your animation at src/lib/output_2opt.avi.     
Time taken by function: 0 ms

bool CycleDetection(std::vector<double> &square);

In this section, we use a square-shaped subgraph of the original graph by using four coordinates stored in std::vector<double> square, which follows the order of left, right, upper, and lower bounds.

Then try to determine if there is a cycle path in the that subgraph. If it does, return true and report that path on the map. Otherwise return false.

Example 1:

Input: square = {-118.299, -118.264, 34.032, 34.011}
Output: true

Here we use the whole original graph as our subgraph.

Example 2:

Input: square = {-118.290, -118.289, 34.030, 34.020}
Output: false

Here we use a square area inside USC campus as our subgraph

5
**************************************************************
* 5. Cycle Detection                                          
**************************************************************

Please input the left bound longitude(between -118.320 and -118.250):-118.299
Please input the right bound longitude(between -118.320 and -118.250):-118.264
Please input the upper bound latitude(between 34.000 and 34.040):34.032
Please input the lower bound latitude(between 34.000 and 34.040):34.011
*************************Results******************************
there exists a cycle in the subgraph 
**************************************************************
Time taken by function: 0 ms

5
**************************************************************
* 5. Cycle Detection                                          
**************************************************************

Please input the left bound longitude(between -118.320 and -118.250):-118.290
Please input the right bound longitude(between -118.320 and -118.250):-118.289
Please input the upper bound latitude(between 34.000 and 34.040):34.030
Please input the lower bound latitude(between 34.000 and 34.040):34.020
*************************Results******************************
there exist no cycle in the subgraph 
**************************************************************
Time taken by function: 0 ms

std::vector<std::string> DeliveringTrojan(std::vector<std::string> &location_names,
                                            std::vector<std::vector<std::string>> &dependencies);

In this section, we assume that we are using a UAV which means we can fly directly from 1 point to another point. Tommy Trojan got a part-time job from TrojanEats, for which he needs to pick up and deliver food from local restaurants to various location near the campus. Tommy needs to visit a few different location near the campus with certain order, since there are some constraints. For example, he must first get the food from the restaurant before arriving at the delivery point.

The TrojanEats app will have some instructions about these constraints. So, Tommy asks you to help him figure out the feasible route!

Here we will give you a vector of location names that Tommy needs to visit, and also some dependencies between those locations.

For example,

Input: 
location_names = {"Ralphs", "Chick-fil-A", "KFC"}
dependencies = {{"Ralphs","KFC"}, {"Ralphs","Chick-fil-A"}, {"Chick-fil-A", "KFC"}}

Here, {"Ralphs","KFC"} means that Tommy must go to Ralphs prior to KFC.

Your output should be:

Output: Ralphs  -> Chick-fil-A -> KFC

Also, we provide PlotPointsOrder function that can visualize the results on the map. It will plot each location name and also some arrowed lines to demonstrate a feasible route.

If no feasible route exists, you could simply return an empty vector.

Hint:

• You also need to finish ReadLocationsFromCSVFile and ReadDependenciesFromCSVFile functions, so you could read and parse data from you own CSV files. We also give two sample CSV files under input folder, which could be a reference.
• When it asks you filenames, you need to give the absolute path.
• If you do not have ReadLocationsFromCSVFile and ReadDependenciesFromCSVFile functions ready yet, you can just press enter when it asks you filenames. It will call the default locations and dependencies.
• The locations are actually nodes, and the dependencies could be directed edges. You may want to first construct a DAG and then implement topological sort algorithm to get the route.

*************************Results******************************
Topological Sorting Results:
Ralphs
Chick-fil-A
KFC
**************************************************************
Time taken by function: 2 ms

In the user interface, we read the locations and dependencies from topologicalsort_dependencies.csv and topologicalsort_locations.csv to modify your input there.

Given a attribute name C, a location name L and a number r and k, find at most k locations in attribute C on the map near L(do not include L) with the range of r and return a vector of string ids. The order of locaitons should from nearest to farthest. And you should not include the current location.

std::vector<std::string> TrojanMap::FindNearby(std::string attributesName, std::string name, double r, int k);

All attributes

'artwork', 'attraction', 'bakery', 'bank', 'bar', 'beauty', 'beverages', 'bicycle', 'bicycle_rental', 'bus_station', 'cafe', 'car', 'car_repair', 'car_wash', 'charging_station', 'childcare', 'clinic', 'clothes', 'confectionery', 'convenience', 'copyshop', 'dentist', 'department_store', 'driving_school', 'fabric', 'fast_food', 'food_court', 'fountain', 'fuel', 'gallery', 'hairdresser', 'hospital', 'hotel', 'library', 'marketplace', 'mobile_phone', 'museum', 'music', 'optician', 'parcel_locker', 'parking', 'pharmacy', 'place_of_worship', 'police', 'post_office', 'restaurant', 'school', 'shoe_repair', 'shoes', 'skate', 'social_facility', 'supermarket', 'theatre', 'tobacco', 'yes', 'yoga'

Please report and compare the time spent by this algorithm and show the points on the map.

**************************************************************
* 7. Find Nearby                                    
**************************************************************

Please input the attribute:supermarket
Please input the locations:Ralphs
Please input radius r:10
Please input number k:10
*************************Results******************************
Find Nearby Results:
1 Trader Joes
2 Cal Mart Beer & Wine Food Store
3 Food 4 Less
**************************************************************
Time taken by function: 5 ms

For each menu item, your program should show the time it took to finish each task.

Please make sure to provide various examples when you report the runtime. For example for topological sort, show an example with few nodes and another example with 10 or more nodes. The idea is to see how your runtime grows as input size grows.

For shortest path algorithms, you should compare solving the same problem with different algorithms (Dijkstra and Bellman-Ford). Please show the results on at least 3 different examples.

Similarly for TSP problem, please provide various examples that show the runtime comparison. In particular, you should show at what point using the exhaustive search is not practical and compare the same input with the heuristic implementation.

Your final project should be checked into Github. The README of your project is your report.

Your REPORT.md file should include four sections: Please create a new REPORT.md file and write your report there.

1. High-level overview of your design (Use diagrams and pictures for your data structures).
2. Detailed description of each function and its time complexity.
3. Time spent for each function.
4. Discussion, conclusion, and lessons learned.

1. Implementation of Auto complete: 5 points. (Phase 1)
2. Implementation of GetPosition: 5 points. (Phase 1)
3. Implementation of EditDistance: 10 points. (Phase 1)
4. Implementation of shortest path: 15 points. (Phase 2)
   1. Bellman-Ford implementation
   2. Dijkstra implementation
   3. Plot two paths, and measure and report time spent by two algorithms.
5. Implement of Cycle detection: 10 points. (Phase 2)
   1. Boolean value and draw the cycle if there exists one.
6. Topological Sort: 10 points. (Phase 2)
   1. Check whether there exist a topological sort or not
   2. Return the correct order and plot those point on the map
7. Implementation of Travelling Trojan: (Phase 3)
   1. Brute-force: 5 points.
   2. Brute-force enhanced with early backtracking: 5 points.
   3. 2-opt: 10 points.
   4. Animated plot: 5 points.
8. FindNearby points: 10 points. (Phase 3)
   1. Return the correct ids and draw the points.
9. Video presentation and report: 10 points. (Phase 3)
10. Creating reasonable unit tests: 10 points.
    1. Three different unit tests for each item.
11. Extra credit items: Maximum of 20 points:

    1. 3-opt: 10 points.

    2. Genetic algorithm implementation for Travelling Trojan: 10 points

    3. Create dynamic and animated UI using ncurses: 10 points

       • Uncomment #define NCURSES in main.cc and mapui.h
       • Create your menu in DynamicPrintMenu().
       • You could check https://github.com/ourarash/ncurses_bazel
       • Please develope your own UI.
       • Example

         

    4. Accurate measurement of your algorithm runtime using Google Benchmark while sweeping the input size and providing a diagram of how the runtime grows based on the input size: 10 points.