pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
astar.c
1 /*PGR-GNU*****************************************************************
2 
3  * 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 "astar.h"
40 
41 //-------------------------------------------------------------------------
42 
43 /*
44  * Define this to have profiling enabled
45  */
46 //#define PROFILE
47 
48 #ifdef PROFILE
49 #include <sys/time.h>
50 
51 struct timeval prof_astar, prof_store, prof_extract, prof_total;
52 long proftime[5];
53 long profipts1, profipts2, profopts;
54 
55 #define profstart(x) do { gettimeofday(&x, NULL); } while (0);
56 #define profstop(n, x) do { struct timeval _profstop; \
57  long _proftime; \
58  gettimeofday(&_profstop, NULL); \
59  _proftime = ( _profstop.tv_sec*1000000+_profstop.tv_usec) - \
60  ( x.tv_sec*1000000+x.tv_usec); \
61  elog(NOTICE, \
62  "PRF(%s) %lu (%f ms)", \
63  (n), \
64  _proftime, _proftime / 1000.0); \
65  } while (0);
66 
67 #else
68 
69 #define profstart(x) do { } while (0);
70 #define profstop(n, x) do { } while (0);
71 
72 #endif // PROFILE
73 
74 
75 //-------------------------------------------------------------------------
76 
77 Datum shortest_path_astar(PG_FUNCTION_ARGS);
78 
79 #undef DEBUG
80 //#define DEBUG 1
81 #include "../../common/src/debug_macro.h"
82 #include "../../common/src/pgr_types.h"
83 #include "../../common/src/postgres_connection.h"
84 
85 // The number of tuples to fetch from the SPI cursor at each iteration
86 #define TUPLIMIT 1000
87 
88 typedef struct edge_astar_columns
89 {
90  int id;
91  int source;
92  int target;
93  int cost;
94  int reverse_cost;
95  int s_x;
96  int s_y;
97  int t_x;
98  int t_y;
100 
101 
102 static int
103 fetch_edge_astar_columns(SPITupleTable *tuptable,
105  bool has_reverse_cost)
106 {
107  edge_columns->id = SPI_fnumber(SPI_tuptable->tupdesc, "id");
108  edge_columns->source = SPI_fnumber(SPI_tuptable->tupdesc, "source");
109  edge_columns->target = SPI_fnumber(SPI_tuptable->tupdesc, "target");
110  edge_columns->cost = SPI_fnumber(SPI_tuptable->tupdesc, "cost");
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) elog(ERROR, "reverse_cost contains a null value");
205  target_edge->reverse_cost = DatumGetFloat8(binval);
206  }
207 
208  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->s_x, &isnull);
209  if (isnull) elog(ERROR, "source x contains a null value");
210  target_edge->s_x = DatumGetFloat8(binval);
211 
212  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->s_y, &isnull);
213  if (isnull) elog(ERROR, "source y contains a null value");
214  target_edge->s_y = DatumGetFloat8(binval);
215 
216  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->t_x, &isnull);
217  if (isnull) elog(ERROR, "target x contains a null value");
218  target_edge->t_x = DatumGetFloat8(binval);
219 
220  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->t_y, &isnull);
221  if (isnull) elog(ERROR, "target y contains a null value");
222  target_edge->t_y = DatumGetFloat8(binval);
223 }
224 
225 
226 static int compute_shortest_path_astar(char* sql, int source_vertex_id,
227  int target_vertex_id, bool directed,
228  bool has_reverse_cost,
229  path_element_t **path, size_t *path_count)
230 {
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  {
254  int id;
255  int key;
256  };
257 
258  PGR_DBG("start shortest_path_astar\n");
259 
260  pgr_SPI_connect();
261  SPIplan = pgr_SPI_prepare(sql);
262  SPIportal = pgr_SPI_cursor_open(SPIplan);
263 
264 
265  while (moredata == TRUE) {
266  SPI_cursor_fetch(SPIportal, TRUE, TUPLIMIT);
267 
268  if (edge_columns.id == -1) {
269  if (fetch_edge_astar_columns(SPI_tuptable, &edge_columns,
270  has_reverse_cost) == -1) {
271  pgr_SPI_finish();
272  return -1;
273  }
274  }
275 
276  ntuples = SPI_processed;
277  total_tuples += ntuples;
278  if (!edges)
279  edges = palloc(total_tuples * sizeof(edge_astar_t));
280  else
281  edges = repalloc(edges, total_tuples * sizeof(edge_astar_t));
282 
283  if (edges == NULL) {
284  elog(ERROR, "Out of memory");
285  pgr_SPI_finish();
286  return -1;
287  }
288 
289  if (ntuples > 0) {
290  size_t t;
291  SPITupleTable *tuptable = SPI_tuptable;
292  TupleDesc tupdesc = SPI_tuptable->tupdesc;
293 
294  for (t = 0; t < ntuples; t++) {
295  HeapTuple tuple = tuptable->vals[t];
296  fetch_edge_astar(&tuple, &tupdesc, &edge_columns,
297  &edges[total_tuples - ntuples + t]);
298  }
299  SPI_freetuptable(tuptable);
300  }
301  else {
302  moredata = FALSE;
303  }
304  }
305 
306  //defining min and max vertex id
307 
308  PGR_DBG("Total %i tuples", total_tuples);
309 
310  for(z=0; z<total_tuples; z++) {
311  if(edges[z].source<v_min_id) v_min_id=edges[z].source;
312  if(edges[z].source>v_max_id) v_max_id=edges[z].source;
313  if(edges[z].target<v_min_id) v_min_id=edges[z].target;
314  if(edges[z].target>v_max_id) v_max_id=edges[z].target;
315 
316  PGR_DBG("%i <-> %i", v_min_id, v_max_id);
317  }
318 
319  //::::::::::::::::::::::::::::::::::::
320  //:: reducing vertex id (renumbering)
321  //::::::::::::::::::::::::::::::::::::
322  for(z=0; z<total_tuples; z++) {
323  //check if edges[] contains source and target
324  if(edges[z].source == source_vertex_id ||
325  edges[z].target == source_vertex_id)
326  ++s_count;
327  if(edges[z].source == target_vertex_id ||
328  edges[z].target == target_vertex_id)
329  ++t_count;
330 
331  edges[z].source-=v_min_id;
332  edges[z].target-=v_min_id;
333  PGR_DBG("%i - %i", edges[z].source, edges[z].target);
334  }
335 
336  PGR_DBG("Total %i tuples", total_tuples);
337 
338  if(s_count == 0) {
339  elog(ERROR, "Start vertex was not found.");
340  return -1;
341  }
342 
343  if(t_count == 0) {
344  elog(ERROR, "Target vertex was not found.");
345  return -1;
346  }
347 
348  PGR_DBG("Total %i tuples", total_tuples);
349 
350  profstop("extract", prof_extract);
351  profstart(prof_astar);
352 
353  PGR_DBG("Calling boost_astar <%i>\n", total_tuples);
354 
355  // calling C++ A* function
356  ret = boost_astar(edges, total_tuples, source_vertex_id-v_min_id,
357  target_vertex_id-v_min_id,
358  directed, has_reverse_cost,
359  path, path_count, &err_msg);
360 
361  if (ret < 0) {
362  elog(ERROR, "Error computing path: %s", err_msg);
363  }
364 
365  PGR_DBG("SIZE %i\n",*path_count);
366  PGR_DBG("ret = %i\n",ret);
367 
368  //::::::::::::::::::::::::::::::::
369  //:: restoring original vertex id
370  //::::::::::::::::::::::::::::::::
371  for(z=0; z<*path_count; z++) {
372  //PGR_DBG("vetex %i\n",(*path)[z].vertex_id);
373  (*path)[z].vertex_id += v_min_id;
374  }
375 
376  profstop("astar", prof_astar);
377  profstart(prof_store);
378 
379  pgr_SPI_finish();
380  return 0;
381 
382 }
383 
384 
385 PG_FUNCTION_INFO_V1(shortest_path_astar);
386 Datum
387 shortest_path_astar(PG_FUNCTION_ARGS)
388 {
389  FuncCallContext *funcctx;
390  uint32_t call_cntr;
391  uint32_t max_calls;
392  TupleDesc tuple_desc;
393  path_element_t *path = 0;
394 
395  /* stuff done only on the first call of the function */
396  if (SRF_IS_FIRSTCALL()) {
397  MemoryContext oldcontext;
398  size_t path_count = 0;
399 #ifdef DEBUG
400  int ret;
401 #endif
402 
403  // XXX profiling messages are not thread safe
404  profstart(prof_total);
405  profstart(prof_extract);
406 
407  /* create a function context for cross-call persistence */
408  funcctx = SRF_FIRSTCALL_INIT();
409 
410  /* switch to memory context appropriate for multiple function calls */
411  oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
412 
413 
414 #ifdef DEBUG
415  ret =
416 #endif
417  compute_shortest_path_astar(pgr_text2char(PG_GETARG_TEXT_P(0)),
418  PG_GETARG_INT32(1),
419  PG_GETARG_INT32(2),
420  PG_GETARG_BOOL(3),
421  PG_GETARG_BOOL(4),
422  &path, &path_count);
423 
424 #ifdef DEBUG
425  PGR_DBG("Ret is %i", ret);
426  int i;
427  for (i = 0; i < path_count; i++) {
428  PGR_DBG("Step # %i vertex_id %i ", i, path[i].vertex_id);
429  PGR_DBG(" edge_id %i ", path[i].edge_id);
430  PGR_DBG(" cost %f ", path[i].cost);
431  }
432 #endif
433 
434  /* total number of tuples to be returned */
435  PGR_DBG("Conting tuples number\n");
436  funcctx->max_calls = (uint32_t)path_count;
437  funcctx->user_fctx = path;
438 
439  PGR_DBG("Path count %i", path_count);
440 
441  funcctx->tuple_desc =
442  BlessTupleDesc(RelationNameGetTupleDesc("pgr_costResult"));
443 
444  MemoryContextSwitchTo(oldcontext);
445  }
446 
447  /* stuff done on every call of the function */
448  PGR_DBG("Strange stuff doing\n");
449 
450  funcctx = SRF_PERCALL_SETUP();
451 
452  call_cntr = funcctx->call_cntr;
453  max_calls = funcctx->max_calls;
454  tuple_desc = funcctx->tuple_desc;
455  path = (path_element_t*) funcctx->user_fctx;
456 
457  PGR_DBG("Trying to allocate some memory\n");
458 
459  if (call_cntr < max_calls) { /* do when there is more left to send */
460  HeapTuple tuple;
461  Datum result;
462  Datum *values;
463  char* nulls;
464 
465  values = palloc(4 * sizeof(Datum));
466  nulls = palloc(4 * sizeof(char));
467 
468  values[0] = Int32GetDatum(call_cntr);
469  nulls[0] = ' ';
470  values[1] = Int32GetDatum(path[call_cntr].vertex_id);
471  nulls[1] = ' ';
472  values[2] = Int32GetDatum(path[call_cntr].edge_id);
473  nulls[2] = ' ';
474  values[3] = Float8GetDatum(path[call_cntr].cost);
475  nulls[3] = ' ';
476 
477  PGR_DBG("Heap making\n");
478 
479  tuple = heap_formtuple(tuple_desc, values, nulls);
480 
481  PGR_DBG("Datum making\n");
482 
483  /* make the tuple into a datum */
484  result = HeapTupleGetDatum(tuple);
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  {
496  if (path) free(path);
497  profstop("store", prof_store);
498  profstop("total", prof_total);
499 #ifdef PROFILE
500  elog(NOTICE, "_________");
501 #endif
502  SRF_RETURN_DONE(funcctx);
503  }
504 }