pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
bdastar.c
1 /*PGR-GNU*****************************************************************
2 
3 Bi Directional A* Shortest path algorithm for PostgreSQL
4 
5 Copyright (c) 2006 Anton A. Patrushev, Orkney, Inc.
6 Mail: project@pgrouting.org
7 
8 ------
9 
10 This program is free software; you can redistribute it and/or modify
11 it under the terms of the GNU General Public License as published by
12 the Free Software Foundation; either version 2 of the License, or
13 (at your option) any later version.
14 
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
19 
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
23 
24 ********************************************************************PGR-GNU*/
25 
26 #include "../../common/src/pgr_types.h"
27 #include "postgres.h"
28 #include "executor/spi.h"
29 #include "funcapi.h"
30 #include "catalog/pg_type.h"
31 #if PGSQL_VERSION > 92
32 #include "access/htup_details.h"
33 #endif
34 
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <search.h>
38 
39 #include "../../common/src/postgres_connection.h"
40 #include "bdastar.h"
41 
42 //-------------------------------------------------------------------------
43 
44 /*
45  * Define this to have profiling enabled
46  */
47 //#define PROFILE
48 
49 #ifdef PROFILE
50 #include <sys/time.h>
51 
52 struct timeval prof_astar, prof_store, prof_extract, prof_total;
53 long proftime[5];
54 long profipts1, profipts2, profopts;
55 
56 #define profstart(x) do { gettimeofday(&x, NULL); } while (0);
57 #define profstop(n, x) do { struct timeval _profstop; \
58  long _proftime; \
59  gettimeofday(&_profstop, NULL); \
60  _proftime = ( _profstop.tv_sec*1000000+_profstop.tv_usec) - \
61  ( x.tv_sec*1000000+x.tv_usec); \
62  elog(NOTICE, \
63  "PRF(%s) %lu (%f ms)", \
64  (n), \
65  _proftime, _proftime / 1000.0); \
66  } while (0);
67 
68 #else
69 
70 #define profstart(x) do { } while (0);
71 #define profstop(n, x) do { } while (0);
72 
73 #endif // PROFILE
74 
75 
76 //-------------------------------------------------------------------------
77 
78 Datum bidir_astar_shortest_path(PG_FUNCTION_ARGS);
79 
80 #undef DEBUG
81 #include "../../common/src/debug_macro.h"
82 
83 
84 // The number of tuples to fetch from the SPI cursor at each iteration
85 #define TUPLIMIT 1000
86 
87 typedef struct edge_astar_columns
88 {
89  int id;
90  int source;
91  int target;
92  int cost;
93  int reverse_cost;
94  int s_x;
95  int s_y;
96  int t_x;
97  int t_y;
99 
100 
101 static int
102 fetch_edge_astar_columns(SPITupleTable *tuptable,
104  bool has_reverse_cost)
105 {
106  edge_columns->id = SPI_fnumber(SPI_tuptable->tupdesc, "id");
107  edge_columns->source = SPI_fnumber(SPI_tuptable->tupdesc, "source");
108  edge_columns->target = SPI_fnumber(SPI_tuptable->tupdesc, "target");
109  edge_columns->cost = SPI_fnumber(SPI_tuptable->tupdesc, "cost");
110 
111  if (edge_columns->id == SPI_ERROR_NOATTRIBUTE ||
112  edge_columns->source == SPI_ERROR_NOATTRIBUTE ||
113  edge_columns->target == SPI_ERROR_NOATTRIBUTE ||
114  edge_columns->cost == SPI_ERROR_NOATTRIBUTE) {
115 
116  elog(ERROR, "Error, query must return columns "
117  "'id', 'source', 'target' and 'cost'");
118  return -1;
119  }
120 
121  if (SPI_gettypeid(SPI_tuptable->tupdesc,
122  edge_columns->source) != INT4OID ||
123  SPI_gettypeid(SPI_tuptable->tupdesc,
124  edge_columns->target) != INT4OID ||
125  SPI_gettypeid(SPI_tuptable->tupdesc, edge_columns->cost) != FLOAT8OID) {
126 
127  elog(ERROR, "Error, columns 'source', 'target' must be of type int4, "
128  "'cost' must be of type float8");
129  return -1;
130  }
131 
132  PGR_DBG("columns: id %i source %i target %i cost %i",
133  edge_columns->id, edge_columns->source,
134  edge_columns->target, edge_columns->cost);
135 
136  if (has_reverse_cost) {
137  edge_columns->reverse_cost = SPI_fnumber(SPI_tuptable->tupdesc,
138  "reverse_cost");
139 
140  if (edge_columns->reverse_cost == SPI_ERROR_NOATTRIBUTE) {
141  elog(ERROR, "Error, reverse_cost is used, but query did't return "
142  "'reverse_cost' column");
143  return -1;
144  }
145 
146  if (SPI_gettypeid(SPI_tuptable->tupdesc,
147  edge_columns->reverse_cost) != FLOAT8OID) {
148  elog(ERROR, "Error, columns 'reverse_cost' must be of type float8");
149  return -1;
150  }
151 
152  PGR_DBG("columns: reverse_cost cost %i", edge_columns->reverse_cost);
153  }
154 
155  edge_columns->s_x = SPI_fnumber(SPI_tuptable->tupdesc, "x1");
156  edge_columns->s_y = SPI_fnumber(SPI_tuptable->tupdesc, "y1");
157  edge_columns->t_x = SPI_fnumber(SPI_tuptable->tupdesc, "x2");
158  edge_columns->t_y = SPI_fnumber(SPI_tuptable->tupdesc, "y2");
159 
160  if (edge_columns->s_x == SPI_ERROR_NOATTRIBUTE ||
161  edge_columns->s_y == SPI_ERROR_NOATTRIBUTE ||
162  edge_columns->t_x == SPI_ERROR_NOATTRIBUTE ||
163  edge_columns->t_y == SPI_ERROR_NOATTRIBUTE) {
164 
165  elog(ERROR, "Error, query must return columns "
166  "'x1', 'x2', 'y1' and 'y2'");
167  return -1;
168  }
169 
170  PGR_DBG("columns: x1 %i y1 %i x2 %i y2 %i",
171  edge_columns->s_x, edge_columns->s_y,
172  edge_columns->t_x,edge_columns->t_y);
173 
174  return 0;
175 }
176 
177 static void
178 fetch_edge_astar(HeapTuple *tuple, TupleDesc *tupdesc,
179  edge_astar_columns_t *edge_columns,
180  edge_astar_t *target_edge)
181 {
182  Datum binval;
183  bool isnull;
184 
185  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->id, &isnull);
186  if (isnull) elog(ERROR, "id contains a null value");
187  target_edge->id = DatumGetInt32(binval);
188 
189  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->source, &isnull);
190  if (isnull) elog(ERROR, "source contains a null value");
191  target_edge->source = DatumGetInt32(binval);
192 
193  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->target, &isnull);
194  if (isnull) elog(ERROR, "target contains a null value");
195  target_edge->target = DatumGetInt32(binval);
196 
197  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->cost, &isnull);
198  if (isnull) elog(ERROR, "cost contains a null value");
199  target_edge->cost = DatumGetFloat8(binval);
200 
201  if (edge_columns->reverse_cost != -1) {
202  binval = SPI_getbinval(*tuple, *tupdesc,
203  edge_columns->reverse_cost, &isnull);
204  if (isnull)
205  elog(ERROR, "reverse_cost contains a null value");
206  target_edge->reverse_cost = DatumGetFloat8(binval);
207  }
208 
209  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->s_x, &isnull);
210  if (isnull) elog(ERROR, "source x contains a null value");
211  target_edge->s_x = DatumGetFloat8(binval);
212 
213  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->s_y, &isnull);
214  if (isnull) elog(ERROR, "source y contains a null value");
215  target_edge->s_y = DatumGetFloat8(binval);
216 
217  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->t_x, &isnull);
218  if (isnull) elog(ERROR, "target x contains a null value");
219  target_edge->t_x = DatumGetFloat8(binval);
220 
221  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->t_y, &isnull);
222  if (isnull) elog(ERROR, "target y contains a null value");
223  target_edge->t_y = DatumGetFloat8(binval);
224 }
225 
226 
227 static int compute_shortest_path_astar(char* sql, int source_vertex_id,
228  int target_vertex_id, bool directed,
229  bool has_reverse_cost,
230  path_element_t **path, size_t *path_count)
231 {
232  void *SPIplan;
233  Portal SPIportal;
234  bool moredata = TRUE;
235  size_t ntuples;
236  edge_astar_t *edges = NULL;
237  size_t total_tuples = 0;
238 
239  int v_max_id=0;
240  int v_min_id=INT_MAX;
241 
242  edge_astar_columns_t edge_columns = {.id= -1, .source= -1, .target= -1,
243  .cost= -1, .reverse_cost= -1,
244  .s_x= -1, .s_y= -1, .t_x= -1, .t_y= -1};
245  char *err_msg;
246  int ret = -1;
247  register int z;
248 
249  int s_count=0;
250  int t_count=0;
251 
252  struct vItem {
253  int id;
254  int key;
255  };
256 
257  PGR_DBG("start shortest_path_astar\n");
258 
259  pgr_SPI_connect();
260  SPIplan = pgr_SPI_prepare(sql);
261  SPIportal = pgr_SPI_cursor_open(SPIplan);
262 
263  while (moredata == TRUE) {
264  SPI_cursor_fetch(SPIportal, TRUE, TUPLIMIT);
265 
266  if (edge_columns.id == -1) {
267  if (fetch_edge_astar_columns(SPI_tuptable, &edge_columns,
268  has_reverse_cost) == -1) {
269  pgr_SPI_finish();
270  return -1;
271  }
272  }
273 
274  ntuples = SPI_processed;
275  total_tuples += ntuples;
276  if (!edges)
277  edges = palloc(total_tuples * sizeof(edge_astar_t));
278  else
279  edges = repalloc(edges, total_tuples * sizeof(edge_astar_t));
280 
281  if (edges == NULL) {
282  elog(ERROR, "Out of memory");
283  pgr_SPI_finish();
284  return -1;
285  }
286 
287  if (ntuples > 0) {
288  size_t t;
289  SPITupleTable *tuptable = SPI_tuptable;
290  TupleDesc tupdesc = SPI_tuptable->tupdesc;
291 
292  for (t = 0; t < ntuples; t++) {
293  HeapTuple tuple = tuptable->vals[t];
294  fetch_edge_astar(&tuple, &tupdesc, &edge_columns,
295  &edges[total_tuples - ntuples + t]);
296  }
297  SPI_freetuptable(tuptable);
298  }
299  else {
300  moredata = FALSE;
301  }
302  }
303 
304  //defining min and max vertex id
305 
306  PGR_DBG("Total %i tuples", total_tuples);
307 
308  for(z=0; z<total_tuples; z++)
309  {
310  if(edges[z].source<v_min_id) v_min_id=edges[z].source;
311  if(edges[z].source>v_max_id) v_max_id=edges[z].source;
312  if(edges[z].target<v_min_id) v_min_id=edges[z].target;
313  if(edges[z].target>v_max_id) v_max_id=edges[z].target;
314  PGR_DBG("%i <-> %i", v_min_id, v_max_id);
315  }
316 
317  //::::::::::::::::::::::::::::::::::::
318  //:: reducing vertex id (renumbering)
319  //::::::::::::::::::::::::::::::::::::
320  for(z=0; z<total_tuples; z++) {
321  //check if edges[] contains source and target
322  if(edges[z].source == source_vertex_id ||
323  edges[z].target == source_vertex_id)
324  ++s_count;
325  if(edges[z].source == target_vertex_id ||
326  edges[z].target == target_vertex_id)
327  ++t_count;
328 
329  edges[z].source-=v_min_id;
330  edges[z].target-=v_min_id;
331  PGR_DBG("%i - %i", edges[z].source, edges[z].target);
332  }
333 
334  PGR_DBG("Total %i tuples", total_tuples);
335 
336  if(s_count == 0) {
337  elog(ERROR, "Start vertex was not found.");
338  return -1;
339  }
340 
341  if(t_count == 0) {
342  elog(ERROR, "Target vertex was not found.");
343  return -1;
344  }
345 
346  PGR_DBG("Total %i tuples", total_tuples);
347 
348  profstop("extract", prof_extract);
349  profstart(prof_astar);
350 
351  PGR_DBG("Calling bidir_astar <%i>\n", total_tuples);
352 
353  // calling C++ A* function
354  ret = bdastar_wrapper(edges, total_tuples, v_max_id + 1, source_vertex_id-v_min_id,
355  target_vertex_id-v_min_id,
356  directed, has_reverse_cost,
357  path, path_count, &err_msg);
358 
359  PGR_DBG("SIZE %i\n",*path_count);
360 
361  PGR_DBG("ret = %i\n",ret);
362 
363  //::::::::::::::::::::::::::::::::
364  //:: restoring original vertex id
365  //::::::::::::::::::::::::::::::::
366  for(z=0; z<*path_count; z++) {
367  //PGR_DBG("vetex %i\n",(*path)[z].vertex_id);
368  (*path)[z].vertex_id+=v_min_id;
369  }
370 
371  profstop("astar", prof_astar);
372  profstart(prof_store);
373 
374  if (ret < 0) {
375  elog(ERROR, "Error computing path: %s", err_msg);
376  }
377  pgr_SPI_finish();
378  return ret;
379 }
380 
381 
382 PG_FUNCTION_INFO_V1(bidir_astar_shortest_path);
383 Datum
384 bidir_astar_shortest_path(PG_FUNCTION_ARGS)
385 {
386  FuncCallContext *funcctx;
387  uint32_t call_cntr;
388  uint32_t max_calls;
389  TupleDesc tuple_desc;
390  path_element_t *path;
391 
392  /* stuff done only on the first call of the function */
393  if (SRF_IS_FIRSTCALL()) {
394  MemoryContext oldcontext;
395  size_t path_count = 0;
396 #ifdef DEBUG
397  int ret;
398 #endif
399 
400  // XXX profiling messages are not thread safe
401  profstart(prof_total);
402  profstart(prof_extract);
403 
404  /* create a function context for cross-call persistence */
405  funcctx = SRF_FIRSTCALL_INIT();
406 
407  /* switch to memory context appropriate for multiple function calls */
408  oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
409 
410 
411 #ifdef DEBUG
412  ret =
413 #endif
414  compute_shortest_path_astar(pgr_text2char(PG_GETARG_TEXT_P(0)),
415  PG_GETARG_INT32(1),
416  PG_GETARG_INT32(2),
417  PG_GETARG_BOOL(3),
418  PG_GETARG_BOOL(4),
419  &path, &path_count);
420 
421 #ifdef DEBUG
422  PGR_DBG("Ret is %i", ret);
423  if (ret >= 0) {
424  int i;
425  for (i = 0; i < path_count; i++) {
426  PGR_DBG("Step # %i vertex_id %i ", i, path[i].vertex_id);
427  PGR_DBG(" edge_id %i ", path[i].edge_id);
428  PGR_DBG(" cost %f ", path[i].cost);
429  }
430  }
431 #endif
432 
433  /* total number of tuples to be returned */
434  PGR_DBG("Conting tuples number\n");
435  funcctx->max_calls = (uint32_t)path_count;
436  funcctx->user_fctx = path;
437 
438  PGR_DBG("Path count %i", path_count);
439 
440  funcctx->tuple_desc =
441  BlessTupleDesc(RelationNameGetTupleDesc("pgr_costResult"));
442 
443  MemoryContextSwitchTo(oldcontext);
444  }
445 
446  /* stuff done on every call of the function */
447  PGR_DBG("Strange stuff doing\n");
448 
449  funcctx = SRF_PERCALL_SETUP();
450 
451  call_cntr = funcctx->call_cntr;
452  max_calls = funcctx->max_calls;
453  tuple_desc = funcctx->tuple_desc;
454  path = (path_element_t*) funcctx->user_fctx;
455 
456  PGR_DBG("Trying to allocate some memory\n");
457 
458  if (call_cntr < max_calls) { /* do when there is more left to send */
459  HeapTuple tuple;
460  Datum result;
461  Datum *values;
462  char* nulls;
463 
464  values = palloc(4 * sizeof(Datum));
465  nulls = palloc(4 * sizeof(char));
466 
467  values[0] = Int32GetDatum(call_cntr);
468  nulls[0] = ' ';
469  values[1] = Int32GetDatum(path[call_cntr].vertex_id);
470  nulls[1] = ' ';
471  values[2] = Int32GetDatum(path[call_cntr].edge_id);
472  nulls[2] = ' ';
473  values[3] = Float8GetDatum(path[call_cntr].cost);
474  nulls[3] = ' ';
475 
476  PGR_DBG("Heap making\n");
477 
478  tuple = heap_formtuple(tuple_desc, values, nulls);
479 
480  PGR_DBG("Datum making\n");
481 
482  /* make the tuple into a datum */
483  result = HeapTupleGetDatum(tuple);
484 
485 
486  PGR_DBG("Trying to free some memory\n");
487 
488  /* clean up (this is not really necessary) */
489  pfree(values);
490  pfree(nulls);
491 
492  SRF_RETURN_NEXT(funcctx, result);
493  }
494  else { /* do when there is no more left */
495  PGR_DBG("Freeing path");
496  if (path) free(path);
497 
498  profstop("store", prof_store);
499  profstop("total", prof_total);
500 #ifdef PROFILE
501  elog(NOTICE, "_________");
502 #endif
503  SRF_RETURN_DONE(funcctx);
504  }
505 }