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
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 #if 0
32 #if defined(__MINGW32__) || defined(_MSC_VER)
33 #include <winsock2.h>
34 #include <windows.h>
35 #ifdef open
36 #undef open
37 #endif
38 #endif
39 #endif
40 
41 #include <boost/config.hpp>
42 #include <boost/graph/adjacency_list.hpp>
43 #include <boost/property_map/property_map.hpp>
44 #include <boost/graph/johnson_all_pairs_shortest.hpp>
45 #include <boost/graph/floyd_warshall_shortest.hpp>
46 
47 
48 #include <deque>
49 #include <vector>
50 #include <set>
51 #include <limits>
52 
53 
54 #include "./../../common/src/pgr_types.h"
55 #include "../../common/src/pgr_alloc.hpp"
56 #include "./../../common/src/basePath_SSEC.hpp"
57 #include "./../../common/src/pgr_base_graph.hpp"
58 
59 template < class G > class Pgr_allpairs;
60 
61 // user's functions
62 template < class G >
63 void
64 pgr_johnson(G &graph, std::vector< Matrix_cell_t> &rows) {
65  Pgr_allpairs< G > fn_johnson;
66  fn_johnson.johnson(graph, rows);
67 }
68 
69 template < class G >
70 void
71 pgr_floydWarshall(G &graph, std::vector< Matrix_cell_t> &rows) {
72  Pgr_allpairs< G > fn_floydWarshall;
73  fn_floydWarshall.floydWarshall(graph, rows);
74 }
75 
76 // for postgres
77 template < class G >
78 void
80  G &graph,
81  size_t &result_tuple_count,
82  Matrix_cell_t **postgres_rows) {
83  Pgr_allpairs< G > fn_johnson;
84  fn_johnson.johnson(graph, result_tuple_count, postgres_rows);
85 }
86 
87 
88 template < class G >
89 void
91  G &graph,
92  size_t &result_tuple_count,
93  Matrix_cell_t **postgres_rows) {
94  Pgr_allpairs< G > fn_floydWarshall;
95  fn_floydWarshall.floydWarshall(graph, result_tuple_count, postgres_rows);
96 }
97 
98 
99 // template class
100 template < class G >
101 class Pgr_allpairs {
102  // default constructors and destructors
103  /*
104  Matrix_cell_t description:
105  int64_t from_vid;
106  int64_t to_vid;
107  float8 cost;
108  */
109  public:
110  void floydWarshall(
111  G &graph,
112  size_t &result_tuple_count,
113  Matrix_cell_t **postgres_rows);
114 
115 
116  void floydWarshall(
117  G &graph,
118  std::vector< Matrix_cell_t> &rows);
119 
120  void johnson(
121  G &graph,
122  size_t &result_tuple_count,
123  Matrix_cell_t **postgres_rows);
124 
125 
126  void johnson(
127  G &graph,
128  std::vector< Matrix_cell_t> &rows);
129 
130  private:
131  void make_matrix(
132  size_t v_size,
133  std::vector< std::vector<double>> &matrix) const;
134 
135  void make_result(
136  const G &graph,
137  const std::vector< std::vector<double> > &matrix,
138  size_t &result_tuple_count,
139  Matrix_cell_t **postgres_rows) const;
140 
141  size_t count_rows(
142  const G &graph,
143  const std::vector< std::vector<double> > &matrix) const;
144 
145  void make_result(
146  G &graph,
147  std::vector< std::vector<double> > &matrix,
148  std::vector< Matrix_cell_t> &rows);
149 
150  template <typename T>
151  struct inf_plus {
152  T operator()(const T& a, const T& b) const {
153  T inf = std::numeric_limits<T>::max();
154  if (a == inf || b == inf)
155  return inf;
156  return a + b;
157  }
158  };
159 };
160 
161 /*
162  * PUBLIC FUNCTIONS
163  */
164 
165 template < class G >
167  G &graph,
168  size_t &result_tuple_count,
169  Matrix_cell_t **postgres_rows) {
170  std::vector< std::vector<double>> matrix;
171  make_matrix(graph.num_vertices(), matrix);
172  inf_plus<double> combine;
173  boost::floyd_warshall_all_pairs_shortest_paths(
174  graph.graph,
175  matrix,
176  weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
177  distance_combine(combine).
178  distance_inf(std::numeric_limits<double>::max()).
179  distance_zero(0));
180 
181  make_result(graph, matrix, result_tuple_count, postgres_rows);
182 }
183 
184 
185 template < class G >
187  G &graph,
188  std::vector< Matrix_cell_t> &rows) {
189  std::vector< std::vector<double>> matrix;
190  make_matrix(boost::num_vertices(graph.graph), matrix);
191  inf_plus<double> combine;
192  boost::floyd_warshall_all_pairs_shortest_paths(
193  graph.graph,
194  matrix,
195  weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
196  distance_combine(combine).
197  distance_inf(std::numeric_limits<double>::max()).
198  distance_zero(0));
199 
200  make_result(graph, matrix, rows);
201 }
202 
203 template < class G >
205  G &graph,
206  size_t &result_tuple_count,
207  Matrix_cell_t **postgres_rows) {
208  std::vector< std::vector<double>> matrix;
209  make_matrix(graph.num_vertices(), matrix);
210  inf_plus<double> combine;
211  boost::johnson_all_pairs_shortest_paths(
212  graph.graph,
213  matrix,
214  weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
215  distance_combine(combine).
216  distance_inf(std::numeric_limits<double>::max()).
217  distance_zero(0));
218 
219  make_result(graph, matrix, result_tuple_count, postgres_rows);
220 }
221 
222 
223 template < class G >
225  G &graph,
226  std::vector< Matrix_cell_t> &rows) {
227  std::vector< std::vector<double>> matrix;
228  make_matrix(boost::num_vertices(graph.graph), matrix);
229  inf_plus<double> combine;
230  boost::johnson_all_pairs_shortest_paths(
231  graph.graph,
232  matrix,
233  weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
234  distance_combine(combine).
235  distance_inf(std::numeric_limits<double>::max()).
236  distance_zero(0));
237 
238  make_result(graph, matrix, rows);
239 }
240 
241 
242 
243 
244 /*
245  * PRIVATE FUNCTIONS
246  */
247 
248 template < class G >
249 void
251  size_t v_size,
252  std::vector< std::vector<double>> &matrix) const {
253  matrix.resize(v_size);
254  for (size_t i=0; i < v_size; i++)
255  matrix[i].resize(v_size);
256 }
257 
258 template < class G >
259 size_t
261  const G &graph,
262  const std::vector< std::vector<double> > &matrix) const {
263  size_t result_tuple_count = 0;
264  for (size_t i = 0; i < graph.num_vertices(); i++) {
265  for (size_t j = 0; j < graph.num_vertices(); j++) {
266  if (i == j) continue;
267  if (matrix[i][j] != std::numeric_limits<double>::max()) {
268  result_tuple_count++;
269  } // if
270  } // for j
271  } // for i
272  return result_tuple_count;
273 }
274 
275 // for postgres
276 template < class G >
277 void
279  const G &graph,
280  const std::vector< std::vector<double> > &matrix,
281  size_t &result_tuple_count,
282  Matrix_cell_t **postgres_rows) const {
283  result_tuple_count = count_rows(graph, matrix);
284  *postgres_rows = pgr_alloc(result_tuple_count, (*postgres_rows));
285 
286 
287  size_t seq = 0;
288  for (size_t i = 0; i < graph.num_vertices(); i++) {
289  for (size_t j = 0; j < graph.num_vertices(); j++) {
290  if (i == j) continue;
291  if (matrix[i][j] != std::numeric_limits<double>::max()) {
292  (*postgres_rows)[seq].from_vid = graph.graph[i].id;
293  (*postgres_rows)[seq].to_vid = graph.graph[j].id;
294  (*postgres_rows)[seq].cost = matrix[i][j];
295  seq++;
296  } // if
297  } // for j
298  } // for i
299 }
300 
301 
302 template < class G >
303 void
305  G &graph,
306  std::vector< std::vector<double> > &matrix,
307  std::vector< Matrix_cell_t> &rows) {
308  size_t count = count_rows(graph, matrix);
309  rows.resize(count);
310  size_t seq = 0;
311 
312  for (size_t i = 0; i < graph.num_vertices(); i++) {
313  for (size_t j = 0; j < graph.num_vertices(); j++) {
314  if (matrix[i][j] != std::numeric_limits<double>::max()) {
315  rows[seq] =
316  {graph.graph[i].id, graph.graph[j].id, matrix[i][j]};
317  seq++;
318  } // if
319  } // for j
320  } // for i
321 }
322 
323 #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)
static int a
Definition: tsplib.c:114
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)
static int b
Definition: tsplib.c:115
T * pgr_alloc(std::size_t size, T *ptr)
allocates memory
Definition: pgr_alloc.hpp:52
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)