PGROUTING  2.6
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
 exception for termination More...
 

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)
 

Private Member Functions

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
 

Private Attributes

members;
std::vector< Vpredecessors
 
std::vector< double > distances
 
std::deque< VnodesInDistance
 

Detailed Description

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

Definition at line 52 of file pgr_astar.hpp.

Member Typedef Documentation

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

Definition at line 55 of file pgr_astar.hpp.

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

Definition at line 54 of file pgr_astar.hpp.

Member Function Documentation

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 67 of file pgr_astar.hpp.

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

74  {
75  clear();
76 
77  predecessors.resize(graph.num_vertices());
78  distances.resize(graph.num_vertices());
79 
80  if (!graph.has_vertex(start_vertex)
81  || !graph.has_vertex(end_vertex)) {
82  return Path(start_vertex, end_vertex);
83  }
84 
85  auto v_source(graph.get_V(start_vertex));
86  auto v_target(graph.get_V(end_vertex));
87 
88  // perform the algorithm
89  astar_1_to_1(graph, v_source, v_target, heuristic, factor, epsilon);
90 
91  return Path(graph,
92  v_source, v_target,
94  only_cost);
95  }
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:280
std::vector< double > distances
Definition: pgr_astar.hpp:173

Here is the caller graph for this function:

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 98 of file pgr_astar.hpp.

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

105  {
106  clear();
107 
108  predecessors.resize(graph.num_vertices());
109  distances.resize(graph.num_vertices());
110 
111  if (!graph.has_vertex(start_vertex)) return std::deque<Path>();
112  auto v_source(graph.get_V(start_vertex));
113 
114  std::vector<V> v_targets;
115  for (const auto &vertex : end_vertex) {
116  if (graph.has_vertex(vertex)) {
117  v_targets.push_back(graph.get_V(vertex));
118  }
119  }
120 
121  astar_1_to_many(graph,
122  v_source,
123  v_targets,
124  heuristic,
125  factor,
126  epsilon);
127 
128  auto paths = get_paths(graph, v_source, v_targets, only_cost);
129 
130  std::stable_sort(paths.begin(), paths.end(),
131  [](const Path &e1, const Path &e2)->bool {
132  return e1.end_id() < e2.end_id();
133  });
134 
135  return paths;
136  }
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:307
std::deque< Path > get_paths(const G &graph, V source, const std::vector< V > &targets, bool only_cost) const
Definition: pgr_astar.hpp:338
int64_t end_id() const
std::vector< double > distances
Definition: pgr_astar.hpp:173

Here is the call graph for this function:

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 139 of file pgr_astar.hpp.

References pgrouting::algorithms::Pgr_astar< G >::astar(), Path::end_id(), and Path::start_id().

146  {
147  std::deque<Path> paths;
148  for (const auto &start : start_vertex) {
149  auto r_paths = astar(graph, start, end_vertex,
150  heuristic, factor, epsilon, only_cost);
151  paths.insert(paths.begin(), r_paths.begin(), r_paths.end());
152  }
153 
154  std::sort(paths.begin(), paths.end(),
155  [](const Path &e1, const Path &e2)->bool {
156  return e1.end_id() < e2.end_id();
157  });
158  std::stable_sort(paths.begin(), paths.end(),
159  [](const Path &e1, const Path &e2)->bool {
160  return e1.start_id() < e2.start_id();
161  });
162  return paths;
163  }
int64_t end_id() const
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:67
int64_t start_id() const

Here is the call graph for this function:

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 280 of file pgr_astar.hpp.

References pgrouting::Basic_edge::cost.

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

286  {
287  bool found = false;
288  try {
289  // Call A* named parameter interface
290  boost::astar_search(
291  graph.graph, source,
292  distance_heuristic(graph.graph, target,
293  heuristic, factor * epsilon),
294  boost::predecessor_map(&predecessors[0])
295  .weight_map(get(&pgrouting::Basic_edge::cost, graph.graph))
296  .distance_map(&distances[0])
297  .visitor(astar_one_goal_visitor(target)));
298  }
299  catch(found_goals &) {
300  found = true; // Target vertex found
301  }
302  return found;
303  }
std::vector< double > distances
Definition: pgr_astar.hpp:173

Here is the caller graph for this function:

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 307 of file pgr_astar.hpp.

References pgrouting::Basic_edge::cost.

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

313  {
314  bool found = false;
315  try {
316  boost::astar_search(
317  graph.graph, source,
318  distance_heuristic(
319  graph.graph, targets,
320  heuristic, factor * epsilon),
321  boost::predecessor_map(&predecessors[0])
322  .weight_map(get(&pgrouting::Basic_edge::cost, graph.graph))
323  .distance_map(&distances[0])
324  .visitor(astar_many_goals_visitor(targets)));
325  }
326  catch(found_goals &) {
327  found = true; // Target vertex found
328  }
329  return found;
330  }
std::vector< double > distances
Definition: pgr_astar.hpp:173

Here is the caller graph for this function:

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

Definition at line 58 of file pgr_astar.hpp.

References pgrouting::algorithms::Pgr_astar< G >::astar(), pgrouting::algorithms::Pgr_astar< G >::astar_1_to_1(), pgrouting::algorithms::Pgr_astar< G >::distances, and pgrouting::algorithms::Pgr_astar< G >::predecessors.

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

58  {
59  predecessors.clear();
60  distances.clear();
61  }
std::vector< double > distances
Definition: pgr_astar.hpp:173

Here is the call graph for this function:

Here is the caller graph for this function:

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 338 of file pgr_astar.hpp.

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

342  {
343  std::deque<Path> paths;
344  for (const auto &target : targets) {
345  paths.push_back(
346  Path(graph,
347  source, target,
349  only_cost));
350  }
351  return paths;
352  }
std::vector< double > distances
Definition: pgr_astar.hpp:173

Here is the caller graph for this function:

Member Data Documentation

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

Definition at line 174 of file pgr_astar.hpp.

template<class G>
std::vector< V > pgrouting::algorithms::Pgr_astar< G >::predecessors
private

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