-> Author : Hardik Prajapati
-> Email : hprajapa@usc.edu
-> Demo : https://www.youtube.com/watch?v=wWINKB1CmvU
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.
};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
**************************************************************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? -> O(n), where n is length of total locations (nodes) in our database
- (Optional) Can you do it faster than
O(n)? -> Yes, this can be done using 'Trie' data structure. It would reduce time complexity from O(n) to O(d) where d=length of longest word starting with the given initials.
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
- What is the runtime of your algorithm? -> O(n), where n is length of total locations (nodes) in our database
For example, if I type Rolphs, I should get a warning like "Did you mean Ralphs instead of Rolphs?".
- What is the runtime of your algorithm? -> O(p*q), where p=length of location 1, q=length of location 2
Input: "Rolphs", "Ralphs"
Output: 1
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- What is the runtime of your algorithm? -> O(n * p * q) , where n is length of total locations (nodes) in our database and p=length of location 1, q=length of location 2
In this section, our program prints all available categories among all existing categories in the map.
- What is the runtime of your algorithm? -> O(n * d) , where n is length of total locations (nodes) in our database and d=max length of attribute set among all locations
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", our program prints all location ids that match the "bank" category.
- What is the runtime of your algorithm? -> O(n * 1) , where n is length of total locations (nodes) in our database.
In this section if the user enters a regular expression, they should see all location ids that match that regular expression.
Our program also verifies if the input regular expression was correct.
- What is the runtime of your algorithm? -> O(n) , where n is length of total locations (nodes) in our database
Given 2 locations A and B, the program finds the best route from A to B. The distance between 2 points is the euclidean distance using latitude and longitude. The program uses both Dijkstra algorithm and Bellman-Ford algorithm. The time comparison for the different methods is as below. The program show the routes on the map.
The runtime of the algorithm for several examples.
| Point A to Point B | Dijkstra | Bellman Ford |
|---|---|---|
| Cava - Chipotle | 63 | 67459 |
| Pico - Cava | 680 | 107370 |
| KFC - Chevron | 239 | 78777 |
| Tommy Trojan - Target | 44 | 55250 |
| Pico - Dulce | 226 | 104080 |
| Cava - Target | 14 | 50191 |
| Tommy Trojan - KFC | 96 | 66793 |
| Tommy Trojan - Chipotle | 20 | 60195 |
| Tommy Trojan - Chevron | 67 | 71792 |
| Tommy Trojan - Pico | 379 | 83604 |
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
- What is the runtime of your algorithm? -> Dijkstra: O(V^2) , where V = total locations (nodes) visited. -> Bellman Ford: O(E*V), where E = number of paths observed between locations and V = number of locations visited.
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, we return true and report the path of the cycle on the map. Otherwise return false.
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
Example 3:
Input: square = {-118.295, -118.285, 34.018, 34.016}
Output: trueHere we use a rectangel area inside USC campus as our subgraph
Example 4:
Input: square = {-118.300, -118.265, 34.011, 34.005}
Output: trueHere we use a rectangel area inside USC campus as our subgraph
Example 5:
Input: square = {-118.290, -118.289, 34.005, 34.004}
Output: falseHere we use a rectangel 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- What is the runtime of your algorithm? -> O(n) , where n = total locations (nodes) in the subgraph.
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, the app will 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.
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.
Output:
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.
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.
- What is the runtime of your algorithm? -> O(n) , where n = total locations (nodes) to be visited.
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). The app finds the shortest route that covers all the locations exactly once and goes back to the start point.
We will use the following algorithms:
-
Brute-force (i.e. generating all permutations, and returning the minimum)
-
Brute-force enhanced with early backtracking
-
2-opt Heuristic. Also see this paper
We use early backtracking when the current cost is higher than current minimum.
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 the app needs 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
| Number of points | Brute Force | Backtracking | 2-opt |
|---|---|---|---|
| 3 | 14 | 0 | 0 |
| 4 | 0 | 0 | 0 |
| 5 | 2 | 1 | 0 |
| 6 | 8 | 1 | 0 |
| 7 | time limit exceed | ~ | ~ |
- What is the runtime of your algorithm? -> Brute Force: O(n!) , where n = total locations (nodes) to be visited. -> Backtracking: O((n-1)!) , where n = total locations (nodes) to be visited. -> 2-opt: O(i*n^2) , where n = total locations (nodes) to be visited, i=iterations.
Given an attribute name C, a location name L and a number r and k, the app finds at most k locations in attribute C on the map near L with the range of r and return a vector of string ids.
The order of locations are from nearest to farthest.
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'
**************************************************************
* 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: 29 ms
**************************************************************
* 10. Find Nearby
**************************************************************
Please input the attribute:fuel
Please input the locations:target
Please input radius r:1
Please input number k:3
*************************Results******************************
Find Nearby Results:
1 Arco
2 Chevron 2
**************************************************************
Time taken by function: 428 ms
- What is the runtime of your algorithm? -> O(n) , where n = total locations (nodes) in our database.
Given an vector of locations, the app finds the shortest path to visit all the locations.
**************************************************************
* 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
input: Tommy Trojan, Chipotle, Chevron, Ralphs
The distance of the path is:2.06923 miles
Time taken by function: 1184 ms
- What is the runtime of your algorithm? -> O(V^2*(n*(n-1)/2) + (n-1)!) , where n = total locations (nodes) to be visited, V=maximum neighbors among all the pairs of places to be visited.
-> Data Structures: Tree, Graphs, Stacks, Queues, Priority Queues, Maps, Sets
-> Algorithms: Dijkstra, Bellman Ford, Travelling Salesman Problem
-> Techniques: DFS, BFS, Recursion, Backtracking, Dynamic Programming
-> Coding: C++ STL commands
-> Ubuntu OS environment
-> GIT version control