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
tsp2.c
Go to the documentation of this file.
1 /*PGR-MIT*****************************************************************
2 
3  * Traveling Sales Problem solver for pgRouting and PostgreSQL
4  *
5  * Copyright 2013, Stephen Woodbridge, iMaptools.com
6  * This program is released under an MIT-X license.
7  *
8 
9 ------
10 MIT/X license
11 
12 Permission is hereby granted, free of charge, to any person obtaining a copy
13 of this software and associated documentation files (the "Software"), to deal
14 in the Software without restriction, including without limitation the rights
15 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
16 copies of the Software, and to permit persons to whom the Software is
17 furnished to do so, subject to the following conditions:
18 
19 
20 The above copyright notice and this permission notice shall be included in
21 all copies or substantial portions of the Software.
22 
23 
24 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
25 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
26 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
27 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
28 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
29 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
30 THE SOFTWARE.
31 
32 ********************************************************************PGR-MIT*/
33 
34 /*
35  * This code is deprecated
36  */
37 
38 #include "./tsp.h"
39 #include <math.h>
40 
41 #include "postgres.h"
42 #include "funcapi.h"
43 #include "catalog/pg_type.h"
44 #include "utils/array.h"
45 #include "utils/lsyscache.h"
46 #if PGSQL_VERSION > 92
47 #include "access/htup_details.h"
48 #endif
49 
50 #include "fmgr.h"
51 
52 PGDLLEXPORT Datum tsp_matrix(PG_FUNCTION_ARGS);
53 
54 #undef DEBUG
55 #include "../../common/src/debug_macro.h"
56 
57 #if 0
58 #ifndef INFINITY
59 #ifndef _MSC_VER
60 #define INFINITY (1.0/0.0)
61 #else // _MSC_VER
62 #define INFINITY (DBL_MAX + DBL_MAX);
63 #endif // _MSC_VER
64 #endif
65 #endif
66 
67 // The number of tuples to fetch from the SPI cursor at each iteration
68 #define TUPLIMIT 1000
69 
70 
71 static DTYPE *get_pgarray(int *num, ArrayType *input) {
72  int ndims, *dims; // , *lbs;
73  bool *nulls;
74  Oid i_eltype;
75  int16 i_typlen;
76  bool i_typbyval;
77  char i_typalign;
78  Datum *i_data;
79  int i, n;
80  DTYPE *data;
81 
82  /* get input array element type */
83  i_eltype = ARR_ELEMTYPE(input);
84  get_typlenbyvalalign(i_eltype, &i_typlen, &i_typbyval, &i_typalign);
85 
86 
87  /* validate input data type */
88  switch (i_eltype) {
89  case INT2OID:
90  case INT4OID:
91  case FLOAT4OID:
92  case FLOAT8OID:
93  break;
94  default:
95  elog(ERROR, "Invalid input data type");
96  break;
97  }
98 
99  /* get various pieces of data from the input array */
100  ndims = ARR_NDIM(input);
101  dims = ARR_DIMS(input);
102  // lbs = ARR_LBOUND(input);
103 
104  if (ndims != 2 || dims[0] != dims[1]) {
105  elog(ERROR, "Error: matrix[num][num] in its definition.");
106  }
107 
108  /* get src data */
109  deconstruct_array(input, i_eltype, i_typlen, i_typbyval, i_typalign,
110 &i_data, &nulls, &n);
111 
112  PGR_DBG("get_pgarray: ndims=%d, n=%d", ndims, n);
113 
114 #ifdef DEBUG
115  for (i = 0; i < ndims; i++) {
116  // PGR_DBG(" dims[%d]=%d, lbs[%d]=%d", i, dims[i], i, lbs[i]);
117  PGR_DBG(" dims[%d]=%d", i, dims[i]);
118  }
119 #endif
120 
121  /* construct a C array */
122  data = (DTYPE *) palloc((size_t)(n) * sizeof(DTYPE));
123  if (!data) {
124  elog(ERROR, "Error: Out of memory!");
125  }
126 
127  for (i = 0; i < n; i++) {
128  if (nulls[i]) {
129  data[i] = (DTYPE) 0;
130  } else {
131  switch (i_eltype) {
132  case INT2OID:
133  data[i] = (DTYPE) DatumGetInt16(i_data[i]);
134  break;
135  case INT4OID:
136  data[i] = (DTYPE) DatumGetInt32(i_data[i]);
137  break;
138  case FLOAT4OID:
139  data[i] = (DTYPE) DatumGetFloat4(i_data[i]);
140  break;
141  case FLOAT8OID:
142  data[i] = (DTYPE) DatumGetFloat8(i_data[i]);
143  break;
144  }
145  /* we assume negative values are INFINTY */
146  /********************************************************
147  TODO: based on trying to add an endpt it is likely
148  that this will not work and you will get and error in
149  findEulerianPath
150  **********************************************************/
151  if (data[i] < 0) {
152  data[i] = (DTYPE) 0;
153  nulls[i] = true;
154  }
155  }
156  PGR_DBG(" data[%d]=%.4f", i, data[i]);
157  }
158 
159  pfree(nulls);
160  pfree(i_data);
161 
162  *num = dims[0];
163 
164  return data;
165 }
166 
167 
168 // macro to store distance values as matrix[num][num]
169 #define D(i, j) matrix[(i) * num + j]
170 
171 static int solve_tsp(DTYPE *matrix, int num, int start, int end, int **results) {
172  int ret;
173  int i;
174  int *ids;
175  DTYPE fit;
176  char *err_msg = NULL;
177 
178  PGR_DBG("In solve_tsp: num: %d, start: %d, end: %d", num, start, end);
179 
180  if (num < 4)
181  elog(ERROR, "Error TSP requires four or more locations to optimize. Only %d were supplied.", num);
182 
183  if (start < 0 || start >= num)
184  elog(ERROR, "Error start must be in the range of 0 <= start(%d) < num(%d).", start, num);
185 
186  if (end >= num)
187  elog(ERROR, "Error end must be in the range of 0 <= end(%d) < num(%d).", end, num);
188 
189  /* if start and end are the same this is the same as setting end = -1 */
190  if (start == end)
191  end = -1;
192 
193  /*
194  fix up matrix id we have an end point
195  basically set D(start,end)=INFINITY and D(end,start)=0.0
196  */
197  if (end >= 0) {
198  PGR_DBG("Updating start end costs");
199  D(start, end) = 0.0;
200  D(end, start) = 0.0;
201  }
202 
203  PGR_DBG("Alloc ids");
204 
205  ids = (int *) malloc((size_t)(num) * sizeof(int));
206  if (!ids) {
207  elog(ERROR, "Error: Out of memory (solve_tsp)");
208  }
209 
210  for (i = 0; i < num; i++) {
211  ids[i] = i;
212  }
213 
214  PGR_DBG("Calling find_tsp_solution");
215 
216 // int find_tsp_solution(int num, DTYPE *dist, int *p_ids, int source, DTYPE *fit, char* err_msg);
217  ret = find_tsp_solution(num, matrix, ids, start, end, &fit, err_msg);
218  if (ret < 0) {
219  elog(ERROR, "Error solving TSP, %s", err_msg);
220  }
221 
222  PGR_DBG("TSP solved, Score: %f", fit);
223 
224  *results = ids;
225  return ret;
226 }
227 
228 /*
229  * select seq, id from pgr_tsp(matrix float8[][], start int,
230  * OUT seq int, OUT id int);
231 */
232 
234 PGDLLEXPORT Datum
235 tsp_matrix(PG_FUNCTION_ARGS) {
236  FuncCallContext *funcctx;
237  uint32_t call_cntr;
238  uint32_t max_calls;
239  TupleDesc tuple_desc;
240  // AttInMetadata *attinmeta;
241 
242  DTYPE *matrix;
243  int *tsp_res;
244  int num;
245 
246  /* stuff done only on the first call of the function */
247  if (SRF_IS_FIRSTCALL()) {
248  MemoryContext oldcontext;
249  // int path_count;
250  int ret = -1;
251 
252  /* create a function context for cross-call persistence */
253  funcctx = SRF_FIRSTCALL_INIT();
254 
255  /* switch to memory context appropriate for multiple function calls */
256  oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
257 
258  matrix = get_pgarray(&num, PG_GETARG_ARRAYTYPE_P(0));
259 
260  ret = solve_tsp(matrix, num,
261  PG_GETARG_INT32(1), // start index
262  PG_GETARG_INT32(2), // end index
263  &tsp_res);
264 
265  pfree(matrix);
266  if (ret < 0) {
267  elog(ERROR, "Error, failed to solve TSP.");
268  }
269 
270  funcctx->max_calls = (uint32_t)num;
271  funcctx->user_fctx = tsp_res;
272 
273  /* Build a tuple descriptor for our result type */
274  if (get_call_result_type(fcinfo, NULL, &tuple_desc) != TYPEFUNC_COMPOSITE)
275  ereport(ERROR,
276  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
277  errmsg("function returning record called in context "
278  "that cannot accept type record")));
279 
280  funcctx->tuple_desc = BlessTupleDesc(tuple_desc);
281 
282  /*
283  * generate attribute metadata needed later to produce tuples from raw
284  * C strings
285  */
286  // attinmeta = TupleDescGetAttInMetadata(tuple_desc);
287  // funcctx->attinmeta = attinmeta;
288 
289  MemoryContextSwitchTo(oldcontext);
290  }
291 
292  /* stuff done on every call of the function */
293  funcctx = SRF_PERCALL_SETUP();
294 
295  call_cntr = funcctx->call_cntr;
296  max_calls = funcctx->max_calls;
297  tuple_desc = funcctx->tuple_desc;
298  tsp_res = funcctx->user_fctx;
299 
300  PGR_DBG("Trying to allocate some memory");
301  PGR_DBG("call_cntr = %i, max_calls = %i", call_cntr, max_calls);
302 
303  if (call_cntr < max_calls) { /* do when there is more left to send */
304  HeapTuple tuple;
305  Datum result;
306  Datum *values;
307  bool* nulls;
308 
309  values = palloc(2 * sizeof(Datum));
310  nulls = palloc(2 * sizeof(bool));
311 
312  values[0] = Int32GetDatum(call_cntr);
313  nulls[0] = false;
314  values[1] = Int32GetDatum(tsp_res[call_cntr]);
315  nulls[1] = false;
316 
317  PGR_DBG("RESULT: %d, %d", call_cntr, tsp_res[call_cntr]);
318 
319  PGR_DBG("Heap making");
320 
321  tuple = heap_form_tuple(tuple_desc, values, nulls);
322 
323  PGR_DBG("Datum making");
324 
325  /* make the tuple into a datum */
326  result = HeapTupleGetDatum(tuple);
327 
328  PGR_DBG("RESULT: seq:%d, id:%d", call_cntr, tsp_res[call_cntr]);
329  PGR_DBG("Trying to free some memory");
330 
331  /* clean up (this is not really necessary) */
332  pfree(values);
333  pfree(nulls);
334 
335 
336  SRF_RETURN_NEXT(funcctx, result);
337  } else { /* do when there is no more left */
338  PGR_DBG("Freeing tsp_res");
339  free(tsp_res);
340 
341  PGR_DBG("Ending function");
342  SRF_RETURN_DONE(funcctx);
343  }
344 }
345 
PG_FUNCTION_INFO_V1(tsp_matrix)
#define D(i, j)
Definition: tsp2.c:169
static double * get_pgarray(int *num, ArrayType *input)
Definition: tsp2.c:71
int find_tsp_solution(int num, double *dist, int *p_ids, int source, int end, double *fit, char *err_msg)
Definition: tsplib.c:467
#define PGR_DBG(...)
Definition: debug_macro.h:33
static int solve_tsp(double *matrix, int num, int start, int end, int **results)
Definition: tsp2.c:171
#define DTYPE
Definition: tsp.h:33
char * err_msg
Definition: BDATester.cpp:50
PGDLLEXPORT Datum tsp_matrix(PG_FUNCTION_ARGS)
Definition: tsp2.c:235