pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
src/BiDirAStar.h
1 /*PGR-MIT*****************************************************************
2 
3 * $Id$
4 *
5 * Project: pgRouting bdsp and bdastar algorithms
6 * Purpose:
7 * Author: Razequl Islam <ziboncsedu@gmail.com>
8 *
9 
10 ------
11 MIT/X license
12 
13 Permission is hereby granted, free of charge, to any person obtaining a copy
14 of this software and associated documentation files (the "Software"), to deal
15 in the Software without restriction, including without limitation the rights
16 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
17 copies of the Software, and to permit persons to whom the Software is
18 furnished to do so, subject to the following conditions:
19 
20 
21 The above copyright notice and this permission notice shall be included in
22 all copies or substantial portions of the Software.
23 
24 
25 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
26 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
27 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
28 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
29 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
30 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
31 THE SOFTWARE.
32 
33 ********************************************************************PGR-MIT*/
34 #ifndef BIDIRASTAR_H
35 #define BIDIRASTAR_H
36 
37 #include <vector>
38 #include <map>
39 #include <utility>
40 
41 #include "MinHeap.h"
42 #include "bdastar.h"
43 
44 #define INF 1e15
45 
46 
47 
48 typedef std::vector<long> LongVector;
49 typedef std::vector<LongVector> VectorOfLongVector;
50 typedef std::pair<double, int> PDI;
51 
52 typedef struct{
53  int par_Node;
54  int par_Edge;
56 
57 typedef struct{
58  int NodeID;
59  double xpos;
60  double ypos;
61  std::vector<int> Connected_Nodes;
62  std::vector<size_t> Connected_Edges_Index;
64 
66 {
67 public:
68  int EdgeID;
69  size_t EdgeIndex;
70  int Direction;
71  double Cost;
72  double ReverseCost;
73  int StartNode;
74  int EndNode;
75 };
76 
77 typedef std::vector<GraphEdgeInfo> GraphEdgeVector;
78 typedef std::map<long,LongVector> Long2LongVectorMap;
79 typedef std::map<long,long> Long2LongMap;
80 typedef std::vector<GraphNodeInfo> GraphNodeVector;
81 
82 
84 {
85 public:
86  BiDirAStar(void);
87  ~BiDirAStar(void);
88 
89  int bidir_astar(edge_astar_t *edges, size_t edge_count, int maxNode, int start_vertex, int end_vertex,
90  path_element_t **path, size_t *path_count, char **err_msg);
91 
92 
93 private:
94  bool construct_graph(edge_astar_t *edges, size_t edge_count, int maxNode);
95  void fconstruct_path(int node_id);
96  void rconstruct_path(int node_id);
97  bool addEdge(edge_astar_t edgeIn);
98  bool connectEdge(GraphEdgeInfo& firstEdge, GraphEdgeInfo& secondEdge, bool bIsStartNodeSame);
99  void init();
100  void initall(int maxNode);
101  void deleteall();
102  //void explore(int cur_node, double cur_cost, int dir, std::priority_queue<PDI, std::vector<PDI>, std::greater<PDI> > &que);
103  void explore(int cur_node, double cur_cost, int dir, MinHeap &que);
104  double getcost(int node_id, int dir);
105  void setcost(int node_id, int dir, double c);
106  void setparent(int node_id, int dir, int parnode, int paredge);
107  double gethcost(int node_id, int dir);
108  double dist(double x1, double y1, double x2, double y2);
109 
110 private:
111  GraphEdgeVector m_vecEdgeVector;
112  Long2LongMap m_mapEdgeId2Index;
113  Long2LongVectorMap m_mapNodeId2Edge;
114  GraphNodeVector m_vecNodeVector;
115  int max_node_id;
116  int max_edge_id;
117  int m_lStartNodeId;
118  int m_lEndNodeId;
119 
120  double m_MinCost;
121  int m_MidNode;
122  std::vector <path_element_t> m_vecPath;
123  PARENT_PATH *m_pFParent;
124  PARENT_PATH *m_pRParent;
125  double *m_pFCost;
126  double *m_pRCost;
127 };
128 
129 #endif