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