pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
bdastar.c
Go to the documentation of this file.
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 "postgres.h"
27 #include "executor/spi.h"
28 #include "funcapi.h"
29 #include "catalog/pg_type.h"
30 #if PGSQL_VERSION > 92
31 #include "access/htup_details.h"
32 #endif
33 
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <search.h>
37 
38 #include "../../common/src/pgr_types.h"
39 #include "../../common/src/postgres_connection.h"
40 #include "./bdastar_driver.h"
41 
42 
43 //-------------------------------------------------------------------------
44 
45 PGDLLEXPORT
46 Datum bidir_astar_shortest_path(PG_FUNCTION_ARGS);
47 
48 #undef DEBUG
49 #include "../../common/src/debug_macro.h"
50 
51 // The number of tuples to fetch from the SPI cursor at each iteration
52 #define TUPLIMIT 1000
53 
54 typedef struct edge_astar_columns {
55  int id;
56  int source;
57  int target;
58  int cost;
60  int s_x;
61  int s_y;
62  int t_x;
63  int t_y;
65 
66 
67 static int
68 fetch_edge_astar_columns(SPITupleTable *tuptable,
70  bool has_reverse_cost) {
71  edge_columns->id = SPI_fnumber(SPI_tuptable->tupdesc, "id");
72  edge_columns->source = SPI_fnumber(SPI_tuptable->tupdesc, "source");
73  edge_columns->target = SPI_fnumber(SPI_tuptable->tupdesc, "target");
74  edge_columns->cost = SPI_fnumber(SPI_tuptable->tupdesc, "cost");
75 
76  if (edge_columns->id == SPI_ERROR_NOATTRIBUTE ||
77  edge_columns->source == SPI_ERROR_NOATTRIBUTE ||
78  edge_columns->target == SPI_ERROR_NOATTRIBUTE ||
79  edge_columns->cost == SPI_ERROR_NOATTRIBUTE) {
80  elog(ERROR, "Error, query must return columns "
81  "'id', 'source', 'target' and 'cost'");
82  return -1;
83  }
84 
85  if (SPI_gettypeid(SPI_tuptable->tupdesc,
86  edge_columns->source) != INT4OID ||
87  SPI_gettypeid(SPI_tuptable->tupdesc,
88  edge_columns->target) != INT4OID ||
89  SPI_gettypeid(SPI_tuptable->tupdesc, edge_columns->cost) != FLOAT8OID) {
90  elog(ERROR, "Error, columns 'source', 'target' must be of type int4, "
91  "'cost' must be of type float8");
92  return -1;
93  }
94 
95  PGR_DBG("columns: id %i source %i target %i cost %i",
96  edge_columns->id, edge_columns->source,
97  edge_columns->target, edge_columns->cost);
98 
99  if (has_reverse_cost) {
100  edge_columns->reverse_cost = SPI_fnumber(SPI_tuptable->tupdesc,
101  "reverse_cost");
102 
103  if (edge_columns->reverse_cost == SPI_ERROR_NOATTRIBUTE) {
104  elog(ERROR, "Error, reverse_cost is used, but query did't return "
105  "'reverse_cost' column");
106  return -1;
107  }
108 
109  if (SPI_gettypeid(SPI_tuptable->tupdesc,
110  edge_columns->reverse_cost) != FLOAT8OID) {
111  elog(ERROR, "Error, columns 'reverse_cost' must be of type float8");
112  return -1;
113  }
114 
115  PGR_DBG("columns: reverse_cost cost %i", edge_columns->reverse_cost);
116  }
117 
118  edge_columns->s_x = SPI_fnumber(SPI_tuptable->tupdesc, "x1");
119  edge_columns->s_y = SPI_fnumber(SPI_tuptable->tupdesc, "y1");
120  edge_columns->t_x = SPI_fnumber(SPI_tuptable->tupdesc, "x2");
121  edge_columns->t_y = SPI_fnumber(SPI_tuptable->tupdesc, "y2");
122 
123  if (edge_columns->s_x == SPI_ERROR_NOATTRIBUTE ||
124  edge_columns->s_y == SPI_ERROR_NOATTRIBUTE ||
125  edge_columns->t_x == SPI_ERROR_NOATTRIBUTE ||
126  edge_columns->t_y == SPI_ERROR_NOATTRIBUTE) {
127  elog(ERROR, "Error, query must return columns "
128  "'x1', 'x2', 'y1' and 'y2'");
129  return -1;
130  }
131 
132  PGR_DBG("columns: x1 %i y1 %i x2 %i y2 %i",
133  edge_columns->s_x, edge_columns->s_y,
134  edge_columns->t_x, edge_columns->t_y);
135 
136  return 0;
137 }
138 
139 static void
140 fetch_edge_astar(HeapTuple *tuple, TupleDesc *tupdesc,
142  edge_astar_t *target_edge) {
143  Datum binval;
144  bool isnull;
145 
146  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->id, &isnull);
147  if (isnull) elog(ERROR, "id contains a null value");
148  target_edge->id = DatumGetInt32(binval);
149 
150  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->source, &isnull);
151  if (isnull) elog(ERROR, "source contains a null value");
152  target_edge->source = DatumGetInt32(binval);
153 
154  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->target, &isnull);
155  if (isnull) elog(ERROR, "target contains a null value");
156  target_edge->target = DatumGetInt32(binval);
157 
158  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->cost, &isnull);
159  if (isnull) elog(ERROR, "cost contains a null value");
160  target_edge->cost = DatumGetFloat8(binval);
161 
162  if (edge_columns->reverse_cost != -1) {
163  binval = SPI_getbinval(*tuple, *tupdesc,
164  edge_columns->reverse_cost, &isnull);
165  if (isnull)
166  elog(ERROR, "reverse_cost contains a null value");
167  target_edge->reverse_cost = DatumGetFloat8(binval);
168  }
169 
170  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->s_x, &isnull);
171  if (isnull) elog(ERROR, "source x contains a null value");
172  target_edge->s_x = DatumGetFloat8(binval);
173 
174  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->s_y, &isnull);
175  if (isnull) elog(ERROR, "source y contains a null value");
176  target_edge->s_y = DatumGetFloat8(binval);
177 
178  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->t_x, &isnull);
179  if (isnull) elog(ERROR, "target x contains a null value");
180  target_edge->t_x = DatumGetFloat8(binval);
181 
182  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->t_y, &isnull);
183  if (isnull) elog(ERROR, "target y contains a null value");
184  target_edge->t_y = DatumGetFloat8(binval);
185 }
186 
187 
188 static int compute_shortest_path_astar(char* sql, int source_vertex_id,
189  int target_vertex_id, bool directed,
190  bool has_reverse_cost,
191  path_element_t **path, size_t *path_count) {
192  void *SPIplan;
193  Portal SPIportal;
194  bool moredata = TRUE;
195  size_t ntuples;
196  edge_astar_t *edges = NULL;
197  size_t total_tuples = 0;
198 
199  int v_max_id = 0;
200  int v_min_id = INT_MAX;
201 
202 #ifndef _MSC_VER
203  edge_astar_columns_t edge_columns = {.id = -1, .source = -1, .target = -1,
204  .cost = -1, .reverse_cost = -1,
205  .s_x = -1, .s_y = -1, .t_x = -1, .t_y = -1};
206 #else // _MSC_VER
207  edge_astar_columns_t edge_columns = {-1, -1, -1, -1, -1, -1, -1, -1, -1};
208 #endif // _MSC_VER
209  char *err_msg;
210  int ret = -1;
211  register int z;
212 
213  int s_count = 0;
214  int t_count = 0;
215 
216  struct vItem {
217  int id;
218  int key;
219  };
220 
221  PGR_DBG("start shortest_path_astar\n");
222 
223  pgr_SPI_connect();
224  SPIplan = pgr_SPI_prepare(sql);
225  SPIportal = pgr_SPI_cursor_open(SPIplan);
226 
227  while (moredata == TRUE) {
228  SPI_cursor_fetch(SPIportal, TRUE, TUPLIMIT);
229 
230  if (edge_columns.id == -1) {
231  if (fetch_edge_astar_columns(SPI_tuptable, &edge_columns,
232  has_reverse_cost) == -1) {
233  pgr_SPI_finish();
234  return -1;
235  }
236  }
237 
238  ntuples = SPI_processed;
239  total_tuples += ntuples;
240  if (!edges)
241  edges = palloc(total_tuples * sizeof(edge_astar_t));
242  else
243  edges = repalloc(edges, total_tuples * sizeof(edge_astar_t));
244 
245  if (edges == NULL) {
246  elog(ERROR, "Out of memory");
247  pgr_SPI_finish();
248  return -1;
249  }
250 
251  if (ntuples > 0) {
252  size_t t;
253  SPITupleTable *tuptable = SPI_tuptable;
254  TupleDesc tupdesc = SPI_tuptable->tupdesc;
255 
256  for (t = 0; t < ntuples; t++) {
257  HeapTuple tuple = tuptable->vals[t];
258  fetch_edge_astar(&tuple, &tupdesc, &edge_columns,
259  &edges[total_tuples - ntuples + t]);
260  }
261  SPI_freetuptable(tuptable);
262  } else {
263  moredata = FALSE;
264  }
265  }
266 
267  // defining min and max vertex id
268 
269  PGR_DBG("Total %lu tuples", total_tuples);
270 
271  for (z = 0; z < total_tuples; z++) {
272  if (edges[z].source < v_min_id) v_min_id = edges[z].source;
273  if (edges[z].source > v_max_id) v_max_id = edges[z].source;
274  if (edges[z].target < v_min_id) v_min_id = edges[z].target;
275  if (edges[z].target > v_max_id) v_max_id = edges[z].target;
276  PGR_DBG("%i <-> %i", v_min_id, v_max_id);
277  }
278 
279  //::::::::::::::::::::::::::::::::::::
280  //:: reducing vertex id (renumbering)
281  //::::::::::::::::::::::::::::::::::::
282  for (z=0; z < total_tuples; z++) {
283  // check if edges[] contains source and target
284  if (edges[z].source == source_vertex_id ||
285  edges[z].target == source_vertex_id)
286  ++s_count;
287  if (edges[z].source == target_vertex_id ||
288  edges[z].target == target_vertex_id)
289  ++t_count;
290 
291  edges[z].source -= v_min_id;
292  edges[z].target -= v_min_id;
293  PGR_DBG("%i - %i", edges[z].source, edges[z].target);
294  }
295 
296  PGR_DBG("Total %lu tuples", total_tuples);
297 
298  if (s_count == 0) {
299  elog(ERROR, "Start vertex was not found.");
300  return -1;
301  }
302 
303  if (t_count == 0) {
304  elog(ERROR, "Target vertex was not found.");
305  return -1;
306  }
307 
308  PGR_DBG("Total %lu tuples", total_tuples);
309 
310  PGR_DBG("Calling bidir_astar <%lu>\n", total_tuples);
311 
312  // calling C++ A* function
313  ret = bdastar_wrapper(edges, total_tuples, v_max_id + 1, source_vertex_id-v_min_id,
314  target_vertex_id-v_min_id,
315  directed, has_reverse_cost,
316  path, path_count, &err_msg);
317 
318  PGR_DBG("SIZE %lu\n", *path_count);
319 
320  PGR_DBG("ret = %i\n", ret);
321 
322  //::::::::::::::::::::::::::::::::
323  //:: restoring original vertex id
324  //::::::::::::::::::::::::::::::::
325  for (z = 0; z < *path_count; z++) {
326  // PGR_DBG("vetex %i\n",(*path)[z].vertex_id);
327  (*path)[z].vertex_id += v_min_id;
328  }
329  if (ret < 0) {
330  elog(ERROR, "Error computing path: %s", err_msg);
331  }
332  pgr_SPI_finish();
333  return ret;
334 }
335 
336 
338 PGDLLEXPORT Datum
339 bidir_astar_shortest_path(PG_FUNCTION_ARGS) {
340  FuncCallContext *funcctx;
341  uint32_t call_cntr;
342  uint32_t max_calls;
343  TupleDesc tuple_desc;
345 
346  /* stuff done only on the first call of the function */
347  if (SRF_IS_FIRSTCALL()) {
348  MemoryContext oldcontext;
349  size_t path_count = 0;
350 #ifdef DEBUG
351  int ret;
352 #endif
353 
354  /* create a function context for cross-call persistence */
355  funcctx = SRF_FIRSTCALL_INIT();
356 
357  /* switch to memory context appropriate for multiple function calls */
358  oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
359 
360 
361 #ifdef DEBUG
362  ret =
363 #endif
364  compute_shortest_path_astar(pgr_text2char(PG_GETARG_TEXT_P(0)),
365  PG_GETARG_INT32(1),
366  PG_GETARG_INT32(2),
367  PG_GETARG_BOOL(3),
368  PG_GETARG_BOOL(4),
369  &path, &path_count);
370 
371 #ifdef DEBUG
372  PGR_DBG("Ret is %i", ret);
373  if (ret >= 0) {
374  int i;
375  for (i = 0; i < path_count; i++) {
376  PGR_DBG("Step # %i vertex_id %i ", i, path[i].vertex_id);
377  PGR_DBG(" edge_id %i ", path[i].edge_id);
378  PGR_DBG(" cost %f ", path[i].cost);
379  }
380  }
381 #endif
382 
383  /* total number of tuples to be returned */
384  PGR_DBG("Conting tuples number\n");
385  funcctx->max_calls = (uint32_t)path_count;
386  funcctx->user_fctx = path;
387 
388  PGR_DBG("Path count %lu", path_count);
389 
390  funcctx->tuple_desc =
391  BlessTupleDesc(RelationNameGetTupleDesc("pgr_costResult"));
392 
393  MemoryContextSwitchTo(oldcontext);
394  }
395 
396  /* stuff done on every call of the function */
397  PGR_DBG("Strange stuff doing\n");
398 
399  funcctx = SRF_PERCALL_SETUP();
400 
401  call_cntr = funcctx->call_cntr;
402  max_calls = funcctx->max_calls;
403  tuple_desc = funcctx->tuple_desc;
404  path = (path_element_t*) funcctx->user_fctx;
405 
406  PGR_DBG("Trying to allocate some memory\n");
407 
408  if (call_cntr < max_calls) { /* do when there is more left to send */
409  HeapTuple tuple;
410  Datum result;
411  Datum *values;
412  bool* nulls;
413 
414  values = palloc(4 * sizeof(Datum));
415  nulls = palloc(4 * sizeof(bool));
416 
417  values[0] = Int32GetDatum(call_cntr);
418  nulls[0] = false;
419  values[1] = Int32GetDatum(path[call_cntr].vertex_id);
420  nulls[1] = false;
421  values[2] = Int32GetDatum(path[call_cntr].edge_id);
422  nulls[2] = false;
423  values[3] = Float8GetDatum(path[call_cntr].cost);
424  nulls[3] = false;
425 
426  PGR_DBG("Heap making\n");
427 
428  tuple = heap_form_tuple(tuple_desc, values, nulls);
429 
430  PGR_DBG("Datum making\n");
431 
432  /* make the tuple into a datum */
433  result = HeapTupleGetDatum(tuple);
434 
435 
436  PGR_DBG("Trying to free some memory\n");
437 
438  /* clean up (this is not really necessary) */
439  pfree(values);
440  pfree(nulls);
441 
442  SRF_RETURN_NEXT(funcctx, result);
443  } else { /* do when there is no more left */
444  PGR_DBG("Freeing path");
445  if (path) free(path);
446  SRF_RETURN_DONE(funcctx);
447  }
448 }
struct edge_astar_columns edge_astar_columns_t
double cost
#define TUPLIMIT
Definition: bdastar.c:52
int path_count
Definition: BDATester.cpp:51
int bdastar_wrapper(edge_astar_t *edges, size_t edge_count, int maxnode, int source_vertex_id, int target_vertex_id, bool directed, bool has_reverse_cost, path_element_t **path, size_t *path_count, char **err_msg)
#define PGR_DBG(...)
Definition: debug_macro.h:33
static void fetch_edge_astar(HeapTuple *tuple, TupleDesc *tupdesc, edge_astar_columns_t *edge_columns, edge_astar_t *target_edge)
Definition: bdastar.c:140
int id
Definition: bdsp.c:55
PGDLLEXPORT Datum bidir_astar_shortest_path(PG_FUNCTION_ARGS)
Definition: bdastar.c:339
double s_y
PG_FUNCTION_INFO_V1(bidir_astar_shortest_path)
void pgr_SPI_finish(void)
edge_astar_t * edges
Definition: BDATester.cpp:46
double s_x
double t_y
void pgr_SPI_connect(void)
path_element_t * path
Definition: BDATester.cpp:49
Portal pgr_SPI_cursor_open(SPIPlanPtr SPIplan)
char * err_msg
Definition: BDATester.cpp:50
static int fetch_edge_astar_columns(SPITupleTable *tuptable, edge_astar_columns_t *edge_columns, bool has_reverse_cost)
Definition: bdastar.c:68
static int compute_shortest_path_astar(char *sql, int source_vertex_id, int target_vertex_id, bool directed, bool has_reverse_cost, path_element_t **path, size_t *path_count)
Definition: bdastar.c:188
double t_x
char * pgr_text2char(text *in)
SPIPlanPtr pgr_SPI_prepare(char *sql)
double reverse_cost