-
Notifications
You must be signed in to change notification settings - Fork 0
/
trojanmap.h
148 lines (109 loc) · 5.92 KB
/
trojanmap.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#ifndef TROJAN_MAP_H
#define TROJAN_MAP_H
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <cfloat>
#include <math.h>
#include <fstream>
#include <sstream>
#include <climits>
// A Node is the location of one point in the map.
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.
};
class TrojanMap{
public:
// Constructor
TrojanMap(){CreateGraphFromCSVFile();};
// A map of ids to Nodes.
std::unordered_map<std::string, Node> data;
//-----------------------------------------------------
// Read in the data
void CreateGraphFromCSVFile();
//-----------------------------------------------------
// TODO: Implement these functions and create unit tests for them:
// Get the Latitude of a Node given its id.
double GetLat(const std::string& id);
// Get the Longitude of a Node given its id.
double GetLon(const std::string& id);
// Get the name of a Node given its id.
std::string GetName(const std::string& id);
// Get the id given its name.
std::string GetID(const std::string& name);
// Get the neighbor ids of a Node.
std::vector<std::string> GetNeighborIDs(const std::string& id);
// Returns a vector of names given a partial name.
std::vector<std::string> Autocomplete(std::string name);
// Returns lat and lon of the given the name.
std::pair<double, double> GetPosition(std::string name);
// Calculate location names' edit distance
int CalculateEditDistance(std::string, std::string);
// Find the closest name
std::string FindClosestName(std::string name);
// Get the distance between 2 nodes.
double CalculateDistance(const std::string &a, const std::string &b);
// Calculates the total path length for the locations inside the vector.
double CalculatePathLength(const std::vector<std::string> &path);
// Given the name of two locations, it should return the **ids** of the nodes
// on the shortest path.
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);
void TravellingTrojan_helper(std::vector<std::string> &location_ids,std::vector<std::vector<double>> &weights,std::vector<std::vector<std::string>> &path,double &minDist,std::vector<int> ¤tPath,double currDist,std::unordered_set<int> &seen, bool is_bruteforce);
// Given CSV filename, it read and parse locations data from CSV file,
// and return locations vector for topological sort problem.
std::vector<std::string> ReadLocationsFromCSVFile(std::string locations_filename);
// Given CSV filenames, it read and parse dependencise data from CSV file,
// and return dependencies vector for topological sort problem.
//
std::vector<std::vector<std::string>> ReadDependenciesFromCSVFile(std::string dependencies_filename);
// Given a vector of location names, it should return a sorting of nodes
// that satisfies the given dependencies.
std::vector<std::string> DeliveringTrojan(std::vector<std::string> &location_names,
std::vector<std::vector<std::string>> &dependencies);
void TopologicalSort(std::string &location, std::unordered_map<std::string, std::vector<std::string>> &dependency_map, std::unordered_map<std::string, bool> &visited, std::vector<std::string> &result);
// void DFSHelper(std::string &root, std::vector<std::string> &result, std::vector<std::vector<std::string>> &dependencies);
// Given a vector of location ids, it should reorder them such that the path
// that covers all these points has the minimum length.
// The return value is a pair where the first member is the total_path,
// and the second member is the reordered vector of points.
// (Notice that we don't find the optimal answer. You can return an estimated
// path.)
std::pair<double, std::vector<std::vector<std::string>>> TravellingTrojan_Brute_force(
std::vector<std::string> location_ids);
std::pair<double, std::vector<std::vector<std::string>>> TravellingTrojan_Backtracking(
std::vector<std::string> location_ids);
std::pair<double, std::vector<std::vector<std::string>>> TravellingTrojan_2opt(
std::vector<std::string> location_ids);
// Check whether the id is in square or not
bool inSquare(std::string id, std::vector<double> &square);
bool hasCycle(std::string current_id,std::unordered_map<std::string, bool> &visited, std::string parent_id);
// Get the subgraph based on the input
std::vector<std::string> GetSubgraph(std::vector<double> &square);
// Given a subgraph specified by a square-shape area, determine whether there is a
// cycle or not in this subgraph.
bool CycleDetection(std::vector<std::string> &subgraph, std::vector<double> &square);
// Given a location id and k, find the k closest points on the map
std::vector<std::string> FindNearby(std::string, std::string, double, int);
void CreateAnimation(std::vector<std::vector<std::string>> path_progress);
// std::pair<double, std::vector<std::vector<std::string>>> TravellingTrojan_3opt(
// std::vector<std::string> &location_ids);
//----------------------------------------------------- User-defined functions
};
#endif