pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
tsp_driver.cpp
1 /*// PGR-GNU*****************************************************************
2  * File: tspi_driver.cpp
3  *
4  * Generated with Template by:
5  * Copyright (c) 2015 pgRouting developers
6  * Mail: project@pgrouting.org
7  *
8  * Function's developer:
9  * Copyright (c) 2015 Celia Virginia Vergara Castillo
10  * Mail: vicky_vergara@hotmail.com
11  *
12  * ------
13  *
14  * This program is free software; you can redistribute it and/or modify
15  * it under the terms of the GNU General Public License as published by
16  * the Free Software Foundation; either version 2 of the License, or
17  * (at your option) any later version.
18  *
19  * This program is distributed in the hope that it will be useful,
20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22  * GNU General Public License for more details.
23  *
24  * You should have received a copy of the GNU General Public License
25  * along with this program; if not, write to the Free Software
26  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
27  *
28  * ******************************************************************** PGR-GNU*/
29 
30 #ifdef __MINGW32__
31 #include <winsock2.h>
32 #include <windows.h>
33 #endif
34 
35 
36 #include <vector>
37 #include <algorithm>
38 
39 #include "./tsp_driver.h"
40 
41 #include "./Dmatrix.hpp"
42 #include "./pgr_tsp.hpp"
43 /*
44  * Defs
45  */
46 
47 typedef std::vector< int64_t > Ids;
48 
49 int
50 do_pgr_tsp(
51  Matrix_cell_t *distances,
52  size_t total_distances,
53  int64_t start_vid,
54  int64_t end_vid,
56  size_t *total_results,
57  char **err_msg) {
58 
59  std::vector < Matrix_cell_t > data_costs(distances, distances + total_distances);
60  Dmatrix costs(data_costs);
61 
62  if (!costs.has_no_infinity()) {
63  return 5;
64  }
65  if (!costs.obeys_triangle_inequality()) {
66  return 6;
67  }
68  costs = costs.get_symetric();
69 
70 
71 #if 0
72  int i, j;
73  int istart = 0;
74  int jstart = 0;
75  int iend = -1;
76  int jend = -1;
77  int rev = 0;
78  long seed = -314159L;
79  size_t blength;
80 #endif
81 
82  // PGR_DBG("sizeof(long)=%d", (int)sizeof(long));
83 
84 #if 0
85  // moving forward
86  initRand(seed);
87 #endif
88 
89  /* initialize tsp struct */
90  TSP tsp(costs);
91 #if 0
92  tsp.n = num;
93  tsp.dist = NULL;
94  tsp.iorder = NULL;
95  tsp.jorder = NULL;
96  tsp.border = NULL;
97 
98 
99  if (!(tsp.iorder = (int*) palloc (tsp.n * sizeof(int))) ||
100  !(tsp.jorder = (int*) palloc (tsp.n * sizeof(int))) ||
101  !(tsp.border = (int*) palloc (tsp.n * sizeof(int))) ) {
102  elog(FATAL, "Memory allocation failed!");
103  return -1;
104  }
105 
106  tsp.maxd = 0;
107  for (i=0; i<tsp.n*tsp.n; i++) {
108  tsp.maxd = MAX(tsp.maxd, cost[i]);
109  }
110 
111  /* identity permutation */
112  for (i = 0; i < tsp.n; i++) tsp.iorder[i] = i;
113 
114  tsp.bestlen = pathLength(&tsp);
115  for (i = 0; i < tsp.n; i++) tsp.border[i] = tsp.iorder[i];
116 #endif
117 
118  // PGR_DBG("Initial Path Length: %.4f", tsp.bestlen);
119 
120  /*
121  * Set up first eulerian path iorder to be improved by
122  * simulated annealing.
123  */
124  if (!tsp.findEulerianPath())
125  return 8;
126 
127 #if 0
128  // this is done automatically in tsp.findEulerianPath call
129  blength = pathLength(&tsp);
130  if (blength < tsp.bestlen) {
131  tsp.bestlen = blength;
132  for (i = 0; i < tsp.n; i++) tsp.border[i] = tsp.iorder[i];
133  }
134 #endif
135 
136  // PGR_DBG("Approximated Path Length: %.4f", tsp.bestlen);
137 
138  tsp.annealing();
139 
140  *total_results = tsp.bestlen;
141  // PGR_DBG("Final Path Length: %.4f", tsp.bestlen);
142 
143  tsp.iorder = tsp.border;
144 #if 0
145  for (i=0; i<tsp.n; i++) tsp.iorder[i] = tsp.border[i];
146  // PGR_DBG("Best Path Length: %.4f", *total_len);
147 #endif
148 
149  // reorder ids[] with start as first
150 
151 #ifdef DEBUG
152  for (i=0; i<tsp.n; i++) {
153  // PGR_DBG("i: %d, ids[i]: %d, io[i]: %d, jo[i]: %d, jo[io[i]]: %d",
154  i, ids[i], tsp.iorder[i], tsp.jorder[i], tsp.jorder[tsp.iorder[i]]);
155  }
156 #endif
157 
158  size_t istart = costs.get_index(start_vid);
159  auto start_ptr = std::find(tsp.iorder.begin(), tsp.iorder.end(), istart);
160 
161  /*
162  * 1 2 3 4 5 6 e s 7 8 9
163  * =>
164  * s 7 8 9 1 2 3 4 5 6 e
165  */
166  Ids results(start_ptr, tsp.iorder.end());
167  std::copy(tsp.iorder.begin(), start_ptr, results.end());
168 
169  std::vector< General_path_element_t > result;
170  result.reserve(tsp.iorder.size());
171  auto prev_id = tsp.iorder.front();
172  double agg_cost = 0;
173  for (const auto &id : tsp.iorder) {
175  data.node = costs.get_id(id);
176  data.cost = id == prev_id? 0: costs[prev_id][id];
177  agg_cost += data.cost;
178  data.agg_cost = agg_cost;
179  result.push_back(data);
180  }
181 
182  *path = static_cast<General_path_element_t *>(malloc(sizeof(General_path_element_t) * (result.size())));
183 
184  //store the results
185  int seq = 0;
186  if (end_vid == -1) {};
187  for (const auto &row : result) {
188  (*path)[seq] = row;
189  ++seq;
190  }
191 
192  *total_results = result.size();
193 
194  (*err_msg) = NULL;
195  return 0;
196 
197 #if 0
198 /*
199  * If the end is specified and the end point and it follow start
200  * then we swap start and end and extract the list backwards
201  * and later we reverse the list for the desired order.
202  */
203 if ((jend > 0 && jend == jstart + 1)
204  || (jend == 0 && jstart == tsp.n-1)) {
205  int tmp = jend;
206  jend = jstart;
207  jstart = tmp;
208  rev = 1;
209  // PGR_DBG("reversed start and end: jstart: %d, jend: %d", jstart, jend);
210 }
211 
212 // copy ids to tsp.jorder so we can rewrite ids
213 memcpy(tsp.jorder, ids, tsp.n * sizeof(int));
214 
215 // write reordered ids into ids[]
216 // remember at this point jorder is our list if ids
217 for (i=jstart, j=0; i < tsp.n; i++, j++)
218 ids[j] = tsp.jorder[tsp.iorder[i]];
219 
220 for (i=0; i < jstart; i++, j++)
221 ids[j] =tsp.jorder[tsp.iorder[i]];
222 
223 // if we reversed the order above, now put it correct.
224 if (rev) {
225  int tmp = jend;
226  jend = jstart;
227  jstart = tmp;
228  reverse(tsp.n, ids);
229 }
230 #endif
231 
232 }
233 
234 
Definition: pgr_tsp.hpp:35