PGROUTING  2.6
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

Definition at line 53 of file pgr_bdAstar.hpp.

template<typename G>
typedef Pgr_bidirectional<G>::E pgrouting::bidirectional::Pgr_bdAstar< G >::E
private

Definition at line 52 of file pgr_bdAstar.hpp.

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 69 of file pgr_bidirectional.hpp.

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

template<typename G>
pgrouting::bidirectional::Pgr_bdAstar< G >::Pgr_bdAstar ( G &  pgraph)
inlineexplicit

Definition at line 77 of file pgr_bdAstar.hpp.

References pgrouting::bidirectional::Pgr_bidirectional< G >::m_log, and pgrouting::bidirectional::Pgr_bdAstar< G >::~Pgr_bdAstar().

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

Here is the call graph for this function:

template<typename G>
pgrouting::bidirectional::Pgr_bdAstar< G >::~Pgr_bdAstar ( )
default

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

Here is the caller graph for this function:

Member Function Documentation

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

Definition at line 119 of file pgr_bidirectional.hpp.

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename G>
void pgrouting::bidirectional::Pgr_bidirectional< G >::clean_log ( )
inlineinherited
template<typename G>
void pgrouting::bidirectional::Pgr_bidirectional< G >::clear ( )
inlineinherited

Definition at line 83 of file pgr_bidirectional.hpp.

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 >::forward_cost, pgrouting::bidirectional::Pgr_bidirectional< G >::forward_edge, pgrouting::bidirectional::Pgr_bidirectional< G >::forward_finished, pgrouting::bidirectional::Pgr_bidirectional< G >::forward_predecessor, and pgrouting::bidirectional::Pgr_bidirectional< G >::forward_queue.

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

83  {
84  while (!forward_queue.empty()) forward_queue.pop();
85  while (!backward_queue.empty()) backward_queue.pop();
86 
87  backward_finished.clear();
88  backward_edge.clear();
89  backward_predecessor.clear();
90  backward_cost.clear();
91 
92  forward_finished.clear();
93  forward_edge.clear();
94  forward_predecessor.clear();
95  forward_cost.clear();
96  }

Here is the caller graph for this function:

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 133 of file pgr_bdAstar.hpp.

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.

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

Here is the call graph for this function:

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 107 of file pgr_bdAstar.hpp.

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.

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

Here is the call graph for this function:

template<typename G>
bool pgrouting::bidirectional::Pgr_bidirectional< G >::found ( const V node)
inlineprotectedinherited

Definition at line 191 of file pgr_bidirectional.hpp.

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 >::explore_backward(), pgrouting::bidirectional::Pgr_bidirectional< G >::explore_forward(), 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().

191  {
192  /*
193  * Update common node
194  */
195  if (forward_finished[node] && backward_finished[node]) {
196  if (best_cost >= forward_cost[node] + backward_cost[node]) {
197  v_min_node = node;
198  best_cost = forward_cost[node] + backward_cost[node];
199  return false;
200  } else {
201  return true;
202  }
203  }
204  return false;
205  }

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 160 of file pgr_bdAstar.hpp.

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

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

Here is the caller graph for this function:

template<typename G>
void pgrouting::bidirectional::Pgr_bidirectional< G >::initialize ( )
inlineprotectedinherited

Definition at line 100 of file pgr_bidirectional.hpp.

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 81 of file pgr_bidirectional.hpp.

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

Referenced by pgr_bdAstar(), and pgr_bdDijkstra().

81 {return m_log.str();}

Here is the caller graph for this function:

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.

References pgrouting::bidirectional::Pgr_bidirectional< G >::bidirectional(), pgrouting::bidirectional::Pgr_bdAstar< G >::heuristic(), pgrouting::bidirectional::Pgr_bdAstar< G >::m_factor, pgrouting::bidirectional::Pgr_bdAstar< G >::m_heuristic, pgrouting::bidirectional::Pgr_bidirectional< G >::m_log, pgrouting::bidirectional::Pgr_bidirectional< G >::v_source, and pgrouting::bidirectional::Pgr_bidirectional< G >::v_target.

Referenced by pgr_bdAstar().

90  {
91  m_log << "pgr_bdAstar\n";
92  v_source = start_vertex;
93  v_target = end_vertex;
95  m_factor = factor * epsilon;
96 
97  if (v_source == v_target) {
98  return Path(v_source, v_target);
99  }
100  return bidirectional(only_cost);
101  }

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

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

Definition at line 226 of file pgr_bidirectional.hpp.


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