← Back to branch summary

~valhalla-routing/+junk/valhalla_2.1.9-0ubuntu1

« back to all changes in this revision

Viewing changes to libvalhalla/valhalla/thor/bidirectional_astar.h

  • Committer: valhalla
  • Date: 2017-04-24 20:20:53 UTC
  • Revision ID: valhalla@mapzen.com-20170424202053-7o69b9nwx9ee0tw3
Packaging for 2.1.9-0ubuntu1.

Show diffs side-by-side

added added

removed removed

Lines of Context:
libvalhalla/valhalla/thor/bidirectional_astar.h
 
1
#ifndef VALHALLA_THOR_BIDIRECTIONAL_ASTAR_H_
 
2
#define VALHALLA_THOR_BIDIRECTIONAL_ASTAR_H_
 
3
 
 
4
#include <vector>
 
5
#include <map>
 
6
#include <unordered_map>
 
7
#include <utility>
 
8
#include <memory>
 
9
 
 
10
#include <valhalla/baldr/double_bucket_queue.h>
 
11
#include <valhalla/sif/edgelabel.h>
 
12
#include <valhalla/sif/hierarchylimits.h>
 
13
#include <valhalla/thor/pathalgorithm.h>
 
14
#include <valhalla/thor/astarheuristic.h>
 
15
#include <valhalla/thor/edgestatus.h>
 
16
 
 
17
namespace valhalla {
 
18
namespace thor {
 
19
 
 
20
/**
 
21
 * Candidate connections - a directed edge and its opposing directed edge
 
22
 * are both temporarily labeled. Store the edge Ids and its cost.
 
23
 */
 
24
struct CandidateConnection {
 
25
  baldr::GraphId edgeid;
 
26
  baldr::GraphId opp_edgeid;
 
27
  float cost;
 
28
};
 
29
 
 
30
/**
 
31
 * Bidirectional A* algorithm. Method for finding least-cost path.
 
32
 */
 
33
class BidirectionalAStar : public PathAlgorithm {
 
34
 public:
 
35
  /**
 
36
   * Constructor.
 
37
   */
 
38
  BidirectionalAStar();
 
39
 
 
40
  /**
 
41
   * Destructor
 
42
   */
 
43
  virtual ~BidirectionalAStar();
 
44
 
 
45
  /**
 
46
   * Form path between and origin and destination location using
 
47
   * the supplied mode and costing method.
 
48
   * @param  origin  Origin location
 
49
   * @param  dest    Destination location
 
50
   * @param  graphreader  Graph reader for accessing routing graph.
 
51
   * @param  mode_costing  An array of costing methods, one per TravelMode.
 
52
   * @param  mode     Travel mode from the origin.
 
53
   * @return  Returns the path edges (and elapsed time/modes at end of
 
54
   *          each edge).
 
55
   */
 
56
  std::vector<PathInfo> GetBestPath(baldr::PathLocation& origin,
 
57
           baldr::PathLocation& dest, baldr::GraphReader& graphreader,
 
58
           const std::shared_ptr<sif::DynamicCost>* mode_costing,
 
59
           const sif::TravelMode mode);
 
60
 
 
61
  /**
 
62
   * Clear the temporary information generated during path construction.
 
63
   */
 
64
  void Clear();
 
65
 
 
66
 protected:
 
67
  // Access mode used by the costing method
 
68
  uint32_t access_mode_;
 
69
 
 
70
  // Current travel mode
 
71
  sif::TravelMode mode_;
 
72
 
 
73
  // Current travel type
 
74
  uint8_t travel_type_;
 
75
 
 
76
  // Current costing mode
 
77
  std::shared_ptr<sif::DynamicCost> costing_;
 
78
 
 
79
  // Hierarchy limits
 
80
  std::vector<sif::HierarchyLimits> hierarchy_limits_forward_;
 
81
  std::vector<sif::HierarchyLimits> hierarchy_limits_reverse_;
 
82
 
 
83
  // A* heuristic
 
84
  float cost_diff_;
 
85
  AStarHeuristic astarheuristic_forward_;
 
86
  AStarHeuristic astarheuristic_reverse_;
 
87
 
 
88
  // Vector of edge labels (requires access by index).
 
89
  std::vector<sif::EdgeLabel> edgelabels_forward_;
 
90
  std::vector<sif::EdgeLabel> edgelabels_reverse_;
 
91
 
 
92
  // Adjacency list - approximate double bucket sort
 
93
  std::shared_ptr<baldr::DoubleBucketQueue> adjacencylist_forward_;
 
94
  std::shared_ptr<baldr::DoubleBucketQueue> adjacencylist_reverse_;
 
95
 
 
96
  // Edge status. Mark edges that are in adjacency list or settled.
 
97
  std::shared_ptr<EdgeStatus> edgestatus_forward_;
 
98
  std::shared_ptr<EdgeStatus> edgestatus_reverse_;
 
99
 
 
100
  // Best candidate connection and threshold to extend search.
 
101
  uint32_t threshold_;
 
102
  CandidateConnection best_connection_;
 
103
 
 
104
  /**
 
105
   * Initialize the A* heuristic and adjacency lists for both the forward
 
106
   * and reverse search.
 
107
   * @param  origll  Lat,lng of the origin.
 
108
   * @param  destll  Lat,lng of the destination.
 
109
   * @param  costing Dynamic costing method.
 
110
   */
 
111
  void Init(const PointLL& origll, const PointLL& destll);
 
112
 
 
113
  /**
 
114
   * Expand from the node along the forward search path.
 
115
   */
 
116
  void ExpandForward(baldr::GraphReader& graphreader,
 
117
           const baldr::GraphId& node, const sif::EdgeLabel& pred,
 
118
           const uint32_t pred_idx, const bool from_transition);
 
119
 
 
120
  /**
 
121
   * Expand from the node along the reverse search path.
 
122
   */
 
123
  void ExpandReverse(baldr::GraphReader& graphreader,
 
124
           const baldr::GraphId& node, const sif::EdgeLabel& pred,
 
125
           const uint32_t pred_idx, const baldr::DirectedEdge* opp_pred_edge,
 
126
           const bool from_transition);
 
127
 
 
128
  /**
 
129
   * Add edges at the origin to the forward adjacency list.
 
130
   * @param  graphreader  Graph tile reader.
 
131
   * @param  origin       Location information of the destination
 
132
   * @param  costing      Dynamic costing
 
133
   */
 
134
  void SetOrigin(baldr::GraphReader& graphreader,
 
135
                 baldr::PathLocation& origin);
 
136
 
 
137
  /**
 
138
   * Add destination edges to the reverse path adjacency list.
 
139
   * @param   dest         Location information of the destination
 
140
   * @param   costing      Dynamic costing
 
141
   */
 
142
  void SetDestination(baldr::GraphReader& graphreader,
 
143
                       const baldr::PathLocation& dest);
 
144
 
 
145
  /**
 
146
   * The edge on the forward search connects to a reached edge on the reverse
 
147
   * search tree. Check if this is the best connection so far and set the
 
148
   * search threshold.
 
149
   * @param  pred  Edge label of the predecessor.
 
150
   */
 
151
  void SetForwardConnection(const sif::EdgeLabel& pred);
 
152
 
 
153
  /**
 
154
   * The edge on the reverse search connects to a reached edge on the forward
 
155
   * search tree. Check if this is the best connection so far and set the
 
156
   * search threshold.
 
157
   * @param  pred  Edge label of the predecessor.
 
158
   */
 
159
  void SetReverseConnection(const sif::EdgeLabel& pred);
 
160
 
 
161
   /**
 
162
    * Form the path from the adjacency lists. Recovers the path from the
 
163
    * where the paths meet back towards the origin then reverses this path.
 
164
    * The path from where the paths meet to the destination is then appended
 
165
    * using the opposing edges (so the path is traversed forward).
 
166
    * @param   graphreader  Graph tile reader (for getting opposing edges).
 
167
    * @return  Returns the path info, a list of GraphIds representing the
 
168
    *          directed edges along the path - ordered from origin to
 
169
    *          destination - along with travel modes and elapsed time.
 
170
    */
 
171
  std::vector<PathInfo> FormPath(baldr::GraphReader& graphreader);
 
172
};
 
173
 
 
174
}
 
175
}
 
176
 
 
177
#endif  // VALHALLA_THOR_BIDIRECTIONAL_ASTAR_H_