root/tags/release-1.02/core/src/astar.c

Revision 162, 15.3 KB (checked in by anton, 3 years ago)

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