PGROUTING  2.6
eucledianTSP_driver.cpp File Reference
#include "drivers/tsp/eucledianTSP_driver.h"
#include <string.h>
#include <sstream>
#include <vector>
#include <algorithm>
#include "tsp/pgr_tsp.hpp"
#include "tsp/eucledianDmatrix.h"
#include "cpp_common/pgr_alloc.hpp"
#include "cpp_common/pgr_assert.h"
Include dependency graph for eucledianTSP_driver.cpp:

Go to the source code of this file.

Functions

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 **notice_msg, char **err_msg)
 

Function Documentation

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 **  notice_msg,
char **  err_msg 
)

Definition at line 45 of file eucledianTSP_driver.cpp.

References General_path_element_t::agg_cost, pgrouting::tsp::TSP< MATRIX >::annealing(), General_path_element_t::cost, pgrouting::tsp::eucledianDmatrix::distance(), General_path_element_t::edge, pgrouting::tsp::eucledianDmatrix::get_id(), pgrouting::tsp::eucledianDmatrix::get_index(), pgrouting::tsp::TSP< MATRIX >::get_log(), pgrouting::tsp::TSP< MATRIX >::get_stats(), pgrouting::tsp::TSP< MATRIX >::get_tour(), pgrouting::tsp::TSP< MATRIX >::greedyInitial(), pgrouting::tsp::eucledianDmatrix::has_id(), General_path_element_t::node, pgassert, pgr_alloc(), pgr_free(), pgr_msg(), pgrouting::tsp::eucledianDmatrix::set(), pgrouting::tsp::eucledianDmatrix::size(), pgrouting::tsp::eucledianDmatrix::tourCost(), and AssertFailedException::what().

Referenced by process().

64  {
65  std::ostringstream log;
66  std::ostringstream notice;
67  std::ostringstream err;
68 
69  try {
70  std::vector< Coordinate_t > coordinates(
71  coordinates_data,
72  coordinates_data + total_coordinates);
73 
74  pgrouting::tsp::eucledianDmatrix costs(coordinates);
75 
76 
77  size_t idx_start = costs.has_id(start_vid) ?
78  costs.get_index(start_vid) : 0;
79 
80  size_t idx_end = costs.has_id(end_vid) ?
81  costs.get_index(end_vid) : 0;
82 
83  /* The ending vertex needs to be by the starting vertex */
84  double real_cost = 0;
85  if (costs.has_id(start_vid)
86  && costs.has_id(end_vid)
87  && start_vid != end_vid) {
88  /*
89  * Saving the real cost (distance) between the start_vid and end_vid
90  */
91  real_cost = costs.distance(idx_start, idx_end);
92  /*
93  * Temporarily setting the cost between the start_vid and end_vid to 0
94  */
95  costs.set(idx_start, idx_end, 0);
96  }
97 
98 
99  log << "pgr_eucledianTSP Processing Information\n"
100  << "Initializing tsp class --->";
102 
103 
104  log << " tsp.greedyInitial --->";
105  tsp.greedyInitial(idx_start);
106 
107 
108 
109  log << " tsp.annealing --->";
110  tsp.annealing(
111  initial_temperature,
112  final_temperature,
113  cooling_factor,
114  tries_per_temperature,
115  max_changes_per_temperature,
116  max_consecutive_non_changes,
117  randomize,
118  time_limit);
119  log << " OK\n";
120  log << tsp.get_log();
121  log << tsp.get_stats();
122 
123 
124  auto bestTour(tsp.get_tour());
125 
126  /* The ending vertex needs to be by the starting vertex */
127  if (costs.has_id(start_vid)
128  && costs.has_id(end_vid)
129  && start_vid != end_vid) {
130  /*
131  * Restoring the real cost (distance) between the start_vid and end_vid
132  */
133  costs.set(idx_start, idx_end, real_cost);
134  }
135 
136  log << "\nBest cost reached = " << costs.tourCost(bestTour);
137 
138  auto start_ptr = std::find(
139  bestTour.cities.begin(),
140  bestTour.cities.end(),
141  idx_start);
142 
143  std::rotate(
144  bestTour.cities.begin(),
145  start_ptr,
146  bestTour.cities.end());
147 
148  if (costs.has_id(start_vid)
149  && costs.has_id(end_vid)
150  && start_vid != end_vid) {
151  if (*(bestTour.cities.begin() + 1) == idx_end) {
152  std::reverse(
153  bestTour.cities.begin() + 1,
154  bestTour.cities.end());
155  }
156  }
157 
158 
159  std::vector< General_path_element_t > result;
160  result.reserve(bestTour.cities.size() + 1);
161  pgassert(bestTour.cities.size() == costs.size());
162 
163  bestTour.cities.push_back(bestTour.cities.front());
164 
165  auto prev_id = bestTour.cities.front();
166  double agg_cost = 0;
167  for (const auto &id : bestTour.cities) {
168  if (id == prev_id) continue;
170  data.node = costs.get_id(prev_id);
171  data.edge = prev_id;
172  data.cost = costs.distance(prev_id, id);
173  data.agg_cost = agg_cost;
174  result.push_back(data);
175  agg_cost += data.cost;
176  prev_id = id;
177  }
178 
179  /* inserting the returning to starting point */
180  {
182  data.node = costs.get_id(bestTour.cities.front());
183  data.edge = bestTour.cities.front();
184  data.cost = costs.distance(prev_id, bestTour.cities.front());
185  agg_cost += data.cost;
186  data.agg_cost = agg_cost;
187  result.push_back(data);
188  }
189 
190  pgassert(result.size() == bestTour.cities.size());
191  *return_count = bestTour.size();
192  (*return_tuples) = pgr_alloc(result.size(), (*return_tuples));
193 
194  /* store the results */
195  int seq = 0;
196  for (const auto &row : result) {
197  (*return_tuples)[seq] = row;
198  ++seq;
199  }
200 
201  pgassert(!log.str().empty());
202  *log_msg = log.str().empty()?
203  *log_msg :
204  pgr_msg(log.str().c_str());
205  *notice_msg = notice.str().empty()?
206  *notice_msg :
207  pgr_msg(notice.str().c_str());
208  } catch (AssertFailedException &except) {
209  (*return_tuples) = pgr_free(*return_tuples);
210  (*return_count) = 0;
211  err << except.what();
212  *err_msg = pgr_msg(err.str().c_str());
213  *log_msg = pgr_msg(log.str().c_str());
214  } catch (std::exception &except) {
215  (*return_tuples) = pgr_free(*return_tuples);
216  (*return_count) = 0;
217  err << except.what();
218  *err_msg = pgr_msg(err.str().c_str());
219  *log_msg = pgr_msg(log.str().c_str());
220  } catch(...) {
221  (*return_tuples) = pgr_free(*return_tuples);
222  (*return_count) = 0;
223  err << "Caught unknown exception!";
224  *err_msg = pgr_msg(err.str().c_str());
225  *log_msg = pgr_msg(log.str().c_str());
226  }
227 }
Extends std::exception and is the exception that we throw if an assert fails.
Definition: pgr_assert.h:126
T * pgr_free(T *ptr)
Definition: pgr_alloc.hpp:77
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
char * pgr_msg(const std::string &msg)
Definition: pgr_alloc.cpp:30
T * pgr_alloc(std::size_t size, T *ptr)
allocates memory
Definition: pgr_alloc.hpp:66
virtual const char * what() const
Definition: pgr_assert.cpp:53

Here is the call graph for this function:

Here is the caller graph for this function: