pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
Dmatrix.cpp
1 #ifdef __MINGW32__
2 #include <winsock2.h>
3 #include <windows.h>
4 #endif
5 
6 
7 #include <algorithm>
8 #include <vector>
9 #include "./Dmatrix.hpp"
10 
11 
12 
13 double
14 Dmatrix::pathCost(const Ids &path) const {
15  double len = 0;
16  if (path.empty()) return len;
17  auto prev_id = path.front();
18  for (const auto &id : path) {
19  if (id == path.front()) continue;
20  if (costs[prev_id][id] == std::numeric_limits<double>::max())
21  return std::numeric_limits<double>::max();
22  len += costs[prev_id][id];
23  prev_id = id;
24  }
25  len += costs[prev_id][ids.front()];
26  return len;
27 }
28 
29 
30 
31 double
32 Dmatrix::max() const {
33  double maxd(0);
34  for (const auto &row : costs) {
35  auto row_max = std::max_element(row.begin(),row.end());
36  maxd = maxd < *row_max? *row_max : maxd;
37  }
38  return maxd;
39 }
40 
41 void
42 Dmatrix::set_ids(const std::vector < Matrix_cell_t > &data_costs) {
43  ids.reserve(data_costs.size() * 2);
44  for (const auto &cost : data_costs) {
45  ids.push_back(cost.from_vid);
46  ids.push_back(cost.to_vid);
47  }
48  std::sort(ids.begin(), ids.end());
49  auto last = std::unique(ids.begin(), ids.end());
50  ids.erase(last, ids.end());
51  /*
52  * freeing up unused space
53  */
54  ids.shrink_to_fit();
55 }
56 
57 size_t
58 Dmatrix::get_index(int64_t id) const {
59  auto pos = std::lower_bound(ids.begin(), ids.end(), id);
60  return pos - ids.begin();
61 }
62 
63 int64_t
64 Dmatrix::get_id(size_t id) const{
65  return ids[id];
66 }
67 
68 /*
69  * Transforms the input data to a matrix
70  */
71 Dmatrix::Dmatrix(const std::vector < Matrix_cell_t > &data_costs) {
72  set_ids(data_costs);
73  costs.resize(ids.size());
74  for (auto &row : costs) {
75  row.resize(ids.size());
76  for (auto &cell : row) {
77  cell = std::numeric_limits<double>::max();
78  }
79  }
80  for (const auto &data : data_costs) {
81  costs[get_index(data.from_vid)][get_index(data.to_vid)] = data.cost;
82  }
83 
84  for (size_t i = 0; i < costs.size(); ++i) {
85  costs[i][i] = 0;
86  }
87 }
88 
89 bool
90 Dmatrix::has_no_infinity() const {
91  for (const auto &row : costs) {
92  for (const auto &val : row) {
93  if (val == std::numeric_limits<double>::max()) return false;
94  }
95  }
96  return true;
97 }
98 
99 
100 bool
101 Dmatrix::obeys_triangle_inequality() const {
102  /*
103  * Triangle Inequality Theorem.
104  * The sum of the lengths of any two sides of a triangle is greater than the length of the third side.
105  * NOTE: can also be equal for streets
106  * costs[i][k] != inf
107  * costs[i][k] <= costs[i][j] + costs[j][k]
108  */
109  for (size_t i = 0; i < costs.size(); ++i) {
110  for (size_t j = 0; j < costs.size(); ++j) {
111  for (size_t k = 0; k < costs.size(); ++k) {
112  if (costs[i][k] <= (costs[i][j] + costs[j][k])) return false;
113  }
114  }
115  }
116  return true;
117 }
118 
119 bool
120 Dmatrix::is_symetric() const{
121  for (size_t i = 0; i < costs.size(); ++i) {
122  for (size_t j = 0; j < costs.size(); ++j) {
123  if (costs[i][j] != costs[j][i]) return false;
124  }
125  }
126  return true;
127 }
128 
129 
130 Dmatrix
131 Dmatrix::get_symetric() const {
132  double sum(0);
133  for (const auto &row : costs) {
134  for (const auto &cell : row) {
135  sum += cell;
136  }
137  }
138  if (is_symetric()) return *this;
139  Dmatrix new_costs;
140  new_costs.costs.resize(costs.size() * 2);
141  for (auto &row : new_costs.costs) {
142  row.resize(costs.size() * 2);
143  for (auto &cell : row) {
144  cell = std::numeric_limits<double>::max();
145  }
146  }
147 
148  /*
149  * Matrix cuadrants
150  * A= inf B= transposed original
151  * C=original D= inf
152  *
153  * B & C "semi" diagonals are 0
154  */
155  for (size_t i = 0; i < costs.size(); ++i) {
156  for (size_t j = 0; j < costs.size(); ++j) {
157  /*
158  * A & D
159  */
160  new_costs[i][j] =
161  new_costs[i + costs.size()][j + costs.size()] =
162  std::numeric_limits<double>::max();
163 
164  /*
165  * B
166  */
167  new_costs[i + costs.size()][j] =
168  i == j? costs[i][j] : 0;
169 
170  /*
171  * C
172  */
173  new_costs[i][j + costs.size()] =
174  i == j? costs[j][i] : 0;
175  }
176  }
177  new_costs.ids = ids;
178  new_costs.ids.insert(new_costs.ids.end(), ids.begin(), ids.end());
179 
180  return new_costs;
181 }