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
Dmatrix.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 FILE: Dmatrix.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 #if defined(__MINGW32__) || defined(_MSC_VER)
26 #include <winsock2.h>
27 #include <windows.h>
28 #undef min
29 #undef max
30 #endif
31 
32 #include "./Dmatrix.h"
33 
34 #include <string.h>
35 #include <sstream>
36 #include <algorithm>
37 #include <limits>
38 #include <vector>
39 #include <cmath>
40 
41 #include "../../common/src/pgr_assert.h"
42 
43 #include "./tour.h"
44 
45 namespace pgrouting {
46 namespace tsp {
47 
48 double
49 Dmatrix::tourCost(const Tour &tour) const {
50  double total_cost(0);
51  if (tour.cities.empty()) return total_cost;
52 
53  auto prev_id = tour.cities.front();
54  for (const auto &id : tour.cities) {
55  if (id == tour.cities.front()) continue;
56 
57  pgassert(distance(prev_id, id) != std::numeric_limits<double>::max());
58 
59  total_cost += costs[prev_id][id];
60  prev_id = id;
61  }
62  total_cost += costs[prev_id][tour.cities.front()];
63  return total_cost;
64 }
65 
66 
67 
68 void
69 Dmatrix::set_ids(const std::vector < Matrix_cell_t > &data_costs) {
70  ids.reserve(data_costs.size() * 2);
71  for (const auto &cost : data_costs) {
72  ids.push_back(cost.from_vid);
73  ids.push_back(cost.to_vid);
74  }
75  std::sort(ids.begin(), ids.end());
76  ids.erase(std::unique(ids.begin(), ids.end()), ids.end());
77  /*
78  * freeing up unused space
79  */
80  ids.shrink_to_fit();
81 }
82 
83 bool
84 Dmatrix::has_id(int64_t id) const {
85  auto pos = std::lower_bound(ids.begin(), ids.end(), id);
86  return *pos == id;
87 }
88 
89 
90 size_t
91 Dmatrix::get_index(int64_t id) const {
92  auto pos = std::lower_bound(ids.begin(), ids.end(), id);
93  return pos - ids.begin();
94 }
95 
96 int64_t
97 Dmatrix::get_id(size_t id) const {
98  return ids[id];
99 }
100 
101 /*
102  * Transforms the input data to a matrix
103  */
104 Dmatrix::Dmatrix(const std::vector < Matrix_cell_t > &data_costs) {
105  set_ids(data_costs);
106  costs.resize(ids.size());
107  for (auto &row : costs) {
108  row.resize(ids.size());
109  for (auto &cell : row) {
110  cell = std::numeric_limits<double>::max();
111  }
112  }
113  for (const auto &data : data_costs) {
114  costs[get_index(data.from_vid)][get_index(data.to_vid)] = data.cost;
115  }
116 
117  for (size_t i = 0; i < costs.size(); ++i) {
118  costs[i][i] = 0;
119  }
120 }
121 
122 bool
124  for (const auto &row : costs) {
125  for (const auto &val : row) {
126  if (val == std::numeric_limits<double>::max()) return false;
127  }
128  }
129  return true;
130 }
131 
132 
133 bool
135  /*
136  * Triangle Inequality Theorem.
137  * The sum of the lengths of any two sides of a triangle is greater than the length of the third side.
138  * NOTE: can also be equal for streets
139  * costs[i][k] != inf
140  * costs[i][k] <= costs[i][j] + costs[j][k]
141  */
142  for (size_t i = 0; i < costs.size(); ++i) {
143  for (size_t j = 0; j < costs.size(); ++j) {
144  for (size_t k = 0; k < costs.size(); ++k) {
145  if (!(costs[i][k] <= (costs[i][j] + costs[j][k]))) return false;
146  }
147  }
148  }
149  return true;
150 }
151 
152 bool
154  for (size_t i = 0; i < costs.size(); ++i) {
155  for (size_t j = 0; j < costs.size(); ++j) {
156  if (0.000001 < std::fabs(costs[i][j] - costs[j][i])) {
157  std::ostringstream log;
158  log << "i \t" << i
159  << "j \t" << j
160  << "costs[i][j] \t" << costs[i][j]
161  << "costs[j][i] \t" << costs[j][i]
162  << "\n";
163  log << (*this);
164  pgassertwm(false, log.str());
165  return false;
166  }
167  }
168  }
169  return true;
170 }
171 
172 
173 std::ostream& operator<<(std::ostream &log, const Dmatrix &matrix) {
174  for (const auto id : matrix.ids) {
175  log << "\t" << id;
176  }
177  log << "\n";
178  size_t i = 0;
179  for (const auto row : matrix.costs) {
180  size_t j = 0;
181  for (const auto cost : row) {
182  log << "(" << i << "," << j << ")"
183  << "\t(" << matrix.ids[i] << "," << matrix.ids[j] << ")"
184  << "\t(" << matrix.get_index(matrix.ids[i])
185  << "," << matrix.get_index(matrix.ids[j]) << ")"
186  << "\t = " << cost
187  << "\t = " << matrix.costs[i][j]
188  << "\t = " << matrix.costs[j][i] << "\n";
189  ++j;
190  }
191  ++i;
192  }
193  for (size_t i = 0; i < matrix.costs.size(); ++i) {
194  for (size_t j = 0; j < matrix.costs.size(); ++j) {
195  for (size_t k = 0; k < matrix.costs.size(); ++k) {
196  log << matrix.costs[i][k] << " <= ("
197  << matrix.costs[i][j] << " + " << matrix.costs[j][k] << ")"
198  << (matrix.costs[i][k] <= (matrix.costs[i][j] + matrix.costs[j][k]))
199  << "\n";
200  }
201  }
202  }
203 
204  return log;
205 }
206 
207 
208 } // namespace tsp
209 } // namespace pgrouting
bool is_symmetric() const
Definition: Dmatrix.cpp:153
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:104
bool obeys_triangle_inequality() const
Definition: Dmatrix.cpp:134
void set_ids(const std::vector< matrix_cell > &data_costs)
Definition: Dmatrix.cpp:69
std::vector< int64_t > ids
Definition: Dmatrix.h:113
std::ostream & operator<<(std::ostream &log, const Dmatrix &matrix)
Definition: Dmatrix.cpp:173
int64_t get_id(size_t idx) const
idx -> original id
Definition: Dmatrix.cpp:97
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
bool has_no_infinity() const
Definition: Dmatrix.cpp:123
std::vector< size_t > cities
Definition: tour.h:154
double tourCost(const Tour &tour) const
tour evaluation
Definition: Dmatrix.cpp:49
bool has_id(int64_t id) const
original id -> true
Definition: Dmatrix.cpp:84
size_t get_index(int64_t id) const
original id -> idx
Definition: Dmatrix.cpp:91
double distance(size_t i, size_t j) const
Definition: Dmatrix.h:104