pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
GraphDefinition.h
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 
30 #include <sstream>
31 #include "trsp.h"
32 
33 
34 typedef std::pair<double, std::vector<int64_t> > PDVI;
35 
36 
38  typedef std::vector<long> LongVector;
39  typedef std::vector<LongVector> VectorOfLongVector;
40  typedef std::pair<int, bool> PIB;
41  typedef std::pair<double, PIB> PDP;
42  typedef struct{
43  int64_t ed_ind[2];
44  int64_t v_pos[2];
45  } PARENT_PATH;
46 
47  typedef struct{
48  double cost;
49  std::vector<int64_t> precedencelist;
50  } Rule;
51 
52  typedef struct{
53  double startCost, endCost;
54  } CostHolder;
55 
56  typedef std::map<int64_t, std::vector<Rule> > RuleTable;
57 
58 
59 
60  class GraphEdgeInfo {
61  public:
62  GraphEdgeInfo() = default;
63  GraphEdgeInfo(int64_t eid, int64_t index, int64_t node1, int64_t node2, double cost, double reverse_cost) :
64  m_lEdgeID(eid), m_lEdgeIndex(index), m_lStartNode(node1), m_lEndNode(node2),
65  m_dCost(cost), m_dReverseCost(reverse_cost) {
66  m_vecStartConnectedEdge.clear();
67  m_vecEndConnedtedEdge.clear();
68  m_vecRestrictedEdge.clear();
69  }
70 
71 
72  public:
73  long m_lEdgeID;
74  long m_lEdgeIndex;
75  long m_lStartNode;
76  long m_lEndNode;
77  double m_dCost;
78  double m_dReverseCost;
79  short m_sDirection;
80  LongVector m_vecStartConnectedEdge;
81  LongVector m_vecEndConnedtedEdge;
82  //LongVector m_vecConnectedNode;
83  bool m_bIsLeadingRestrictedEdge;
84  VectorOfLongVector m_vecRestrictedEdge;
85 
86  };
87 
88 
89  typedef std::vector<GraphEdgeInfo> GraphEdgeVector;
90  typedef std::map<long,LongVector> Long2LongVectorMap;
91  typedef std::map<long,long> Long2LongMap;
92 
93 
94 
95 
96  public:
97  ~GraphDefinition(void);
99  edge_t *edges,
100  unsigned int edge_count,
101  bool directed,
102  bool has_rcost);
103 
104 
105  int my_dijkstra(
106  int64_t start_vertex, int64_t end_vertex,
107  path_element_t **path, size_t *path_count,
108  std::ostringstream &log);
109 
110  void set_restrictions(
111  int64_t start_vertex,
112  int64_t end_vertex,
113  std::vector<PDVI> &ruleList);
114 
115  void add_virtual_vertices(
116  int start_edge, double start_part,
117  int end_edge, double end_part,
118  int64_t &start_vertex, int64_t &end_vertex);
119 
120 
121  bool construct_graph(
122  edge_t *edges,
123  bool has_rcost,
124  bool directed);
125 
126 
127  private:
128  double construct_path(int64_t ed_id, int64_t v_pos);
129  void explore(int64_t cur_node, GraphEdgeInfo& cur_edge, bool isStart, LongVector &vecIndex, std::priority_queue<PDP, std::vector<PDP>, std::greater<PDP> > &que);
130  double getRestrictionCost(int64_t cur_node, GraphEdgeInfo &new_edge, bool isStart);
131  bool addEdge(edge_t edgeIn);
132  bool connectEdge(GraphEdgeInfo& firstEdge, GraphEdgeInfo &secondEdge, bool bIsStartNodeSame);
133  bool get_single_cost(double total_cost, path_element_t **path, size_t *path_count);
134  void init();
135  void deleteall();
136 
137  private:
138  GraphEdgeVector m_vecEdgeVector;
139  Long2LongMap m_mapEdgeId2Index;
140  Long2LongVectorMap m_mapNodeId2Edge;
141  int64_t max_node_id;
142  int64_t max_edge_id;
143  int m_lStartEdgeId;
144  int m_lEndEdgeId;
145  double m_dStartpart;
146  double m_dEndPart;
147  bool isStartVirtual;
148  bool isEndVirtual;
149 
150  unsigned int m_edge_count;
151 
152  std::vector <path_element_t> m_vecPath;
153  std::vector < PARENT_PATH > parent;
154  std::vector < CostHolder > m_dCost;
155  RuleTable m_ruleTable;
156  bool m_bIsturnRestrictOn;
157  bool m_bIsGraphConstructed;
158 };
159 
160 #endif