pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
BDATester.cpp
1 /*PGR-MIT*****************************************************************
2 
3 * $Id$
4 *
5 * Project: pgRouting bdsp and bdastar algorithms
6 * Purpose:
7 * Author: Razequl Islam <ziboncsedu@gmail.com>
8 *
9 
10 ------
11 MIT/X license
12 
13 Permission is hereby granted, free of charge, to any person obtaining a copy
14 of this software and associated documentation files (the "Software"), to deal
15 in the Software without restriction, including without limitation the rights
16 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
17 copies of the Software, and to permit persons to whom the Software is
18 furnished to do so, subject to the following conditions:
19 
20 
21 The above copyright notice and this permission notice shall be included in
22 all copies or substantial portions of the Software.
23 
24 
25 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
26 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
27 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
28 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
29 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
30 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
31 THE SOFTWARE.
32 
33 ********************************************************************PGR-MIT*/
34 
35 #include "BiDirAStar.h"
36 #include "utils.h"
37 #include<math.h>
38 #include<time.h>
39 #include<stdio.h>
40 #include<string.h>
41 
42 #define EPS 1e-8
43 
44 
45 std::vector<edge_astar_t> vecEdges;
46 edge_astar_t *edges;
47 int edge_count, maxNode;
48 char buff[1024];
49 path_element_t *path;
50 char *err_msg;
51 int path_count;
52 int kase;
53 
54 /*
55  This method load the edge information from a csv file and put them in the edge_t array that can be passed to the algorithm to find route
56 */
57 
58 void loadGraph(std::string edgeFile)
59 {
60  // Open file for reading
61  freopen(edgeFile.c_str(), "rt", stdin);
62 
63  edge_count = 0;
64  vecEdges.clear();
65  maxNode = -1;
66 
67  // Read line by line edge info
68  while(gets(buff))
69  {
70  if(strlen(buff) == 0)
71  break;
72  edge_count++;
73 
74  StringTokenizer token;
75  // tokenize using comma
76  token.parse(buff, ",");
77  std::vector<std::string> vecToken;
78  vecToken.clear();
79  token.getTokens(vecToken);
80 
81  // There should be exactly 9 values: edge_id, start_node_id, end_node_id,
82  // start_node_longitude, start_node_latitude, end_node_longitude, end_node_latitude, cost, reverse_cost
83  if(vecToken.size() < 5)
84  fprintf(stderr, "Error in %d edge\n", edge_count);
85 
86  // Populate Edge_t structure
87  edge_astar_t tempEdge;
88  tempEdge.id = atoi(vecToken[0].c_str());
89  tempEdge.source = atoi(vecToken[1].c_str());
90  tempEdge.target = atoi(vecToken[2].c_str());
91  tempEdge.cost = atof(vecToken[3].c_str());
92  tempEdge.reverse_cost = atof(vecToken[4].c_str());
93  tempEdge.s_x = atof(vecToken[5].c_str());
94  tempEdge.s_y = atof(vecToken[6].c_str());
95  tempEdge.t_x = atof(vecToken[7].c_str());
96  tempEdge.t_y = atof(vecToken[8].c_str());
97 
98  // Update max_node_id
99  if(tempEdge.source > maxNode)
100  maxNode = tempEdge.source;
101  if(tempEdge.target > maxNode)
102  maxNode = tempEdge.target;
103 
104  vecEdges.push_back(tempEdge);
105  }
106 
107  edges = new edge_astar_t[edge_count];
108  int i;
109 
110  for(i = 0; i < edge_count; i++)
111  {
112  edges[i] = vecEdges[i];
113  }
114  fclose(stdin);
115 }
116 /*
117  Write the route in the path file
118 */
119 void write_result(std::string fileName, int res)
120 {
121  int i;
122  freopen(fileName.c_str(), "wt", stdout);
123  if(res < 0)
124  printf("%s\n", err_msg);
125  else
126  {
127  for(i = 0; i < path_count; i++)
128  {
129  printf("%d\t|%d\t|%.6lf\n", path[i].vertex_id, path[i].edge_id, path[i].cost);
130  }
131  }
132  fclose(stdout);
133 }
134 
135 /*
136  Match output with answer file and write result in the result file
137 */
138 
139 void match(std::string fileName1, std::string fileName2, std::string outFile, double ttime)
140 {
141  // Open the first file
142  freopen(fileName1.c_str(), "rt", stdin);
143 
144  // Initialization
145  std::vector<int> nodeList1;
146  nodeList1.clear();
147  double totCost1, totCost2;
148  int nid, eid;
149  double cost;
150  totCost1 = 0.0;
151 
152  // Read paths push node_id, edge_id inthe vector and update total cost
153  while(gets(buff))
154  {
155  if(sscanf(buff, "%d |%d |%lf", &nid, &eid, &cost) != 3)
156  {
157  totCost1 = -1;
158  break;
159  }
160  nodeList1.push_back(nid);
161  nodeList1.push_back(eid);
162  totCost1 += cost;
163  }
164  fclose(stdin);
165  bool flag = true;
166  // Open the second file
167  freopen(fileName2.c_str(), "rt", stdin);
168  totCost2 = 0.0;
169  int pos = 0;
170 
171  // Read paths compare with previously constructed vector of node-id, edge_id and updte total cost
172  while(gets(buff))
173  {
174  if(sscanf(buff, "%d |%d |%lf", &nid, &eid, &cost) != 3)
175  {
176  totCost2 = -1;
177  break;
178  }
179  if(pos >= nodeList1.size() || nodeList1[pos] != nid)
180  {
181  flag = false;
182  }
183  pos++;
184  if(pos >= nodeList1.size() || nodeList1[pos] != eid)
185  {
186  flag = false;
187  }
188  pos++;
189  totCost2 += cost;
190  }
191  fclose(stdin);
192 
193  // Open output file to write
194  freopen(outFile.c_str(), "a+", stdout);
195  printf("Case %d: ", kase);
196 
197  // Both costs matches
198  if(fabs(totCost1 - totCost2) < EPS)
199  {
200  // Path also matches
201  if(flag == true)
202  {
203  printf("Perfect Match!!!\n");
204  }
205  else // path mismatch
206  {
207  printf("Cost same, but path differs!!!\n");
208  }
209  }
210  else // Cost mispatch
211  {
212  printf("Cost differs, %s costs %lf and %s costs %lf\n", fileName1.c_str(), totCost1, fileName2.c_str(), totCost2);
213  }
214  printf("Query time: %lf sec\n\n", ttime);
215  fclose(stdout);
216 }
217 
218 int main()
219 {
220  int i;
221  double cl;
222  kase = 1;
223 
224  // The final output will be written in the outFile and the initial input will be read from inFile
225  std::string outFile = "output.txt";
226  std::string inFile = "input.txt";
227 
228  // Create the output file
229  FILE *fpout = fopen(outFile.c_str(), "wt");
230  fclose(fpout);
231 
232  // Open the input file
233  FILE *fpin = fopen(inFile.c_str(), "rt");
234 
235  // Reading each of the cases, There may be two types of cases, with 4 parameters, with 5 parameters
236  // There may also be comments that starts with #
237  while(fgets(buff, 1000, fpin))
238  {
239  // No data
240  if(strlen(buff) == 0)
241  continue;
242  // Comment
243  if(buff[0] == '#')
244  continue;
245  StringTokenizer token;
246 
247  // tokeniize using space
248  token.parse(buff, " \n\r");
249  std::vector<std::string> vecToken;
250  token.getTokens(vecToken);
251 
252  int totParam = vecToken.size();
253 
254  // Not enough parameters
255  if(totParam < 4)
256  continue;
257 
258  // First token is the graph file name
259  std::string graphFile = vecToken[0];
260 
261  // 2nd and 3rd tokens are start and end node id respectively
262  int startNode = atoi(vecToken[1].c_str());
263  int endNode = atoi(vecToken[2].c_str());
264 
265  // 4th Token is the result file for this query
266  std::string pathFile = vecToken[3];
267  int ind = pathFile.length() - 1;
268  while(pathFile[ind] < 32)
269  {
270  pathFile[ind] = '\0';
271  ind--;
272  }
273 
274  // Load edge information from graph file
275  loadGraph(graphFile);
276 
277  // Use bidirectional AStar to get the route
278  BiDirAStar gdef;
279  cl = clock();
280  int res = gdef.bidir_astar(edges, edge_count, maxNode, startNode, endNode, &path, &path_count, &err_msg);
281  cl = clock() - cl;
282 
283  // Write the route in the result file
284  write_result(pathFile, res);
285 
286  // There is an answer file
287  if(totParam > 4)
288  {
289  std::string ansFile = vecToken[4];
290  ind = ansFile.length() - 1;
291  while(ansFile[ind] < 32)
292  {
293  ansFile[ind] = '\0';
294  ind--;
295  }
296  // Match and write result in the final output file
297  match(pathFile, ansFile, outFile, cl / CLOCKS_PER_SEC);
298  }
299  else
300  {
301  // Provide information that the route is generated in path file.
302  fpout = fopen(outFile.c_str(), "a+");
303  fprintf(fpout, "Case %d: Path Written to file %s", kase, pathFile.c_str());
304  fprintf(fpout, "Query Time: %lf sec\n\n", cl / CLOCKS_PER_SEC);
305  fclose(fpout);
306  }
307  kase++;
308  free(path);
309  delete [] edges;
310  }
311  return 0;
312 }