PGROUTING  2.6
newTSP_driver.h File Reference
Include dependency graph for newTSP_driver.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

void do_pgr_tsp (Matrix_cell_t *distances, size_t total_distances, 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 **results, size_t *total_results, char **log_msg, char **notice_msg, char **err_msg)
 

Function Documentation

void do_pgr_tsp ( Matrix_cell_t distances,
size_t  total_distances,
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 **  results,
size_t *  total_results,
char **  log_msg,
char **  notice_msg,
char **  err_msg 
)

Definition at line 44 of file newTSP_driver.cpp.

References General_path_element_t::agg_cost, pgrouting::tsp::TSP< MATRIX >::annealing(), General_path_element_t::cost, pgrouting::tsp::Dmatrix::distance(), General_path_element_t::edge, pgrouting::tsp::Dmatrix::get_id(), pgrouting::tsp::Dmatrix::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::Dmatrix::has_id(), pgrouting::tsp::Dmatrix::has_no_infinity(), pgrouting::tsp::Dmatrix::is_symmetric(), General_path_element_t::node, pgassert, pgr_alloc(), pgr_free(), pgr_msg(), pgrouting::tsp::Dmatrix::set(), pgrouting::tsp::Dmatrix::size(), pgrouting::tsp::Dmatrix::tourCost(), and AssertFailedException::what().

Referenced by process().

63  {
64  std::ostringstream log;
65  std::ostringstream notice;
66  std::ostringstream err;
67 
68  try {
69  std::vector <Matrix_cell_t> data_costs(
70  distances,
71  distances + total_distances);
72 
73  pgrouting::tsp::Dmatrix costs(data_costs);
74 
75  if (!costs.has_no_infinity()) {
76  err << "An Infinity value was found on the Matrix";
77  *err_msg = pgr_msg(err.str().c_str());
78  return;
79  }
80 
81  if (!costs.is_symmetric()) {
82  err << "A Non symmetric Matrix was given as input";
83  *err_msg = pgr_msg(err.str().c_str());
84  return;
85  }
86 
87  double real_cost = -1;
88 
89  size_t idx_start = costs.has_id(start_vid) ?
90  costs.get_index(start_vid) : 0;
91 
92  size_t idx_end = costs.has_id(end_vid) ?
93  costs.get_index(end_vid) : 0;
94 
95  if (costs.has_id(start_vid)
96  && costs.has_id(end_vid)
97  && start_vid != end_vid) {
98  /* An ending vertex needs to be by the starting vertex */
99  real_cost = costs.distance(idx_start, idx_end);
100  costs.set(idx_start, idx_end, 0);
101  }
102 
103 
104  log << "pgr_eucledianTSP Processing Information \n"
105  << "Initializing tsp class --->";
107 
108 
109  log << " tsp.greedyInitial --->";
110  tsp.greedyInitial(idx_start);
111 
112 
113 
114  log << " tsp.annealing --->";
115  tsp.annealing(
116  initial_temperature,
117  final_temperature,
118  cooling_factor,
119  tries_per_temperature,
120  max_changes_per_temperature,
121  max_consecutive_non_changes,
122  randomize,
123  time_limit);
124  log << " OK\n";
125  log << tsp.get_log();
126  log << tsp.get_stats();
127 
128  auto bestTour(tsp.get_tour());
129 
130  if (costs.has_id(start_vid)
131  && costs.has_id(end_vid)
132  && start_vid != end_vid) {
133  costs.set(idx_start, idx_end, real_cost);
134  }
135 
136 
137  log << "\nBest cost reached = " << costs.tourCost(bestTour);
138 
139  auto start_ptr = std::find(
140  bestTour.cities.begin(),
141  bestTour.cities.end(),
142  idx_start);
143 
144 
145  std::rotate(
146  bestTour.cities.begin(),
147  start_ptr,
148  bestTour.cities.end());
149 
150  if (costs.has_id(start_vid)
151  && costs.has_id(end_vid)
152  && start_vid != end_vid) {
153  if (*(bestTour.cities.begin() + 1) == idx_end) {
154  std::reverse(
155  bestTour.cities.begin() + 1,
156  bestTour.cities.end());
157  }
158  }
159 
160 
161  std::vector< General_path_element_t > result;
162  result.reserve(bestTour.cities.size() + 1);
163  pgassert(bestTour.cities.size() == costs.size());
164 
165  bestTour.cities.push_back(bestTour.cities.front());
166 
167  auto prev_id = bestTour.cities.front();
168  double agg_cost = 0;
169  for (const auto &id : bestTour.cities) {
170  if (id == prev_id) continue;
172  data.node = costs.get_id(prev_id);
173  data.edge = prev_id;
174  data.cost = costs.distance(prev_id, id);
175  data.agg_cost = agg_cost;
176  result.push_back(data);
177  agg_cost += data.cost;
178  prev_id = id;
179  }
180 
181  /* inserting the returning to starting point */
182  {
184  data.node = costs.get_id(bestTour.cities.front());
185  data.edge = bestTour.cities.front();
186  data.cost = costs.distance(prev_id, bestTour.cities.front());
187  agg_cost += data.cost;
188  data.agg_cost = agg_cost;
189  result.push_back(data);
190  }
191 
192  pgassert(result.size() == bestTour.cities.size());
193  *return_count = bestTour.size();
194  (*return_tuples) = pgr_alloc(result.size(), (*return_tuples));
195 
196  /* store the results */
197  int seq = 0;
198  for (const auto &row : result) {
199  (*return_tuples)[seq] = row;
200  ++seq;
201  }
202 
203  *log_msg = log.str().empty()?
204  *log_msg :
205  pgr_msg(log.str().c_str());
206  *notice_msg = notice.str().empty()?
207  *notice_msg :
208  pgr_msg(notice.str().c_str());
209  } catch (AssertFailedException &except) {
210  (*return_tuples) = pgr_free(*return_tuples);
211  (*return_count) = 0;
212  err << except.what();
213  *err_msg = pgr_msg(err.str().c_str());
214  *log_msg = pgr_msg(log.str().c_str());
215  } catch (std::exception &except) {
216  (*return_tuples) = pgr_free(*return_tuples);
217  (*return_count) = 0;
218  err << except.what();
219  *err_msg = pgr_msg(err.str().c_str());
220  *log_msg = pgr_msg(log.str().c_str());
221  } catch(...) {
222  (*return_tuples) = pgr_free(*return_tuples);
223  (*return_count) = 0;
224  err << "Caught unknown exception!";
225  *err_msg = pgr_msg(err.str().c_str());
226  *log_msg = pgr_msg(log.str().c_str());
227  }
228 }
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: