PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
src/BiDirAStar.h
Go to the documentation of this file.
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 SRC_BD_ASTAR_SRC_BIDIRASTAR_H_
35 #define SRC_BD_ASTAR_SRC_BIDIRASTAR_H_
36 #pragma once
37 
38 #include <vector>
39 #include <map>
40 #include <utility>
41 
42 #include "./MinHeap.h"
43 #include "./bdastar_driver.h"
44 
45 #define INF 1e15
46 
47 
48 
49 typedef std::vector<size_t> LongVector;
50 typedef std::vector<LongVector> VectorOfLongVector;
51 typedef std::pair<double, int> PDI;
52 
53 typedef struct {
54  int par_Node;
55  int par_Edge;
56 } PARENT_PATH;
57 
58 typedef struct {
59  int NodeID;
60  double xpos;
61  double ypos;
62  std::vector<int> Connected_Nodes;
63  std::vector<size_t> Connected_Edges_Index;
65 
66 struct GraphEdgeInfo {
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<size_t, LongVector> Long2LongVectorMap;
79 typedef std::map<size_t, size_t> Long2LongMap;
80 typedef std::vector<GraphNodeInfo> GraphNodeVector;
81 
82 
83 class BiDirAStar {
84  public:
85  BiDirAStar(void);
86  ~BiDirAStar(void);
87 
88  int bidir_astar(edge_astar_t *edges, size_t edge_count, int maxNode, int start_vertex, int end_vertex,
89  path_element_t **path, size_t *path_count, char **err_msg);
90 
91  private:
92  bool construct_graph(edge_astar_t *edges, size_t edge_count, int maxNode);
93  void fconstruct_path(int node_id);
94  void rconstruct_path(int node_id);
95  bool addEdge(edge_astar_t edgeIn);
96  bool connectEdge(GraphEdgeInfo& firstEdge, GraphEdgeInfo& secondEdge, bool bIsStartNodeSame);
97  void init();
98  void initall(int maxNode);
99  void deleteall();
100  // void explore(int cur_node, double cur_cost, int dir, std::priority_queue<PDI, std::vector<PDI>, std::greater<PDI> > &que);
101  void explore(int cur_node, double cur_cost, int dir, MinHeap &que);
102  double getcost(int node_id, int dir);
103  void setcost(int node_id, int dir, double c);
104  void setparent(int node_id, int dir, int parnode, int paredge);
105  double gethcost(int node_id, int dir);
106  double dist(double x1, double y1, double x2, double y2);
107 
108  private:
117 
118  double m_MinCost;
120  std::vector <path_element_t> m_vecPath;
123  double *m_pFCost;
124  double *m_pRCost;
125 };
126 
127 #endif // SRC_BD_ASTAR_SRC_BIDIRASTAR_H_
PARENT_PATH * m_pFParent
std::vector< LongVector > VectorOfLongVector
double m_MinCost
double * m_pRCost
std::vector< size_t > Connected_Edges_Index
std::vector< GraphEdgeInfo > GraphEdgeVector
int path_count
Definition: BDATester.cpp:51
std::map< size_t, LongVector > Long2LongVectorMap
bool construct_graph(edge_astar_t *edges, size_t edge_count, int maxNode)
PARENT_PATH * m_pRParent
Long2LongVectorMap m_mapNodeId2Edge
std::pair< double, int > PDI
std::map< size_t, size_t > Long2LongMap
double ReverseCost
std::vector< int > Connected_Nodes
bool connectEdge(GraphEdgeInfo &firstEdge, GraphEdgeInfo &secondEdge, bool bIsStartNodeSame)
int bidir_astar(edge_astar_t *edges, size_t edge_count, int maxNode, int start_vertex, int end_vertex, path_element_t **path, size_t *path_count, char **err_msg)
double gethcost(int node_id, int dir)
std::vector< GraphNodeInfo > GraphNodeVector
void setcost(int node_id, int dir, double c)
GraphNodeVector m_vecNodeVector
int maxNode
Definition: BDATester.cpp:47
void explore(int cur_node, double cur_cost, int dir, MinHeap &que)
int edge_count
Definition: BDATester.cpp:47
std::vector< path_element_t > m_vecPath
edge_astar_t * edges
Definition: BDATester.cpp:46
double getcost(int node_id, int dir)
GraphEdgeVector m_vecEdgeVector
void deleteall()
void fconstruct_path(int node_id)
double * m_pFCost
std::vector< size_t > LongVector
path_element_t * path
Definition: BDATester.cpp:49
void setparent(int node_id, int dir, int parnode, int paredge)
double dist(double x1, double y1, double x2, double y2)
char * err_msg
Definition: BDATester.cpp:50
Long2LongMap m_mapEdgeId2Index
void rconstruct_path(int node_id)
bool addEdge(edge_astar_t edgeIn)
void initall(int maxNode)