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< Path >	astar (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< Path >	astar (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< Path >	astar (G &graph, const std::vector< pgr_combination_t > &combinations, int heuristic, double factor, double epsilon, bool only_cost)

members;
std::vector< V >	predecessors
std::vector< double >	distances
std::deque< V >	nodesInDistance
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< Path >	get_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.

                             {
         // a call to 1 to many is faster for each of the sources
         std::deque<Path> paths;
 
         // group targets per distinct source
         std::map< int64_t, std::vector<int64_t> > vertex_map;
         for (const pgr_combination_t &comb : combinations) {
             std::map< int64_t, std::vector<int64_t> >::iterator it = vertex_map.find(comb.source);
             if (it != vertex_map.end()) {
                 it->second.push_back(comb.target);
             } else {
                 std::vector<int64_t > targets{comb.target};
                 vertex_map[comb.source] = targets;
             }
         }
 
         for (const auto &start_ends : vertex_map) {
             auto r_paths = astar(
                     graph,
                     start_ends.first, start_ends.second,
                     heuristic, factor, epsilon, only_cost);
             paths.insert(paths.end(), r_paths.begin(), r_paths.end());
         }
 
         return paths;
     }

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.

                             {
         clear();
 
         predecessors.resize(graph.num_vertices());
         distances.resize(graph.num_vertices());
 
         if (!graph.has_vertex(start_vertex)
                 || !graph.has_vertex(end_vertex)) {
             return Path(start_vertex, end_vertex);
         }
 
         auto v_source(graph.get_V(start_vertex));
         auto v_target(graph.get_V(end_vertex));
 
         // perform the algorithm
         astar_1_to_1(graph, v_source, v_target, heuristic, factor, epsilon);
 
         auto solution = Path(graph, Path(graph,
                 v_source, v_target,
                 predecessors, distances,
                 false), only_cost);
 
         return solution;
     }

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.

                             {
         clear();
 
         predecessors.resize(graph.num_vertices());
         distances.resize(graph.num_vertices());
 
         if (!graph.has_vertex(start_vertex)) return std::deque<Path>();
         auto v_source(graph.get_V(start_vertex));
 
         std::vector<V> v_targets;
         for (const auto &vertex : end_vertex) {
             if (graph.has_vertex(vertex)) {
                 v_targets.push_back(graph.get_V(vertex));
             }
         }
 
         astar_1_to_many(graph,
                 v_source,
                 v_targets,
                 heuristic,
                 factor,
                 epsilon);
 
         auto paths = get_paths(graph, v_source, v_targets, only_cost);
 
         std::stable_sort(paths.begin(), paths.end(),
                 [](const Path &e1, const Path &e2)->bool {
                 return e1.end_id() < e2.end_id();
                 });
 
         return paths;
     }

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.

                             {
         std::deque<Path> paths;
         for (const auto &start : start_vertex) {
             auto r_paths = astar(graph, start, end_vertex,
                     heuristic, factor, epsilon, only_cost);
              paths.insert(paths.begin(), r_paths.begin(), r_paths.end());
         }
 
         std::sort(paths.begin(), paths.end(),
                 [](const Path &e1, const Path &e2)->bool {
                 return e1.end_id() < e2.end_id();
                 });
         std::stable_sort(paths.begin(), paths.end(),
                 [](const Path &e1, const Path &e2)->bool {
                 return e1.start_id() < e2.start_id();
                 });
         return paths;
     }

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.

                             {
         bool found = false;
         /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
         CHECK_FOR_INTERRUPTS();
         try {
             // Call A* named parameter interface
             boost::astar_search(
                     graph.graph, source,
                     distance_heuristic(graph.graph, target,
                         heuristic, factor * epsilon),
                     boost::predecessor_map(&predecessors[0])
                     .weight_map(get(&pgrouting::Basic_edge::cost, graph.graph))
                     .distance_map(&distances[0])
                     .visitor(astar_one_goal_visitor(target)));
         }
         catch(found_goals &) {
             found = true;  // Target vertex found
         }
         return found;
     }

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.

                             {
         bool found = false;
         /* abort in case of an interruption occurs (e.g. the query is being cancelled) */
         CHECK_FOR_INTERRUPTS();
         try {
             boost::astar_search(
                     graph.graph, source,
                     distance_heuristic(
                         graph.graph, targets,
                         heuristic, factor * epsilon),
                     boost::predecessor_map(&predecessors[0])
                     .weight_map(get(&pgrouting::Basic_edge::cost, graph.graph))
                     .distance_map(&distances[0])
                     .visitor(astar_many_goals_visitor(targets)));
         }
         catch(found_goals &) {
             found = true;  // Target vertex found
         }
         return found;
     }

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

Definition at line 60 of file pgr_astar.hpp.

                  {
         predecessors.clear();
         distances.clear();
     }

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

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

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.

                                   {
         std::deque<Path> paths;
         for (const auto &target : targets) {
             auto p = Path(graph,
                         source, target,
                         predecessors, distances,
                         false);
             paths.push_back(Path(graph, p, only_cost));
         }
         return paths;
     }

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

template<class G >

std::vector< double > pgrouting::algorithms::Pgr_astar< G >::distances

private

Definition at line 211 of file pgr_astar.hpp.

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

nodesInDistance

template<class G >

std::deque< V > pgrouting::algorithms::Pgr_astar< G >::nodesInDistance

private

Definition at line 212 of file pgr_astar.hpp.

predecessors

template<class G >

std::vector< V > pgrouting::algorithms::Pgr_astar< G >::predecessors

private

Definition at line 210 of file pgr_astar.hpp.

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

---

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

• pgr_astar.hpp