PGROUTING  2.5
Pgr_allpairs< G > Class Template Reference

#include "pgr_allpairs.hpp"

Classes

struct  inf_plus
 

Public Member Functions

void floydWarshall (G &graph, size_t &result_tuple_count, Matrix_cell_t **postgres_rows)
 
void floydWarshall (G &graph, std::vector< Matrix_cell_t > &rows)
 
void johnson (G &graph, size_t &result_tuple_count, Matrix_cell_t **postgres_rows)
 
void johnson (G &graph, std::vector< Matrix_cell_t > &rows)
 

Private Member Functions

size_t count_rows (const G &graph, const std::vector< std::vector< double > > &matrix) const
 
void make_matrix (size_t v_size, std::vector< std::vector< double >> &matrix) const
 
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 make_result (G &graph, std::vector< std::vector< double > > &matrix, std::vector< Matrix_cell_t > &rows)
 

Detailed Description

template<class G>
class Pgr_allpairs< G >

Definition at line 51 of file pgr_allpairs.hpp.

Member Function Documentation

template<class G >
size_t Pgr_allpairs< G >::count_rows ( const G &  graph,
const std::vector< std::vector< double > > &  matrix 
) const
private

Definition at line 253 of file pgr_allpairs.hpp.

Referenced by Pgr_allpairs< G >::make_result(), and pgr_floydWarshall().

255  {
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 }

Here is the caller graph for this function:

template<class G >
void Pgr_allpairs< G >::floydWarshall ( G &  graph,
size_t &  result_tuple_count,
Matrix_cell_t **  postgres_rows 
)

Definition at line 158 of file pgr_allpairs.hpp.

References pgrouting::Basic_edge::cost, Pgr_allpairs< G >::make_matrix(), and Pgr_allpairs< G >::make_result().

Referenced by pgr_floydWarshall().

161  {
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 }
void make_matrix(size_t v_size, std::vector< std::vector< double >> &matrix) const
void make_result(const G &graph, const std::vector< std::vector< double > > &matrix, size_t &result_tuple_count, Matrix_cell_t **postgres_rows) const

Here is the call graph for this function:

Here is the caller graph for this function:

template<class G >
void Pgr_allpairs< G >::floydWarshall ( G &  graph,
std::vector< Matrix_cell_t > &  rows 
)

Definition at line 178 of file pgr_allpairs.hpp.

References pgrouting::Basic_edge::cost, Pgr_allpairs< G >::make_matrix(), and Pgr_allpairs< G >::make_result().

180  {
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 }
void make_matrix(size_t v_size, std::vector< std::vector< double >> &matrix) const
void make_result(const G &graph, const std::vector< std::vector< double > > &matrix, size_t &result_tuple_count, Matrix_cell_t **postgres_rows) const

Here is the call graph for this function:

template<class G >
void Pgr_allpairs< G >::johnson ( G &  graph,
size_t &  result_tuple_count,
Matrix_cell_t **  postgres_rows 
)

Definition at line 196 of file pgr_allpairs.hpp.

References pgrouting::Basic_edge::cost, Pgr_allpairs< G >::make_matrix(), and Pgr_allpairs< G >::make_result().

Referenced by pgr_floydWarshall(), and pgr_johnson().

199  {
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 }
void make_matrix(size_t v_size, std::vector< std::vector< double >> &matrix) const
void make_result(const G &graph, const std::vector< std::vector< double > > &matrix, size_t &result_tuple_count, Matrix_cell_t **postgres_rows) const

Here is the call graph for this function:

Here is the caller graph for this function:

template<class G >
void Pgr_allpairs< G >::johnson ( G &  graph,
std::vector< Matrix_cell_t > &  rows 
)

Definition at line 216 of file pgr_allpairs.hpp.

References pgrouting::Basic_edge::cost, Pgr_allpairs< G >::make_matrix(), and Pgr_allpairs< G >::make_result().

218  {
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 }
void make_matrix(size_t v_size, std::vector< std::vector< double >> &matrix) const
void make_result(const G &graph, const std::vector< std::vector< double > > &matrix, size_t &result_tuple_count, Matrix_cell_t **postgres_rows) const

Here is the call graph for this function:

template<class G >
void Pgr_allpairs< G >::make_matrix ( size_t  v_size,
std::vector< std::vector< double >> &  matrix 
) const
private

Definition at line 242 of file pgr_allpairs.hpp.

Referenced by Pgr_allpairs< G >::floydWarshall(), Pgr_allpairs< G >::johnson(), and pgr_floydWarshall().

244  {
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 }

Here is the caller graph for this function:

template<class G >
void Pgr_allpairs< G >::make_result ( const G &  graph,
const std::vector< std::vector< double > > &  matrix,
size_t &  result_tuple_count,
Matrix_cell_t **  postgres_rows 
) const
private

Definition at line 271 of file pgr_allpairs.hpp.

References Pgr_allpairs< G >::count_rows(), and pgr_alloc().

Referenced by Pgr_allpairs< G >::floydWarshall(), Pgr_allpairs< G >::johnson(), and pgr_floydWarshall().

275  {
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 }
size_t count_rows(const G &graph, const std::vector< std::vector< double > > &matrix) const
T * pgr_alloc(std::size_t size, T *ptr)
allocates memory
Definition: pgr_alloc.hpp:68

Here is the call graph for this function:

Here is the caller graph for this function:

template<class G >
void Pgr_allpairs< G >::make_result ( G &  graph,
std::vector< std::vector< double > > &  matrix,
std::vector< Matrix_cell_t > &  rows 
)
private

Definition at line 297 of file pgr_allpairs.hpp.

References Pgr_allpairs< G >::count_rows().

300  {
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 }
size_t count_rows(const G &graph, const std::vector< std::vector< double > > &matrix) const

Here is the call graph for this function:


The documentation for this class was generated from the following file: