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
bdsp.c
Go to the documentation of this file.
1 /*PGR-MIT*****************************************************************
2 
3 * $Id$
4 *
5 * Project: pgRouting bdsp and bdastar algorithms
6 * Purpose:
7 * Author: Razequl Islam <ziboncsedu@gmail.com>
8 Copyright (c) 2015 pgRouting developers
9 
10 ------
11 
12 This program is free software; you can redistribute it and/or modify
13 it under the terms of the GNU General Public License as published by
14 the Free Software Foundation; either version 2 of the License, or
15 (at your option) any later version.
16 
17 This program is distributed in the hope that it will be useful,
18 but WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 GNU General Public License for more details.
21 
22 You should have received a copy of the GNU General Public License
23 along with this program; if not, write to the Free Software
24 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
25 
26 ********************************************************************PGR-MIT*/
27 
28 
29 #include "postgres.h"
30 #include "executor/spi.h"
31 #include "funcapi.h"
32 #include "catalog/pg_type.h"
33 #if PGSQL_VERSION > 92
34 #include "access/htup_details.h"
35 #endif
36 
37 #include "fmgr.h"
38 
39 
40 
41 #include "bdsp_driver.h"
42 
43 
44 #undef DEBUG
45 #include "../../common/src/debug_macro.h"
46 #include "../../common/src/pgr_types.h"
47 #include "../../common/src/postgres_connection.h"
48 
49 // The number of tuples to fetch from the SPI cursor at each iteration
50 #define TUPLIMIT 1000
51 
52 PGDLLEXPORT Datum bidir_dijkstra_shortest_path(PG_FUNCTION_ARGS);
53 
54 typedef struct edge_columns {
55  int id;
56  int source;
57  int target;
58  int cost;
61 
62 
63 
64 /*
65  * This function fetches the edge columns from the SPITupleTable.
66  *
67 */
68 static int
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, edge_columns->source) != INT4OID ||
86  SPI_gettypeid(SPI_tuptable->tupdesc, edge_columns->target) != INT4OID ||
87  SPI_gettypeid(SPI_tuptable->tupdesc, edge_columns->cost) != FLOAT8OID) {
88  elog(ERROR, "Error, columns 'source', 'target' must be of type int4, 'cost' must be of type float8");
89  return -1;
90  }
91 
92  PGR_DBG("columns: id %i source %i target %i cost %i",
93  edge_columns->id, edge_columns->source,
94  edge_columns->target, edge_columns->cost);
95 
96  if (has_reverse_cost) {
97  edge_columns->reverse_cost = SPI_fnumber(SPI_tuptable->tupdesc,
98  "reverse_cost");
99 
100  if (edge_columns->reverse_cost == SPI_ERROR_NOATTRIBUTE) {
101  elog(ERROR, "Error, reverse_cost is used, but query did't return "
102  "'reverse_cost' column");
103  return -1;
104  }
105 
106  if (SPI_gettypeid(SPI_tuptable->tupdesc, edge_columns->reverse_cost)
107  != FLOAT8OID) {
108  elog(ERROR, "Error, columns 'reverse_cost' must be of type float8");
109  return -1;
110  }
111 
112  PGR_DBG("columns: reverse_cost cost %i", edge_columns->reverse_cost);
113  }
114 
115  return 0;
116 }
117 
118 /*
119  * To fetch a edge from Tuple.
120  *
121  */
122 
123 static void
124 fetch_edge(HeapTuple *tuple, TupleDesc *tupdesc,
125  edge_columns_t *edge_columns, edge_t *target_edge) {
126  Datum binval;
127  bool isnull;
128 
129  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->id, &isnull);
130  if (isnull) elog(ERROR, "id contains a null value");
131  target_edge->id = DatumGetInt32(binval);
132 
133  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->source, &isnull);
134  if (isnull) elog(ERROR, "source contains a null value");
135  target_edge->source = DatumGetInt32(binval);
136 
137  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->target, &isnull);
138  if (isnull) elog(ERROR, "target contains a null value");
139  target_edge->target = DatumGetInt32(binval);
140 
141  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->cost, &isnull);
142  if (isnull) elog(ERROR, "cost contains a null value");
143  target_edge->cost = DatumGetFloat8(binval);
144 
145  if (edge_columns->reverse_cost != -1) {
146  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->reverse_cost,
147  &isnull);
148  if (isnull) elog(ERROR, "reverse_cost contains a null value");
149  target_edge->reverse_cost = DatumGetFloat8(binval);
150  }
151 }
152 
153 static int compute_bidirsp(char* sql, int64_t start_vertex,
154  int64_t end_vertex, bool directed,
155  bool has_reverse_cost,
156  path_element_t **path, int *path_count) {
157  void *SPIplan;
158  Portal SPIportal;
159  bool moredata = TRUE;
160  uint32_t ntuples;
161  edge_t *edges = NULL;
162  uint32_t total_tuples = 0;
163 #ifndef _MSC_VER
164  edge_columns_t edge_columns = {.id = -1, .source = -1, .target = -1,
165  .cost = -1, .reverse_cost = -1};
166 #else // _MSC_VER
167  edge_columns_t edge_columns = {-1, -1, -1, -1, -1};
168 #endif // _MSC_VER
169  int64_t v_max_id = 0;
170  int64_t v_min_id = INT_MAX;
171 
172  int s_count = 0;
173  int t_count = 0;
174 
175  char *err_msg;
176  int ret = -1;
177  int64_t z;
178 
179  PGR_DBG("start shortest_path\n");
180 
181  pgr_SPI_connect();
182  SPIplan = pgr_SPI_prepare(sql);
183  SPIportal = pgr_SPI_cursor_open(SPIplan);
184 
185  while (moredata == TRUE) {
186  SPI_cursor_fetch(SPIportal, TRUE, TUPLIMIT);
187 
188  if (edge_columns.id == -1) {
189  if (fetch_edge_columns(SPI_tuptable, &edge_columns,
190  has_reverse_cost) == -1) {
191  pgr_SPI_finish();
192  return -1;
193  }
194  }
195 
196  ntuples = SPI_processed;
197  total_tuples += ntuples;
198  if (!edges)
199  edges = palloc(total_tuples * sizeof(edge_t));
200  else
201  edges = repalloc(edges, total_tuples * sizeof(edge_t));
202 
203  if (edges == NULL) {
204  elog(ERROR, "Out of memory");
205  pgr_SPI_finish();
206  return -1;
207  }
208 
209  if (ntuples > 0) {
210  uint64_t t;
211  SPITupleTable *tuptable = SPI_tuptable;
212  TupleDesc tupdesc = SPI_tuptable->tupdesc;
213 
214  for (t = 0; t < ntuples; t++) {
215  HeapTuple tuple = tuptable->vals[t];
216  fetch_edge(&tuple, &tupdesc, &edge_columns,
217  &edges[total_tuples - ntuples + t]);
218  }
219  SPI_freetuptable(tuptable);
220  } else {
221  moredata = FALSE;
222  }
223  }
224 
225  // defining min and max vertex id
226 
227  PGR_DBG("Total %i tuples", total_tuples);
228 
229  for (z = 0; z < total_tuples; z++) {
230  if (edges[z].source < v_min_id) v_min_id = edges[z].source;
231  if (edges[z].source > v_max_id) v_max_id = edges[z].source;
232  if (edges[z].target < v_min_id) v_min_id = edges[z].target;
233  if (edges[z].target > v_max_id) v_max_id = edges[z].target;
234  // PGR_DBG("%i <-> %i", v_min_id, v_max_id);
235  }
236 
237  //::::::::::::::::::::::::::::::::::::
238  //:: reducing vertex id (renumbering)
239  //::::::::::::::::::::::::::::::::::::
240  for (z = 0; z < total_tuples; z++) {
241  // check if edges[] contains source and target
242  if (edges[z].source == start_vertex || edges[z].target == start_vertex)
243  ++s_count;
244  if (edges[z].source == end_vertex || edges[z].target == end_vertex)
245  ++t_count;
246 
247  edges[z].source -= v_min_id;
248  edges[z].target -= v_min_id;
249  // PGR_DBG("%i - %i", edges[z].source, edges[z].target);
250  }
251 
252  PGR_DBG("Total %i tuples", total_tuples);
253 
254  if (s_count == 0) {
255  elog(ERROR, "Start vertex was not found.");
256  return -1;
257  }
258 
259  if (t_count == 0) {
260  elog(ERROR, "Target vertex was not found.");
261  return -1;
262  }
263 
264  start_vertex -= v_min_id;
265  end_vertex -= v_min_id;
266 
267  // v_max_id -= v_min_id;
268 
269  PGR_DBG("Calling bidirsp_wrapper(edges, %u, %ld, %ld, %ld, %d, %d, ...)\n",
270  total_tuples, v_max_id + 2, start_vertex, end_vertex,
271  directed, has_reverse_cost);
272 
273  ret = bidirsp_wrapper(edges, total_tuples, (int)v_max_id + 2, (int)start_vertex, (int)end_vertex,
274  directed, has_reverse_cost,
275  path, path_count, &err_msg);
276 
277  PGR_DBG("Back from bidirsp_wrapper() ret: %d", ret);
278  if (ret < 0) {
279  elog(ERROR, "Error computing path: %s", err_msg);
280  }
281 
282  PGR_DBG("*path_count = %i\n", *path_count);
283 
284  //::::::::::::::::::::::::::::::::
285  //:: restoring original vertex id
286  //::::::::::::::::::::::::::::::::
287  for (z = 0; z < *path_count; z++) {
288  // PGR_DBG("vetex %i\n", (*path)[z].vertex_id);
289  (*path)[z].vertex_id+= v_min_id;
290  }
291 
292  PGR_DBG("ret = %i\n", ret);
293 
294  pgr_SPI_finish();
295  return 0;
296 }
297 
298 
300 PGDLLEXPORT Datum
301 bidir_dijkstra_shortest_path(PG_FUNCTION_ARGS) {
302  FuncCallContext *funcctx;
303  uint32_t call_cntr;
304  uint32_t max_calls;
305  TupleDesc tuple_desc;
307  // char * sql;
308 
309 
310  // stuff done only on the first call of the function
311  if (SRF_IS_FIRSTCALL()) {
312  MemoryContext oldcontext;
313  int path_count = 0;
314 #ifdef DEBUG
315  int ret = -1;
316 #endif
317  int i;
318 
319  // create a function context for cross-call persistence
320  funcctx = SRF_FIRSTCALL_INIT();
321 
322  // switch to memory context appropriate for multiple function calls
323  oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
324 
325  // verify that the first 5 args are not NULL
326  for (i = 0; i < 5; i++)
327  if (PG_ARGISNULL(i)) {
328  elog(ERROR, "bidir_dijkstra_shortest_path(): Argument %i may not be NULL", i+1);
329  }
330 
331  PGR_DBG("Calling compute_bidirsp");
332 
333 #ifdef DEBUG
334  ret =
335 #endif
336  compute_bidirsp(pgr_text2char(PG_GETARG_TEXT_P(0)),
337  (int64_t)PG_GETARG_INT32(1),
338  (int64_t)PG_GETARG_INT32(2),
339  PG_GETARG_BOOL(3),
340  PG_GETARG_BOOL(4),
341  &path, &path_count);
342 #ifdef DEBUG
343  double total_cost = 0;
344  PGR_DBG("Ret is %i", ret);
345  if (ret >= 0) {
346  int i;
347  for (i = 0; i < path_count; i++) {
348  // PGR_DBG("Step %i vertex_id %i ", i, path[i].vertex_id);
349  // PGR_DBG(" edge_id %i ", path[i].edge_id);
350  // PGR_DBG(" cost %f ", path[i].cost);
351  total_cost+= path[i].cost;
352  }
353  }
354  PGR_DBG("Total cost is: %f", total_cost);
355 #endif
356 
357  // total number of tuples to be returned
358  funcctx->max_calls = (uint32_t)path_count;
359  funcctx->user_fctx = path;
360 
361  funcctx->tuple_desc =
362  BlessTupleDesc(RelationNameGetTupleDesc("pgr_costResult"));
363 
364  MemoryContextSwitchTo(oldcontext);
365  }
366 
367  // stuff done on every call of the function
368  funcctx = SRF_PERCALL_SETUP();
369 
370  call_cntr = funcctx->call_cntr;
371  max_calls = funcctx->max_calls;
372  tuple_desc = funcctx->tuple_desc;
373  path = (path_element_t*) funcctx->user_fctx;
374 
375  if (call_cntr < max_calls) { // do when there is more left to send
376  HeapTuple tuple;
377  Datum result;
378  Datum *values;
379  bool* nulls;
380 
381  values = palloc(4 * sizeof(Datum));
382  nulls = palloc(4 * sizeof(bool));
383 
384  values[0] = Int32GetDatum(call_cntr);
385  nulls[0] = false;
386  values[1] = Int32GetDatum(path[call_cntr].vertex_id);
387  nulls[1] = false;
388  values[2] = Int32GetDatum(path[call_cntr].edge_id);
389  nulls[3] = false;
390  values[3] = Float8GetDatum(path[call_cntr].cost);
391  nulls[3] = false;
392 
393  tuple = heap_form_tuple(tuple_desc, values, nulls);
394 
395  // make the tuple into a datum
396  result = HeapTupleGetDatum(tuple);
397 
398  // clean up (this is not really necessary)
399  pfree(values);
400  pfree(nulls);
401 
402  SRF_RETURN_NEXT(funcctx, result);
403  } else { // do when there is no more left
404  PGR_DBG("Going to free path");
405  if (path) free(path);
406  SRF_RETURN_DONE(funcctx);
407  }
408 }
int reverse_cost
Definition: bdsp.c:59
#define TUPLIMIT
Definition: bdsp.c:50
double reverse_cost
Definition: pgr_types.h:132
int path_count
Definition: BDATester.cpp:51
int64_t source
Definition: pgr_types.h:129
int64_t target
Definition: pgr_types.h:130
#define PGR_DBG(...)
Definition: debug_macro.h:33
int id
Definition: bdsp.c:55
struct edge_columns edge_columns_t
static int compute_bidirsp(char *sql, int64_t start_vertex, int64_t end_vertex, bool directed, bool has_reverse_cost, path_element_t **path, int *path_count)
Definition: bdsp.c:153
int cost
Definition: bdsp.c:58
int source
Definition: bdsp.c:56
void pgr_SPI_finish(void)
static void fetch_edge(HeapTuple *tuple, TupleDesc *tupdesc, edge_columns_t *edge_columns, edge_t *target_edge)
Definition: bdsp.c:124
int64_t id
Definition: pgr_types.h:128
PGDLLEXPORT Datum bidir_dijkstra_shortest_path(PG_FUNCTION_ARGS)
Definition: bdsp.c:301
double cost
Definition: pgr_types.h:131
edge_astar_t * edges
Definition: BDATester.cpp:46
void pgr_SPI_connect(void)
int bidirsp_wrapper(edge_t *edges, unsigned int edge_count, int maxNode, int start_vertex, int end_vertex, bool directed, bool has_reverse_cost, path_element_t **path, int *path_count, char **err_msg)
Definition: bdsp_driver.cpp:41
static int fetch_edge_columns(SPITupleTable *tuptable, edge_columns_t *edge_columns, bool has_reverse_cost)
Definition: bdsp.c:69
path_element_t * path
Definition: BDATester.cpp:49
int target
Definition: bdsp.c:57
Portal pgr_SPI_cursor_open(SPIPlanPtr SPIplan)
char * err_msg
Definition: BDATester.cpp:50
PG_FUNCTION_INFO_V1(bidir_dijkstra_shortest_path)
char * pgr_text2char(text *in)
SPIPlanPtr pgr_SPI_prepare(char *sql)
double cost
Definition: pgr_types.h:76