PGROUTING  2.4
 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 "./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 "./tour.h"
36 #include "../../common/src/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 
84 size_t
85 Dmatrix::get_index(int64_t id) const {
86  auto pos = std::lower_bound(ids.begin(), ids.end(), id);
87  return pos - ids.begin();
88 }
89 
90 int64_t
91 Dmatrix::get_id(size_t id) const {
92  return ids[id];
93 }
94 
95 /*
96  * Transforms the input data to a matrix
97  */
98 Dmatrix::Dmatrix(const std::vector < Matrix_cell_t > &data_costs) {
99  set_ids(data_costs);
100  costs.resize(
101  ids.size(),
102  std::vector<double>(
103  ids.size(),
104  (std::numeric_limits<double>::max)()));
105 
106  for (const auto &data : data_costs) {
107  costs[get_index(data.from_vid)][get_index(data.to_vid)] = data.cost;
108  }
109 
110  for (size_t i = 0; i < costs.size(); ++i) {
111  costs[i][i] = 0;
112  }
113 }
114 
115 bool
117  for (const auto &row : costs) {
118  for (const auto &val : row) {
119  if (val == (std::numeric_limits<double>::infinity)()) return false;
120  if (val == (std::numeric_limits<double>::max)()) return false;
121  }
122  }
123  return true;
124 }
125 
126 
127 bool
129  /*
130  * Triangle Inequality Theorem.
131  * The sum of the lengths of any two sides of a triangle is greater than the length of the third side.
132  * NOTE: can also be equal for streets
133  * costs[i][k] != inf
134  * costs[i][k] <= costs[i][j] + costs[j][k]
135  */
136  for (size_t i = 0; i < costs.size(); ++i) {
137  for (size_t j = 0; j < costs.size(); ++j) {
138  for (size_t k = 0; k < costs.size(); ++k) {
139  if (!(costs[i][k] <= (costs[i][j] + costs[j][k]))) return false;
140  }
141  }
142  }
143  return true;
144 }
145 
146 bool
148  for (size_t i = 0; i < costs.size(); ++i) {
149  for (size_t j = 0; j < costs.size(); ++j) {
150  if (0.000001 < std::fabs(costs[i][j] - costs[j][i])) {
151  std::ostringstream log;
152  log << "i \t" << i
153  << "j \t" << j
154  << "costs[i][j] \t" << costs[i][j]
155  << "costs[j][i] \t" << costs[j][i]
156  << "\n";
157  log << (*this);
158  pgassertwm(false, log.str());
159  return false;
160  }
161  }
162  }
163  return true;
164 }
165 
166 
167 std::ostream& operator<<(std::ostream &log, const Dmatrix &matrix) {
168  for (const auto id : matrix.ids) {
169  log << "\t" << id;
170  }
171  log << "\n";
172  size_t i = 0;
173  for (const auto row : matrix.costs) {
174  size_t j = 0;
175  for (const auto cost : row) {
176  log << "(" << i << "," << j << ")"
177  << "\t(" << matrix.ids[i] << "," << matrix.ids[j] << ")"
178  << "\t(" << matrix.get_index(matrix.ids[i])
179  << "," << matrix.get_index(matrix.ids[j]) << ")"
180  << "\t = " << cost
181  << "\t = " << matrix.costs[i][j]
182  << "\t = " << matrix.costs[j][i]
183  << "=inf:" << (matrix.costs[i][j] == (std::numeric_limits<double>::infinity)())
184  << "=inf:" << (matrix.costs[j][i] == (std::numeric_limits<double>::infinity)())
185  << "\n";
186  ++j;
187  }
188  ++i;
189  }
190  for (size_t i = 0; i < matrix.costs.size(); ++i) {
191  for (size_t j = 0; j < matrix.costs.size(); ++j) {
192  for (size_t k = 0; k < matrix.costs.size(); ++k) {
193  log << matrix.costs[i][k] << " <= ("
194  << matrix.costs[i][j] << " + " << matrix.costs[j][k] << ")"
195  << (matrix.costs[i][k]
196  <= (matrix.costs[i][j] + matrix.costs[j][k]))
197  << "\n";
198  }
199  }
200  }
201 
202  return log;
203 }
204 
205 
206 } // namespace tsp
207 } // namespace pgrouting
bool is_symmetric() const
Definition: Dmatrix.cpp:147
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:104
bool obeys_triangle_inequality() const
Definition: Dmatrix.cpp:128
void set_ids(const std::vector< matrix_cell > &data_costs)
Definition: Dmatrix.cpp:63
std::vector< int64_t > ids
Definition: Dmatrix.h:113
std::ostream & operator<<(std::ostream &log, const Dmatrix &matrix)
Definition: Dmatrix.cpp:167
int64_t get_id(size_t idx) const
idx -> original id
Definition: Dmatrix.cpp:91
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
bool has_no_infinity() const
Definition: Dmatrix.cpp:116
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:85
double distance(size_t i, size_t j) const
Definition: Dmatrix.h:104