PGROUTING  3.2
Public Types | Public Member Functions | Public Attributes | List of all members
Pgr_bellman_ford< G > Class Template Reference

#include "pgr_bellman_ford.hpp"

Inheritance diagram for Pgr_bellman_ford< G >:
Inheritance graph
[legend]
Collaboration diagram for Pgr_bellman_ford< G >:
Collaboration graph
[legend]

Public Types

typedef G::E E
 
typedef G::V V
 

Public Member Functions

std::string get_error () const
 get_error More...
 
std::string get_log () const
 get_log More...
 
std::string get_notice () const
 get_notice More...
 
bool has_error () const
 get_error More...
 

Public Attributes

std::ostringstream error
 Stores the error information. More...
 
std::ostringstream log
 Stores the hint information. More...
 
std::ostringstream notice
 Stores the notice information. More...
 

Private Attributes

members
std::vector< V > predecessors
 
std::vector< double > distances
 

BellmanFord

Path bellman_ford (G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
 BellmanFord 1 to 1. More...
 
std::deque< Path > bellman_ford (G &graph, int64_t start_vertex, const std::vector< int64_t > &end_vertex, bool only_cost=false)
 BellmanFord 1 to many. More...
 
std::deque< Path > bellman_ford (G &graph, const std::vector< int64_t > &start_vertex, int64_t end_vertex, bool only_cost=false)
 
std::deque< Path > bellman_ford (G &graph, const std::vector< int64_t > &start_vertex, const std::vector< int64_t > &end_vertex, bool only_cost=false)
 
std::deque< Path > bellman_ford (G &graph, const std::vector< pgr_combination_t > &combinations, bool only_cost=false)
 
bool bellman_ford_1_to_1 (G &graph, V source)
 Call to BellmanFord 1 source to 1 target. More...
 
bool bellman_ford_1_to_many (G &graph, V source)
 Call to BellmanFord 1 source to many targets. More...
 
void clear ()
 
std::deque< Path > get_paths (const G &graph, V source, std::vector< V > &targets, bool only_cost) const
 

Detailed Description

template<class G>
class Pgr_bellman_ford< G >

Definition at line 53 of file pgr_bellman_ford.hpp.

Member Typedef Documentation

◆ E

template<class G >
typedef G::E Pgr_bellman_ford< G >::E

Definition at line 56 of file pgr_bellman_ford.hpp.

◆ V

template<class G >
typedef G::V Pgr_bellman_ford< G >::V

Definition at line 55 of file pgr_bellman_ford.hpp.

Member Function Documentation

◆ bellman_ford() [1/5]

template<class G >
std::deque<Path> Pgr_bellman_ford< G >::bellman_ford ( G &  graph,
const std::vector< int64_t > &  start_vertex,
const std::vector< int64_t > &  end_vertex,
bool  only_cost = false 
)
inline

Definition at line 158 of file pgr_bellman_ford.hpp.

162  {
163  // a call to 1 to many is faster for each of the sources
164  std::deque<Path> paths;
165  log << std::string(__FUNCTION__) << "\n";
166 
167  for (const auto &start : start_vertex) {
168  auto r_paths = bellman_ford(graph, start, end_vertex, only_cost);
169  paths.insert(paths.begin(), r_paths.begin(), r_paths.end());
170  }
171 
172 
173  std::sort(paths.begin(), paths.end(),
174  [](const Path &e1, const Path &e2)->bool {
175  return e1.end_id() < e2.end_id();
176  });
177  std::stable_sort(paths.begin(), paths.end(),
178  [](const Path &e1, const Path &e2)->bool {
179  return e1.start_id() < e2.start_id();
180  });
181  return paths;
182  }

References Pgr_bellman_ford< G >::bellman_ford(), and pgrouting::Pgr_messages::log.

◆ bellman_ford() [2/5]

template<class G >
std::deque<Path> Pgr_bellman_ford< G >::bellman_ford ( G &  graph,
const std::vector< int64_t > &  start_vertex,
int64_t  end_vertex,
bool  only_cost = false 
)
inline

Definition at line 137 of file pgr_bellman_ford.hpp.

141  {
142  std::deque<Path> paths;
143  log << std::string(__FUNCTION__) << "\n";
144  for (const auto &start : start_vertex) {
145  paths.push_back(
146  bellman_ford(graph, start, end_vertex, only_cost));
147  }
148 
149  std::stable_sort(paths.begin(), paths.end(),
150  [](const Path &e1, const Path &e2)->bool {
151  return e1.start_id() < e2.start_id();
152  });
153  return paths;
154  }

References Pgr_bellman_ford< G >::bellman_ford(), and pgrouting::Pgr_messages::log.

◆ bellman_ford() [3/5]

template<class G >
std::deque<Path> Pgr_bellman_ford< G >::bellman_ford ( G &  graph,
const std::vector< pgr_combination_t > &  combinations,
bool  only_cost = false 
)
inline

Definition at line 185 of file pgr_bellman_ford.hpp.

188  {
189  // a call to 1 to many is faster for each of the sources
190  std::deque<Path> paths;
191  log << std::string(__FUNCTION__) << "\n";
192 
193  // group targets per distinct source
194  std::map< int64_t, std::vector<int64_t> > vertex_map;
195  for (const pgr_combination_t &comb : combinations) {
196  std::map< int64_t, std::vector<int64_t> >::iterator it = vertex_map.find(comb.source);
197  if (it != vertex_map.end()) {
198  it->second.push_back(comb.target);
199  } else {
200  std::vector<int64_t > targets{comb.target};
201  vertex_map[comb.source] = targets;
202  }
203  }
204 
205  for (const auto &start_ends : vertex_map) {
206  std::deque<Path> result_paths = bellman_ford(
207  graph,
208  start_ends.first,
209  start_ends.second,
210  only_cost);
211  paths.insert(
212  paths.end(),
213  std::make_move_iterator(result_paths.begin()),
214  std::make_move_iterator(result_paths.end()));
215  }
216 
217  return paths;
218  }

References Pgr_bellman_ford< G >::bellman_ford(), and pgrouting::Pgr_messages::log.

◆ bellman_ford() [4/5]

template<class G >
std::deque<Path> Pgr_bellman_ford< G >::bellman_ford ( G &  graph,
int64_t  start_vertex,
const std::vector< int64_t > &  end_vertex,
bool  only_cost = false 
)
inline

BellmanFord 1 to many.

Definition at line 97 of file pgr_bellman_ford.hpp.

101  {
102  // adjust predecessors and distances vectors
103  clear();
104  log << std::string(__FUNCTION__) << "\n";
105  predecessors.resize(graph.num_vertices());
106  distances.resize(graph.num_vertices());
107 
108  // get the graphs source and target
109  if (!graph.has_vertex(start_vertex))
110  return std::deque<Path>();
111  auto v_source(graph.get_V(start_vertex));
112 
113  std::set< V > s_v_targets;
114  for (const auto &vertex : end_vertex) {
115  if (graph.has_vertex(vertex)) {
116  s_v_targets.insert(graph.get_V(vertex));
117  }
118  }
119 
120  std::vector< V > v_targets(s_v_targets.begin(), s_v_targets.end());
121  // perform the algorithm
122  bellman_ford_1_to_many(graph, v_source);
123 
124  std::deque< Path > paths;
125  // get the results // route id are the targets
126  paths = get_paths(graph, v_source, v_targets, only_cost);
127 
128  std::stable_sort(paths.begin(), paths.end(),
129  [](const Path &e1, const Path &e2)->bool {
130  return e1.end_id() < e2.end_id();
131  });
132 
133  return paths;
134  }

References Pgr_bellman_ford< G >::bellman_ford_1_to_many(), Pgr_bellman_ford< G >::clear(), Pgr_bellman_ford< G >::distances, Pgr_bellman_ford< G >::get_paths(), pgrouting::Pgr_messages::log, and Pgr_bellman_ford< G >::predecessors.

◆ bellman_ford() [5/5]

template<class G >
Path Pgr_bellman_ford< G >::bellman_ford ( G &  graph,
int64_t  start_vertex,
int64_t  end_vertex,
bool  only_cost = false 
)
inline

BellmanFord 1 to 1.

Definition at line 62 of file pgr_bellman_ford.hpp.

66  {
67  clear();
68  log << std::string(__FUNCTION__) << "\n";
69 
70  // adjust predecessors and distances vectors
71  predecessors.resize(graph.num_vertices());
72  distances.resize(graph.num_vertices());
73 
74 
75  if (!graph.has_vertex(start_vertex)
76  || !graph.has_vertex(end_vertex)) {
77  return Path(start_vertex, end_vertex);
78  }
79 
80  // get the graphs source and target
81  auto v_source(graph.get_V(start_vertex));
82  auto v_target(graph.get_V(end_vertex));
83 
84  // perform the algorithm
85  bellman_ford_1_to_1(graph, v_source, v_target);
86 
87  // get the results
88  return Path(
89  graph,
90  v_source, v_target,
91  predecessors, distances,
92  only_cost, true);
93  }

Referenced by Pgr_bellman_ford< G >::bellman_ford(), and pgr_bellman_ford().

◆ bellman_ford_1_to_1()

template<class G >
bool Pgr_bellman_ford< G >::bellman_ford_1_to_1 ( G &  graph,
V  source 
)
inlineprivate

Call to BellmanFord 1 source to 1 target.

Definition at line 224 of file pgr_bellman_ford.hpp.

227  {
228  log << std::string(__FUNCTION__) << "\n";
229  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
230  CHECK_FOR_INTERRUPTS();
231  try {
232  boost::bellman_ford_shortest_paths(
233  graph.graph,
234  static_cast<int>(graph.num_vertices()),
235  boost::predecessor_map(&predecessors[0])
236  .weight_map(get(&G::G_T_E::cost, graph.graph))
237  .distance_map(&distances[0])
238  .root_vertex(source));
239  } catch (boost::exception const& ex) {
240  (void)ex;
241  throw;
242  } catch (std::exception &e) {
243  (void)e;
244  throw;
245  } catch (...) {
246  throw;
247  }
248  return true;
249  }

References Pgr_bellman_ford< G >::distances, pgrouting::Pgr_messages::log, and Pgr_bellman_ford< G >::predecessors.

◆ bellman_ford_1_to_many()

template<class G >
bool Pgr_bellman_ford< G >::bellman_ford_1_to_many ( G &  graph,
V  source 
)
inlineprivate

Call to BellmanFord 1 source to many targets.

Definition at line 251 of file pgr_bellman_ford.hpp.

253  {
254  log << std::string(__FUNCTION__) << "\n";
255  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
256  CHECK_FOR_INTERRUPTS();
257  try {
258  boost::bellman_ford_shortest_paths(
259  graph.graph,
260  static_cast<int>(graph.num_vertices()),
261  boost::predecessor_map(&predecessors[0])
262  .weight_map(get(&G::G_T_E::cost, graph.graph))
263  .distance_map(&distances[0])
264  .root_vertex(source));
265  } catch (boost::exception const& ex) {
266  (void)ex;
267  throw;
268  } catch (std::exception &e) {
269  (void)e;
270  throw;
271  } catch (...) {
272  throw;
273  }
274  return true;
275  }

References Pgr_bellman_ford< G >::distances, pgrouting::Pgr_messages::log, and Pgr_bellman_ford< G >::predecessors.

Referenced by Pgr_bellman_ford< G >::bellman_ford().

◆ clear()

template<class G >
void Pgr_bellman_ford< G >::clear ( )
inlineprivate

Definition at line 279 of file pgr_bellman_ford.hpp.

279  {
280  predecessors.clear();
281  distances.clear();
282  }

References Pgr_bellman_ford< G >::distances, and Pgr_bellman_ford< G >::predecessors.

Referenced by Pgr_bellman_ford< G >::bellman_ford().

◆ get_error()

std::string pgrouting::Pgr_messages::get_error ( ) const
inherited

get_error

Returns
the current contents of the log and clears the log

Definition at line 53 of file pgr_messages.cpp.

53  {
54  auto str = error.str();
55  return str;
56 }

References pgrouting::Pgr_messages::error.

Referenced by do_pgr_many_withPointsDD(), do_pgr_pickDeliver(), do_pgr_pickDeliverEuclidean(), do_pgr_withPoints(), do_pgr_withPointsKsp(), and pgrouting::vrp::Pgr_pickDeliver::Pgr_pickDeliver().

◆ get_log()

std::string pgrouting::Pgr_messages::get_log ( ) const
inherited

get_log

Returns
the current contents of the log and clears the log

Definition at line 36 of file pgr_messages.cpp.

36  {
37  auto str = log.str();
38  return str;
39 }

References pgrouting::Pgr_messages::log.

Referenced by do_pgr_bipartite(), do_pgr_boyerMyrvold(), do_pgr_LTDTree(), do_pgr_makeConnected(), do_pgr_many_withPointsDD(), do_pgr_pickDeliver(), do_pgr_pickDeliverEuclidean(), do_pgr_withPoints(), do_pgr_withPointsKsp(), pgr_bellman_ford(), pgr_dijkstraTR(), and pgrouting::vrp::Pgr_pickDeliver::Pgr_pickDeliver().

◆ get_notice()

std::string pgrouting::Pgr_messages::get_notice ( ) const
inherited

get_notice

Returns
the current contents of the log and clears the log

Definition at line 42 of file pgr_messages.cpp.

42  {
43  auto str = notice.str();
44  return str;
45 }

References pgrouting::Pgr_messages::notice.

◆ get_paths()

template<class G >
std::deque<Path> Pgr_bellman_ford< G >::get_paths ( const G &  graph,
V  source,
std::vector< V > &  targets,
bool  only_cost 
) const
inlineprivate

Definition at line 286 of file pgr_bellman_ford.hpp.

290  {
291  log << std::string(__FUNCTION__) << "\n";
292  std::deque<Path> paths;
293  for (const auto target : targets) {
294  paths.push_back(Path(
295  graph,
296  source, target,
297  predecessors, distances,
298  only_cost, true));
299  }
300  return paths;
301  }

References Pgr_bellman_ford< G >::distances, pgrouting::Pgr_messages::log, and Pgr_bellman_ford< G >::predecessors.

Referenced by Pgr_bellman_ford< G >::bellman_ford().

◆ has_error()

bool pgrouting::Pgr_messages::has_error ( ) const
inherited

get_error

Returns
the current contents of the log and clears the log

Definition at line 48 of file pgr_messages.cpp.

48  {
49  return !error.str().empty();
50 }

References pgrouting::Pgr_messages::error.

Referenced by do_pgr_many_withPointsDD(), do_pgr_withPoints(), and do_pgr_withPointsKsp().

Member Data Documentation

◆ distances

template<class G >
std::vector< double > Pgr_bellman_ford< G >::distances
private

Definition at line 308 of file pgr_bellman_ford.hpp.

Referenced by Pgr_bellman_ford< G >::bellman_ford(), Pgr_bellman_ford< G >::bellman_ford_1_to_1(), Pgr_bellman_ford< G >::bellman_ford_1_to_many(), Pgr_bellman_ford< G >::clear(), and Pgr_bellman_ford< G >::get_paths().

◆ error

std::ostringstream pgrouting::Pgr_messages::error
mutableinherited

Stores the error information.

Definition at line 85 of file pgr_messages.h.

Referenced by pgrouting::vrp::Fleet::build_fleet(), pgrouting::Pg_points_graph::check_points(), pgrouting::Pgr_messages::clear(), pgrouting::Pg_points_graph::create_new_edges(), pgrouting::Pgr_messages::get_error(), pgrouting::Pgr_messages::has_error(), pgrouting::vrp::Fleet::is_fleet_ok(), and pgrouting::vrp::Pgr_pickDeliver::Pgr_pickDeliver().

◆ log

std::ostringstream pgrouting::Pgr_messages::log
mutableinherited

Stores the hint information.

Definition at line 81 of file pgr_messages.h.

Referenced by pgrouting::vrp::Fleet::add_vehicle(), Pgr_bellman_ford< G >::bellman_ford(), Pgr_bellman_ford< G >::bellman_ford_1_to_1(), Pgr_bellman_ford< G >::bellman_ford_1_to_many(), pgrouting::alphashape::Pgr_alphaShape::build_best_alpha(), pgrouting::vrp::Fleet::build_fleet(), pgrouting::Pg_points_graph::check_points(), pgrouting::Pgr_messages::clear(), pgrouting::Pg_points_graph::create_new_edges(), pgrouting::vrp::Vehicle_pickDeliver::do_while_feasable(), pgrouting::vrp::Initial_solution::do_while_foo(), pgrouting::functions::Pgr_makeConnected< G >::generatemakeConnected(), pgrouting::Pgr_messages::get_log(), Pgr_bellman_ford< G >::get_paths(), pgrouting::vrp::Pgr_pickDeliver::get_postgres_result(), pgrouting::vrp::Vehicle::get_postgres_result(), pgrouting::vrp::Fleet::get_truck(), pgrouting::vrp::Optimize::inter_swap(), pgrouting::vrp::Fleet::is_fleet_ok(), pgrouting::vrp::Initial_solution::one_truck_all_orders(), pgrouting::vrp::Optimize::Optimize(), pgrouting::Pg_points_graph::Pg_points_graph(), pgrouting::vrp::Pgr_pickDeliver::Pgr_pickDeliver(), pgrouting::vrp::Optimize::save_if_best(), pgrouting::vrp::Solution::Solution(), pgrouting::vrp::Pgr_pickDeliver::solve(), and pgrouting::vrp::Vehicle::Vehicle().

◆ notice

std::ostringstream pgrouting::Pgr_messages::notice
mutableinherited

Stores the notice information.

Definition at line 83 of file pgr_messages.h.

Referenced by pgrouting::Pgr_messages::clear(), and pgrouting::Pgr_messages::get_notice().

◆ predecessors

template<class G >
std::vector< V > Pgr_bellman_ford< G >::predecessors
private

Definition at line 307 of file pgr_bellman_ford.hpp.

Referenced by Pgr_bellman_ford< G >::bellman_ford(), Pgr_bellman_ford< G >::bellman_ford_1_to_1(), Pgr_bellman_ford< G >::bellman_ford_1_to_many(), Pgr_bellman_ford< G >::clear(), and Pgr_bellman_ford< G >::get_paths().

The documentation for this class was generated from the following file:
Path
Definition: basePath_SSEC.hpp:47
Pgr_bellman_ford::bellman_ford
Path bellman_ford(G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
BellmanFord 1 to 1.
Definition: pgr_bellman_ford.hpp:62
pgrouting::Pgr_messages::error
std::ostringstream error
Stores the error information.
Definition: pgr_messages.h:85
pgrouting::Pgr_messages::log
std::ostringstream log
Stores the hint information.
Definition: pgr_messages.h:81
pgr_combination_t
Definition: pgr_combination_t.h:43
Pgr_bellman_ford::clear
void clear()
Definition: pgr_bellman_ford.hpp:279
Pgr_bellman_ford::bellman_ford_1_to_1
bool bellman_ford_1_to_1(G &graph, V source)
Call to BellmanFord 1 source to 1 target.
Definition: pgr_bellman_ford.hpp:224
pgrouting::Pgr_messages::notice
std::ostringstream notice
Stores the notice information.
Definition: pgr_messages.h:83
Pgr_bellman_ford::distances
std::vector< double > distances
Definition: pgr_bellman_ford.hpp:308
Pgr_bellman_ford::predecessors
std::vector< V > predecessors
Definition: pgr_bellman_ford.hpp:307
Pgr_bellman_ford::get_paths
std::deque< Path > get_paths(const G &graph, V source, std::vector< V > &targets, bool only_cost) const
Definition: pgr_bellman_ford.hpp:286
Pgr_bellman_ford::bellman_ford_1_to_many
bool bellman_ford_1_to_many(G &graph, V source)
Call to BellmanFord 1 source to many targets.
Definition: pgr_bellman_ford.hpp:251