pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
shooting_star.c
1 /*PGR-GNU*****************************************************************
2 
3 Copyright (c) 2015 pgRouting developers
4 Mail: project@pgrouting.org
5 
6 ------
7 
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12 
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17 
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 
22 ********************************************************************PGR-GNU*/
23 /*
24  * Shooting* Shortest path algorithm for PostgreSQL
25  *
26  * Copyright (c) 2007 Anton A. Patrushev, Orkney, Inc.
27  *
28  * This program is free software; you can redistribute it and/or modify
29  * it under the terms of the GNU General Public License as published by
30  * the Free Software Foundation; either version 2 of the License, or
31  * (at your option) any later version.
32  *
33  * This program is distributed in the hope that it will be useful,
34  * but WITHOUT ANY WARRANTY; without even the implied warranty of
35  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
36  * GNU General Public License for more details.
37  *
38  * You should have received a copy of the GNU General Public License
39  * along with this program; if not, write to the Free Software
40  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
41  *
42  */
43 
44 #include "postgres.h"
45 #include "executor/spi.h"
46 #include "funcapi.h"
47 #include "catalog/pg_type.h"
48 #if PGSQL_VERSION > 92
49 #include "access/htup_details.h"
50 #endif
51 
52 #include <stdio.h>
53 #include <stdlib.h>
54 #include <search.h>
55 
56 #include <string.h>
57 #include <time.h>
58 
59 #include "shooting_star.h"
60 
61 //-------------------------------------------------------------------------
62 
63 Datum shortest_path_shooting_star(PG_FUNCTION_ARGS);
64 
65 #undef DEBUG
66 //#define DEBUG 1
67 
68 #ifdef DEBUG
69 #define DBG(format, arg...) \
70  elog(NOTICE, format , ## arg)
71 #else
72 #define DBG(format, arg...) do { ; } while (0)
73 #endif
74 
75 // The number of tuples to fetch from the SPI cursor at each iteration
76 #define TUPLIMIT 1000
77 
78 static char *
79 text2char(text *in)
80 {
81  char *out = palloc(VARSIZE(in));
82 
83  memcpy(out, VARDATA(in), VARSIZE(in) - VARHDRSZ);
84  out[VARSIZE(in) - VARHDRSZ] = '\0';
85  return out;
86 }
87 
88 static int
89 finish(int code, int ret)
90 {
91  code = SPI_finish();
92  if (code != SPI_OK_FINISH )
93  {
94  elog(ERROR,"couldn't disconnect from SPI");
95  return -1 ;
96  }
97 
98  return ret;
99 }
100 
102 {
103  int id;
104  int source;
105  int target;
106  int cost;
107  int reverse_cost;
108  int s_x;
109  int s_y;
110  int t_x;
111  int t_y;
112  int to_cost;//cost of transit to adjacent edge
113  int rule;
115 
116 static int
117 fetch_edge_shooting_star_columns(SPITupleTable *tuptable,
119  bool has_reverse_cost)
120 {
121  edge_columns->id = SPI_fnumber(SPI_tuptable->tupdesc, "id");
122  edge_columns->source = SPI_fnumber(SPI_tuptable->tupdesc, "source");
123  edge_columns->target = SPI_fnumber(SPI_tuptable->tupdesc, "target");
124  edge_columns->cost = SPI_fnumber(SPI_tuptable->tupdesc, "cost");
125  if (edge_columns->id == SPI_ERROR_NOATTRIBUTE ||
126  edge_columns->source == SPI_ERROR_NOATTRIBUTE ||
127  edge_columns->target == SPI_ERROR_NOATTRIBUTE ||
128  edge_columns->cost == SPI_ERROR_NOATTRIBUTE)
129  {
130  elog(ERROR, "Error, query must return columns "
131  "'id', 'source', 'target' and 'cost'");
132  return -1;
133  }
134 
135  if (SPI_gettypeid(SPI_tuptable->tupdesc,
136  edge_columns->source) != INT4OID ||
137  SPI_gettypeid(SPI_tuptable->tupdesc,
138  edge_columns->target) != INT4OID ||
139  SPI_gettypeid(SPI_tuptable->tupdesc, edge_columns->cost) != FLOAT8OID)
140  {
141  elog(ERROR, "Error, columns 'source', 'target' must be of type int4, "
142  "'cost' must be of type float8");
143  return -1;
144  }
145 
146  DBG("columns: id %i source %i target %i cost %i",
147  edge_columns->id, edge_columns->source,
148  edge_columns->target, edge_columns->cost);
149 
150  if (has_reverse_cost)
151  {
152  edge_columns->reverse_cost = SPI_fnumber(SPI_tuptable->tupdesc,
153  "reverse_cost");
154 
155  if (edge_columns->reverse_cost == SPI_ERROR_NOATTRIBUTE)
156  {
157  elog(ERROR, "Error, reverse_cost is used, but query did't return "
158  "'reverse_cost' column");
159  return -1;
160  }
161 
162  if (SPI_gettypeid(SPI_tuptable->tupdesc,
163  edge_columns->reverse_cost) != FLOAT8OID)
164  {
165  elog(ERROR, "Error, columns 'reverse_cost' must be of type float8");
166  return -1;
167  }
168 
169  DBG("columns: reverse_cost cost %i", edge_columns->reverse_cost);
170  }
171 
172  edge_columns->s_x = SPI_fnumber(SPI_tuptable->tupdesc, "x1");
173  edge_columns->s_y = SPI_fnumber(SPI_tuptable->tupdesc, "y1");
174  edge_columns->t_x = SPI_fnumber(SPI_tuptable->tupdesc, "x2");
175  edge_columns->t_y = SPI_fnumber(SPI_tuptable->tupdesc, "y2");
176 
177  if (edge_columns->s_x == SPI_ERROR_NOATTRIBUTE ||
178  edge_columns->s_y == SPI_ERROR_NOATTRIBUTE ||
179  edge_columns->t_x == SPI_ERROR_NOATTRIBUTE ||
180  edge_columns->t_y == SPI_ERROR_NOATTRIBUTE)
181  {
182  elog(ERROR, "Error, query must return columns "
183  "'x1', 'x2', 'y1' and 'y2'");
184  return -1;
185  }
186 
187  DBG("columns: x1 %i y1 %i x2 %i y2 %i",
188  edge_columns->s_x, edge_columns->s_y,
189  edge_columns->t_x,edge_columns->t_y);
190 
191 
192  edge_columns->to_cost = SPI_fnumber(SPI_tuptable->tupdesc, "to_cost");
193  edge_columns->rule = SPI_fnumber(SPI_tuptable->tupdesc, "rule");
194 
195  if (edge_columns->to_cost == SPI_ERROR_NOATTRIBUTE ||
196  edge_columns->rule == SPI_ERROR_NOATTRIBUTE)
197  {
198  elog(ERROR, "Error, query must return columns "
199  "'to_cost' and 'rule'");
200  return -1;
201  }
202 
203  return 0;
204 }
205 
206 //edges should be ordered by id or else we have to search for
207 //existing edges every time we want to add adjacent edge
208 static void
209 fetch_edge_shooting_star(HeapTuple *tuple, TupleDesc *tupdesc,
210  edge_shooting_star_columns_t *edge_columns,
211  edge_shooting_star_t *target_edge)
212 {
213  Datum binval;
214  bool isnull;
215  int t;
216 
217  for(t=0; t<MAX_RULE_LENGTH;++t)
218  target_edge->rule[t] = -1;
219 
220  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->id, &isnull);
221  if (isnull)
222  elog(ERROR, "id contains a null value");
223  target_edge->id = DatumGetInt32(binval);
224 
225  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->source, &isnull);
226  if (isnull)
227  elog(ERROR, "source contains a null value");
228  target_edge->source = DatumGetInt32(binval);
229 
230  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->target, &isnull);
231  if (isnull)
232  elog(ERROR, "target contains a null value");
233  target_edge->target = DatumGetInt32(binval);
234 
235  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->cost, &isnull);
236  if (isnull)
237  elog(ERROR, "cost contains a null value");
238  target_edge->cost = DatumGetFloat8(binval);
239 
240  if (edge_columns->reverse_cost != -1)
241  {
242  binval = SPI_getbinval(*tuple, *tupdesc,
243  edge_columns->reverse_cost, &isnull);
244  if (isnull)
245  elog(ERROR, "reverse_cost contains a null value");
246  target_edge->reverse_cost = DatumGetFloat8(binval);
247  }
248 
249  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->s_x, &isnull);
250  if (isnull)
251  elog(ERROR, "source x contains a null value");
252  target_edge->s_x = DatumGetFloat8(binval);
253 
254  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->s_y, &isnull);
255  if (isnull)
256  elog(ERROR, "source y contains a null value");
257  target_edge->s_y = DatumGetFloat8(binval);
258 
259  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->t_x, &isnull);
260  if (isnull)
261  elog(ERROR, "target x contains a null value");
262  target_edge->t_x = DatumGetFloat8(binval);
263 
264  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->t_y, &isnull);
265  if (isnull)
266  elog(ERROR, "target y contains a null value");
267  target_edge->t_y = DatumGetFloat8(binval);
268 
269  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->to_cost, &isnull);
270  if (isnull)
271  target_edge->to_cost = 0;
272 
273  else
274  target_edge->to_cost = DatumGetFloat8(binval);
275 
276  char *str = DatumGetCString(SPI_getvalue(*tuple, *tupdesc, edge_columns->rule));
277 
278  if(str!=NULL)
279  {
280  char* pch = NULL;
281  int ci = MAX_RULE_LENGTH;
282 
283  pch = (char *)strtok (str," ,");
284 
285  while (pch != NULL)
286  {
287  --ci;
288  target_edge->rule[ci] = atoi(pch);
289  pch = (char *)strtok (NULL, " ,");
290  }
291  }
292 }
293 
294 
295 static int compute_shortest_path_shooting_star(char* sql, int source_edge_id,
296  int target_edge_id, bool directed,
297  bool has_reverse_cost,
298  path_element_t **path, int *path_count)
299 {
300 
301  int SPIcode;
302  void *SPIplan;
303  Portal SPIportal;
304  bool moredata = TRUE;
305  int ntuples;
306  edge_shooting_star_t *edges = NULL;
307  int total_tuples = 0;
308 
309 // int v_max_id=0;
310 // int v_min_id=INT_MAX;
311  int e_max_id=0;
312  int e_min_id=INT_MAX;
313 
314  edge_shooting_star_columns_t edge_columns = {id: -1, source: -1, target: -1,
315  cost: -1, reverse_cost: -1,
316  s_x: -1, s_y: -1, t_x: -1, t_y: -1,
317  to_cost: -1, rule: -1};
318  char *err_msg;
319  int ret = -1;
320  register int z, t;
321 
322  int s_count=0;
323  int t_count=0;
324 
325  DBG("start shortest_path_shooting_star\n");
326 
327  SPIcode = SPI_connect();
328  if (SPIcode != SPI_OK_CONNECT)
329  {
330  elog(ERROR, "shortest_path_shooting_star: couldn't open a connection to SPI");
331  return -1;
332  }
333 
334  SPIplan = SPI_prepare(sql, 0, NULL);
335  if (SPIplan == NULL)
336  {
337  elog(ERROR, "shortest_path_shooting_star: couldn't create query plan via SPI");
338  return -1;
339  }
340 
341  if ((SPIportal = SPI_cursor_open(NULL, SPIplan, NULL, NULL, true)) == NULL)
342  {
343  elog(ERROR, "shortest_path_shooting_star: SPI_cursor_open('%s') returns NULL",
344  sql);
345  return -1;
346  }
347 
348  while (moredata == TRUE)
349  {
350  SPI_cursor_fetch(SPIportal, TRUE, TUPLIMIT);
351 
352  if (edge_columns.id == -1)
353  {
354  if (fetch_edge_shooting_star_columns(SPI_tuptable, &edge_columns,
355  has_reverse_cost) == -1)
356  return finish(SPIcode, ret);
357  }
358 
359  //DBG("***%i***", ret);
360 
361  ntuples = SPI_processed;
362  total_tuples += ntuples;
363 
364  if (!edges)
365  edges = palloc(total_tuples * sizeof(edge_shooting_star_t));
366  else
367  edges = repalloc(edges, total_tuples * sizeof(edge_shooting_star_t));
368 
369  if (edges == NULL)
370  {
371  elog(ERROR, "Out of memory");
372  return finish(SPIcode, ret);
373  }
374 
375  if (ntuples > 0)
376  {
377  int t;
378  SPITupleTable *tuptable = SPI_tuptable;
379  TupleDesc tupdesc = SPI_tuptable->tupdesc;
380 
381  for (t = 0; t < ntuples; t++)
382  {
383  HeapTuple tuple = tuptable->vals[t];
384  fetch_edge_shooting_star(&tuple, &tupdesc, &edge_columns,
385  &edges[total_tuples - ntuples + t]);
386  }
387  SPI_freetuptable(tuptable);
388  }
389  else
390  {
391  moredata = FALSE;
392  }
393  }
394 
395 
396  DBG("Total %i tuples", total_tuples);
397 
398 
399 
400  for(z=0; z<total_tuples; z++)
401  {
402  if(edges[z].id<e_min_id)
403  e_min_id=edges[z].id;
404 
405  if(edges[z].id>e_max_id)
406  e_max_id=edges[z].id;
407 
408  }
409 
410  DBG("E : %i <-> %i", e_min_id, e_max_id);
411 
412  for(z=0; z<total_tuples; ++z)
413  {
414 
415  //check if edges[] contains source and target
416  if(edges[z].id == source_edge_id)
417  ++s_count;
418  if(edges[z].id == target_edge_id)
419  ++t_count;
420 
421 
422  //edges[z].source-=v_min_id;
423  //edges[z].target-=v_min_id;
424 
425  }
426 
427  DBG("Total %i tuples", total_tuples);
428 
429  if(s_count == 0)
430  {
431  elog(ERROR, "Start edge was not found.");
432  return -1;
433  }
434 
435  if(t_count == 0)
436  {
437  elog(ERROR, "Target edge was not found.");
438  return -1;
439  }
440 
441  DBG("Total %i tuples", total_tuples);
442 
443  DBG("Calling boost_shooting_star <%i>\n", total_tuples);
444 
445  //time_t stime = time(NULL);
446 
447  ret = boost_shooting_star(edges, total_tuples, source_edge_id,
448  target_edge_id,
449  directed, has_reverse_cost,
450  path, path_count, &err_msg, e_max_id);
451 
452  //time_t etime = time(NULL);
453 
454  //DBG("Path was calculated in %f seconds. \n", difftime(etime, stime));
455 
456  DBG("SIZE %i\n",*path_count);
457 
458  DBG("ret = %i\n",ret);
459 
460 
461  if (ret < 0)
462  {
463  ereport(ERROR, (errcode(ERRCODE_E_R_E_CONTAINING_SQL_NOT_PERMITTED),
464  errmsg("Error computing path: %s", err_msg)));
465  }
466  return finish(SPIcode, ret);
467 }
468 
469 
470 PG_FUNCTION_INFO_V1(shortest_path_shooting_star);
471 Datum
472 shortest_path_shooting_star(PG_FUNCTION_ARGS)
473 {
474  FuncCallContext *funcctx;
475  int call_cntr;
476  int max_calls;
477  TupleDesc tuple_desc;
478  path_element_t *path = 0;
479 
480  /* stuff done only on the first call of the function */
481  if (SRF_IS_FIRSTCALL())
482  {
483  MemoryContext oldcontext;
484  int path_count = 0;
485  int ret;
486 
487  /* create a function context for cross-call persistence */
488  funcctx = SRF_FIRSTCALL_INIT();
489 
490  /* switch to memory context appropriate for multiple function calls */
491  oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
492 
493 
494  ret = compute_shortest_path_shooting_star(text2char(PG_GETARG_TEXT_P(0)),
495  PG_GETARG_INT32(1),
496  PG_GETARG_INT32(2),
497  PG_GETARG_BOOL(3),
498  PG_GETARG_BOOL(4),
499  &path, &path_count);
500 
501 #ifdef DEBUG
502  DBG("Ret is %i", ret);
503  if (ret >= 0)
504  {
505  int i;
506  for (i = 0; i < path_count; i++)
507  {
508  DBG("Step # %i vertex_id %i ", i, path[i].vertex_id);
509  DBG(" edge_id %i ", path[i].edge_id);
510  DBG(" cost %f ", path[i].cost);
511  }
512  }
513 #endif
514 
515  /* total number of tuples to be returned */
516  DBG("Conting tuples number\n");
517  funcctx->max_calls = path_count;
518  funcctx->user_fctx = path;
519 
520  DBG("Path count %i", path_count);
521 
522  funcctx->tuple_desc =
523  BlessTupleDesc(RelationNameGetTupleDesc("pgr_costResult"));
524 
525  MemoryContextSwitchTo(oldcontext);
526  }
527 
528  /* stuff done on every call of the function */
529 
530  funcctx = SRF_PERCALL_SETUP();
531 
532  call_cntr = funcctx->call_cntr;
533  max_calls = funcctx->max_calls;
534  tuple_desc = funcctx->tuple_desc;
535  path = (path_element_t*) funcctx->user_fctx;
536 
537  DBG("Trying to allocate some memory\n");
538 
539  if (call_cntr < max_calls) /* do when there is more left to send */
540  {
541  HeapTuple tuple;
542  Datum result;
543  Datum *values;
544  char* nulls;
545 
546  values = palloc(4 * sizeof(Datum));
547  nulls = palloc(4 * sizeof(char));
548 
549  values[0] = Int32GetDatum(call_cntr);
550  nulls[0] = ' ';
551  values[1] = Int32GetDatum(path[call_cntr].vertex_id);
552  nulls[1] = ' ';
553  values[2] = Int32GetDatum(path[call_cntr].edge_id);
554  nulls[2] = ' ';
555  values[3] = Float8GetDatum(path[call_cntr].cost);
556  nulls[3] = ' ';
557 
558  tuple = heap_formtuple(tuple_desc, values, nulls);
559 
560  /* make the tuple into a datum */
561  result = HeapTupleGetDatum(tuple);
562 
563  /* clean up (this is not really necessary) */
564  pfree(values);
565  pfree(nulls);
566 
567  SRF_RETURN_NEXT(funcctx, result);
568  }
569  else /* do when there is no more left */
570  {
571  if (path) free(path);
572  SRF_RETURN_DONE(funcctx);
573  }
574 }