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
GraphDefinition.h
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 Copyright (c) 2015 pgRouting developers
4 Mail: project@pgrouting.org
5 
6 ------
7 
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12 
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17 
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 
22 ********************************************************************PGR-GNU*/
23 #ifndef GRAPHDEFINITION_H
24 #define GRAPHDEFINITION_H
25 
26 #include <vector>
27 #include <map>
28 #include <queue>
29 #if defined(_MSC_VER) && _MSC_VER >= 1700
30 #include <functional>
31 #endif
32 #include <sstream>
33 #include "trsp_driver.h"
34 
35 
36 typedef std::pair<double, std::vector<int64_t> > PDVI;
37 
38 
40  typedef std::vector<int64_t> LongVector;
41  typedef std::vector<LongVector> VectorOfLongVector;
42  typedef std::pair<int, bool> PIB;
43  typedef std::pair<double, PIB> PDP;
44  typedef struct{
45  int64_t ed_ind[2];
46  int64_t v_pos[2];
47  } PARENT_PATH;
48 
49  typedef struct{
50  double cost;
51  std::vector<int64_t> precedencelist;
52  } Rule;
53 
54  typedef struct{
55  double startCost, endCost;
56  } CostHolder;
57 
58  typedef std::map<int64_t, std::vector<Rule> > RuleTable;
59 
60 
61 
62  class GraphEdgeInfo {
63  public:
64  GraphEdgeInfo() = default;
65  GraphEdgeInfo(int64_t eid, int64_t index, int64_t node1, int64_t node2, double cost, double reverse_cost) :
66  m_lEdgeID(eid), m_lEdgeIndex(index), m_lStartNode(node1), m_lEndNode(node2),
67  m_dCost(cost), m_dReverseCost(reverse_cost) {
69  m_vecEndConnedtedEdge.clear();
70  m_vecRestrictedEdge.clear();
71  }
72 
73 
74  public:
75  int64_t m_lEdgeID;
76  int64_t m_lEdgeIndex;
77  int64_t m_lStartNode;
78  int64_t m_lEndNode;
79  double m_dCost;
81  short m_sDirection;
84  //LongVector m_vecConnectedNode;
87 
88  };
89 
90 
91  typedef std::vector<GraphEdgeInfo> GraphEdgeVector;
92  typedef std::map<int64_t,LongVector> Long2LongVectorMap;
93  typedef std::map<int64_t,int64_t> Long2LongMap;
94 
95 
96 
97 
98  public:
99  ~GraphDefinition(void);
101  edge_t *edges,
102  unsigned int edge_count,
103  bool directed,
104  bool has_rcost);
105 
106 
107  int my_dijkstra(
108  int64_t start_vertex, int64_t end_vertex,
109  path_element_t **path, size_t *path_count,
110  std::ostringstream &log);
111 
112  void set_restrictions(
113  int64_t start_vertex,
114  int64_t end_vertex,
115  std::vector<PDVI> &ruleList);
116 
118  int start_edge, double start_part,
119  int end_edge, double end_part,
120  int64_t &start_vertex, int64_t &end_vertex);
121 
122 
123  bool construct_graph(
124  edge_t *edges,
125  bool has_rcost,
126  bool directed);
127 
128 
129  private:
130  double construct_path(int64_t ed_id, int64_t v_pos);
131  void explore(int64_t cur_node, GraphEdgeInfo& cur_edge, bool isStart, LongVector &vecIndex, std::priority_queue<PDP, std::vector<PDP>, std::greater<PDP> > &que);
132  double getRestrictionCost(int64_t cur_node, GraphEdgeInfo &new_edge, bool isStart);
133  bool addEdge(edge_t edgeIn);
134  bool connectEdge(GraphEdgeInfo& firstEdge, GraphEdgeInfo &secondEdge, bool bIsStartNodeSame);
135  bool get_single_cost(double total_cost, path_element_t **path, size_t *path_count);
136  void init();
137  void deleteall();
138 
139  private:
143  int64_t max_node_id;
144  int64_t max_edge_id;
147  double m_dStartpart;
148  double m_dEndPart;
151 
152  unsigned int m_edge_count;
153 
154  std::vector <path_element_t> m_vecPath;
155  std::vector < PARENT_PATH > parent;
156  std::vector < CostHolder > m_dCost;
160 };
161 
162 #endif
bool addEdge(edge_t edgeIn)
std::map< int64_t, std::vector< Rule > > RuleTable
std::pair< double, std::vector< int64_t > > PDVI
bool construct_graph(edge_t *edges, bool has_rcost, bool directed)
int path_count
Definition: BDATester.cpp:51
std::vector< PARENT_PATH > parent
double construct_path(int64_t ed_id, int64_t v_pos)
void set_restrictions(int64_t start_vertex, int64_t end_vertex, std::vector< PDVI > &ruleList)
std::map< int64_t, int64_t > Long2LongMap
GraphEdgeVector m_vecEdgeVector
int my_dijkstra(int64_t start_vertex, int64_t end_vertex, path_element_t **path, size_t *path_count, std::ostringstream &log)
std::map< int64_t, LongVector > Long2LongVectorMap
void explore(int64_t cur_node, GraphEdgeInfo &cur_edge, bool isStart, LongVector &vecIndex, std::priority_queue< PDP, std::vector< PDP >, std::greater< PDP > > &que)
std::vector< path_element_t > m_vecPath
RuleTable m_ruleTable
Long2LongMap m_mapEdgeId2Index
Long2LongVectorMap m_mapNodeId2Edge
std::pair< int, bool > PIB
std::vector< GraphEdgeInfo > GraphEdgeVector
bool get_single_cost(double total_cost, path_element_t **path, size_t *path_count)
std::vector< int64_t > precedencelist
void add_virtual_vertices(int start_edge, double start_part, int end_edge, double end_part, int64_t &start_vertex, int64_t &end_vertex)
bool connectEdge(GraphEdgeInfo &firstEdge, GraphEdgeInfo &secondEdge, bool bIsStartNodeSame)
int edge_count
Definition: BDATester.cpp:47
edge_astar_t * edges
Definition: BDATester.cpp:46
GraphDefinition(edge_t *edges, unsigned int edge_count, bool directed, bool has_rcost)
GraphEdgeInfo(int64_t eid, int64_t index, int64_t node1, int64_t node2, double cost, double reverse_cost)
path_element_t * path
Definition: BDATester.cpp:49
double getRestrictionCost(int64_t cur_node, GraphEdgeInfo &new_edge, bool isStart)
std::vector< LongVector > VectorOfLongVector
VectorOfLongVector m_vecRestrictedEdge
std::vector< CostHolder > m_dCost
std::vector< int64_t > LongVector
unsigned int m_edge_count
std::pair< double, PIB > PDP