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
eucledianTSP_driver.cpp
Go to the documentation of this file.
1 /* PGR-GNU*****************************************************************
2  * File: eucledianTSP_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 #if defined(__MINGW32__) || defined(_MSC_VER)
31 #include <winsock2.h>
32 #include <windows.h>
33 #endif
34 
35 
36 #include <string.h>
37 #include <sstream>
38 #include <vector>
39 #include <algorithm>
40 
41 #include "./eucledianTSP_driver.h"
42 #include "./eucledianDmatrix.h"
43 
44 #include "./pgr_tsp.hpp"
45 #include "./../../common/src/pgr_assert.h"
46 #include "./../../common/src/pgr_alloc.hpp"
47 
48 void
50  Coordinate_t *coordinates_data,
51  size_t total_coordinates,
52  int64_t start_vid,
53  int64_t end_vid,
54 
55  double initial_temperature,
56  double final_temperature,
57  double cooling_factor,
58  int64_t tries_per_temperature,
59  int64_t max_changes_per_temperature,
60  int64_t max_consecutive_non_changes,
61  bool randomize,
62  double time_limit,
63 
64  General_path_element_t **return_tuples,
65  size_t *return_count,
66  char **log_msg,
67  char **err_msg) {
68  std::ostringstream err;
69  std::ostringstream log;
70 
71  try {
72  std::vector< Coordinate_t > coordinates(
73  coordinates_data,
74  coordinates_data + total_coordinates);
75 
76  pgrouting::tsp::eucledianDmatrix costs(coordinates);
77 
78  double real_cost = -1;
79 
80  size_t idx_start = costs.has_id(start_vid) ?
81  costs.get_index(start_vid) : 0;
82 
83  size_t idx_end = costs.has_id(end_vid) ?
84  costs.get_index(end_vid) : 0;
85 
86  if (costs.has_id(start_vid) && costs.has_id(end_vid) && start_vid != end_vid) {
87  /* An ending vertex needs to be by the starting vertex */
88  real_cost = costs.distance(idx_start, idx_end);
89  costs.set(idx_start, idx_end, 0);
90  }
91 
92 
93  log << "pgr_eucledianTSP Processing Information \nInitializing tsp class --->";
95 
96 
97  log << " tsp.greedyInitial --->";
98  tsp.greedyInitial(idx_start);
99 
100 
101 
102  log << " tsp.annealing --->";
103  tsp.annealing(
104  initial_temperature,
105  final_temperature,
106  cooling_factor,
107  tries_per_temperature,
108  max_changes_per_temperature,
109  max_consecutive_non_changes,
110  randomize,
111  time_limit);
112  log << " OK\n";
113  log << tsp.get_log();
114  log << tsp.get_stats();
115 
116  auto bestTour(tsp.get_tour());
117 
118  if (costs.has_id(start_vid) && costs.has_id(end_vid) && start_vid != end_vid) {
119  costs.set(idx_start, idx_end, real_cost);
120  }
121 
122  log << "\nBest cost reached = " << costs.tourCost(bestTour);
123 
124  auto start_ptr = std::find(
125  bestTour.cities.begin(),
126  bestTour.cities.end(),
127  idx_start);
128 
129  std::rotate(
130  bestTour.cities.begin(),
131  start_ptr,
132  bestTour.cities.end());
133 
134  if (costs.has_id(start_vid) && costs.has_id(end_vid) && start_vid != end_vid) {
135  if (*(bestTour.cities.begin() + 1) == idx_end) {
136  std::reverse(
137  bestTour.cities.begin() + 1,
138  bestTour.cities.end());
139  }
140  }
141 
142 
143  std::vector< General_path_element_t > result;
144  result.reserve(bestTour.cities.size() + 1);
145  pgassert(bestTour.cities.size() == costs.size());
146 
147  bestTour.cities.push_back(bestTour.cities.front());
148 
149  auto prev_id = bestTour.cities.front();
150  double agg_cost = 0;
151  for (const auto &id : bestTour.cities) {
152  if (id == prev_id) continue;
154  data.node = costs.get_id(prev_id);
155  data.edge = prev_id;
156  data.cost = costs.distance(prev_id, id);
157  data.agg_cost = agg_cost;
158  result.push_back(data);
159  agg_cost += data.cost;
160  prev_id = id;
161  }
162 
163  /* inserting the returning to starting point */
164  {
166  data.node = costs.get_id(bestTour.cities.front());
167  data.edge = bestTour.cities.front();
168  data.cost = costs.distance(prev_id, bestTour.cities.front());
169  agg_cost += data.cost;
170  data.agg_cost = agg_cost;
171  result.push_back(data);
172  }
173 
174  pgassert(result.size() == bestTour.cities.size());
175  *return_count = bestTour.size();
176  (*return_tuples) = pgr_alloc(result.size(), (*return_tuples));
177 
178  /* store the results */
179  int seq = 0;
180  for (const auto &row : result) {
181  (*return_tuples)[seq] = row;
182  ++seq;
183  }
184 
185  *log_msg = strdup(log.str().c_str());
186  (*err_msg) = NULL;
187  return;
188  } catch (AssertFailedException &except) {
189  if (*return_tuples) free(*return_tuples);
190  (*return_count) = 0;
191  err << except.what() << "\n";
192  *err_msg = strdup(err.str().c_str());
193  *log_msg = strdup(log.str().c_str());
194  } catch (std::exception& except) {
195  if (*return_tuples) free(*return_tuples);
196  (*return_count) = 0;
197  err << except.what() << "\n";
198  *err_msg = strdup(err.str().c_str());
199  *log_msg = strdup(log.str().c_str());
200  } catch(...) {
201  if (*return_tuples) free(*return_tuples);
202  (*return_count) = 0;
203  err << "Caught unknown exception!\n";
204  *err_msg = strdup(err.str().c_str());
205  *log_msg = strdup(log.str().c_str());
206  }
207 }
int64_t get_id(size_t idx) const
idx -> original id
double tourCost(const Tour &tour) const
tour evaluation
Extends std::exception and is the exception that we throw if an assert fails.
Definition: pgr_assert.h:126
size_t get_index(int64_t id) const
original id -> idx
void greedyInitial(size_t idx_start=0)
Definition: pgr_tsp.cpp:149
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
void annealing(double initial_temperature, double final_temperature, double cooling_factor, int64_t tries_per_temperature, int64_t max_changes_per_temperature, int64_t max_consecutive_non_changes, bool randomize, double time_limit)
Definition: pgr_tsp.cpp:433
void set(size_t i, size_t j, double dist)
sets a special value for the distance(i,j)
void do_pgr_eucledianTSP(Coordinate_t *coordinates_data, size_t total_coordinates, int64_t start_vid, int64_t end_vid, double initial_temperature, double final_temperature, double cooling_factor, int64_t tries_per_temperature, int64_t max_changes_per_temperature, int64_t max_consecutive_non_changes, bool randomize, double time_limit, General_path_element_t **return_tuples, size_t *return_count, char **log_msg, char **err_msg)
std::string get_stats() const
Definition: pgr_tsp.hpp:76
T * pgr_alloc(std::size_t size, T *ptr)
allocates memory
Definition: pgr_alloc.hpp:52
virtual const char * what() const
Definition: pgr_assert.cpp:62
Tour get_tour() const
Definition: pgr_tsp.hpp:74
char * err_msg
Definition: BDATester.cpp:50
std::string get_log() const
Definition: pgr_tsp.hpp:85
static void reverse(int num, int *ids)
Definition: tsplib.c:457
bool has_id(int64_t id) const
original id -> true
double distance(size_t i, size_t j) const