PGROUTING  2.6
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
inlineprivate

Definition at line 200 of file pgr_allpairs.hpp.

Referenced by Pgr_allpairs< G >::make_result().

202  {
203  size_t result_tuple_count = 0;
204  for (size_t i = 0; i < graph.num_vertices(); i++) {
205  for (size_t j = 0; j < graph.num_vertices(); j++) {
206  if (i == j) continue;
207  if (matrix[i][j] != (std::numeric_limits<double>::max)()) {
208  result_tuple_count++;
209  } // if
210  } // for j
211  } // for i
212  return result_tuple_count;
213  }

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 
)
inline

Definition at line 95 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().

98  {
99  std::vector< std::vector<double>> matrix;
100  make_matrix(graph.num_vertices(), matrix);
101  inf_plus<double> combine;
102  boost::floyd_warshall_all_pairs_shortest_paths(
103  graph.graph,
104  matrix,
105  weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
106  distance_combine(combine).
107  distance_inf((std::numeric_limits<double>::max)()).
108  distance_zero(0));
109 
110  make_result(graph, matrix, result_tuple_count, postgres_rows);
111  }
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 
)
inline

Definition at line 113 of file pgr_allpairs.hpp.

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

115  {
116  std::vector< std::vector<double>> matrix;
117  make_matrix(graph.num_vertices(), matrix);
118  inf_plus<double> combine;
119  boost::floyd_warshall_all_pairs_shortest_paths(
120  graph.graph,
121  matrix,
122  weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
123  distance_combine(combine).
124  distance_inf((std::numeric_limits<double>::max)()).
125  distance_zero(0));
126 
127  make_result(graph, matrix, rows);
128  }
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 
)
inline

Definition at line 130 of file pgr_allpairs.hpp.

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

Referenced by pgr_johnson().

133  {
134  std::vector< std::vector<double>> matrix;
135  make_matrix(graph.num_vertices(), matrix);
136  inf_plus<double> combine;
137  boost::johnson_all_pairs_shortest_paths(
138  graph.graph,
139  matrix,
140  weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
141  distance_combine(combine).
142  distance_inf((std::numeric_limits<double>::max)()).
143  distance_zero(0));
144 
145  make_result(graph, matrix, result_tuple_count, postgres_rows);
146  }
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 
)
inline

Definition at line 149 of file pgr_allpairs.hpp.

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

151  {
152  std::vector< std::vector<double>> matrix;
153  make_matrix(graph.num_vertices(), matrix);
154  inf_plus<double> combine;
155  boost::johnson_all_pairs_shortest_paths(
156  graph.graph,
157  matrix,
158  weight_map(get(&pgrouting::Basic_edge::cost, graph.graph)).
159  distance_combine(combine).
160  distance_inf((std::numeric_limits<double>::max)()).
161  distance_zero(0));
162 
163  make_result(graph, matrix, rows);
164  }
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
inlineprivate

Definition at line 167 of file pgr_allpairs.hpp.

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

169  {
170  // TODO(vicky) in one step
171  matrix.resize(v_size);
172  for (size_t i=0; i < v_size; i++)
173  matrix[i].resize(v_size);
174  }

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
inlineprivate

Definition at line 176 of file pgr_allpairs.hpp.

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

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

180  {
181  result_tuple_count = count_rows(graph, matrix);
182  *postgres_rows = pgr_alloc(result_tuple_count, (*postgres_rows));
183 
184 
185  size_t seq = 0;
186  for (typename G::V v_i = 0; v_i < graph.num_vertices(); v_i++) {
187  for (typename G::V v_j = 0; v_j < graph.num_vertices(); v_j++) {
188  if (v_i == v_j) continue;
189  if (matrix[v_i][v_j] != (std::numeric_limits<double>::max)()) {
190  (*postgres_rows)[seq].from_vid = graph[v_i].id;
191  (*postgres_rows)[seq].to_vid = graph[v_j].id;
192  (*postgres_rows)[seq].cost = matrix[v_i][v_j];
193  seq++;
194  } // if
195  } // for j
196  } // for i
197  }
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:66

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 
)
inlineprivate

Definition at line 215 of file pgr_allpairs.hpp.

References Pgr_allpairs< G >::count_rows().

218  {
219  size_t count = count_rows(graph, matrix);
220  rows.resize(count);
221  size_t seq = 0;
222 
223  for (typename G::V v_i = 0; v_i < graph.num_vertices(); v_i++) {
224  for (typename G::V v_j = 0; v_j < graph.num_vertices(); v_j++) {
225  if (matrix[v_i][v_j] != (std::numeric_limits<double>::max)()) {
226  rows[seq] =
227  {graph[v_i].id, graph[v_j].id, matrix[v_i][v_j]};
228  seq++;
229  } // if
230  } // for j
231  } // for i
232  }
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: