pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
BiDirDijkstra.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 Copyright (c) 2015 pgRouting developers
9 Mail: project@pgrouting.org
10 
11 ------
12 
13 This program is free software; you can redistribute it and/or modify
14 it under the terms of the GNU General Public License as published by
15 the Free Software Foundation; either version 2 of the License, or
16 (at your option) any later version.
17 
18 This program is distributed in the hope that it will be useful,
19 but WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 GNU General Public License for more details.
22 
23 You should have received a copy of the GNU General Public License
24 along with this program; if not, write to the Free Software
25 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
26 
27 ********************************************************************PGR-MIT*/
28 
29 #ifndef BIDIRDIJKSTRA_H
30 #define BIDIRDIJKSTRA_H
31 
32 #include <vector>
33 #include <map>
34 #include <queue>
35 #include <utility>
36 #include <functional>
37 
38 #include "../../common/src/pgr_types.h"
39 #include "bdsp.h"
40 
41 #define INF 1e15
42 
43 
44 
45 typedef std::vector<long> LongVector;
46 typedef std::vector<LongVector> VectorOfLongVector;
47 typedef std::pair<double, int> PDI;
48 
49 typedef struct{
50  int par_Node;
51  int par_Edge;
53 
54 typedef struct{
55  int NodeID;
56  std::vector<int> Connected_Nodes;
57  std::vector<int> Connected_Edges_Index;
59 
60 struct GraphEdgeInfo
61 {
62 public:
63  int EdgeID;
64  int EdgeIndex;
65  int Direction;
66  double Cost;
67  double ReverseCost;
68  int StartNode;
69  int EndNode;
70 };
71 
72 typedef std::vector<GraphEdgeInfo> GraphEdgeVector;
73 typedef std::map<long,LongVector> Long2LongVectorMap;
74 typedef std::map<long,long> Long2LongMap;
75 typedef std::vector<GraphNodeInfo*> GraphNodeVector;
76 
77 
79 {
80 public:
81  BiDirDijkstra(void);
82  ~BiDirDijkstra(void);
83 
84  int bidir_dijkstra(edge_t *edges, unsigned int edge_count, int maxNode, int start_vertex, int end_vertex,
85  path_element_t **path, int *path_count, char **err_msg);
86 
87 
88 private:
89  bool construct_graph(edge_t *edges, int edge_count, int maxNode);
90  void fconstruct_path(int node_id);
91  void rconstruct_path(int node_id);
92  bool addEdge(edge_t edgeIn);
93  bool connectEdge(GraphEdgeInfo& firstEdge, GraphEdgeInfo& secondEdge, bool bIsStartNodeSame);
94  void init();
95  void initall(int maxNode);
96  void deleteall();
97  void explore(int cur_node, double cur_cost, int dir, std::priority_queue<PDI, std::vector<PDI>, std::greater<PDI> > &que);
98  double getcost(int node_id, int dir);
99  void setcost(int node_id, int dir, double c);
100  void setparent(int node_id, int dir, int parnode, int paredge);
101 
102 private:
103  GraphEdgeVector m_vecEdgeVector;
104  Long2LongMap m_mapEdgeId2Index;
105  Long2LongVectorMap m_mapNodeId2Edge;
106  GraphNodeVector m_vecNodeVector;
107  int max_node_id;
108  int max_edge_id;
109  int m_lStartNodeId;
110  int m_lEndNodeId;
111 
112  double m_MinCost;
113  int m_MidNode;
114  std::vector <path_element_t> m_vecPath;
115  PARENT_PATH *m_pFParent;
116  PARENT_PATH *m_pRParent;
117  double *m_pFCost;
118  double *m_pRCost;
119 };
120 
121 #endif