pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
tester/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 
35 #ifndef BIDIRASTAR_H
36 #define BIDIRASTAR_H
37 
38 #include <vector>
39 #include <map>
40 #include <queue>
41 #include <string>
42 #include <stdlib.h>
43 #include <iostream>
44 #include <math.h>
45 #include <stdio.h>
46 #include <string.h>
47 
48 #include "MinHeap.h"
49 //#include "bdastar.h"
50 
51 #define INF 1e15
52 
53 
54 
55 typedef std::vector<long> LongVector;
56 typedef std::vector<LongVector> VectorOfLongVector;
57 //typedef std::pair<int, bool> PIB;
58 typedef std::pair<double, int> PDI;
59 //typedef std::pair<double, std::vector<int> > PDVI;
60 
61 typedef struct edge
62 {
63  int id;
64  int source;
65  int target;
66  double s_x;
67  double s_y;
68  double t_x;
69  double t_y;
70  double cost;
71  double reverse_cost;
72 } edge_astar_t;
73 
74 typedef struct path_element
75 {
76  int vertex_id;
77  int edge_id;
78  double cost;
80 
81 
82 typedef struct{
83  int par_Node;
84  int par_Edge;
86 
87 typedef struct{
88  int NodeID;
89  double xpos;
90  double ypos;
91  std::vector<int> Connected_Nodes;
92  std::vector<int> Connected_Edges_Index;
94 
95 struct GraphEdgeInfo
96 {
97 public:
98  int EdgeID;
99  int EdgeIndex;
100  int Direction;
101  double Cost;
102  double ReverseCost;
103  int StartNode;
104  int EndNode;
105 };
106 
107 typedef std::vector<GraphEdgeInfo> GraphEdgeVector;
108 typedef std::map<long,LongVector> Long2LongVectorMap;
109 typedef std::map<long,long> Long2LongMap;
110 typedef std::vector<GraphNodeInfo> GraphNodeVector;
111 
112 
113 class BiDirAStar
114 {
115 public:
116  BiDirAStar(void);
117  ~BiDirAStar(void);
118 
119  int bidir_astar(edge_astar_t *edges, unsigned int edge_count, int maxNode, int start_vertex, int end_vertex,
120  path_element_t **path, int *path_count, char **err_msg);
121 
122 
123 private:
124  bool construct_graph(edge_astar_t *edges, int edge_count, int maxNode);
125  void fconstruct_path(int node_id);
126  void rconstruct_path(int node_id);
127  bool addEdge(edge_astar_t edgeIn);
128  bool connectEdge(GraphEdgeInfo& firstEdge, GraphEdgeInfo& secondEdge, bool bIsStartNodeSame);
129  void init();
130  void initall(int maxNode);
131  void deleteall();
132  //void explore(int cur_node, double cur_cost, int dir, std::priority_queue<PDI, std::vector<PDI>, std::greater<PDI> > &que);
133  void explore(int cur_node, double cur_cost, int dir, MinHeap &que);
134  double getcost(int node_id, int dir);
135  void setcost(int node_id, int dir, double c);
136  void setparent(int node_id, int dir, int parnode, int paredge);
137  double gethcost(int node_id, int dir);
138  double dist(double x1, double y1, double x2, double y2);
139 
140 private:
141  GraphEdgeVector m_vecEdgeVector;
142  Long2LongMap m_mapEdgeId2Index;
143  Long2LongVectorMap m_mapNodeId2Edge;
144  GraphNodeVector m_vecNodeVector;
145  int max_node_id;
146  int max_edge_id;
147  int m_lStartNodeId;
148  int m_lEndNodeId;
149 
150  double m_MinCost;
151  int m_MidNode;
152  std::vector <path_element_t> m_vecPath;
153  PARENT_PATH *m_pFParent;
154  PARENT_PATH *m_pRParent;
155  double *m_pFCost;
156  double *m_pRCost;
157 };
158 
159 #endif