EE599 Final Project - TrojanMap

TrojanMap

This project focuses on using data structures and graph search algorithms to build a mapping 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 tests.

---

The data Structure

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

class Node {
  public:
    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.
};

---

Prerequisites

OpenCV Installation

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

Notice: Installing this library may take a long time. This is only for visualization. You can still start coding even without installing this library and visualization.

Use the following commands to install OpenCV.

cd TrojanMap
git clone https://github.com/opencv/opencv.git
cd opencv/
mkdir build install
cd build

For Ubuntu,

sudo apt-get install cmake libgtk2.0-dev pkg-config
sudo apt install libcanberra-gtk-module libcanberra-gtk3-module

For MacOS,

brew install cmake

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.

cmake -D CMAKE_INSTALL_PREFIX=**path_to_install_folder** -D BUILD_LIST=core,highgui,imgcodecs,imgproc,videoio  -D WITH_TBB=ON -D WITH_OPENMP=ON -D WITH_IPP=ON -D CMAKE_BUILD_TYPE=RELEASE -D BUILD_EXAMPLES=OFF -D WITH_NVCUVID=ON -D WITH_CUDA=ON -D BUILD_DOCS=OFF -D BUILD_PERF_TESTS=OFF -D BUILD_TESTS=OFF -D WITH_CSTRIPES=ON -D WITH_OPENCL=ON ..
make install

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

cmake -D CMAKE_INSTALL_PREFIX=/Users/ari/github/TrojanMap/opencv/install  -D BUILD_LIST=core,highgui,imgcodecs,imgproc,videoio  -D WITH_TBB=ON -D WITH_OPENMP=ON -D WITH_IPP=ON -D CMAKE_BUILD_TYPE=RELEASE -D BUILD_EXAMPLES=OFF -D WITH_NVCUVID=ON -D WITH_CUDA=ON -D BUILD_DOCS=OFF -D BUILD_PERF_TESTS=OFF -D BUILD_TESTS=OFF -D WITH_CSTRIPES=ON -D WITH_OPENCL=ON ..
make install

---

Run the program

Please run:

bazel run src/main:main

If everything is correct, this menu will show up.

**************************************************************
* Select the function you want to execute.
* 1. Autocomplete
* 2. Find the position
* 3. CalculateShortestPath
* 4. Traveling salesman problem
* 5. Exit
**************************************************************

Test the program

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

bazel test tests:tests:trojanmap_test

Please add you test in the trojanmap_test_student.cc and run

bazel test tests:trojanmap_test_student

First task is to implement a function for each menu item

Step 1: Autocomplete the location name

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: "ch"
Output: ["ChickfilA", "Chipotle Mexican Grill"]

Input: "ta"
Output: ["Target", "Tap Two Blue"]

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

Please input a partial location:ch
*************************Results******************************
ChickfilA
Chipotle Mexican Grill
**************************************************************

Step 2: Find the place's Cordinates in the Map

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

Given a location name, return the latitude and longitude. There is no duplicate location name. Mark the locations on the map. If the location does not exists, return (-1, -1).

Example:

Input: "ChickfilA"
Output: (34.0167334, -118.2825307)

Input: "Ralphs"
Output: (34.0317653, -118.2908339)

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

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

Please input a location:Target
*************************Results******************************
Latitude: 34.0257 Longitude: -118.284
**************************************************************

Step 3: CalculateShortestPath between two places

std::vector<std::string> CalculateShortestPath(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 can use Dijkstra algorithm or A* algorithm. Compare the time for the different methods. Show the routes on the map. If there is no path, please return empty vector.

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
**************************************************************
* 3. CalculateShortestPath
**************************************************************
*************************Results******************************
2578244375
5559640911
6787470571

...

6820935911
4547476733
**************************************************************

Step 4: The Travelling Trojan Problem (AKA Traveling salesman!)

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

In this section, we assume that a complete graph is given to you. That means each node is a neighbor of all other nodes. Given a vector of location ids, assume every location can reach every location in the list (Complete graph. Do not care the neighbors). Find the shortest route that covers all the locations and goes back to the start point. You will need to return the progress to get the shortest route which will be converted to a animation.

We will use the following algorithms:

• Brute Force Method

std::pair<double, std::vector<std::vector<std::string>>> TravellingTrojan(
      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);

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
**************************************************************
* 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:10
Calculating ...
*************************Results******************************
123120189
1931345270
4011837224
4011837229
2514542032
2514541020
6807909279
63068532
214470792
4015477529
123120189
**************************************************************
The distance of the path is:4.61742
**************************************************************
You could find your animation at src/lib/output.avi

Report and Rubrics:

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

Report:

Your README file should include two sections:

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

Rubrics:

1. Implementation of auto complete: 10 points.
2. Implementation of GetPosition: 5 points.
3. Implementation of shortest path: 20 points.
4. Implementation of Travelling Trojan:
   1. Brute Force: 10 points
   2. 2-opt: 15 points.
   3. Animated plot: 10 points.
5. Creating reasonable unit tests: 20 points.
6. Video presentation and report: 10 points.
7. Extra credit items: Maximum of 20 points:
   1. A second shortest path algorithms (For example, you can implement both Bellman-Ford and Dijkstra): 10 points.
   2. 3-opt (If you chose to implement 2-opt for Travelling Trojan): 20 points.
   3. Genetic algorithm implementation for Travelling Trojan: 20 points.