PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgr_allpairs.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_allpairs.hpp
3 
4 Copyright (c) 2015 Celia Virginia Vergara Castillo
5 Mail: vicky_vergara@hotmail.com
6 
7 ------
8 
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2 of the License, or
12 (at your option) any later version.
13 
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18 
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22 
23 ********************************************************************PGR-GNU*/
24 
25 // http://www.cs.rpi.edu/~musser/archive/2005/gsd/restricted/FloydWarshall/FloydWarshall.pdf
26 
27 #ifndef SRC_ALLPAIRS_SRC_PGR_ALLPAIRS_HPP_
28 #define SRC_ALLPAIRS_SRC_PGR_ALLPAIRS_HPP_
29 #pragma once
30 
31 
32 #include <boost/config.hpp>
33 #include <boost/graph/adjacency_list.hpp>
34 #include <boost/property_map/property_map.hpp>
35 #include <boost/graph/johnson_all_pairs_shortest.hpp>
36 #include <boost/graph/floyd_warshall_shortest.hpp>
37 
38 
39 #include <deque>
40 #include <vector>
41 #include <set>
42 #include <limits>
43 
44 
45 #include "./../../common/src/pgr_types.h"
46 #include "./../../common/src/basePath_SSEC.hpp"
47 #include "./../../common/src/pgr_base_graph.hpp"
48 
49 // TODO(vicky) don't keep it here
50 #include "../../common/src/pgr_alloc.hpp"
51 
52 template < class G > class Pgr_allpairs;
53 
54 // user's functions
55 template < class G >
56 void
57 pgr_johnson(G &graph, std::vector< Matrix_cell_t> &rows) {
58  Pgr_allpairs< G > fn_johnson;
59  fn_johnson.johnson(graph, rows);
60 }
61 
62 template < class G >
63 void
64 pgr_floydWarshall(G &graph, std::vector< Matrix_cell_t> &rows) {
65  Pgr_allpairs< G > fn_floydWarshall;
66  fn_floydWarshall.floydWarshall(graph, rows);
67 }
68 
69 // for postgres
70 template < class G >
71 void
73  G &graph,
74  size_t &result_tuple_count,
75  Matrix_cell_t **postgres_rows) {
76  Pgr_allpairs< G > fn_johnson;
77  fn_johnson.johnson(graph, result_tuple_count, postgres_rows);
78 }
79 
80 
81 template < class G >
82 void
84  G &graph,
85  size_t &result_tuple_count,
86  Matrix_cell_t **postgres_rows) {
87  Pgr_allpairs< G > fn_floydWarshall;
88  fn_floydWarshall.floydWarshall(graph, result_tuple_count, postgres_rows);
89 }
90 
91 
92 // template class
93 template < class G >
94 class Pgr_allpairs {
95  // default constructors and destructors
96  /*
97  Matrix_cell_t description:
98  int64_t from_vid;
99  int64_t to_vid;
100  float8 cost;
101  */
102  public:
103  void floydWarshall(
104  G &graph,
105  size_t &result_tuple_count,
106  Matrix_cell_t **postgres_rows);
107 
108 
109  void floydWarshall(
110  G &graph,
111  std::vector< Matrix_cell_t> &rows);
112 
113  void johnson(
114  G &graph,
115  size_t &result_tuple_count,
116  Matrix_cell_t **postgres_rows);
117 
118 
119  void johnson(
120  G &graph,
121  std::vector< Matrix_cell_t> &rows);
122 
123  private:
124  void make_matrix(
125  size_t v_size,
126  std::vector< std::vector<double>> &matrix) const;
127 
128  void make_result(
129  const G &graph,
130  const std::vector< std::vector<double> > &matrix,
131  size_t &result_tuple_count,
132  Matrix_cell_t **postgres_rows) const;
133 
134  size_t count_rows(
135  const G &graph,
136  const std::vector< std::vector<double> > &matrix) const;
137 
138  void make_result(
139  G &graph,
140  std::vector< std::vector<double> > &matrix,
141  std::vector< Matrix_cell_t> &rows);
142 
143  template <typename T>
144  struct inf_plus {
145  T operator()(const T& a, const T& b) const {
146  T inf = (std::numeric_limits<T>::max)();
147  if (a == inf || b == inf)
148  return inf;
149  return a + b;
150  }
151  };
152 };
153 
154 /*
155  * PUBLIC FUNCTIONS
156  */
157 
158 template < class G >
160  G &graph,
161  size_t &result_tuple_count,
162  Matrix_cell_t **postgres_rows) {
163  std::vector< std::vector<double>> matrix;
164  make_matrix(graph.num_vertices(), matrix);
165  inf_plus<double> combine;
166  boost::floyd_warshall_all_pairs_shortest_paths(
167  graph.graph,
168  matrix,
169  weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
170  distance_combine(combine).
171  distance_inf((std::numeric_limits<double>::max)()).
172  distance_zero(0));
173 
174  make_result(graph, matrix, result_tuple_count, postgres_rows);
175 }
176 
177 
178 template < class G >
180  G &graph,
181  std::vector< Matrix_cell_t> &rows) {
182  std::vector< std::vector<double>> matrix;
183  make_matrix(graph.num_vertices(), matrix);
184  inf_plus<double> combine;
185  boost::floyd_warshall_all_pairs_shortest_paths(
186  graph.graph,
187  matrix,
188  weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
189  distance_combine(combine).
190  distance_inf((std::numeric_limits<double>::max)()).
191  distance_zero(0));
192 
193  make_result(graph, matrix, rows);
194 }
195 
196 template < class G >
198  G &graph,
199  size_t &result_tuple_count,
200  Matrix_cell_t **postgres_rows) {
201  std::vector< std::vector<double>> matrix;
202  make_matrix(graph.num_vertices(), matrix);
203  inf_plus<double> combine;
204  boost::johnson_all_pairs_shortest_paths(
205  graph.graph,
206  matrix,
207  weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
208  distance_combine(combine).
209  distance_inf((std::numeric_limits<double>::max)()).
210  distance_zero(0));
211 
212  make_result(graph, matrix, result_tuple_count, postgres_rows);
213 }
214 
215 
216 template < class G >
218  G &graph,
219  std::vector< Matrix_cell_t> &rows) {
220  std::vector< std::vector<double>> matrix;
221  make_matrix(graph.num_vertices(), matrix);
222  inf_plus<double> combine;
223  boost::johnson_all_pairs_shortest_paths(
224  graph.graph,
225  matrix,
226  weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
227  distance_combine(combine).
228  distance_inf((std::numeric_limits<double>::max)()).
229  distance_zero(0));
230 
231  make_result(graph, matrix, rows);
232 }
233 
234 
235 
236 
237 /*
238  * PRIVATE FUNCTIONS
239  */
240 
241 template < class G >
242 void
244  size_t v_size,
245  std::vector< std::vector<double>> &matrix) const {
246  // TODO(vicky) in one step
247  matrix.resize(v_size);
248  for (size_t i=0; i < v_size; i++)
249  matrix[i].resize(v_size);
250 }
251 
252 template < class G >
253 size_t
255  const G &graph,
256  const std::vector< std::vector<double> > &matrix) const {
257  size_t result_tuple_count = 0;
258  for (size_t i = 0; i < graph.num_vertices(); i++) {
259  for (size_t j = 0; j < graph.num_vertices(); j++) {
260  if (i == j) continue;
261  if (matrix[i][j] != (std::numeric_limits<double>::max)()) {
262  result_tuple_count++;
263  } // if
264  } // for j
265  } // for i
266  return result_tuple_count;
267 }
268 
269 // TODO(vicky) don't keep it here for postgres
270 template < class G >
271 void
273  const G &graph,
274  const std::vector< std::vector<double> > &matrix,
275  size_t &result_tuple_count,
276  Matrix_cell_t **postgres_rows) const {
277  result_tuple_count = count_rows(graph, matrix);
278  *postgres_rows = pgr_alloc(result_tuple_count, (*postgres_rows));
279 
280 
281  size_t seq = 0;
282  for (typename G::V v_i = 0; v_i < graph.num_vertices(); v_i++) {
283  for (typename G::V v_j = 0; v_j < graph.num_vertices(); v_j++) {
284  if (v_i == v_j) continue;
285  if (matrix[v_i][v_j] != (std::numeric_limits<double>::max)()) {
286  (*postgres_rows)[seq].from_vid = graph[v_i].id;
287  (*postgres_rows)[seq].to_vid = graph[v_j].id;
288  (*postgres_rows)[seq].cost = matrix[v_i][v_j];
289  seq++;
290  } // if
291  } // for j
292  } // for i
293 }
294 
295 
296 template < class G >
297 void
299  G &graph,
300  std::vector< std::vector<double> > &matrix,
301  std::vector< Matrix_cell_t> &rows) {
302  size_t count = count_rows(graph, matrix);
303  rows.resize(count);
304  size_t seq = 0;
305 
306  for (typename G::V v_i = 0; v_i < graph.num_vertices(); v_i++) {
307  for (typename G::V v_j = 0; v_j < graph.num_vertices(); v_j++) {
308  if (matrix[v_i][v_j] != (std::numeric_limits<double>::max)()) {
309  rows[seq] =
310  {graph[v_i].id, graph[v_j].id, matrix[v_i][v_j]};
311  seq++;
312  } // if
313  } // for j
314  } // for i
315 }
316 
317 #endif // SRC_ALLPAIRS_SRC_PGR_ALLPAIRS_HPP_
size_t count_rows(const G &graph, const std::vector< std::vector< double > > &matrix) const
void johnson(G &graph, size_t &result_tuple_count, Matrix_cell_t **postgres_rows)
void make_matrix(size_t v_size, std::vector< std::vector< double >> &matrix) const
T operator()(const T &a, const T &b) const
void floydWarshall(G &graph, size_t &result_tuple_count, Matrix_cell_t **postgres_rows)
T * pgr_alloc(std::size_t size, T *ptr)
allocates memory
Definition: pgr_alloc.hpp:62
void pgr_floydWarshall(G &graph, std::vector< Matrix_cell_t > &rows)
void make_result(const G &graph, const std::vector< std::vector< double > > &matrix, size_t &result_tuple_count, Matrix_cell_t **postgres_rows) const
void pgr_johnson(G &graph, std::vector< Matrix_cell_t > &rows)