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
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 #if defined(__MINGW32__) || defined(_MSC_VER)
27 #include <winsock2.h>
28 #include <windows.h>
29 #endif
30 
31 
32 #include <algorithm>
33 #include <vector>
34 #include <cmath>
35 #include "../../common/src/pgr_assert.h"
36 
37 #include "./eucledianDmatrix.h"
38 #include "./tour.h"
39 
40 namespace pgrouting {
41 namespace tsp {
42 
43 
44 const std::vector<double>
45 eucledianDmatrix::get_row(size_t i) const {
46  std::vector<double> result;
47 
48  for (size_t j = 0; j < ids.size(); ++j) {
49  result.push_back(distance(i, j));
50  }
51 
52  pgassert(result.size() == ids.size());
53  return result;
54 }
55 
56 
57 double
58 eucledianDmatrix::comparable_distance(size_t i, size_t j) const {
59  if (special_distance >= 0 &&
60  ((row == i && column == j)
61  ||(row == j && column == i))) {
63  }
64  auto dx = coordinates[i].x - coordinates[j].x;
65  auto dy = coordinates[i].y - coordinates[j].y;
66  return dx * dx + dy * dy;
67 }
68 
69 double
70 eucledianDmatrix::distance(size_t i, size_t j) const {
71  if (special_distance >= 0 &&
72  ((row == i && column == j)
73  ||(row == j && column == i))) {
74  return special_distance;
75  }
76  if (i == j) return 0;
77  return std::sqrt(comparable_distance(i, j));
78 }
79 
80 double
81 eucledianDmatrix::tourCost(const Tour &tour) const {
82  double total_cost(0);
83  if (tour.cities.empty()) return total_cost;
84 
85  auto prev_id = tour.cities.front();
86  for (const auto &id : tour.cities) {
87  if (id == tour.cities.front()) continue;
88 
89  total_cost += distance(prev_id, id);
90  prev_id = id;
91  }
92  total_cost += distance(prev_id, tour.cities.front());
93  return total_cost;
94 }
95 
96 
97 
98 bool
99 eucledianDmatrix::has_id(int64_t id) const {
100  auto pos = std::lower_bound(ids.begin(), ids.end(), id);
101  return *pos == id;
102 }
103 
104 size_t
105 eucledianDmatrix::get_index(int64_t id) const {
106  auto pos = std::lower_bound(ids.begin(), ids.end(), id);
107  return pos - ids.begin();
108 }
109 
110 int64_t
111 eucledianDmatrix::get_id(size_t id) const {
112  return ids[id];
113 }
114 
115 /*
116  * constructor
117  */
119  const std::vector < Coordinate_t > &data_coordinates)
120  : coordinates(data_coordinates) {
121  set_ids();
122  std::sort(coordinates.begin(), coordinates.end(),
123  [](const Coordinate_t &lhs, const Coordinate_t &rhs)
124  {return lhs.id < rhs.id;});
125  }
126 
127 void
129  ids.reserve(coordinates.size());
130  for (const auto &data : coordinates) {
131  ids.push_back(data.id);
132  }
133  std::sort(ids.begin(), ids.end());
134 #ifndef NDEBUG
135  auto total = ids.size();
136 #endif
137  ids.erase(std::unique(ids.begin(), ids.end()), ids.end());
138  pgassertwm(total == ids.size(), "Duplicated id found");
139 }
140 
141 bool
143  return true;
144 }
145 
146 bool
148  return true;
149 }
150 
151 bool
153  return true;
154 }
155 
156 std::ostream& operator<<(std::ostream &log, const eucledianDmatrix &matrix) {
157  for (const auto id : matrix.ids) {
158  log << "\t" << id;
159  }
160  log << "\n";
161  for (const auto row : matrix.coordinates) {
162  log << row.id << "(" << row.x << "," << row.y << ")\n";
163  }
164  return log;
165 }
166 
167 
168 } // namespace tsp
169 } // 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:43
size_t get_index(int64_t id) const
original id -> idx
std::ostream & operator<<(std::ostream &log, const Dmatrix &matrix)
Definition: Dmatrix.cpp:173
#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