-
Notifications
You must be signed in to change notification settings - Fork 0
/
Prune.h
155 lines (120 loc) · 4.05 KB
/
Prune.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
149
150
151
152
153
154
155
#ifndef PRUNE_H
#define PRUNE_H
#include "QueryGenerator.h"
/***************************************
* Route structure
**************************************/
struct Route
{
Route():
route_len(1), cost(0.0), p_cost(0.0), rec(0)
{ }
Route(int len, vector<int> node_seq):
route_len(len), route(node_seq)
{ }
Route(int len, vector<int> node_seq, double cost):
route_len(len), route(node_seq), cost(cost)
{ }
Route(int len, vector<int> node_seq, double cost, bool rec):
route_len(len), route(node_seq), cost(cost), rec(rec)
{ }
int route_len;
vector<int> route;
double cost;
double p_cost;
bool rec;
};
/***************************************
* Route table class
**************************************/
class RouteTable
{
public:
RouteTable() {};
list<vector<Route>> table;
// vector<Route> current_step;
// vector<Route> next_step;
// int step_counter;
vector<Route> result_set;
int table_init(int start_ID, int first_cate);
Route extend_route(Route exam_route, int vq_ID, int neighbor_ID, double cost);
Route replace_route(Route exam_route, int vl_ID, int neighbor_ID, double cost);
void print_last_step(bool print);
void print_route(Route route_to_print, bool print);
void print_result_set(bool print);
void print_hash_table(vector<Route> route_table);
// ************* FNN
//initilize Forward and Backward Relationship Matrix
void RelaM_init();
//Return shortest distance between two nodes
double Query(int startNodeID,int endNodeID);
//comparator for priority queue
//bool PQComparator(const pair<int,double> &a,const pair<int,double> &b);
//pruned dijkstra algorithm forward for Lin and backward for Lout
void prunedDijkForward(int start_NodeID);
void prunedDijkBackward(int start_NodeID);
//initialization of Lin and Lout in preporcessing
void Lin_Lout_init();
//initialization of category vector
void cateVector_init();
//initialization of Inverted Label
void InvertedLabel_init();
//Initilialization of data for FNN
void FNN_init();
//return nearest xth neighbor NodeID of source node in next category
NodeIDC FNN(int source_ID, int next_cate_ID, int xth, int TargetNode);
protected:
private:
//forward and backward relationship matrix
vector<vector<int>> RelaMForward;
vector<vector<int>> RelaMBackward;
//vector of hash tables for Lin and Lout
vector<map<int,double>> Lin;
vector<map<int,double>> Lout;
//vector of cateories that group nodes withines each category
vector<vector<int>> cateVector;
//inverted label
vector<map<int,map<int,double>>> InvertedLabel;
};
/***************************************
* Vertex Hash Pair struct
**************************************/
struct Hash_table
{
Hash_table() {};
vector<Route> dominating_table;
vector<Route> dominated_table;
};
/***************************************
* Vertex Hash Table class
**************************************/
class HashPool
{
public:
HashPool() {};
unordered_map<int, Hash_table> Hash_list;
void insert_pair();
void delete_pair();
bool check_domination(Route exam_route, int vq_ID);
void add_to_dominating(Route exam_route, int vq_ID);
void add_to_dominated(Route exam_route, int vq_ID);
Route extract_min(vector<Route> *route_table, int rec_len);
protected:
private:
};
/***************************************
* Pruning KOSR algorithm
**************************************/
class PruneKOSR
{
public:
PruneKOSR() {};
void main();
static float ave_querytime;
static int ave_examinedroute;
static int ave_nnqueries;
protected:
private:
int current_k;
};
#endif // PRUNE_H