PGROUTING  3.2
pgrouting::algorithms::Pgr_astar< G > Class Template Reference

#include "pgr_astar.hpp"

Collaboration diagram for pgrouting::algorithms::Pgr_astar< G >:

Classes

class  astar_many_goals_visitor
 class for stopping when all targets are found More...
 
class  astar_one_goal_visitor
 visitor that terminates when we find the goal More...
 
class  distance_heuristic
 
struct  found_goals
 

Public Types

typedef G::B_G B_G
 
typedef G::V V
 

Public Member Functions

void clear ()
 
Astar
Path astar (G &graph, int64_t start_vertex, int64_t end_vertex, int heuristic, double factor, double epsilon, bool only_cost)
 one to one astar 1 to 1 More...
 
std::deque< Pathastar (G &graph, int64_t start_vertex, std::vector< int64_t > end_vertex, int heuristic, double factor, double epsilon, bool only_cost)
 astar 1 to many More...
 
std::deque< Pathastar (G &graph, std::vector< int64_t > start_vertex, std::vector< int64_t > end_vertex, int heuristic, double factor, double epsilon, bool only_cost)
 
std::deque< Pathastar (G &graph, const std::vector< pgr_combination_t > &combinations, int heuristic, double factor, double epsilon, bool only_cost)
 

members;

std::vector< Vpredecessors
 
std::vector< double > distances
 
std::deque< VnodesInDistance
 
bool astar_1_to_1 (G &graph, V source, V target, int heuristic, double factor, double epsilon)
 Call to Astar 1 source to 1 target. More...
 
bool astar_1_to_many (G &graph, V source, const std::vector< V > &targets, int heuristic, double factor, double epsilon)
 Call to astar 1 source to many targets. More...
 
std::deque< Pathget_paths (const G &graph, V source, const std::vector< V > &targets, bool only_cost) const
 

Detailed Description

template<class G>
class pgrouting::algorithms::Pgr_astar< G >

Definition at line 54 of file pgr_astar.hpp.

Member Typedef Documentation

◆ B_G

template<class G >
typedef G::B_G pgrouting::algorithms::Pgr_astar< G >::B_G

Definition at line 57 of file pgr_astar.hpp.

◆ V

template<class G >
typedef G::V pgrouting::algorithms::Pgr_astar< G >::V

Definition at line 56 of file pgr_astar.hpp.

Member Function Documentation

◆ astar() [1/4]

template<class G >
std::deque<Path> pgrouting::algorithms::Pgr_astar< G >::astar ( G &  graph,
const std::vector< pgr_combination_t > &  combinations,
int  heuristic,
double  factor,
double  epsilon,
bool  only_cost 
)
inline

Definition at line 170 of file pgr_astar.hpp.

176  {
177  // a call to 1 to many is faster for each of the sources
178  std::deque<Path> paths;
179 
180  // group targets per distinct source
181  std::map< int64_t, std::vector<int64_t> > vertex_map;
182  for (const pgr_combination_t &comb : combinations) {
183  std::map< int64_t, std::vector<int64_t> >::iterator it = vertex_map.find(comb.source);
184  if (it != vertex_map.end()) {
185  it->second.push_back(comb.target);
186  } else {
187  std::vector<int64_t > targets{comb.target};
188  vertex_map[comb.source] = targets;
189  }
190  }
191 
192  for (const auto &start_ends : vertex_map) {
193  auto r_paths = astar(
194  graph,
195  start_ends.first, start_ends.second,
196  heuristic, factor, epsilon, only_cost);
197  paths.insert(paths.end(), r_paths.begin(), r_paths.end());
198  }
199 
200  return paths;
201  }

References pgrouting::algorithms::Pgr_astar< G >::astar().

◆ astar() [2/4]

template<class G >
Path pgrouting::algorithms::Pgr_astar< G >::astar ( G &  graph,
int64_t  start_vertex,
int64_t  end_vertex,
int  heuristic,
double  factor,
double  epsilon,
bool  only_cost 
)
inline

one to one astar 1 to 1

Definition at line 69 of file pgr_astar.hpp.

76  {
77  clear();
78 
79  predecessors.resize(graph.num_vertices());
80  distances.resize(graph.num_vertices());
81 
82  if (!graph.has_vertex(start_vertex)
83  || !graph.has_vertex(end_vertex)) {
84  return Path(start_vertex, end_vertex);
85  }
86 
87  auto v_source(graph.get_V(start_vertex));
88  auto v_target(graph.get_V(end_vertex));
89 
90  // perform the algorithm
91  astar_1_to_1(graph, v_source, v_target, heuristic, factor, epsilon);
92 
93  auto solution = Path(graph, Path(graph,
94  v_source, v_target,
96  false), only_cost);
97 
98  return solution;
99  }

Referenced by pgrouting::algorithms::Pgr_astar< G >::astar(), and pgr_astar().

◆ astar() [3/4]

template<class G >
std::deque<Path> pgrouting::algorithms::Pgr_astar< G >::astar ( G &  graph,
int64_t  start_vertex,
std::vector< int64_t >  end_vertex,
int  heuristic,
double  factor,
double  epsilon,
bool  only_cost 
)
inline

astar 1 to many

Definition at line 102 of file pgr_astar.hpp.

109  {
110  clear();
111 
112  predecessors.resize(graph.num_vertices());
113  distances.resize(graph.num_vertices());
114 
115  if (!graph.has_vertex(start_vertex)) return std::deque<Path>();
116  auto v_source(graph.get_V(start_vertex));
117 
118  std::vector<V> v_targets;
119  for (const auto &vertex : end_vertex) {
120  if (graph.has_vertex(vertex)) {
121  v_targets.push_back(graph.get_V(vertex));
122  }
123  }
124 
125  astar_1_to_many(graph,
126  v_source,
127  v_targets,
128  heuristic,
129  factor,
130  epsilon);
131 
132  auto paths = get_paths(graph, v_source, v_targets, only_cost);
133 
134  std::stable_sort(paths.begin(), paths.end(),
135  [](const Path &e1, const Path &e2)->bool {
136  return e1.end_id() < e2.end_id();
137  });
138 
139  return paths;
140  }

References pgrouting::algorithms::Pgr_astar< G >::astar_1_to_many(), pgrouting::algorithms::Pgr_astar< G >::clear(), pgrouting::algorithms::Pgr_astar< G >::distances, pgrouting::algorithms::Pgr_astar< G >::get_paths(), and pgrouting::algorithms::Pgr_astar< G >::predecessors.

◆ astar() [4/4]

template<class G >
std::deque<Path> pgrouting::algorithms::Pgr_astar< G >::astar ( G &  graph,
std::vector< int64_t >  start_vertex,
std::vector< int64_t >  end_vertex,
int  heuristic,
double  factor,
double  epsilon,
bool  only_cost 
)
inline

Definition at line 143 of file pgr_astar.hpp.

150  {
151  std::deque<Path> paths;
152  for (const auto &start : start_vertex) {
153  auto r_paths = astar(graph, start, end_vertex,
154  heuristic, factor, epsilon, only_cost);
155  paths.insert(paths.begin(), r_paths.begin(), r_paths.end());
156  }
157 
158  std::sort(paths.begin(), paths.end(),
159  [](const Path &e1, const Path &e2)->bool {
160  return e1.end_id() < e2.end_id();
161  });
162  std::stable_sort(paths.begin(), paths.end(),
163  [](const Path &e1, const Path &e2)->bool {
164  return e1.start_id() < e2.start_id();
165  });
166  return paths;
167  }

References pgrouting::algorithms::Pgr_astar< G >::astar().

◆ astar_1_to_1()

template<class G >
bool pgrouting::algorithms::Pgr_astar< G >::astar_1_to_1 ( G &  graph,
V  source,
V  target,
int  heuristic,
double  factor,
double  epsilon 
)
inlineprivate

Call to Astar 1 source to 1 target.

Definition at line 324 of file pgr_astar.hpp.

330  {
331  bool found = false;
332  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
333  CHECK_FOR_INTERRUPTS();
334  try {
335  // Call A* named parameter interface
336  boost::astar_search(
337  graph.graph, source,
338  distance_heuristic(graph.graph, target,
339  heuristic, factor * epsilon),
340  boost::predecessor_map(&predecessors[0])
341  .weight_map(get(&pgrouting::Basic_edge::cost, graph.graph))
342  .distance_map(&distances[0])
343  .visitor(astar_one_goal_visitor(target)));
344  }
345  catch(found_goals &) {
346  found = true; // Target vertex found
347  }
348  return found;
349  }

References pgrouting::Basic_edge::cost, pgrouting::algorithms::Pgr_astar< G >::distances, and pgrouting::algorithms::Pgr_astar< G >::predecessors.

◆ astar_1_to_many()

template<class G >
bool pgrouting::algorithms::Pgr_astar< G >::astar_1_to_many ( G &  graph,
V  source,
const std::vector< V > &  targets,
int  heuristic,
double  factor,
double  epsilon 
)
inlineprivate

Call to astar 1 source to many targets.

Definition at line 353 of file pgr_astar.hpp.

359  {
360  bool found = false;
361  /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
362  CHECK_FOR_INTERRUPTS();
363  try {
364  boost::astar_search(
365  graph.graph, source,
366  distance_heuristic(
367  graph.graph, targets,
368  heuristic, factor * epsilon),
369  boost::predecessor_map(&predecessors[0])
370  .weight_map(get(&pgrouting::Basic_edge::cost, graph.graph))
371  .distance_map(&distances[0])
372  .visitor(astar_many_goals_visitor(targets)));
373  }
374  catch(found_goals &) {
375  found = true; // Target vertex found
376  }
377  return found;
378  }

References pgrouting::Basic_edge::cost, pgrouting::algorithms::Pgr_astar< G >::distances, and pgrouting::algorithms::Pgr_astar< G >::predecessors.

Referenced by pgrouting::algorithms::Pgr_astar< G >::astar().

◆ clear()

template<class G >
void pgrouting::algorithms::Pgr_astar< G >::clear ( )
inline

◆ get_paths()

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

Definition at line 386 of file pgr_astar.hpp.

390  {
391  std::deque<Path> paths;
392  for (const auto &target : targets) {
393  auto p = Path(graph,
394  source, target,
396  false);
397  paths.push_back(Path(graph, p, only_cost));
398  }
399  return paths;
400  }

References pgrouting::algorithms::Pgr_astar< G >::distances, and pgrouting::algorithms::Pgr_astar< G >::predecessors.

Referenced by pgrouting::algorithms::Pgr_astar< G >::astar().

Member Data Documentation

◆ distances

◆ nodesInDistance

template<class G >
std::deque< V > pgrouting::algorithms::Pgr_astar< G >::nodesInDistance
private

Definition at line 212 of file pgr_astar.hpp.

◆ predecessors


The documentation for this class was generated from the following file:
pgrouting::algorithms::Pgr_astar::distances
std::vector< double > distances
Definition: pgr_astar.hpp:211
Path
Definition: basePath_SSEC.hpp:47
pgrouting::algorithms::Pgr_astar::clear
void clear()
Definition: pgr_astar.hpp:60
pgrouting::algorithms::Pgr_astar::astar_1_to_1
bool astar_1_to_1(G &graph, V source, V target, int heuristic, double factor, double epsilon)
Call to Astar 1 source to 1 target.
Definition: pgr_astar.hpp:324
pgr_combination_t
Definition: pgr_combination_t.h:43
pgrouting::algorithms::Pgr_astar::astar_1_to_many
bool astar_1_to_many(G &graph, V source, const std::vector< V > &targets, int heuristic, double factor, double epsilon)
Call to astar 1 source to many targets.
Definition: pgr_astar.hpp:353
pgrouting::algorithms::Pgr_astar::predecessors
std::vector< V > predecessors
Definition: pgr_astar.hpp:210
pgrouting::Basic_edge::cost
double cost
Definition: basic_edge.h:44
pgrouting::algorithms::Pgr_astar::get_paths
std::deque< Path > get_paths(const G &graph, V source, const std::vector< V > &targets, bool only_cost) const
Definition: pgr_astar.hpp:386
pgrouting::algorithms::Pgr_astar::astar
Path astar(G &graph, int64_t start_vertex, int64_t end_vertex, int heuristic, double factor, double epsilon, bool only_cost)
one to one astar 1 to 1
Definition: pgr_astar.hpp:69