The project is optional: you can select one of the following options:
- Work on the project and submit the reports.
- Submit homework assignments (HW4, 5, 6).
If you chose to work on the project, you don't have to submit the remaining homework assignments. Similarly, if you chose to work on the homework assignment, you do not have to submit the project.
You should inform us of your choice by the first due date (Friday Nov 18).
If you plan to become a software engineer, we recommend to work on the project as it will give you more experience in coding a real life project. Otherwise, you can take the homework assignments.
Not everything in the project is covered in the class. The idea is for you to do some quick research and figure them out. For example, you should read on handling regular expressions in C++.
We expect both options to take similar amount of time. The project however might require extra effort from you during the environment setup and installing prerequisites.
Each team should consist of one or two students. You can find team-mates from who are in other sections of the course. You should select your teammates by the first due date (Nov 18).
The project is submitted in different phases. You are required to submit the following:
-
Phase 1, 2, and 3: these should be submitted on github.
-
Video presentation: you and your team mate will create a 3-4 minute video, post it as an unlisted video on Youtube and submit the link. The video should include:
- Teammates introduction
- Demo of the executable
- Quick overview of the algorithm and code architecture
- Tables, plots and comparisons
- No coding details in the video.
-
Final report in the README file of your github submission. The final report should include the questions that are asked in this README file, your tables and plots for the runtime results, and any other detail of your code.
- Phase 1: Friday, Nov 18, 23:59 pm
- Phase 2: Friday, Nov 25, 23:59 pm
- Phase 3: Friday, Dec 2, 23:59 pm
- Video Presentation: Friday, Dec 2, 23:59 pm
- Report: Friday, Dec 9, 23:59 pm
This project focuses on using data structures in C++ and implementing various graph algorithms to build a map application.
- Please clone the repository, read through README.md and implement the functions of the project.
- Please make sure that your code can run
bazel runandbazel test. - You need to fill in trojanmap.cc, mapui.cc and maybe mapui.h, and add unit tests in the
testsdirectory. - We will use autograder to grade some of the questions
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.
};The details of environment setup will be reviewed in the discussion session. Please do not miss that class!
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 libraries.
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 update
$ sudo apt install cmake libgtk2.0-dev pkg-config
$ sudo apt install libcanberra-gtk-module libcanberra-gtk3-module
$ sudo apt 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=/home/ee538/Hardik/EE538_HWs/fall2022_trojanmap-hp6318/opencv/install -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. Find Path to Visit All Places
* 12. Exit
**************************************************************We created some tests for you to test your program, please run
$ bazel test tests:trojanmap_testPlease add you test in the trojanmap_test_student.cc and run
$ bazel test tests:trojanmap_test_studentstd::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. Please return an empty output if the input string is empty.
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?
- (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 ms
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.
std::vector<std::string> 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 "bank", your program should print all location ids that match the "bank" category.
std::vector<std::string> GetLocationRegex(std::regex location);In this section if the user enters a regular expression, they should see all location ids that match that regular expression.
Your program should also verify if the input regular expression was correct. Return an empty vector if the regex is not valid or matches no items.
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 algorithms.
You should create a table like below, which includes the runtime of the algorithm for several examples.
| Point A to Point B | Dijkstra | Bellman Ford | Bellman Ford optimized |
|---|---|---|---|
| t1 | t2 | t3 |
Your table should show have at least 15 rows.
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
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.
Example 1:
Input: square = {-118.299, -118.264, 34.032, 34.011}
Output: trueHere we use the whole original graph as our subgraph.
Example 2:
Input: square = {-118.290, -118.289, 34.030, 34.020}
Output: falseHere 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 msstd::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
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
Given an vector of locations, you need to find the shortest path to visit all the locations.
std::vector<std::string> TrojanMap::TrojanPath(std::vector<std::string> &location_names)Please report and compare the time spent by this algorithm and show the points on the map.
**************************************************************
* 11. Shortest Path to Visit all Nodes
**************************************************************
Please input the locations filename:
*************************Results******************************
"3088547686","4835551100","4835551099","4835551098","6813565307","6813565306","6813565305","6813565295","6813565296","3402814832","4835551107","6813379403","6813379533","3402814831","6813379501","3402810298","6813565327","3398574883","6813379494","6813379495","6813379544","6813379545","6813379536","6813379546","6813379547","6814916522","6814916523","1732243620","4015372469","4015372463","6819179749","1732243544","6813405275","348121996","348121864","6813405280","1472141024","6813411590","216155217","6813411589","1837212103","1837212101","6814916516","6814916515","6820935910","4547476733","6820935910","6814916515","6814916516","1837212101","6813411588","4015372458","1837212100","6820935907","2753199985","1837212107","1837212104","4015405543","4015405542","1781230449","1781230450","6820935898","6813379556","6820935901","6820935900","6819179753","4540763379","3233702827","1862347583","5231967015","4399697302","4399697304","6807762271","122728406","6787673296","123209598","6814958391","4399697589","4872897515","602606656","3402887080","6814958394","3402887081","6813379483","6813379589","6352865690","4015203127","4015203129","3195897587","4015203132","6389467809","21098539","4015203133","4015203134","4015203136","123152294","6816193786","6816193785","6808069740","6813416155","6813416151","6813416152","6813416153","6813416154","6813416145","7232024780","6818427916","6818427917","6818427898","6818427892","6818427918","6818427919","6818427920","4380040148","4380040152","4380040153","4380040154","2578244375",
The distance of the path is:2.26759 miles
Time taken by function: 233 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 the 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.
Please provide a table like below that compares the runtime of your algorithms for different number of nodes:
| Number of nodes | Time with algorithm 1 | Time with algorithm 2 |
|---|---|---|
| t1 | t2 |
Your table should show have at least 15 rows.
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): 4 Points. (Phase 2)
- Item 5 (GetLocationRegex): 6 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 11 (TrojanPath): 10 points. (Phase 3)
- Return the correct ids and draw the points.
- Creating reasonable unit tests: 10 points. - Three different unit tests for each function.
- 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.
