PGROUTING  2.6
pgr_trspHandler.h
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 FILE: pgr_trspHandler.h
4 
5 Copyright (c) 2017 pgRouting developers
6 Mail: project@pgrouting.org
7 
8 ------
9 
10 This program is free software; you can redistribute it and/or modify
11 it under the terms of the GNU General Public License as published by
12 the Free Software Foundation; either version 2 of the License, or
13 (at your option) any later version.
14 
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
19 
20 You should have received a copy of the GNU General Public License
21 aint64_t with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
23 
24  ********************************************************************PGR-GNU*/
25 
26 #ifndef INCLUDE_TRSP_PGR_TRSPHANDLER_H_
27 #define INCLUDE_TRSP_PGR_TRSPHANDLER_H_
28 
29 #include <stdlib.h>
30 
31 #include <vector>
32 #include <deque>
33 #include <map>
34 #include <queue>
35 #include <string>
36 #include <iostream>
37 #include <utility>
38 #include <functional>
39 #include <limits>
40 
41 
43 #include "trsp/edgeInfo.h"
44 #include "trsp/rule.h"
45 
46 namespace pgrouting {
47 namespace trsp {
48 
49 
50 
51 
56  typedef std::pair<double, std::pair<int64_t, bool>> PDP;
57 
68  enum Position {ILLEGAL = -1, RC_EDGE = 0, C_EDGE = 1};
69 
70 
71  class Predecessor {
72  public:
74  e_idx(2),
75  v_pos(2) {
76  for (auto &p : v_pos) p = ILLEGAL;
77  }
78 
79  bool isIllegal(size_t i) {return v_pos[i] == ILLEGAL;}
80  bool isIllegal(Position i) {
81  pgassert(i != ILLEGAL);
82  return v_pos[i] == ILLEGAL;}
83 
84  std::vector<size_t> e_idx;
85  std::vector<Position> v_pos;
86  };
87 
88 
89  class CostHolder {
90  public:
92  endCost = startCost = (std::numeric_limits<double>::max)();
93  }
94 
95  public:
96  double startCost;
97  double endCost;
98  };
99 
100 
101  public:
103  pgr_edge_t *edges,
104  const size_t edge_count,
105  const bool directed,
106  const std::vector<Rule> &ruleList);
107 
108  Pgr_trspHandler(void) = delete;
109  ~Pgr_trspHandler(void) = default;
110 
111 
112  Path process(
113  const int64_t start_vertex,
114  const int64_t end_vertex);
115 
116  std::deque<Path> process(
117  const std::vector<int64_t> sources,
118  const std::vector<int64_t> targets);
119 
120 
121  void clear();
122 
123  private:
124  void construct_graph(
125  pgr_edge_t *edges,
126  const size_t edge_count,
127  const bool directed);
128 
130  const std::vector<Rule> &ruleList);
131 
132  void initialize_que();
133 
135  size_t edge_count);
136 
138 
139 
140 
141  void explore(
142  int64_t cur_node,
143  const EdgeInfo cur_edge,
144  bool isStart);
145 
146  double getRestrictionCost(
147  int64_t cur_node,
148  const EdgeInfo &new_edge,
149  bool isStart);
150  bool addEdge(const pgr_edge_t edgeIn);
151 
152  void connectStartEdge(
153  size_t firstEdge_idx,
154  size_t secondEdge_idx);
155 
156  void connectEndEdge(
157  size_t firstEdge_idx,
158  size_t secondEdge_idx);
159 
160  double construct_path(int64_t ed_id, Position pos);
161 
162 
163  int64_t renumber_edges(
164  pgr_edge_t *edges,
165  const size_t edge_count) const;
166 
167  void add_to_que(
168  double cost,
169  size_t e_idx,
170  bool isStart);
171 
172  double get_tot_cost(
173  double cost,
174  size_t edge_idx,
175  bool isStart);
176 
177  private:
178  std::vector<EdgeInfo> m_edges;
179 
184  std::map<int64_t, int64_t> m_mapEdgeId2Index;
185 
189  std::map<int64_t, std::vector<size_t>> m_adjacency;
190 
191 
192  int64_t m_start_vertex;
193  int64_t m_end_vertex;
194 
195  /*
196  * Used in dijkstra_exploration
197  */
198  int64_t current_node;
199 
200  int64_t m_min_id;
201 
203 
204  std::vector<Predecessor> m_parent;
205  std::vector<CostHolder> m_dCost;
206 
207  std::map<int64_t, std::vector<Rule>> m_ruleTable;
208 
209  /*
210  * priority queue
211  */
212  std::priority_queue<PDP, std::vector<PDP>, std::greater<PDP> > que;
213 };
214 
215 
216 } // namespace trsp
217 } // namespace pgrouting
218 
219 #endif // INCLUDE_TRSP_PGR_TRSPHANDLER_H_
std::pair< double, std::pair< int64_t, bool > > PDP
Used in the priority queue.
bool addEdge(const pgr_edge_t edgeIn)
void connectStartEdge(size_t firstEdge_idx, size_t secondEdge_idx)
double getRestrictionCost(int64_t cur_node, const EdgeInfo &new_edge, bool isStart)
Path process_trsp(size_t edge_count)
void connectEndEdge(size_t firstEdge_idx, size_t secondEdge_idx)
void construct_graph(pgr_edge_t *edges, const size_t edge_count, const bool directed)
double get_tot_cost(double cost, size_t edge_idx, bool isStart)
std::priority_queue< PDP, std::vector< PDP >, std::greater< PDP > > que
void explore(int64_t cur_node, const EdgeInfo cur_edge, bool isStart)
std::map< int64_t, int64_t > m_mapEdgeId2Index
Used only to veryfy that there are no reppetitions inserted the way it orks, repeating edges id is no...
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
void add_to_que(double cost, size_t e_idx, bool isStart)
std::map< int64_t, std::vector< size_t > > m_adjacency
m_adjacency[vertex] = {edges}
std::vector< CostHolder > m_dCost
int initialize_restrictions(const std::vector< Rule > &ruleList)
int64_t renumber_edges(pgr_edge_t *edges, const size_t edge_count) const
Book keeping class for swapping orders between vehicles.
Definition: basic_edge.cpp:28
std::vector< EdgeInfo > m_edges
Path process(const int64_t start_vertex, const int64_t end_vertex)
process
std::map< int64_t, std::vector< Rule > > m_ruleTable
double construct_path(int64_t ed_id, Position pos)
std::vector< Predecessor > m_parent