PGROUTING  3.2
Classes | Public Member Functions | Private Member Functions | List of all members
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 52 of file pgr_allpairs.hpp.

Member Function Documentation

◆ count_rows()

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 217 of file pgr_allpairs.hpp.

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

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

◆ floydWarshall() [1/2]

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

Definition at line 96 of file pgr_allpairs.hpp.

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

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

Referenced by pgr_floydWarshall().

◆ floydWarshall() [2/2]

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

Definition at line 118 of file pgr_allpairs.hpp.

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

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

◆ johnson() [1/2]

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

Definition at line 139 of file pgr_allpairs.hpp.

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

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

Referenced by pgr_johnson().

◆ johnson() [2/2]

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

Definition at line 162 of file pgr_allpairs.hpp.

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

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

◆ make_matrix()

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

Definition at line 184 of file pgr_allpairs.hpp.

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

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

◆ make_result() [1/2]

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 193 of file pgr_allpairs.hpp.

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

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

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

◆ make_result() [2/2]

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 232 of file pgr_allpairs.hpp.

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

References Pgr_allpairs< G >::count_rows().

The documentation for this class was generated from the following file:
Pgr_allpairs::make_matrix
void make_matrix(size_t v_size, std::vector< std::vector< double >> &matrix) const
Definition: pgr_allpairs.hpp:184
pgr_alloc
T * pgr_alloc(std::size_t size, T *ptr)
allocates memory
Definition: pgr_alloc.hpp:66
Pgr_allpairs::count_rows
size_t count_rows(const G &graph, const std::vector< std::vector< double > > &matrix) const
Definition: pgr_allpairs.hpp:217
Pgr_allpairs::make_result
void make_result(const G &graph, const std::vector< std::vector< double > > &matrix, size_t &result_tuple_count, Matrix_cell_t **postgres_rows) const
Definition: pgr_allpairs.hpp:193
pgrouting::Basic_edge::cost
double cost
Definition: basic_edge.h:44
pgrouting::alphashape::V
boost::graph_traits< BG >::vertex_descriptor V
Definition: pgr_alphaShape.h:58