pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
k_targets_sp.c
1 /*PGR-GNU*****************************************************************
2 
3  * Shortest path algorithm for PostgreSQL
4  *
5  * Copyright (c) 2005 Sylvain Pasche
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/pgr_types.h"
27 #include "postgres.h"
28 #include "executor/spi.h"
29 #include "funcapi.h"
30 #include "utils/array.h"
31 #include "utils/lsyscache.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 #include "k_targets_boost_wrapper.h"
40 
41 Datum manytomany_dijkstra_dmatrix(PG_FUNCTION_ARGS);
42 
43 #undef DEBUG
44 //#define DEBUG 1
45 #include "../../common/src/debug_macro.h"
46 #include "../../common/src/postgres_connection.h"
47 
48 
49 // The number of tuples to fetch from the SPI cursor at each iteration
50 #define TUPLIMIT 1000
51 
52 /*
53 // this is already defined dijkstra.c
54 #ifdef PG_MODULE_MAGIC
55 PG_MODULE_MAGIC;
56 #endif
57 */
58 
59 typedef struct edge_columns
60 {
61  int id;
62  int source;
63  int target;
64  int cost;
65  int reverse_cost;
67 
68 
69 
70 
71 #define DTYPE int
72 
73 static DTYPE *get_pgarray(int *num, ArrayType *input)
74 {
75  int ndims, *dims; // , *lbs;
76  bool *nulls;
77  Oid i_eltype;
78  int16 i_typlen;
79  bool i_typbyval;
80  char i_typalign;
81  Datum *i_data;
82  int i, n;
83  DTYPE *data;
84 
85  /* get input array element type */
86  i_eltype = ARR_ELEMTYPE(input);
87  get_typlenbyvalalign(i_eltype, &i_typlen, &i_typbyval, &i_typalign);
88 
89 
90  /* validate input data type */
91  switch(i_eltype){
92  case INT2OID:
93  case INT4OID:
94  case FLOAT4OID:
95  case FLOAT8OID:
96  break;
97  default:
98  elog(ERROR, "target must be integer[]");
99  break;
100  }
101 
102  /* get various pieces of data from the input array */
103  ndims = ARR_NDIM(input);
104  dims = ARR_DIMS(input);
105  // lbs = ARR_LBOUND(input);
106 
107  if (ndims != 1) {
108  elog(ERROR, "target must be integer[]");
109  }
110 
111  /* get src data */
112  deconstruct_array(input, i_eltype, i_typlen, i_typbyval, i_typalign,
113 &i_data, &nulls, &n);
114 
115  PGR_DBG("get_pgarray: ndims=%d, n=%d", ndims, n);
116 
117 #ifdef DEBUG
118  for (i=0; i<ndims; i++) {
119  PGR_DBG(" dims[%d]=%d, lbs[%d]=%d", i, dims[i], i, lbs[i]);
120  }
121 #endif
122 
123  /* construct a C array */
124  data = (DTYPE *) palloc(n * sizeof(DTYPE));
125  if (!data) {
126  elog(ERROR, "Error: Out of memory!");
127  }
128 
129  for (i=0; i<n; i++) {
130  if (nulls[i]) {
131  data[i] = -1;
132  }
133  else {
134  switch(i_eltype){
135  case INT2OID:
136  data[i] = (DTYPE) DatumGetInt16(i_data[i]);
137  break;
138  case INT4OID:
139  data[i] = (DTYPE) DatumGetInt32(i_data[i]);
140  break;
141  case FLOAT4OID:
142  data[i] = (DTYPE) DatumGetFloat4(i_data[i]);
143  break;
144  case FLOAT8OID:
145  data[i] = (DTYPE) DatumGetFloat8(i_data[i]);
146  break;
147  }
148  }
149  PGR_DBG(" data[%d]=%.4f", i, data[i]);
150  }
151 
152  pfree(nulls);
153  pfree(i_data);
154 
155  *num = dims[0];
156 
157  return data;
158 }
159 
160 
161 /*
162  * This function fetches the edge columns from the SPITupleTable.
163  *
164 */
165 static int fetch_edge_columns(SPITupleTable *tuptable, edge_columns_t *edge_columns, bool has_reverse_cost)
166 {
167  edge_columns->id = SPI_fnumber(SPI_tuptable->tupdesc, "id");
168  edge_columns->source = SPI_fnumber(SPI_tuptable->tupdesc, "source");
169  edge_columns->target = SPI_fnumber(SPI_tuptable->tupdesc, "target");
170  edge_columns->cost = SPI_fnumber(SPI_tuptable->tupdesc, "cost");
171  if (edge_columns->id == SPI_ERROR_NOATTRIBUTE ||
172  edge_columns->source == SPI_ERROR_NOATTRIBUTE ||
173  edge_columns->target == SPI_ERROR_NOATTRIBUTE ||
174  edge_columns->cost == SPI_ERROR_NOATTRIBUTE)
175  {
176  elog(ERROR, "Error, query must return columns "
177  "'id', 'source', 'target' and 'cost'");
178  return -1;
179  }
180 
181  if (SPI_gettypeid(SPI_tuptable->tupdesc, edge_columns->source) != INT4OID ||
182  SPI_gettypeid(SPI_tuptable->tupdesc, edge_columns->target) != INT4OID ||
183  SPI_gettypeid(SPI_tuptable->tupdesc, edge_columns->cost) != FLOAT8OID)
184  {
185  elog(ERROR, "Error, columns 'source', 'target' must be of type int4, 'cost' must be of type float8");
186  return -1;
187  }
188 
189  PGR_DBG("columns: id %i source %i target %i cost %i",
190  edge_columns->id, edge_columns->source,
191  edge_columns->target, edge_columns->cost);
192 
193  if (has_reverse_cost)
194  {
195  edge_columns->reverse_cost = SPI_fnumber(SPI_tuptable->tupdesc,
196  "reverse_cost");
197 
198  if (edge_columns->reverse_cost == SPI_ERROR_NOATTRIBUTE)
199  {
200  elog(ERROR, "Error, reverse_cost is used, but query did't return "
201  "'reverse_cost' column");
202  return -1;
203  }
204 
205  if (SPI_gettypeid(SPI_tuptable->tupdesc, edge_columns->reverse_cost)
206  != FLOAT8OID)
207  {
208  elog(ERROR, "Error, columns 'reverse_cost' must be of type float8");
209  return -1;
210  }
211 
212  PGR_DBG("columns: reverse_cost cost %i", edge_columns->reverse_cost);
213  }
214 
215  return 0;
216 }
217 
218 static void fetch_edge(HeapTuple *tuple, TupleDesc *tupdesc, edge_columns_t *edge_columns, edge_t *target_edge)
219 {
220  Datum binval;
221  bool isnull;
222 
223  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->id, &isnull);
224  if (isnull)
225  elog(ERROR, "id contains a null value");
226  target_edge->id = DatumGetInt32(binval);
227 
228  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->source, &isnull);
229  if (isnull)
230  elog(ERROR, "source contains a null value");
231  target_edge->source = DatumGetInt32(binval);
232 
233  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->target, &isnull);
234  if (isnull)
235  elog(ERROR, "target contains a null value");
236  target_edge->target = DatumGetInt32(binval);
237 
238  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->cost, &isnull);
239  if (isnull)
240  elog(ERROR, "cost contains a null value");
241  target_edge->cost = DatumGetFloat8(binval);
242 
243  if (edge_columns->reverse_cost != -1)
244  {
245  binval = SPI_getbinval(*tuple, *tupdesc, edge_columns->reverse_cost,
246  &isnull);
247  if (isnull)
248  elog(ERROR, "reverse_cost contains a null value");
249  target_edge->reverse_cost = DatumGetFloat8(binval);
250  }
251 }
252 
253 
254 
255 static int many2many_dijkstra_dm(char *sql, int *vids, int num, bool directed,
256  bool has_reverse_cost, bool symmetric, float8 *dm)
257 {
258  // int SPIcode;
259  void *SPIplan;
260  Portal SPIportal;
261  bool moredata = TRUE;
262  int ntuples;
263  edge_t *edges = NULL;
264  int total_tuples = 0;
265  edge_columns_t edge_columns = {.id= -1, .source= -1, .target= -1,
266  .cost= -1, .reverse_cost= -1};
267  int v_max_id = 0;
268  int v_min_id = INT_MAX;
269 
270  // int sumFoundVids = 0;
271 
272  int i, j;
273  int zcnt = 0;
274 
275  int vvids[num];
276  int v_count[num];
277  for (i=0; i<num; i++)
278  v_count[i] = 0;
279 
280  char *err_msg;
281  int ret = -1;
282 
283  pgr_cost_t *dists;
284 
285  PGR_DBG("start many2many_dijkstra_dm");
286 
287  pgr_SPI_connect();
288  SPIplan = pgr_SPI_prepare(sql);
289  SPIportal = pgr_SPI_cursor_open(SPIplan);
290 
291  PGR_DBG("Starting while loop to collect edges ...");
292 
293  while (moredata == TRUE) {
294  PGR_DBG("Calling SPI_cursor_fetch");
295  SPI_cursor_fetch(SPIportal, TRUE, TUPLIMIT);
296 
297  if (fetch_edge_columns(SPI_tuptable, &edge_columns,
298  has_reverse_cost) == -1) {
299  pgr_SPI_finish();
300  return -1;
301  }
302 
303  ntuples = SPI_processed;
304  PGR_DBG("ntuples=%d", ntuples);
305  if (ntuples > 0) {
306  SPITupleTable *tuptable = SPI_tuptable;
307  TupleDesc tupdesc = SPI_tuptable->tupdesc;
308  int t;
309 
310  total_tuples += ntuples;
311 
312  if (!edges)
313  edges = palloc(total_tuples * sizeof(edge_t));
314  else
315  edges = repalloc(edges, total_tuples * sizeof(edge_t));
316 
317  if (edges == NULL) {
318  elog(ERROR, "Out of memory!");
319  pgr_SPI_finish();
320  return -1;
321  }
322 
323  for (t=0; t < ntuples; t++) {
324  HeapTuple tuple = tuptable->vals[t];
325  fetch_edge(&tuple, &tupdesc, &edge_columns,
326  &edges[total_tuples - ntuples + t]);
327  }
328  SPI_freetuptable(tuptable);
329  }
330  else {
331  moredata = FALSE;
332  }
333  }
334  PGR_DBG("Total %d edges!", total_tuples);
335 
336  // find min and max vertex ids
337 
338  for (i=0; i<total_tuples; i++) {
339  if (edges[i].source < v_min_id) v_min_id = edges[i].source;
340  if (edges[i].source > v_max_id) v_max_id = edges[i].source;
341  if (edges[i].target < v_min_id) v_min_id = edges[i].target;
342  if (edges[i].target > v_max_id) v_max_id = edges[i].target;
343  }
344  PGR_DBG("v_min_id: %d, v_max_id: %d", v_min_id, v_max_id);
345 
346  // renumber vertices
347 
348  for (i=0; i<total_tuples; i++) {
349  // check if edge contains vids[]
350  for (j=0; j<num; j++) {
351  if (edges[i].source == vids[j] || edges[i].target == vids[j])
352  v_count[j]++;
353  }
354  edges[i].source -= v_min_id;
355  edges[i].target -= v_min_id;
356  }
357 
358  for (j=0; j< num; j++) {
359  if (v_count[j] == 0) zcnt++;
360  PGR_DBG("vids[%d]: %d, cnt: %d", j, vids[j], v_count[j]);
361  vvids[j] = vids[j] - v_min_id;
362  }
363 
364  if (zcnt > 0) {
365  elog(ERROR, "%d vid(s) were not found in the edges!", zcnt);
366  return -1;
367  }
368 
369  PGR_DBG("Starting loop to build dmatrix!");
370 
371  for (j=0; j<num; j++) {
372  PGR_DBG("Calling onetomany_dijkstra_boostdist j=%d", j);
373 
374  ret = onetomany_dijkstra_boostdist(edges, total_tuples, vvids[j],
375  vvids, num, directed, has_reverse_cost, &dists, &err_msg);
376 
377  if (ret < 0) {
378  elog(ERROR, "onetomany_dijkstra_boostdist failed on j=%d", j);
379  }
380 
381  // ASSUMING: results are in order of vvids array
382  for (i=0; i<num; i++) {
383  dm[j*num + i] = dists[i].cost;
384  }
385 
386  free(dists);
387  dists = NULL;
388  }
389 
390  PGR_DBG("Making the matrix symmertic if requested!");
391 
392  // if symmetric requsted, then average cells to make it symmetric
393 
394  if (symmetric) {
395  for (i=0; i<num; i++) {
396  dm[i * num + i] = 0.0;
397  for (j=i+1; j<num; j++) {
398  if (dm[j*num + i] < 0.0 && dm[i*num + j] > 0.0)
399  dm[j*num + i] = dm[i*num + j];
400  else if (dm[i*num + j] < 0.0 && dm[j*num + i] > 0.0)
401  dm[i*num + j] = dm[j*num + i];
402  else if (dm[j*num + i] < 0.0 && dm[i*num + j] < 0.0)
403  dm[i*num + j] = dm[j*num + i] = -1.0;
404  else
405  dm[j*num + i] = dm[i*num + j] = (dm[j*num + i] + dm[i*num + j]) / 2.0;
406  }
407  }
408  }
409 
410  PGR_DBG("Leaving many2many_dijkstra_dm");
411 
412  pgr_SPI_finish();
413  return 0;
414 }
415 
416 /*
417  create or replace function pgr_vidsToDMatrix(sql text,
418  vids integer[], dir bool, has_rcost bool, symmetric bool)
419  return real8[]
420  as '', 'manytomany_dijkstra_dmatrix' language C stable strict;
421 
422 */
423 
424 PG_FUNCTION_INFO_V1(manytomany_dijkstra_dmatrix);
425 
426 Datum manytomany_dijkstra_dmatrix(PG_FUNCTION_ARGS)
427 {
428  ArrayType *result;
429  Datum *result_data;
430  // Datum *values;
431  bool *nulls;
432  int i;
433  int num;
434  int ret;
435  float8 *dm;
436 
437  Oid o_eltype = FLOAT8OID;
438  int16 o_typlen;
439  bool o_typbyval;
440  char o_typalign;
441 
442  int ndims = 2;
443  int dims[2];
444  int lbs[2] = {1, 1};;
445 
446  char *sql = pgr_text2char(PG_GETARG_TEXT_P(0));
447  int *vids = get_pgarray(&num, PG_GETARG_ARRAYTYPE_P(1));
448 
449  dm = (float8 *)palloc(num * num * sizeof(float8));
450 
451  ret = many2many_dijkstra_dm(sql, vids, num,
452  PG_GETARG_BOOL(2), PG_GETARG_BOOL(3), PG_GETARG_BOOL(4),
453  dm);
454 
455  if (ret) {
456  elog(ERROR, "Error computing distance matrix!");
457  }
458 
459  result_data = (Datum *)palloc(num * num * sizeof(Datum));
460  nulls = (bool *)palloc(num * num * sizeof(bool));
461 
462  for (i=0; i<num*num; i++) {
463  if (dm[i] < 0.0) {
464  nulls[i] = true;
465  result_data[i] = PointerGetDatum(NULL);
466  }
467  else {
468  nulls[i] = false;
469  result_data[i] = Float8GetDatum((float8)dm[i]);
470  }
471  }
472 
473  pfree(dm);
474 
475  dims[0] = dims[1] = num;
476  get_typlenbyvalalign(o_eltype, &o_typlen, &o_typbyval, &o_typalign);
477 
478  result = construct_md_array((void *)result_data, nulls, ndims, dims,
479  lbs, o_eltype, o_typlen, o_typbyval, o_typalign);
480 
481  pfree(result_data);
482  pfree(nulls);
483 
484  PG_RETURN_ARRAYTYPE_P(result);
485 }
486