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