PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
eucledianDmatrix.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 FILE: eucledianDmatrix.cpp
4 
5 Copyright (c) 2015 pgRouting developers
6 Mail: project@pgrouting.org
7 
8 ------
9 
10 This program is free software; you can redistribute it and/or modify
11 it under the terms of the GNU General Public License as published by
12 the Free Software Foundation; either version 2 of the License, or
13 (at your option) any later version.
14 
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
19 
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
23 
24  ********************************************************************PGR-GNU*/
25 
26 
27 #include "./eucledianDmatrix.h"
28 
29 #include <algorithm>
30 #include <vector>
31 #include <cmath>
32 
33 #include "./tour.h"
34 #include "../../common/src/pgr_assert.h"
35 
36 
37 namespace pgrouting {
38 namespace tsp {
39 
40 
41 const std::vector<double>
42 eucledianDmatrix::get_row(size_t i) const {
43  std::vector<double> result;
44 
45  for (size_t j = 0; j < ids.size(); ++j) {
46  result.push_back(distance(i, j));
47  }
48 
49  pgassert(result.size() == ids.size());
50  return result;
51 }
52 
53 
54 double
55 eucledianDmatrix::comparable_distance(size_t i, size_t j) const {
56  if (special_distance >= 0 &&
57  ((row == i && column == j)
58  ||(row == j && column == i))) {
60  }
61  auto dx = coordinates[i].x - coordinates[j].x;
62  auto dy = coordinates[i].y - coordinates[j].y;
63  return dx * dx + dy * dy;
64 }
65 
66 double
67 eucledianDmatrix::distance(size_t i, size_t j) const {
68  if (special_distance >= 0 &&
69  ((row == i && column == j)
70  ||(row == j && column == i))) {
71  return special_distance;
72  }
73  if (i == j) return 0;
74  return std::sqrt(comparable_distance(i, j));
75 }
76 
77 double
78 eucledianDmatrix::tourCost(const Tour &tour) const {
79  double total_cost(0);
80  if (tour.cities.empty()) return total_cost;
81 
82  auto prev_id = tour.cities.front();
83  for (const auto &id : tour.cities) {
84  if (id == tour.cities.front()) continue;
85 
86  total_cost += distance(prev_id, id);
87  prev_id = id;
88  }
89  total_cost += distance(prev_id, tour.cities.front());
90  return total_cost;
91 }
92 
93 
94 
95 bool
96 eucledianDmatrix::has_id(int64_t id) const {
97  auto pos = std::lower_bound(ids.begin(), ids.end(), id);
98  return *pos == id;
99 }
100 
101 size_t
102 eucledianDmatrix::get_index(int64_t id) const {
103  auto pos = std::lower_bound(ids.begin(), ids.end(), id);
104  return pos - ids.begin();
105 }
106 
107 int64_t
108 eucledianDmatrix::get_id(size_t id) const {
109  return ids[id];
110 }
111 
112 /*
113  * constructor
114  */
116  const std::vector < Coordinate_t > &data_coordinates)
117  : coordinates(data_coordinates) {
118  set_ids();
119  std::sort(coordinates.begin(), coordinates.end(),
120  [](const Coordinate_t &lhs, const Coordinate_t &rhs)
121  {return lhs.id < rhs.id;});
122  }
123 
124 void
126  ids.reserve(coordinates.size());
127  for (const auto &data : coordinates) {
128  ids.push_back(data.id);
129  }
130  std::sort(ids.begin(), ids.end());
131 #ifndef NDEBUG
132  auto total = ids.size();
133 #endif
134  ids.erase(std::unique(ids.begin(), ids.end()), ids.end());
135  pgassertwm(total == ids.size(), "Duplicated id found");
136 }
137 
138 bool
140  return true;
141 }
142 
143 bool
145  return true;
146 }
147 
148 bool
150  return true;
151 }
152 
153 std::ostream& operator<<(std::ostream &log, const eucledianDmatrix &matrix) {
154  for (const auto id : matrix.ids) {
155  log << "\t" << id;
156  }
157  log << "\n";
158  for (const auto row : matrix.coordinates) {
159  log << row.id << "(" << row.x << "," << row.y << ")\n";
160  }
161  return log;
162 }
163 
164 
165 } // namespace tsp
166 } // namespace pgrouting
int64_t get_id(size_t idx) const
idx -> original id
double comparable_distance(size_t i, size_t j) const
double tourCost(const Tour &tour) const
tour evaluation
const std::vector< double > get_row(size_t idx) const
returns a row of distances
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:104
std::vector< Coordinate_t > coordinates
int64_t id
Definition: pgr_types.h:57
size_t get_index(int64_t id) const
original id -> idx
std::ostream & operator<<(std::ostream &log, const Dmatrix &matrix)
Definition: Dmatrix.cpp:167
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
std::vector< size_t > cities
Definition: tour.h:154
bool has_id(int64_t id) const
original id -> true
double distance(size_t i, size_t j) const