Author: Boyang Xiao
- Email: boyangxi@usc.edu
- Github: here
- OS: MacOS 12.5.1 / Linux
- Compiler: Bazel 5.1.1
- Language: C++ 11
- Team members:
- Instructor: Arash Saifhashemi
- Video presentation: 👉 here
- Project instructions: 👉 here
In this project, we implement a map application software called TrojanMap. The app is programmed in C++ and several algorithms commonly used on map apps are implemented in this project.
- Item 1: Auto-complete
- Item 2: Find coordinates
- Item 3: Get all categories
- Item 4: Get all locations in a category
- Item 5: Get locations using regular expressions
- Item 6: Find the shortest path
- Item 7: Cycle detection
- Item 8: Toporlogical sorting
- Item 9: Travelling Trojan problem
- Item 10: Find nearby
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. Here are instructions to install OpenCV on your OS:
Step 1. type the following three lines in your terminal
$ brew install cmake
$ brew install opencv
$ brew install ncursesStep 2.
Check the installation paths of opencv and ncurses by
brew info opencvand
brew info ncursesrespectively, and update their paths in the WORKSPACE file of your project root directory with the actual installation paths
Step 1.
$ 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/* ./Step 2. Make sure you set the path_to_install_folder to be the absolute path to the install folder under opencv when running the following commands
$ 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 installFor 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 installFor MacOS users, run
$ bazel run src/main:mainFor Ubuntu users, run
$ bazel run --cxxopt='-std=c++17' src/main:mainIf everything is correct, a menu similar to this will show up.
TrojanMap Menu
**************************************************************
* Enter the function number (1-11) to start:
* 1. Autocomplete
* 2. Find the location
* 3. Find all location categories
* 4. Get all locations of a category
* 5. Get location matching regular expression
* 6. CalculateShortestPath
* 7. Cycle Detection
* 8. Topological Sort
* 9. Traveling salesman problem
* 10. Find Nearby
* 11. Exit
**************************************************************You can use commands below to test the program.
$ bazel test tests:trojanmap_test_student
$ bazel test tests:trojanmap_teststd::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-
What is the runtime of your algorithm?
Answer: Our algorithm has a runtime complexity of O(n). -
(Optional) Can you do it faster than
O(n)?
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 msRuntime complexity: O(n)
int CalculateEditDistance(std::string name1, std::string name2);When entering a location name that does not exist in the map, your program should determine whether the input can be replaced with a "similar name" or not. By "similar names" we mean 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?".
Write a dynamic programming solution to calculate edit distance.
std::string FindClosestName(std::string name);Notes:
- Space can be treated like other characters.
- Spell checking part should be case insensitive.
Example:
Input: "Rolphs", "Ralphs"
Output: 1
In the user interface of your program, you should show the names that have the minimum edit distance to the name that the user entered.
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 msstd::vector<std::string> GetAllCategories();Some of the locations have category types (attributes field in data.csv file).
In this section, your program should print all available categories among all existing categories in the map. There should be no duplicates in the output.
Runtime complexity: O(n)
std::pair<double, double> GetAllLocationsFromCategory(std::string category);In this section if the user entries a category, the program prints all locations that match that category. For example, if there is a category called "Grocery", your program should print all locations that match the "Grocery" category.
Runtime complexity: O(n)
std::pair<double, double> GetLocationRegex(std::regex location);In this section if the user enters a regular expression, they should see all locations that match that regular expression.
Your program should also verify if the input regular expression was correct.
Runtime complexity: O(n)
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.
Example:
**************************************************************
* 6. CalculateShortestPath
**************************************************************
Please input the start location:Ralphs
Please input the destination:Target
*************************Dijkstra*****************************
*************************Results******************************
"2578244375","4380040154","4380040158","4380040167","6805802087","8410938469","6813416131","7645318201","6813416130","6813416129","123318563","452688940","6816193777","123408705","6816193774","452688933","452688931","123230412","6816193770","6787470576","4015442011","6816193692","6816193693","6816193694","4015377691","544693739","6816193696","6804883323","6807937309","6807937306","6816193698","4015377690","4015377689","122814447","6813416159","6813405266","4015372488","4015372487","6813405229","122719216","6813405232","4015372486","7071032399","4015372485","6813379479","6813379584","6814769289","5237417650",
The distance of the path is:0.927969 miles
**************************************************************
Time taken by function: 39 ms
*************************Bellman_Ford*************************
*************************Results******************************
"2578244375","4380040154","4380040158","4380040167","6805802087","8410938469","6813416131","7645318201","6813416130","6813416129","123318563","452688940","6816193777","123408705","6816193774","452688933","452688931","123230412","6816193770","6787470576","4015442011","6816193692","6816193693","6816193694","4015377691","544693739","6816193696","6804883323","6807937309","6807937306","6816193698","4015377690","4015377689","122814447","6813416159","6813405266","4015372488","4015372487","6813405229","122719216","6813405232","4015372486","7071032399","4015372485","6813379479","6813379584","6814769289","5237417650",
The distance of the path is:0.927969 miles
**************************************************************
Time taken by function: 7084 ms
- Dijakstra: O(nlogn)
- Bellman-ford: O(n2)
Runtime samples:
| Point A to Point B | Dijkstra | Bellman-Ford |
|---|---|---|
| Ralphs -> Target | 10420 ms | 8832 ms |
| Chick-fli-A -> Target | 12537 ms | 7937 ms |
| Pico -> Chick-fil-A | 27944 ms | 11851 ms |
| Pizza King -> Pico | 43314 ms | 14126 ms |
| Arco -> 76 | 40047 ms | 10611 ms |
| 76 -> Ralphs | 36251 ms | 10827 ms |
| Chick-fil-A -> Arco | 28814 ms | 8057 ms |
| Bevvy -> Subway | 37924 ms | 11225 ms |
| Subway -> Pizza King | 31580 ms | 8690 ms |
| Arco -> Subway | 33380 ms | 10726 ms |
| Bevvy -> Arco | 8125 ms | 11001 ms |
| Target -> Ralphs | 16421 ms | 8282 ms |
| 76 -> Target | 22278 ms | 10540 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 the path of the cycle on the map. Otherwise return false.
Your report should include at least five examples.
Runtime complexity: O(n) (n stands for # of points in the square area)
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 -> KFCAlso, 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
ReadLocationsFromCSVFileandReadDependenciesFromCSVFilefunctions, so you could read and parse data from you own CSV files. We also give two sample CSV files underinputfolder, which could be a reference. - When it asks you filenames, you need to give the absolute path.
- If you do not have
ReadLocationsFromCSVFileandReadDependenciesFromCSVFilefunctions 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.
Note
- Your report should show several examples of topological sort with at least 5 to 10 nodes.
Below is an example output of 3 nodes
*************************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.
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>>> TravelingTrojan_Brute_force(
std::vector<std::string> location_ids);- Brute-force enhanced with early backtracking
std::pair<double, std::vector<std::vector<std::string>>> TravelingTrojan_Backtracking(
std::vector<std::string> location_ids);- 2-opt Heuristic. Also see this paper
std::pair<double, std::vector<std::vector<std::string>>> TravelingTrojan_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.
**************************************************************
* 9. Traveling 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******************************
TravelingTrojan_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******************************
TravelingTrojan_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******************************
TravelingTrojan_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
- Brute-force: O(nlogn)
- Backtracking: O(nlogn)
- 2-opt: O(1) (It depends on how many times we set to stop the loop)
Runtime samples:
| Number of Points | Brute-force | Backtracking | 2-opt | 2-opt results vs optimized resutls |
|---|---|---|---|---|
| 2 ｜ 0 ms | 0 ms | 0 ms | 0 mi | |
| 3 | 0 ms | 0 ms | 0 ms | 0 mi |
| 4 | 0 ms | 0 ms | 0 ms | 0 mi |
| 5 | 1 ms | 0 ms | 1 ms | 0 mi |
| 6 | 6 ms | 2 ms | 5 ms | 0 mi |
| 7 | 42 ms | 8 ms | 75 ms | 0 mi |
| 8 | 35 ms | 62 ms | 457 ms | 0 mi |
| 9 | 3279 ms | 548 ms | 5796 ms | 0 mi |
| 10 | 34956 ms | 2192 ms | 72937 ms | 0 mi |
| 11 | TIME-OUT* | 3803 ms | TIME-OUT | NULL |
| 12 | TIME-OUT | 8333 ms | TIME-OUT | NULL |
*We set 80,000 ms as a maximum time. If it takes longer than that, it will be marked as TIME-OUT.
Given an 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 locations should be 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.
**************************************************************
* 10. 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
In this project, we expererienced a complete process of developing and optimizing a C++ application. We implemented several very classical functions that are widely used in every kind of map apps and other maps, including the functions aiming for strings (e.g. Auto-complete, Edit distance etc...) and algorithms that are used for guidances and navigations (e.g. Shortest paths, TSP etc...). The experience that we study, implement and debug these classical algrithms from scratch can be really valuable for us to apply for jobs as Software Engineers or Algorithm Engineers.
Also, we tried to modify the UI and test cases to optimize the app, which is a necessary skill to practice when we are encoutering a real-world project. Xihang and I worked as a team and we parallelly worked on branches in Github and collaberated together to build the whole project repository. After every time of pull and commits, we can have some conflicts of course. But we learnt how to collaberate and coordinate and we solved all the conflicts in the end. This can be a even more useful skill when we collaberate with other team members in the real world.
To conclude, in this project, we managed to build a real-world program with C++ and OpenCV. We put several algorithms into practice, leant the project structures of a C++ program and learnt how to collaberate on Github reposetories.
Your final project should be checked into Github. The README.md 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.
- High-level overview of your design (Use diagrams and pictures for your data structures).
- Detailed description of each function and its time complexity.
- Time spent for each function.
- Discussion, conclusion, and lessons learned.
- Item 1 (AutoComplete): 1 point. (Phase 1)
- Item 2-1 (GetPosition): 1 point. (Phase 1)
- Item 2-2 (EditDistance): 10 points. (Phase 2)
- Item 3 (GetAllCategories): 3 Points. (Phase 2)
- Item 4 (GetAllLocationsFromCategory): 5 Points. (Phase 2)
- Item 5 (GetLocationRegex): 5 Points. (Phase 2)
- Item 6 (Shortest path): 15 points. (Phase 2)
- Bellman-Ford implementation
- Dijkstra implementation
- Table/Plot for comparison, and measure and report time spent by two algorithms.
- Item 7 (Cycle detection): 5 points. (Phase 2)
- Boolean value and draw the cycle if there exists one.
- Item 8 (Topological Sort): 5 points (Phase 2)
- Check whether there exist a topological sort or not
- Return the correct order and plot those point on the map
- Item 9 (Traveling Trojan) (Phase 3)
- Brute-force: 5 points.
- Brute-force enhanced with early backtracking: 5 points.
- 2-opt: 10 points.
- Animated plot: 5 points.
- Item 10 (FindNearby): 5 points. (Phase 3)
- Return the correct ids and draw the points.
- Creating reasonable unit tests: 10 points. - Three different unit tests for each function.
- Video presentation and report: 10 points. (Phase 3)
-
Implementation of 3-opt: 10 points.
-
Genetic algorithm implementation for Traveling Trojan: 10 points
-
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
-
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.
