PGROUTING  3.2
pgrouting::bidirectional::Pgr_bdAstar< G > Class Template Reference

#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< Vbackward_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< Vforward_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

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.

77  :
78  Pgr_bidirectional<G>(pgraph),
79  m_heuristic(5),
80  m_factor(1.0) {
81  m_log << "pgr_bdAstar constructor\n";
82  }

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.

122  {
123  m_log << "bidir_astar\n";
124 
126 
127  forward_cost[v_source] = 0;
128  forward_queue.push(std::make_pair(0.0, v_source));
129 
130 
131  backward_cost[v_target] = 0;
132  backward_queue.push(std::make_pair(0.0, v_target));
133 
134  while (!forward_queue.empty() && !backward_queue.empty()) {
135  auto forward_node = forward_queue.top();
136  auto backward_node = backward_queue.top();
137  /*
138  * done: there is no path with lower cost
139  */
140  if (forward_node.first == INF || backward_node.first == INF) {
141  break;
142  }
143 
144  /*
145  * Explore from the cheapest side
146  */
147  if (backward_node.first < forward_node.first) {
148  backward_queue.pop();
149  if (!backward_finished[backward_node.second]) {
150  explore_backward(backward_node);
151  }
152  if (found(backward_node.second)) {
153  break;
154  }
155  } else {
156  forward_queue.pop();
157  if (!forward_finished[forward_node.second]) {
158  explore_forward(forward_node);
159  }
160  if (found(forward_node.second)) {
161  break;
162  }
163  }
164  }
165 
166  if (best_cost == INF) return Path();
167 
168  Path forward_path(
169  graph,
170  v_source,
171  v_min_node,
173  forward_cost,
174  false,
175  true);
176  Path backward_path(
177  graph,
178  v_target,
179  v_min_node,
182  false,
183  false);
184  m_log << forward_path;
185  backward_path.reverse();
186  m_log << backward_path;
187  forward_path.append(backward_path);
188  auto p = Path(graph, forward_path, only_cost);
189  m_log << forward_path;
190  m_log << p;
191  return p;
192  }

References Path::append(), pgrouting::bidirectional::Pgr_bidirectional< G >::backward_cost, pgrouting::bidirectional::Pgr_bidirectional< G >::backward_finished, pgrouting::bidirectional::Pgr_bidirectional< G >::backward_predecessor, pgrouting::bidirectional::Pgr_bidirectional< G >::backward_queue, pgrouting::bidirectional::Pgr_bidirectional< G >::best_cost, pgrouting::bidirectional::Pgr_bidirectional< G >::explore_backward(), pgrouting::bidirectional::Pgr_bidirectional< G >::explore_forward(), pgrouting::bidirectional::Pgr_bidirectional< G >::forward_cost, pgrouting::bidirectional::Pgr_bidirectional< G >::forward_finished, pgrouting::bidirectional::Pgr_bidirectional< G >::forward_predecessor, pgrouting::bidirectional::Pgr_bidirectional< G >::forward_queue, pgrouting::bidirectional::Pgr_bidirectional< G >::found(), pgrouting::bidirectional::Pgr_bidirectional< G >::graph, pgrouting::bidirectional::Pgr_bidirectional< G >::INF, pgrouting::bidirectional::Pgr_bidirectional< G >::initialize(), pgrouting::bidirectional::Pgr_bidirectional< G >::m_log, Path::reverse(), pgrouting::bidirectional::Pgr_bidirectional< G >::v_min_node, pgrouting::bidirectional::Pgr_bidirectional< G >::v_source, and pgrouting::bidirectional::Pgr_bidirectional< G >::v_target.

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()

◆ 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.

130  {
131  typename G::EI_i in, in_end;
132 
133  auto current_cost = node.first;
134  auto current_node = node.second;
135 
136  for (boost::tie(in, in_end) = in_edges(current_node, graph.graph);
137  in != in_end; ++in) {
138  auto edge_cost = graph[*in].cost;
139  auto next_node = graph.adjacent(current_node, *in);
140 
141  if (backward_finished[next_node]) continue;
142 
143  if (edge_cost + current_cost < backward_cost[next_node]) {
144  backward_cost[next_node] = edge_cost + current_cost;
145  backward_predecessor[next_node] = current_node;
146  backward_edge[next_node] = graph[*in].id;
147  backward_queue.push({
148  backward_cost[next_node]
149  + heuristic(next_node, v_source),
150  next_node});
151  }
152  }
153  backward_finished[current_node] = true;
154  }

References pgrouting::bidirectional::Pgr_bidirectional< G >::backward_cost, pgrouting::bidirectional::Pgr_bidirectional< G >::backward_edge, pgrouting::bidirectional::Pgr_bidirectional< G >::backward_finished, pgrouting::bidirectional::Pgr_bidirectional< G >::backward_predecessor, pgrouting::bidirectional::Pgr_bidirectional< G >::backward_queue, pgrouting::bidirectional::Pgr_bidirectional< G >::graph, pgrouting::bidirectional::Pgr_bdAstar< G >::heuristic(), and pgrouting::bidirectional::Pgr_bidirectional< G >::v_source.

◆ 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.

104  {
105  typename G::EO_i out, out_end;
106 
107  auto current_cost = node.first;
108  auto current_node = node.second;
109 
110  for (boost::tie(out, out_end) = out_edges(current_node, graph.graph);
111  out != out_end; ++out) {
112  auto edge_cost = graph[*out].cost;
113  auto next_node = graph.adjacent(current_node, *out);
114 
115  if (forward_finished[next_node]) continue;
116 
117  if (edge_cost + current_cost < forward_cost[next_node]) {
118  forward_cost[next_node] = edge_cost + current_cost;
119  forward_predecessor[next_node] = current_node;
120  forward_edge[next_node] = graph[*out].id;
121  forward_queue.push({
122  forward_cost[next_node]
123  + heuristic(next_node, v_target),
124  next_node});
125  }
126  }
127  forward_finished[current_node] = true;
128  }

References pgrouting::bidirectional::Pgr_bidirectional< G >::forward_cost, pgrouting::bidirectional::Pgr_bidirectional< G >::forward_edge, pgrouting::bidirectional::Pgr_bidirectional< G >::forward_finished, pgrouting::bidirectional::Pgr_bidirectional< G >::forward_predecessor, pgrouting::bidirectional::Pgr_bidirectional< G >::forward_queue, pgrouting::bidirectional::Pgr_bidirectional< G >::graph, pgrouting::bidirectional::Pgr_bdAstar< G >::heuristic(), and pgrouting::bidirectional::Pgr_bidirectional< G >::v_target.

◆ found()

◆ 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.

157  {
158  if (m_heuristic == 0) return 0;
159 
160  double dx = graph[v].x() - graph[u].x();
161  double dy = graph[v].y() - graph[u].y();
162  double current;
163 
164  switch (m_heuristic) {
165  case 0:
166  current = 0;
167  break;
168  case 1:
169  current = std::fabs((std::max)(dx, dy)) * m_factor;
170  break;
171  case 2:
172  current = std::fabs((std::min)(dx, dy)) * m_factor;
173  break;
174  case 3:
175  current = (dx * dx + dy * dy) * m_factor * m_factor;
176  break;
177  case 4:
178  current = std::sqrt(dx * dx + dy * dy) * m_factor;
179  break;
180  case 5:
181  current = (std::fabs(dx) + std::fabs(dy)) * m_factor;
182  break;
183  default:
184  current = 0;
185  }
186  return current;
187  }

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.

103  {
104  m_log << "initializing\n";
105  clear();
106  forward_predecessor.resize(graph.num_vertices());
107  forward_finished.resize(graph.num_vertices(), false);
108  forward_edge.resize(graph.num_vertices(), -1);
109  forward_cost.resize(graph.num_vertices(), INF);
110  std::iota(forward_predecessor.begin(), forward_predecessor.end(), 0);
111 
112  backward_predecessor.resize(graph.num_vertices());
113  backward_finished.resize(graph.num_vertices(), false);
114  backward_edge.resize(graph.num_vertices(), -1);
115  backward_cost.resize(graph.num_vertices(), INF);
116  std::iota(backward_predecessor.begin(), backward_predecessor.end(), 0);
117 
118  v_min_node = 0;
119  best_cost = INF;
120  }

References pgrouting::bidirectional::Pgr_bidirectional< G >::backward_cost, pgrouting::bidirectional::Pgr_bidirectional< G >::backward_edge, pgrouting::bidirectional::Pgr_bidirectional< G >::backward_finished, pgrouting::bidirectional::Pgr_bidirectional< G >::backward_predecessor, pgrouting::bidirectional::Pgr_bidirectional< G >::best_cost, pgrouting::bidirectional::Pgr_bidirectional< G >::clear(), pgrouting::bidirectional::Pgr_bidirectional< G >::forward_cost, pgrouting::bidirectional::Pgr_bidirectional< G >::forward_edge, pgrouting::bidirectional::Pgr_bidirectional< G >::forward_finished, pgrouting::bidirectional::Pgr_bidirectional< G >::forward_predecessor, pgrouting::bidirectional::Pgr_bidirectional< G >::graph, pgrouting::bidirectional::Pgr_bidirectional< G >::INF, pgrouting::bidirectional::Pgr_bidirectional< G >::m_log, and pgrouting::bidirectional::Pgr_bidirectional< G >::v_min_node.

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

Member Data Documentation

◆ backward_cost

◆ backward_edge

◆ backward_finished

◆ backward_predecessor

◆ backward_queue

◆ best_cost

◆ cost_only

template<typename G >
bool pgrouting::bidirectional::Pgr_bidirectional< G >::cost_only
protectedinherited

Definition at line 227 of file pgr_bidirectional.hpp.

◆ forward_cost

◆ forward_edge

◆ forward_finished

◆ forward_predecessor

◆ forward_queue

◆ graph

◆ INF

◆ m_factor

◆ m_heuristic

◆ m_log

◆ v_min_node

◆ v_source

◆ v_target


The documentation for this class was generated from the following file:
Path
Definition: basePath_SSEC.hpp:47
pgrouting::bidirectional::Pgr_bidirectional::forward_edge
std::vector< int64_t > forward_edge
Definition: pgr_bidirectional.hpp:239
pgrouting::bidirectional::Pgr_bidirectional::backward_predecessor
std::vector< V > backward_predecessor
Definition: pgr_bidirectional.hpp:235
pgrouting::bidirectional::Pgr_bidirectional::forward_queue
Priority_queue forward_queue
Definition: pgr_bidirectional.hpp:230
pgrouting::bidirectional::Pgr_bidirectional::explore_backward
virtual void explore_backward(const Cost_Vertex_pair &node)=0
pgrouting::bidirectional::Pgr_bidirectional::m_log
std::ostringstream m_log
Definition: pgr_bidirectional.hpp:229
pgrouting::bidirectional::Pgr_bdAstar::m_heuristic
int m_heuristic
Definition: pgr_bdAstar.hpp:190
pgrouting::bidirectional::Pgr_bidirectional::v_target
V v_target
target descriptor
Definition: pgr_bidirectional.hpp:221
pgrouting::bidirectional::Pgr_bidirectional::backward_finished
std::vector< bool > backward_finished
Definition: pgr_bidirectional.hpp:233
pgrouting::bidirectional::Pgr_bidirectional::v_source
V v_source
source descriptor
Definition: pgr_bidirectional.hpp:220
pgrouting::bidirectional::Pgr_bidirectional::INF
double INF
infinity
Definition: pgr_bidirectional.hpp:224
pgrouting::bidirectional::Pgr_bidirectional::found
bool found(const V &node)
Definition: pgr_bidirectional.hpp:196
pgrouting::bidirectional::Pgr_bidirectional::graph
G & graph
Definition: pgr_bidirectional.hpp:219
pgrouting::bidirectional::Pgr_bidirectional::forward_cost
std::vector< double > forward_cost
Definition: pgr_bidirectional.hpp:241
pgrouting::bidirectional::Pgr_bdAstar::heuristic
double heuristic(V v, V u)
Definition: pgr_bdAstar.hpp:157
pgrouting::bidirectional::Pgr_bidirectional::v_min_node
V v_min_node
target descriptor
Definition: pgr_bidirectional.hpp:222
pgrouting::bidirectional::Pgr_bidirectional::forward_finished
std::vector< bool > forward_finished
Definition: pgr_bidirectional.hpp:238
pgrouting::bidirectional::Pgr_bidirectional::bidirectional
Path bidirectional(bool only_cost)
Definition: pgr_bidirectional.hpp:122
pgrouting::bidirectional::Pgr_bidirectional::backward_cost
std::vector< double > backward_cost
Definition: pgr_bidirectional.hpp:236
pgrouting::bidirectional::Pgr_bidirectional::backward_queue
Priority_queue backward_queue
Definition: pgr_bidirectional.hpp:231
pgrouting::bidirectional::Pgr_bidirectional::best_cost
double best_cost
Definition: pgr_bidirectional.hpp:226
pgrouting::bidirectional::Pgr_bidirectional::clear
void clear()
Definition: pgr_bidirectional.hpp:86
pgrouting::bidirectional::Pgr_bidirectional::forward_predecessor
std::vector< V > forward_predecessor
Definition: pgr_bidirectional.hpp:240
pgrouting::bidirectional::Pgr_bidirectional::initialize
void initialize()
Definition: pgr_bidirectional.hpp:103
pgrouting::bidirectional::Pgr_bidirectional::backward_edge
std::vector< int64_t > backward_edge
Definition: pgr_bidirectional.hpp:234
pgrouting::bidirectional::Pgr_bidirectional::explore_forward
virtual void explore_forward(const Cost_Vertex_pair &node)=0
pgrouting::bidirectional::Pgr_bdAstar::m_factor
double m_factor
Definition: pgr_bdAstar.hpp:191