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