pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
tsp2.c
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 #include "tsp.h"
35 #include <math.h>
36 
37 #include "postgres.h"
38 #include "funcapi.h"
39 #include "catalog/pg_type.h"
40 #include "utils/array.h"
41 #include "utils/lsyscache.h"
42 #if PGSQL_VERSION > 92
43 #include "access/htup_details.h"
44 #endif
45 
46 #include "fmgr.h"
47 
48 #ifndef PG_MODULE_MAGIC
49 PG_MODULE_MAGIC;
50 #endif
51 
52 #undef DEBUG
53 //#define DEBUG 1
54 #include "../../common/src/debug_macro.h"
55 
56 #ifndef INFINITY
57 #define INFINITY (1.0/0.0)
58 #endif
59 
60 // The number of tuples to fetch from the SPI cursor at each iteration
61 #define TUPLIMIT 1000
62 
63 PG_FUNCTION_INFO_V1(tsp_matrix);
64 Datum
65 tsp_matrix(PG_FUNCTION_ARGS);
66 
67 static DTYPE *get_pgarray(int *num, ArrayType *input)
68 {
69  int ndims, *dims; // , *lbs;
70  bool *nulls;
71  Oid i_eltype;
72  int16 i_typlen;
73  bool i_typbyval;
74  char i_typalign;
75  Datum *i_data;
76  int i, n;
77  DTYPE *data;
78 
79  /* get input array element type */
80  i_eltype = ARR_ELEMTYPE(input);
81  get_typlenbyvalalign(i_eltype, &i_typlen, &i_typbyval, &i_typalign);
82 
83 
84  /* validate input data type */
85  switch(i_eltype){
86  case INT2OID:
87  case INT4OID:
88  case FLOAT4OID:
89  case FLOAT8OID:
90  break;
91  default:
92  elog(ERROR, "Invalid input data type");
93  break;
94  }
95 
96  /* get various pieces of data from the input array */
97  ndims = ARR_NDIM(input);
98  dims = ARR_DIMS(input);
99  // lbs = ARR_LBOUND(input);
100 
101  if (ndims != 2 || dims[0] != dims[1]) {
102  elog(ERROR, "Error: matrix[num][num] in its definition.");
103  }
104 
105  /* get src data */
106  deconstruct_array(input, i_eltype, i_typlen, i_typbyval, i_typalign,
107 &i_data, &nulls, &n);
108 
109  PGR_DBG("get_pgarray: ndims=%d, n=%d", ndims, n);
110 
111 #ifdef DEBUG
112  for (i=0; i<ndims; i++) {
113  PGR_DBG(" dims[%d]=%d, lbs[%d]=%d", i, dims[i], i, lbs[i]);
114  }
115 #endif
116 
117  /* construct a C array */
118  data = (DTYPE *) palloc((size_t)(n) * sizeof(DTYPE));
119  if (!data) {
120  elog(ERROR, "Error: Out of memory!");
121  }
122 
123  for (i=0; i<n; i++) {
124  if (nulls[i]) {
125  data[i] = INFINITY;
126  }
127  else {
128  switch(i_eltype){
129  case INT2OID:
130  data[i] = (DTYPE) DatumGetInt16(i_data[i]);
131  break;
132  case INT4OID:
133  data[i] = (DTYPE) DatumGetInt32(i_data[i]);
134  break;
135  case FLOAT4OID:
136  data[i] = (DTYPE) DatumGetFloat4(i_data[i]);
137  break;
138  case FLOAT8OID:
139  data[i] = (DTYPE) DatumGetFloat8(i_data[i]);
140  break;
141  }
142  /* we assume negative values are INFINTY */
143  /********************************************************
144  TODO: based on trying to add an endpt it is likely
145  that this will not work and you will get and error in
146  findEulerianPath
147  **********************************************************/
148  if (data[i] < 0)
149  data[i] = INFINITY;
150  }
151  PGR_DBG(" data[%d]=%.4f", i, data[i]);
152  }
153 
154  pfree(nulls);
155  pfree(i_data);
156 
157  *num = dims[0];
158 
159  return data;
160 }
161 
162 
163 // macro to store distance values as matrix[num][num]
164 #define D(i,j) matrix[(i)*num + j]
165 
166 static int solve_tsp(DTYPE *matrix, int num, int start, int end, int **results)
167 {
168  int ret;
169  int i;
170  int *ids;
171  DTYPE fit;
172  char *err_msg = NULL;
173 
174  PGR_DBG("In solve_tsp: num: %d, start: %d, end: %d", num, start, end);
175 
176  if (num < 4)
177  elog(ERROR, "Error TSP requires four or more locations to optimize. Only %d were supplied.", num);
178 
179  if (start < 0 || start >= num)
180  elog(ERROR, "Error start must be in the range of 0 <= start(%d) < num(%d).", start, num);
181 
182  if (end >= num)
183  elog(ERROR, "Error end must be in the range of 0 <= end(%d) < num(%d).", end, num);
184 
185  /* if start and end are the same this is the same as setting end = -1 */
186  if (start == end)
187  end = -1;
188 
189  /*
190  fix up matrix id we have an end point
191  basically set D(start,end)=INFINITY and D(end,start)=0.0
192  */
193  if (end >= 0) {
194  PGR_DBG("Updating start end costs");
195  D(start,end)=0.0;
196  D(end,start)=0.0;
197  }
198 
199  PGR_DBG("Alloc ids");
200 
201  ids = (int *) malloc((size_t)(num) * sizeof(int));
202  if (!ids) {
203  elog(ERROR, "Error: Out of memory (solve_tsp)");
204  }
205 
206  for(i=0; i<num; i++) {
207  ids[i] = i;
208  }
209 
210  PGR_DBG("Calling find_tsp_solution");
211 
212 // int find_tsp_solution(int num, DTYPE *dist, int *p_ids, int source, DTYPE *fit, char* err_msg);
213  ret = find_tsp_solution(num, matrix, ids, start, end, &fit, err_msg);
214  if (ret < 0) {
215  elog(ERROR, "Error solving TSP, %s", err_msg);
216  }
217 
218  PGR_DBG("TSP solved, Score: %f", fit);
219 
220  *results = ids;
221  return ret;
222 }
223 
224 /*
225  * select seq, id from pgr_tsp(matrix float8[][], start int,
226  * OUT seq int, OUT id int);
227 */
228 
229 Datum
230 tsp_matrix(PG_FUNCTION_ARGS)
231 {
232  FuncCallContext *funcctx;
233  uint32_t call_cntr;
234  uint32_t max_calls;
235  TupleDesc tuple_desc;
236  // AttInMetadata *attinmeta;
237 
238  DTYPE *matrix;
239  int *tsp_res;
240  int num;
241 
242  /* stuff done only on the first call of the function */
243  if (SRF_IS_FIRSTCALL()) {
244  MemoryContext oldcontext;
245  //int path_count;
246  int ret=-1;
247 
248  /* create a function context for cross-call persistence */
249  funcctx = SRF_FIRSTCALL_INIT();
250 
251  /* switch to memory context appropriate for multiple function calls */
252  oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);
253 
254  matrix = get_pgarray(&num, PG_GETARG_ARRAYTYPE_P(0));
255 
256  ret = solve_tsp(matrix, num,
257  PG_GETARG_INT32(1), // start index
258  PG_GETARG_INT32(2), // end index
259  &tsp_res);
260 
261  pfree(matrix);
262  if (ret < 0) {
263  elog(ERROR, "Error, failed to solve TSP.");
264  }
265 
266  funcctx->max_calls = (uint32_t)num;
267  funcctx->user_fctx = tsp_res;
268 
269  /* Build a tuple descriptor for our result type */
270  if (get_call_result_type(fcinfo, NULL, &tuple_desc) != TYPEFUNC_COMPOSITE)
271  ereport(ERROR,
272  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
273  errmsg("function returning record called in context "
274  "that cannot accept type record")));
275 
276  funcctx->tuple_desc = BlessTupleDesc(tuple_desc);
277 
278  /*
279  * generate attribute metadata needed later to produce tuples from raw
280  * C strings
281  */
282  //attinmeta = TupleDescGetAttInMetadata(tuple_desc);
283  //funcctx->attinmeta = attinmeta;
284 
285  MemoryContextSwitchTo(oldcontext);
286  }
287 
288  /* stuff done on every call of the function */
289  funcctx = SRF_PERCALL_SETUP();
290 
291  call_cntr = funcctx->call_cntr;
292  max_calls = funcctx->max_calls;
293  tuple_desc = funcctx->tuple_desc;
294  tsp_res = funcctx->user_fctx;
295 
296  PGR_DBG("Trying to allocate some memory");
297  PGR_DBG("call_cntr = %i, max_calls = %i", call_cntr, max_calls);
298 
299  if (call_cntr < max_calls) { /* do when there is more left to send */
300  HeapTuple tuple;
301  Datum result;
302  Datum *values;
303  char* nulls;
304 
305  values = palloc(2 * sizeof(Datum));
306  nulls = palloc(2 * sizeof(char));
307 
308  values[0] = Int32GetDatum(call_cntr);
309  nulls[0] = ' ';
310  values[1] = Int32GetDatum(tsp_res[call_cntr]);
311  nulls[1] = ' ';
312 
313  PGR_DBG("RESULT: %d, %d", call_cntr, tsp_res[call_cntr]);
314 
315  PGR_DBG("Heap making");
316 
317  tuple = heap_formtuple(tuple_desc, values, nulls);
318 
319  PGR_DBG("Datum making");
320 
321  /* make the tuple into a datum */
322  result = HeapTupleGetDatum(tuple);
323 
324  PGR_DBG("RESULT: seq:%d, id:%d", call_cntr, tsp_res[call_cntr]);
325  PGR_DBG("Trying to free some memory");
326 
327  /* clean up (this is not really necessary) */
328  pfree(values);
329  pfree(nulls);
330 
331 
332  SRF_RETURN_NEXT(funcctx, result);
333  }
334  else { /* do when there is no more left */
335  PGR_DBG("Freeing tsp_res");
336  free(tsp_res);
337 
338  PGR_DBG("Ending function");
339  SRF_RETURN_DONE(funcctx);
340  }
341 }
342