PGROUTING  2.5
 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 INCLUDE_ALLPAIRS_PGR_ALLPAIRS_HPP_
28 #define INCLUDE_ALLPAIRS_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 
47 
48 // TODO(vicky) don't keep it here
49 #include "cpp_common/pgr_alloc.hpp"
50 
51 template < class G > class Pgr_allpairs;
52 
53 // user's functions
54 template < class G >
55 void
56 pgr_johnson(G &graph, std::vector< Matrix_cell_t> &rows) {
57  Pgr_allpairs< G > fn_johnson;
58  fn_johnson.johnson(graph, rows);
59 }
60 
61 template < class G >
62 void
63 pgr_floydWarshall(G &graph, std::vector< Matrix_cell_t> &rows) {
64  Pgr_allpairs< G > fn_floydWarshall;
65  fn_floydWarshall.floydWarshall(graph, rows);
66 }
67 
68 // for postgres
69 template < class G >
70 void
72  G &graph,
73  size_t &result_tuple_count,
74  Matrix_cell_t **postgres_rows) {
75  Pgr_allpairs< G > fn_johnson;
76  fn_johnson.johnson(graph, result_tuple_count, postgres_rows);
77 }
78 
79 
80 template < class G >
81 void
83  G &graph,
84  size_t &result_tuple_count,
85  Matrix_cell_t **postgres_rows) {
86  Pgr_allpairs< G > fn_floydWarshall;
87  fn_floydWarshall.floydWarshall(graph, result_tuple_count, postgres_rows);
88 }
89 
90 
91 // template class
92 template < class G >
93 class Pgr_allpairs {
94  // default constructors and destructors
95  /*
96  Matrix_cell_t description:
97  int64_t from_vid;
98  int64_t to_vid;
99  float8 cost;
100  */
101  public:
102  void floydWarshall(
103  G &graph,
104  size_t &result_tuple_count,
105  Matrix_cell_t **postgres_rows);
106 
107 
108  void floydWarshall(
109  G &graph,
110  std::vector< Matrix_cell_t> &rows);
111 
112  void johnson(
113  G &graph,
114  size_t &result_tuple_count,
115  Matrix_cell_t **postgres_rows);
116 
117 
118  void johnson(
119  G &graph,
120  std::vector< Matrix_cell_t> &rows);
121 
122  private:
123  void make_matrix(
124  size_t v_size,
125  std::vector< std::vector<double>> &matrix) const;
126 
127  void make_result(
128  const G &graph,
129  const std::vector< std::vector<double> > &matrix,
130  size_t &result_tuple_count,
131  Matrix_cell_t **postgres_rows) const;
132 
133  size_t count_rows(
134  const G &graph,
135  const std::vector< std::vector<double> > &matrix) const;
136 
137  void make_result(
138  G &graph,
139  std::vector< std::vector<double> > &matrix,
140  std::vector< Matrix_cell_t> &rows);
141 
142  template <typename T>
143  struct inf_plus {
144  T operator()(const T& a, const T& b) const {
145  T inf = (std::numeric_limits<T>::max)();
146  if (a == inf || b == inf)
147  return inf;
148  return a + b;
149  }
150  };
151 };
152 
153 /*
154  * PUBLIC FUNCTIONS
155  */
156 
157 template < class G >
159  G &graph,
160  size_t &result_tuple_count,
161  Matrix_cell_t **postgres_rows) {
162  std::vector< std::vector<double>> matrix;
163  make_matrix(graph.num_vertices(), matrix);
164  inf_plus<double> combine;
165  boost::floyd_warshall_all_pairs_shortest_paths(
166  graph.graph,
167  matrix,
168  weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
169  distance_combine(combine).
170  distance_inf((std::numeric_limits<double>::max)()).
171  distance_zero(0));
172 
173  make_result(graph, matrix, result_tuple_count, postgres_rows);
174 }
175 
176 
177 template < class G >
179  G &graph,
180  std::vector< Matrix_cell_t> &rows) {
181  std::vector< std::vector<double>> matrix;
182  make_matrix(graph.num_vertices(), matrix);
183  inf_plus<double> combine;
184  boost::floyd_warshall_all_pairs_shortest_paths(
185  graph.graph,
186  matrix,
187  weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
188  distance_combine(combine).
189  distance_inf((std::numeric_limits<double>::max)()).
190  distance_zero(0));
191 
192  make_result(graph, matrix, rows);
193 }
194 
195 template < class G >
197  G &graph,
198  size_t &result_tuple_count,
199  Matrix_cell_t **postgres_rows) {
200  std::vector< std::vector<double>> matrix;
201  make_matrix(graph.num_vertices(), matrix);
202  inf_plus<double> combine;
203  boost::johnson_all_pairs_shortest_paths(
204  graph.graph,
205  matrix,
206  weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
207  distance_combine(combine).
208  distance_inf((std::numeric_limits<double>::max)()).
209  distance_zero(0));
210 
211  make_result(graph, matrix, result_tuple_count, postgres_rows);
212 }
213 
214 
215 template < class G >
217  G &graph,
218  std::vector< Matrix_cell_t> &rows) {
219  std::vector< std::vector<double>> matrix;
220  make_matrix(graph.num_vertices(), matrix);
221  inf_plus<double> combine;
222  boost::johnson_all_pairs_shortest_paths(
223  graph.graph,
224  matrix,
225  weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
226  distance_combine(combine).
227  distance_inf((std::numeric_limits<double>::max)()).
228  distance_zero(0));
229 
230  make_result(graph, matrix, rows);
231 }
232 
233 
234 
235 
236 /*
237  * PRIVATE FUNCTIONS
238  */
239 
240 template < class G >
241 void
243  size_t v_size,
244  std::vector< std::vector<double>> &matrix) const {
245  // TODO(vicky) in one step
246  matrix.resize(v_size);
247  for (size_t i=0; i < v_size; i++)
248  matrix[i].resize(v_size);
249 }
250 
251 template < class G >
252 size_t
254  const G &graph,
255  const std::vector< std::vector<double> > &matrix) const {
256  size_t result_tuple_count = 0;
257  for (size_t i = 0; i < graph.num_vertices(); i++) {
258  for (size_t j = 0; j < graph.num_vertices(); j++) {
259  if (i == j) continue;
260  if (matrix[i][j] != (std::numeric_limits<double>::max)()) {
261  result_tuple_count++;
262  } // if
263  } // for j
264  } // for i
265  return result_tuple_count;
266 }
267 
268 // TODO(vicky) don't keep it here for postgres
269 template < class G >
270 void
272  const G &graph,
273  const std::vector< std::vector<double> > &matrix,
274  size_t &result_tuple_count,
275  Matrix_cell_t **postgres_rows) const {
276  result_tuple_count = count_rows(graph, matrix);
277  *postgres_rows = pgr_alloc(result_tuple_count, (*postgres_rows));
278 
279 
280  size_t seq = 0;
281  for (typename G::V v_i = 0; v_i < graph.num_vertices(); v_i++) {
282  for (typename G::V v_j = 0; v_j < graph.num_vertices(); v_j++) {
283  if (v_i == v_j) continue;
284  if (matrix[v_i][v_j] != (std::numeric_limits<double>::max)()) {
285  (*postgres_rows)[seq].from_vid = graph[v_i].id;
286  (*postgres_rows)[seq].to_vid = graph[v_j].id;
287  (*postgres_rows)[seq].cost = matrix[v_i][v_j];
288  seq++;
289  } // if
290  } // for j
291  } // for i
292 }
293 
294 
295 template < class G >
296 void
298  G &graph,
299  std::vector< std::vector<double> > &matrix,
300  std::vector< Matrix_cell_t> &rows) {
301  size_t count = count_rows(graph, matrix);
302  rows.resize(count);
303  size_t seq = 0;
304 
305  for (typename G::V v_i = 0; v_i < graph.num_vertices(); v_i++) {
306  for (typename G::V v_j = 0; v_j < graph.num_vertices(); v_j++) {
307  if (matrix[v_i][v_j] != (std::numeric_limits<double>::max)()) {
308  rows[seq] =
309  {graph[v_i].id, graph[v_j].id, matrix[v_i][v_j]};
310  seq++;
311  } // if
312  } // for j
313  } // for i
314 }
315 
316 #endif // INCLUDE_ALLPAIRS_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:64
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)