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
45 #include "cpp_common/basePath_SSEC.hpp"
46 #include "cpp_common/pgr_base_graph.hpp"
47 #include "cpp_common/interruption.h"
48
49 // TODO(vicky) don't keep it here
50 #include "cpp_common/pgr_alloc.hpp"
51
52 template < class G > class Pgr_allpairs;
53
54 // user's functions
55 template < class G >
56 void
pgr_johnson(G & graph,std::vector<Matrix_cell_t> & rows)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
pgr_floydWarshall(G & graph,std::vector<Matrix_cell_t> & rows)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
pgr_johnson(G & graph,size_t & result_tuple_count,Matrix_cell_t ** postgres_rows)72 pgr_johnson(
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
pgr_floydWarshall(G & graph,size_t & result_tuple_count,Matrix_cell_t ** postgres_rows)83 pgr_floydWarshall(
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 public:
floydWarshall(G & graph,size_t & result_tuple_count,Matrix_cell_t ** postgres_rows)96 void floydWarshall(
97 G &graph,
98 size_t &result_tuple_count,
99 Matrix_cell_t **postgres_rows) {
100 std::vector< std::vector<double>> matrix;
101 make_matrix(graph.num_vertices(), matrix);
102 inf_plus<double> combine;
103
104 /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
105 CHECK_FOR_INTERRUPTS();
106
107 boost::floyd_warshall_all_pairs_shortest_paths(
108 graph.graph,
109 matrix,
110 weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
111 distance_combine(combine).
112 distance_inf((std::numeric_limits<double>::max)()).
113 distance_zero(0));
114
115 make_result(graph, matrix, result_tuple_count, postgres_rows);
116 }
117
floydWarshall(G & graph,std::vector<Matrix_cell_t> & rows)118 void floydWarshall(
119 G &graph,
120 std::vector< Matrix_cell_t> &rows) {
121 std::vector< std::vector<double>> matrix;
122 make_matrix(graph.num_vertices(), matrix);
123 inf_plus<double> combine;
124
125 /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
126 CHECK_FOR_INTERRUPTS();
127
128 boost::floyd_warshall_all_pairs_shortest_paths(
129 graph.graph,
130 matrix,
131 weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
132 distance_combine(combine).
133 distance_inf((std::numeric_limits<double>::max)()).
134 distance_zero(0));
135
136 make_result(graph, matrix, rows);
137 }
138
johnson(G & graph,size_t & result_tuple_count,Matrix_cell_t ** postgres_rows)139 void johnson(
140 G &graph,
141 size_t &result_tuple_count,
142 Matrix_cell_t **postgres_rows) {
143 std::vector< std::vector<double>> matrix;
144 make_matrix(graph.num_vertices(), matrix);
145 inf_plus<double> combine;
146
147 /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
148 CHECK_FOR_INTERRUPTS();
149
150 boost::johnson_all_pairs_shortest_paths(
151 graph.graph,
152 matrix,
153 weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
154 distance_combine(combine).
155 distance_inf((std::numeric_limits<double>::max)()).
156 distance_zero(0));
157
158 make_result(graph, matrix, result_tuple_count, postgres_rows);
159 }
160
161
johnson(G & graph,std::vector<Matrix_cell_t> & rows)162 void johnson(
163 G &graph,
164 std::vector< Matrix_cell_t> &rows) {
165 std::vector< std::vector<double>> matrix;
166 make_matrix(graph.num_vertices(), matrix);
167 inf_plus<double> combine;
168
169 /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
170 CHECK_FOR_INTERRUPTS();
171
172 boost::johnson_all_pairs_shortest_paths(
173 graph.graph,
174 matrix,
175 weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
176 distance_combine(combine).
177 distance_inf((std::numeric_limits<double>::max)()).
178 distance_zero(0));
179
180 make_result(graph, matrix, rows);
181 }
182
183 private:
make_matrix(size_t v_size,std::vector<std::vector<double>> & matrix) const184 void make_matrix(
185 size_t v_size,
186 std::vector< std::vector<double>> &matrix) const {
187 // TODO(vicky) in one step
188 matrix.resize(v_size);
189 for (size_t i=0; i < v_size; i++)
190 matrix[i].resize(v_size);
191 }
192
make_result(const G & graph,const std::vector<std::vector<double>> & matrix,size_t & result_tuple_count,Matrix_cell_t ** postgres_rows) const193 void make_result(
194 const G &graph,
195 const std::vector< std::vector<double> > &matrix,
196 size_t &result_tuple_count,
197 Matrix_cell_t **postgres_rows) const {
198 result_tuple_count = count_rows(graph, matrix);
199 *postgres_rows = pgr_alloc(result_tuple_count, (*postgres_rows));
200
201
202 size_t seq = 0;
203 for (typename G::V v_i = 0; v_i < graph.num_vertices(); v_i++) {
204 for (typename G::V v_j = 0; v_j < graph.num_vertices(); v_j++) {
205 if (v_i == v_j) continue;
206 if (matrix[v_i][v_j] != (std::numeric_limits<double>::max)()) {
207 (*postgres_rows)[seq].from_vid = graph[v_i].id;
208 (*postgres_rows)[seq].to_vid = graph[v_j].id;
209 (*postgres_rows)[seq].cost = matrix[v_i][v_j];
210 seq++;
211 } // if
212 } // for j
213 } // for i
214 }
215
216
count_rows(const G & graph,const std::vector<std::vector<double>> & matrix) const217 size_t count_rows(
218 const G &graph,
219 const std::vector< std::vector<double> > &matrix) const {
220 size_t result_tuple_count = 0;
221 for (size_t i = 0; i < graph.num_vertices(); i++) {
222 for (size_t j = 0; j < graph.num_vertices(); j++) {
223 if (i == j) continue;
224 if (matrix[i][j] != (std::numeric_limits<double>::max)()) {
225 result_tuple_count++;
226 } // if
227 } // for j
228 } // for i
229 return result_tuple_count;
230 }
231
make_result(G & graph,std::vector<std::vector<double>> & matrix,std::vector<Matrix_cell_t> & rows)232 void make_result(
233 G &graph,
234 std::vector< std::vector<double> > &matrix,
235 std::vector< Matrix_cell_t> &rows) {
236 size_t count = count_rows(graph, matrix);
237 rows.resize(count);
238 size_t seq = 0;
239
240 for (typename G::V v_i = 0; v_i < graph.num_vertices(); v_i++) {
241 for (typename G::V v_j = 0; v_j < graph.num_vertices(); v_j++) {
242 if (matrix[v_i][v_j] != (std::numeric_limits<double>::max)()) {
243 rows[seq] =
244 {graph[v_i].id, graph[v_j].id, matrix[v_i][v_j]};
245 seq++;
246 } // if
247 } // for j
248 } // for i
249 }
250
251 template <typename T>
252 struct inf_plus {
operator ()Pgr_allpairs::inf_plus253 T operator()(const T& a, const T& b) const {
254 T inf = (std::numeric_limits<T>::max)();
255 if (a == inf || b == inf)
256 return inf;
257 return a + b;
258 }
259 };
260 };
261
262
263 #endif // INCLUDE_ALLPAIRS_PGR_ALLPAIRS_HPP_
264