pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
BiDirDijkstra.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 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 SRC_BD_DIJKSTRA_SRC_BIDIRDIJKSTRA_H_
30 #define SRC_BD_DIJKSTRA_SRC_BIDIRDIJKSTRA_H_
31 #pragma once
32 
33 #include <vector>
34 #include <map>
35 #include <queue>
36 #include <utility>
37 #include <functional>
38 
39 #include "../../common/src/pgr_types.h"
40 #include "./bdsp_driver.h"
41 
42 #define INF 1e15
43 
44 
45 
46 typedef std::vector<int64_t> LongVector;
47 typedef std::vector<LongVector> VectorOfLongVector;
48 typedef std::pair<double, int> PDI;
49 
50 typedef struct {
51  int par_Node;
52  int par_Edge;
53 } PARENT_PATH;
54 
55 typedef struct {
56  int NodeID;
57  std::vector<int> Connected_Nodes;
58  std::vector<int> Connected_Edges_Index;
60 
61 struct GraphEdgeInfo {
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<int64_t, LongVector> Long2LongVectorMap;
74 typedef std::map<int64_t, int64_t> Long2LongMap;
75 typedef std::vector<GraphNodeInfo*> GraphNodeVector;
76 
77 
79  public:
80  BiDirDijkstra(void);
81  ~BiDirDijkstra(void);
82 
83  int bidir_dijkstra(edge_t *edges, unsigned int edge_count, int maxNode, int start_vertex, int end_vertex,
84  path_element_t **path, int *path_count, char **err_msg);
85 
86 
87  private:
88  bool construct_graph(edge_t *edges, int edge_count, int maxNode);
89  void fconstruct_path(int node_id);
90  void rconstruct_path(int node_id);
91  bool addEdge(edge_t edgeIn);
92  bool connectEdge(GraphEdgeInfo& firstEdge, GraphEdgeInfo& secondEdge, bool bIsStartNodeSame);
93  void init();
94  void initall(int maxNode);
95  void deleteall();
96  void explore(int cur_node, double cur_cost, int dir, std::priority_queue<PDI, std::vector<PDI>, std::greater<PDI> > &que);
97  double getcost(int node_id, int dir);
98  void setcost(int node_id, int dir, double c);
99  void setparent(int node_id, int dir, int parnode, int paredge);
100 
101  private:
110 
111  double m_MinCost;
113  std::vector <path_element_t> m_vecPath;
116  double *m_pFCost;
117  double *m_pRCost;
118 };
119 
120 #endif // SRC_BD_DIJKSTRA_SRC_BIDIRDIJKSTRA_H_
bool addEdge(edge_t edgeIn)
Long2LongVectorMap m_mapNodeId2Edge
std::vector< GraphEdgeInfo > GraphEdgeVector
int path_count
Definition: BDATester.cpp:51
std::map< size_t, LongVector > Long2LongVectorMap
std::vector< GraphEdgeInfo * > GraphEdgeVector
Definition: BiDirDijkstra.h:72
std::vector< LongVector > VectorOfLongVector
Definition: BiDirDijkstra.h:47
double * m_pFCost
GraphEdgeVector m_vecEdgeVector
double getcost(int node_id, int dir)
std::map< int64_t, int64_t > Long2LongMap
Definition: BiDirDijkstra.h:74
std::pair< double, int > PDI
std::map< size_t, size_t > Long2LongMap
double ReverseCost
PARENT_PATH * m_pRParent
void fconstruct_path(int node_id)
void rconstruct_path(int node_id)
bool construct_graph(edge_t *edges, int edge_count, int maxNode)
GraphNodeVector m_vecNodeVector
std::vector< GraphNodeInfo > GraphNodeVector
Long2LongMap m_mapEdgeId2Index
int maxNode
Definition: BDATester.cpp:47
int edge_count
Definition: BDATester.cpp:47
std::vector< GraphNodeInfo * > GraphNodeVector
Definition: BiDirDijkstra.h:75
std::vector< int64_t > LongVector
Definition: BiDirDijkstra.h:46
edge_astar_t * edges
Definition: BDATester.cpp:46
void explore(int cur_node, double cur_cost, int dir, std::priority_queue< PDI, std::vector< PDI >, std::greater< PDI > > &que)
void setcost(int node_id, int dir, double c)
void setparent(int node_id, int dir, int parnode, int paredge)
int bidir_dijkstra(edge_t *edges, unsigned int edge_count, int maxNode, int start_vertex, int end_vertex, path_element_t **path, int *path_count, char **err_msg)
path_element_t * path
Definition: BDATester.cpp:49
std::pair< double, int > PDI
Definition: BiDirDijkstra.h:48
char * err_msg
Definition: BDATester.cpp:50
double * m_pRCost
std::vector< path_element_t > m_vecPath
bool connectEdge(GraphEdgeInfo &firstEdge, GraphEdgeInfo &secondEdge, bool bIsStartNodeSame)
void initall(int maxNode)
PARENT_PATH * m_pFParent
std::map< int64_t, LongVector > Long2LongVectorMap
Definition: BiDirDijkstra.h:73