#include "pgr_bdAstar.hpp"

Inheritance diagram for pgrouting::bidirectional::Pgr_bdAstar< G >:

Collaboration diagram for pgrouting::bidirectional::Pgr_bdAstar< G >:

Public Member Functions
	Pgr_bdAstar (G &pgraph)

	~Pgr_bdAstar ()=default

void	clean_log ()

void	clear ()

std::string	log () const

Path	pgr_bdAstar (V start_vertex, V end_vertex, int heuristic, double factor, double epsilon, bool only_cost)

Protected Types
typedef std::priority_queue< Cost_Vertex_pair, std::vector< Cost_Vertex_pair >, std::greater< Cost_Vertex_pair > >	Priority_queue

Protected Member Functions
Path	bidirectional (bool only_cost)

bool	found (const V &node)

void	initialize ()

Protected Attributes
std::vector< double >	backward_cost

std::vector< int64_t >	backward_edge

std::vector< bool >	backward_finished

std::vector< V >	backward_predecessor

Priority_queue	backward_queue

double	best_cost

bool	cost_only

std::vector< double >	forward_cost

std::vector< int64_t >	forward_edge

std::vector< bool >	forward_finished

std::vector< V >	forward_predecessor

Priority_queue	forward_queue

G &	graph

double	INF
	infinity More...

std::ostringstream	m_log

V	v_min_node
	target descriptor More...

V	v_source
	source descriptor More...

V	v_target
	target descriptor More...

Private Types
typedef Pgr_bidirectional< G >::Cost_Vertex_pair	Cost_Vertex_pair

typedef Pgr_bidirectional< G >::E	E

typedef Pgr_bidirectional< G >::V	V

Private Member Functions
void	explore_backward (const Cost_Vertex_pair &node)

void	explore_forward (const Cost_Vertex_pair &node)

double	heuristic (V v, V u)

Private Attributes
double	m_factor

int	m_heuristic

Detailed Description

template<typename G>
class pgrouting::bidirectional::Pgr_bdAstar< G >

Definition at line 50 of file pgr_bdAstar.hpp.

Member Typedef Documentation

◆ Cost_Vertex_pair

template<typename G >

typedef Pgr_bidirectional<G>::Cost_Vertex_pair pgrouting::bidirectional::Pgr_bdAstar< G >::Cost_Vertex_pair

private

Definition at line 53 of file pgr_bdAstar.hpp.

◆ E

template<typename G >

typedef Pgr_bidirectional<G>::E pgrouting::bidirectional::Pgr_bdAstar< G >::E

private

Definition at line 52 of file pgr_bdAstar.hpp.

◆ Priority_queue

template<typename G >

typedef std::priority_queue< Cost_Vertex_pair, std::vector<Cost_Vertex_pair>, std::greater<Cost_Vertex_pair> > pgrouting::bidirectional::Pgr_bidirectional< G >::Priority_queue

protectedinherited

Definition at line 71 of file pgr_bidirectional.hpp.

◆ V

template<typename G >

typedef Pgr_bidirectional<G>::V pgrouting::bidirectional::Pgr_bdAstar< G >::V

private

Definition at line 51 of file pgr_bdAstar.hpp.

Constructor & Destructor Documentation

◆ Pgr_bdAstar()

template<typename G >

pgrouting::bidirectional::Pgr_bdAstar< G >::Pgr_bdAstar ( G & pgraph )

inlineexplicit

Definition at line 77 of file pgr_bdAstar.hpp.

                                     :
         Pgr_bidirectional<G>(pgraph),
         m_heuristic(5),
         m_factor(1.0) {
         m_log << "pgr_bdAstar constructor\n";
     }

References pgrouting::bidirectional::Pgr_bidirectional< G >::m_log.

◆ ~Pgr_bdAstar()

template<typename G >

pgrouting::bidirectional::Pgr_bdAstar< G >::~Pgr_bdAstar ( )

default

Member Function Documentation

◆ bidirectional()

template<typename G >

Path pgrouting::bidirectional::Pgr_bidirectional< G >::bidirectional ( bool only_cost )

inlineprotectedinherited

Definition at line 122 of file pgr_bidirectional.hpp.

                                        {
         m_log << "bidir_astar\n";
  
         Pgr_bidirectional< G >::initialize();
  
         forward_cost[v_source] = 0;
         forward_queue.push(std::make_pair(0.0, v_source));
  
  
         backward_cost[v_target] = 0;
         backward_queue.push(std::make_pair(0.0, v_target));
  
         while (!forward_queue.empty() &&  !backward_queue.empty()) {
             auto forward_node = forward_queue.top();
             auto backward_node = backward_queue.top();
             /*
              * done: there is no path with lower cost
              */
             if (forward_node.first == INF || backward_node.first == INF) {
                 break;
             }
  
             /*
              * Explore from the cheapest side
              */
             if (backward_node.first < forward_node.first) {
                 backward_queue.pop();
                 if (!backward_finished[backward_node.second]) {
                     explore_backward(backward_node);
                 }
                 if (found(backward_node.second)) {
                     break;
                 }
             } else {
                 forward_queue.pop();
                 if (!forward_finished[forward_node.second]) {
                     explore_forward(forward_node);
                 }
                 if (found(forward_node.second)) {
                     break;
                 }
             }
         }
  
         if (best_cost == INF) return Path();
  
         Path forward_path(
                 graph,
                 v_source,
                 v_min_node,
                 forward_predecessor,
                 forward_cost,
                 false,
                 true);
         Path backward_path(
                 graph,
                 v_target,
                 v_min_node,
                 backward_predecessor,
                 backward_cost,
                 false,
                 false);
         m_log << forward_path;
         backward_path.reverse();
         m_log << backward_path;
         forward_path.append(backward_path);
         auto p = Path(graph, forward_path, only_cost);
         m_log << forward_path;
         m_log << p;
         return p;
     }

Referenced by pgrouting::bidirectional::Pgr_bdAstar< G >::pgr_bdAstar(), and pgrouting::bidirectional::Pgr_bdDijkstra< G >::pgr_bdDijkstra().

◆ clean_log()

template<typename G >

void pgrouting::bidirectional::Pgr_bidirectional< G >::clean_log ( )

inlineinherited

Definition at line 85 of file pgr_bidirectional.hpp.

85 {m_log.clear();}

References pgrouting::bidirectional::Pgr_bidirectional< G >::m_log.

◆ clear()

template<typename G >

void pgrouting::bidirectional::Pgr_bidirectional< G >::clear ( )

inlineinherited

Definition at line 86 of file pgr_bidirectional.hpp.

                  {
         while (!forward_queue.empty()) forward_queue.pop();
         while (!backward_queue.empty()) backward_queue.pop();
  
         backward_finished.clear();
         backward_edge.clear();
         backward_predecessor.clear();
         backward_cost.clear();
  
         forward_finished.clear();
         forward_edge.clear();
         forward_predecessor.clear();
         forward_cost.clear();
     }

Referenced by pgrouting::bidirectional::Pgr_bidirectional< G >::initialize(), pgr_bdAstar(), and pgr_bdDijkstra().

◆ explore_backward()

template<typename G >

void pgrouting::bidirectional::Pgr_bdAstar< G >::explore_backward ( const Cost_Vertex_pair & node )

inlineprivatevirtual

Implements pgrouting::bidirectional::Pgr_bidirectional< G >.

Definition at line 130 of file pgr_bdAstar.hpp.

                                                         {
         typename G::EI_i in, in_end;
  
         auto current_cost = node.first;
         auto current_node = node.second;
  
         for (boost::tie(in, in_end) = in_edges(current_node, graph.graph);
                 in != in_end; ++in) {
             auto edge_cost = graph[*in].cost;
             auto next_node = graph.adjacent(current_node, *in);
  
             if (backward_finished[next_node]) continue;
  
             if (edge_cost + current_cost < backward_cost[next_node]) {
                 backward_cost[next_node] = edge_cost + current_cost;
                 backward_predecessor[next_node] = current_node;
                 backward_edge[next_node] = graph[*in].id;
                 backward_queue.push({
                         backward_cost[next_node]
                             + heuristic(next_node, v_source),
                         next_node});
             }
         }
         backward_finished[current_node] = true;
     }

◆ explore_forward()

template<typename G >

void pgrouting::bidirectional::Pgr_bdAstar< G >::explore_forward ( const Cost_Vertex_pair & node )

inlineprivatevirtual

Implements pgrouting::bidirectional::Pgr_bidirectional< G >.

Definition at line 104 of file pgr_bdAstar.hpp.

                                                        {
         typename G::EO_i out, out_end;
  
         auto current_cost = node.first;
         auto current_node = node.second;
  
         for (boost::tie(out, out_end) = out_edges(current_node, graph.graph);
                 out != out_end; ++out) {
             auto edge_cost = graph[*out].cost;
             auto next_node = graph.adjacent(current_node, *out);
  
             if (forward_finished[next_node]) continue;
  
             if (edge_cost + current_cost < forward_cost[next_node]) {
                 forward_cost[next_node] = edge_cost + current_cost;
                 forward_predecessor[next_node] = current_node;
                 forward_edge[next_node] = graph[*out].id;
                 forward_queue.push({
                         forward_cost[next_node]
                             + heuristic(next_node, v_target),
                         next_node});
             }
         }
         forward_finished[current_node] = true;
     }

◆ found()

template<typename G >

bool pgrouting::bidirectional::Pgr_bidirectional< G >::found ( const V & node )

inlineprotectedinherited

Definition at line 196 of file pgr_bidirectional.hpp.

                               {
         /*
          * Update common node
          */
         if (forward_finished[node] && backward_finished[node]) {
             if (best_cost >= forward_cost[node] + backward_cost[node]) {
                 v_min_node = node;
                 best_cost =  forward_cost[node] + backward_cost[node];
                 return false;
             } else {
                 return true;
             }
         }
         return false;
     }

References pgrouting::bidirectional::Pgr_bidirectional< G >::backward_cost, pgrouting::bidirectional::Pgr_bidirectional< G >::backward_finished, pgrouting::bidirectional::Pgr_bidirectional< G >::best_cost, pgrouting::bidirectional::Pgr_bidirectional< G >::forward_cost, pgrouting::bidirectional::Pgr_bidirectional< G >::forward_finished, and pgrouting::bidirectional::Pgr_bidirectional< G >::v_min_node.

Referenced by pgrouting::bidirectional::Pgr_bidirectional< G >::bidirectional().

◆ heuristic()

template<typename G >

double pgrouting::bidirectional::Pgr_bdAstar< G >::heuristic	(	V	v,
		V	u
	)

inlineprivate

Definition at line 157 of file pgr_bdAstar.hpp.

                                {
         if (m_heuristic == 0) return 0;
  
         double dx = graph[v].x() - graph[u].x();
         double dy = graph[v].y() - graph[u].y();
         double current;
  
         switch (m_heuristic) {
             case 0:
                 current = 0;
                 break;
             case 1:
                 current = std::fabs((std::max)(dx, dy)) * m_factor;
                 break;
             case 2:
                 current = std::fabs((std::min)(dx, dy)) * m_factor;
                 break;
             case 3:
                 current = (dx * dx + dy * dy) * m_factor * m_factor;
                 break;
             case 4:
                 current = std::sqrt(dx * dx + dy * dy) * m_factor;
                 break;
             case 5:
                 current = (std::fabs(dx) + std::fabs(dy)) * m_factor;
                 break;
             default:
                 current = 0;
         }
         return current;
     }

References pgrouting::bidirectional::Pgr_bidirectional< G >::graph, pgrouting::bidirectional::Pgr_bdAstar< G >::m_factor, and pgrouting::bidirectional::Pgr_bdAstar< G >::m_heuristic.

Referenced by pgrouting::bidirectional::Pgr_bdAstar< G >::explore_backward(), pgrouting::bidirectional::Pgr_bdAstar< G >::explore_forward(), and pgrouting::bidirectional::Pgr_bdAstar< G >::pgr_bdAstar().

◆ initialize()

template<typename G >

void pgrouting::bidirectional::Pgr_bidirectional< G >::initialize ( )

inlineprotectedinherited

Definition at line 103 of file pgr_bidirectional.hpp.

                       {
         m_log << "initializing\n";
         clear();
         forward_predecessor.resize(graph.num_vertices());
         forward_finished.resize(graph.num_vertices(), false);
         forward_edge.resize(graph.num_vertices(), -1);
         forward_cost.resize(graph.num_vertices(), INF);
         std::iota(forward_predecessor.begin(), forward_predecessor.end(), 0);
  
         backward_predecessor.resize(graph.num_vertices());
         backward_finished.resize(graph.num_vertices(), false);
         backward_edge.resize(graph.num_vertices(), -1);
         backward_cost.resize(graph.num_vertices(), INF);
         std::iota(backward_predecessor.begin(), backward_predecessor.end(), 0);
  
         v_min_node = 0;
         best_cost = INF;
     }

Referenced by pgrouting::bidirectional::Pgr_bidirectional< G >::bidirectional().

◆ log()

template<typename G >

std::string pgrouting::bidirectional::Pgr_bidirectional< G >::log ( ) const

inlineinherited

Definition at line 84 of file pgr_bidirectional.hpp.

84 {return m_log.str();}

References pgrouting::bidirectional::Pgr_bidirectional< G >::m_log.

Referenced by pgr_bdAstar(), and pgr_bdDijkstra().

◆ pgr_bdAstar()

template<typename G >

Path pgrouting::bidirectional::Pgr_bdAstar< G >::pgr_bdAstar	(	V	start_vertex,
		V	end_vertex,
		int	heuristic,
		double	factor,
		double	epsilon,
		bool	only_cost
	)

inline

Definition at line 86 of file pgr_bdAstar.hpp.

                             {
         m_log << "pgr_bdAstar\n";
         v_source = start_vertex;
         v_target = end_vertex;
         m_heuristic = heuristic;
         m_factor = factor * epsilon;
  
         return bidirectional(only_cost);
     }