PGROUTING  2.6
pgr_trspHandler.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 File: pgr_trspHandler.cpp
4 
5 Copyright (c) 2011 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 #include "trsp/pgr_trspHandler.h"
27 
28 #include <functional>
29 #include <utility>
30 #include <queue>
31 #include <vector>
32 #include <limits>
33 #include <algorithm>
34 #include <deque>
35 
37 #include "cpp_common/pgr_assert.h"
38 
39 namespace pgrouting {
40 namespace trsp {
41 
42 // -------------------------------------------------------------------------
44  pgr_edge_t *edges,
45  const size_t edge_count,
46  const bool directed,
47  const std::vector<Rule> &ruleList) :
48  m_ruleTable() {
49 
50  initialize_restrictions(ruleList);
51 
52  m_min_id = renumber_edges(edges, edge_count);
53 
55  edges,
56  edge_count,
57  directed);
58 
59 }
60 
61 
62 
63 // -------------------------------------------------------------------------
65  pgr_edge_t *edges,
66  size_t total_edges) const {
67  int64_t v_min_id = UINT64_MAX;
68  size_t z;
69  for (z = 0; z < total_edges; z++) {
70  if (edges[z].source < v_min_id)
71  v_min_id = edges[z].source;
72 
73  if (edges[z].target < v_min_id)
74  v_min_id = edges[z].target;
75  }
76 
77  for (z = 0; z < total_edges; z++) {
78  edges[z].source -= v_min_id;
79  edges[z].target -= v_min_id;
80  }
81 
82  return v_min_id;
83 }
84 
85 
86 
87 
88 // -------------------------------------------------------------------------
90  m_parent.clear();
91  m_dCost.clear();
92  m_path.clear();
93 }
94 
95 
96 // -------------------------------------------------------------------------
97 double Pgr_trspHandler::construct_path(int64_t ed_id, Position pos) {
98  pgassert(pos != ILLEGAL);
99 
100  if (m_parent[ed_id].isIllegal(pos)) {
101  Path_t pelement;
102  auto cur_edge = &m_edges[ed_id];
103  if (pos == RC_EDGE) {
104  pelement.node = cur_edge->startNode();
105  pelement.cost = cur_edge->cost();
106  } else {
107  pelement.node = cur_edge->endNode();
108  pelement.cost = cur_edge->r_cost();
109  }
110  pelement.edge = cur_edge->edgeID();
111 
112  m_path.push_back(pelement);
114  return pelement.cost;
115  }
116 
117  double ret = construct_path(m_parent[ed_id].e_idx[pos],
118  m_parent[ed_id].v_pos[pos]);
119  Path_t pelement;
120  auto cur_edge = &m_edges[ed_id];
121  if (pos == RC_EDGE) {
122  pelement.node = cur_edge->startNode();
123  pelement.cost = m_dCost[ed_id].endCost - ret;
124  ret = m_dCost[ed_id].endCost;
125  } else {
126  pelement.node = cur_edge->endNode();
127  pelement.cost = m_dCost[ed_id].startCost - ret;
128  ret = m_dCost[ed_id].startCost;
129  }
130  pelement.edge = cur_edge->edgeID();
131 
132  m_path.push_back(pelement);
133 
134  return ret;
135 }
136 
137 
138 // -------------------------------------------------------------------------
140  int64_t edge_ind,
141  const EdgeInfo &edge,
142  bool isStart) {
143  double cost = 0.0;
144  int64_t edge_id = edge.edgeID();
145  if (m_ruleTable.find(edge_id) == m_ruleTable.end()) {
146  return(0.0);
147  }
148  auto vecRules = m_ruleTable[edge_id];
149  int64_t st_edge_ind = edge_ind;
150  for (const auto &rule : vecRules) {
151  bool flag = true;
152  int64_t v_pos = (isStart? C_EDGE : RC_EDGE);
153  edge_ind = st_edge_ind;
154 
155  pgassert(!(edge_ind == -1));
156  for (auto const &precedence : rule.precedencelist()) {
157  if (precedence != m_edges[edge_ind].edgeID()) {
158  flag = false;
159  break;
160  }
161  auto m_parent_ind = m_parent[edge_ind].e_idx[v_pos];
162  v_pos = m_parent[edge_ind].v_pos[v_pos];
163  edge_ind = m_parent_ind;
164  }
165  if (flag)
166  cost += rule.cost();
167  }
168  return cost;
169 }
170 
171 
173  double cost,
174  size_t edge_idx,
175  bool isStart) {
176  if (isStart) {
177  return m_dCost[edge_idx].startCost +
178  cost;
179  }
180  return m_dCost[edge_idx].endCost +
181  cost;
182 }
183 
184 
185 // -------------------------------------------------------------------------
187  int64_t cur_node,
188  const EdgeInfo cur_edge,
189  bool isStart) {
190  double extra_cost = 0.0;
191  double totalCost;
192 
193  auto vecIndex = cur_edge.get_idx(isStart);
194 
195  for (const auto &index : vecIndex) {
196  auto edge = m_edges[index];
197 
198  extra_cost = getRestrictionCost(
199  cur_edge.idx(),
200  edge, isStart);
201 
202  if ((edge.startNode() == cur_node) && (edge.cost() >= 0.0)) {
203  totalCost = get_tot_cost(
204  edge.cost() + extra_cost,
205  cur_edge.idx(),
206  isStart);
207 
208  if (totalCost < m_dCost[index].endCost) {
209  m_dCost[index].endCost = totalCost;
210  m_parent[edge.idx()].v_pos[RC_EDGE] = (isStart? C_EDGE : RC_EDGE);
211  m_parent[edge.idx()].e_idx[RC_EDGE] =
212  cur_edge.idx();
213 
214  add_to_que(totalCost, edge.idx(), true);
215  }
216  }
217 
218  if ((edge.endNode() == cur_node) && (edge.r_cost() >= 0.0)) {
219  totalCost = get_tot_cost(
220  edge.r_cost() + extra_cost,
221  cur_edge.idx(),
222  isStart);
223 
224  if (totalCost < m_dCost[index].startCost) {
225  m_dCost[index].startCost = totalCost;
226  m_parent[edge.idx()].v_pos[C_EDGE] = (isStart? C_EDGE : RC_EDGE);
227  m_parent[edge.idx()].e_idx[C_EDGE] = cur_edge.idx();
228 
229  add_to_que(totalCost, edge.idx(), false);
230  }
231  }
232  } // for
233 }
234 
235 
236 
237 // -------------------------------------------------------------------------
239  const std::vector<Rule> &ruleList) {
240  for (const auto rule : ruleList) {
241  auto dest_edge_id = rule.dest_id();
242  if (m_ruleTable.find(dest_edge_id) != m_ruleTable.end()) {
243  m_ruleTable[dest_edge_id].push_back(rule);
244  } else {
245  std::vector<Rule> r;
246  r.push_back(rule);
247  m_ruleTable.insert(std::make_pair(dest_edge_id, r));
248  }
249  }
250 
251  return true;
252 }
253 
259 Path
261  const int64_t start_vertex,
262  const int64_t end_vertex) {
263  clear();
264 
265  m_start_vertex = start_vertex - m_min_id;
266  m_end_vertex = end_vertex - m_min_id;
267 
269  m_path = tmp;
270 
271  if (m_adjacency.find(m_start_vertex) == m_adjacency.end()) {
272  return Path();
273  }
274 
275  if (m_adjacency.find(m_end_vertex) == m_adjacency.end()) {
276  return Path();
277  }
278 
279  return process_trsp(m_edges.size());
280 }
281 
282 
283 
284 
285 
286 
292 std::deque<Path>
294  const std::vector<int64_t> sources,
295  const std::vector<int64_t> targets) {
296  std::deque<Path> paths;
297  for (const auto &s : sources) {
298  for (const auto &t : targets) {
299  paths.push_back(process(s, t));
300  }
301  }
302 
303  std::sort(paths.begin(), paths.end(),
304  [](const Path &e1, const Path &e2)->bool {
305  return e1.end_id() < e2.end_id();
306  });
307  std::stable_sort(paths.begin(), paths.end(),
308  [](const Path &e1, const Path &e2)->bool {
309  return e1.start_id() < e2.start_id();
310  });
311  return paths;
312 }
313 
314 
315 
316 
317 
319  double cost,
320  size_t e_idx,
321  bool isStart) {
322  que.push(std::make_pair(cost,
323  std::make_pair(e_idx, isStart)));
324 }
325 
326 
327 
328 // -------------------------------------------------------------------------
329 
331  /*
332  * For each adjacent edge to the start_vertex
333  */
334  for (const auto source : m_adjacency[m_start_vertex]) {
335  EdgeInfo &cur_edge = m_edges[source];
336 
337  if (cur_edge.startNode() == m_start_vertex
338  && cur_edge.cost() >= 0.0) {
339  m_dCost[cur_edge.idx()].endCost = cur_edge.cost();
340  m_parent[cur_edge.idx()].v_pos[0] = ILLEGAL;
341  add_to_que(cur_edge.cost(), cur_edge.idx(), true);
342  }
343 
344  if (cur_edge.endNode() == m_start_vertex
345  && cur_edge.r_cost() >= 0.0) {
346  m_dCost[cur_edge.idx()].startCost =
347  cur_edge.r_cost();
348  m_parent[cur_edge.idx()].v_pos[1] = ILLEGAL;
349  add_to_que(cur_edge.r_cost(), cur_edge.idx(), false);
350  }
351  }
352 }
353 
355  EdgeInfo cur_edge;
357 
358  while (!que.empty()) {
359  auto cur_pos = que.top();
360  que.pop();
361 
362  auto cure_idxex = cur_pos.second.first;
363  cur_edge = m_edges[cure_idxex];
364 
365  if (cur_pos.second.second) {
366  /*
367  * explore edges connected to end node
368  */
369  current_node = cur_edge.endNode();
370  if (cur_edge.cost() < 0.0) continue;
371  if (current_node == m_end_vertex) break;
372  explore(current_node, cur_edge, false);
373  } else {
374  /*
375  * explore edges connected to start node
376  */
377  current_node = cur_edge.startNode();
378  if (cur_edge.r_cost() < 0.0) continue;
379  if (current_node == m_end_vertex) break;
380  explore(current_node, cur_edge, true);
381  }
382  }
383  return cur_edge;
384 }
385 
386 
387 
388 
389 Path
391  size_t edge_count) {
394  pgassert(m_parent.empty());
395 
396  m_parent.resize(edge_count + 1);
397  m_dCost.resize(edge_count + 1);
398 
399  initialize_que();
400 
402 
404 
405  auto cur_edge = dijkstra_exploration();
406 
408  if (current_node != m_end_vertex) {
410  return result.renumber_vertices(m_min_id);;
411  }
412 
414 
415  if (current_node == cur_edge.startNode()) {
416  construct_path(cur_edge.idx(), C_EDGE);
417  } else {
418  construct_path(cur_edge.idx(), RC_EDGE);
419  }
420 
421  Path_t pelement;
422  pelement.node = m_end_vertex;
423  pelement.edge = -1;
424  pelement.cost = 0.0;
425  m_path.push_back(pelement);
426 
427  m_path.Path::recalculate_agg_cost();
429 }
430 
431 
432 
433 
434 
435 // -------------------------------------------------------------------------
437  pgr_edge_t* edges,
438  const size_t edge_count,
439  const bool directed) {
440 
441  for (size_t i = 0; i < edge_count; i++) {
442  auto current_edge = &edges[i];
443 
444  /*
445  * making all costs > 0
446  */
447  if (current_edge->cost < 0 && current_edge->reverse_cost > 0) {
448  std::swap(current_edge->cost, current_edge->reverse_cost);
449  std::swap(current_edge->source, current_edge->target);
450  }
451 
452  if (!directed) {
453  if (current_edge->reverse_cost < 0) {
454  current_edge->reverse_cost = current_edge->cost;
455  }
456  }
457  addEdge(*current_edge);
458  }
459  m_mapEdgeId2Index.clear();
460 }
461 
462 
463 // -------------------------------------------------------------------------
465  size_t firstEdge_idx,
466  size_t secondEdge_idx) {
467  EdgeInfo &firstEdge = m_edges[firstEdge_idx];
468  EdgeInfo &secondEdge = m_edges[secondEdge_idx];
469 
470  if (firstEdge.r_cost() >= 0.0) {
471  firstEdge.connect_startEdge(secondEdge_idx);
472  }
473 
474  if (firstEdge.startNode() == secondEdge.startNode()
475  && secondEdge.r_cost() >= 0.0) {
476  secondEdge.connect_startEdge(firstEdge_idx);
477  }
478 
479  if (firstEdge.startNode() == secondEdge.endNode()
480  &&secondEdge.cost() >= 0.0) {
481  secondEdge.connect_endEdge(firstEdge_idx);
482  }
483 }
484 
485 
486 // -------------------------------------------------------------------------
488  size_t firstEdge_idx,
489  size_t secondEdge_idx) {
490  EdgeInfo &firstEdge = m_edges[firstEdge_idx];
491  EdgeInfo &secondEdge = m_edges[secondEdge_idx];
492 
493  if (firstEdge.cost() >= 0.0) {
494  firstEdge.connect_endEdge(secondEdge_idx);
495  }
496 
497  if (firstEdge.endNode() == secondEdge.startNode()
498  && secondEdge.r_cost() >= 0.0) {
499  secondEdge.connect_startEdge(firstEdge_idx);
500  }
501 
502  if (firstEdge.endNode() == secondEdge.endNode()
503  && secondEdge.cost() >= 0.0) {
504  secondEdge.connect_endEdge(firstEdge_idx);
505  }
506 }
507 
508 
509 // -------------------------------------------------------------------------
511  /*
512  * The edge was already inserted
513  *
514  * If the user has rows with repeated edge id, the subsequent edges will be ignored
515  *
516  * When changing to boost graph, the additional edges are to be added
517  */
518  if (m_mapEdgeId2Index.find(edgeIn.id) != m_mapEdgeId2Index.end()) {
519  return false;
520  }
521 
522 
523  /*
524  * the index of this new edge in the edges container is
525  * m_edges.size()
526  */
527  EdgeInfo edge(edgeIn, m_edges.size());
528 
529  // Adding edge to the list
530  m_mapEdgeId2Index.insert(
531  std::make_pair(
532  edge.edgeID(),
533  m_edges.size()));
534 
535  m_edges.push_back(edge);
536 
537  EdgeInfo &newEdge = m_edges[m_edges.size()-1];
538 
539 
540 
541  /*
542  * Searching the start node for connectivity
543  */
544  auto itNodeMap = m_adjacency.find(edgeIn.source);
545 
546  if (itNodeMap != m_adjacency.end()) {
547  for (const auto e_idx : itNodeMap->second) {
548  connectStartEdge(edge.idx(), e_idx);
549  }
550  }
551 
552 
553  /*
554  * Searching the end node for connectivity
555  */
556  itNodeMap = m_adjacency.find(edgeIn.target);
557  if (itNodeMap != m_adjacency.end()) {
558  for (const auto e_idx : itNodeMap->second) {
559  connectEndEdge(edge.idx(), e_idx);
560  }
561  }
562 
563 
564  /*
565  * Add the edges to the adjacency list
566  */
567  m_adjacency[edgeIn.source].push_back(newEdge.idx());
568  m_adjacency[edgeIn.target].push_back(newEdge.idx());
569 
570 
571 
572  return true;
573 }
574 
575 
576 
577 } // namespace trsp
578 } // namespace pgrouting
bool addEdge(const pgr_edge_t edgeIn)
double cost() const
Definition: edgeInfo.h:58
float8 cost
Definition: trsp.h:35
void connectStartEdge(size_t firstEdge_idx, size_t secondEdge_idx)
std::vector< size_t > get_idx(bool isStart) const
Definition: edgeInfo.h:82
int64_t endNode() const
Definition: edgeInfo.h:53
double getRestrictionCost(int64_t cur_node, const EdgeInfo &new_edge, bool isStart)
Definition: trsp.h:31
int64_t source
Definition: pgr_edge_t.h:60
Path process_trsp(size_t edge_count)
int64_t target
Definition: pgr_edge_t.h:61
void connect_endEdge(size_t edge_idx)
Definition: edgeInfo.h:67
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
double cost
Definition: path_t.h:39
Path & renumber_vertices(int64_t value)
void push_back(Path_t data)
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...
void connect_startEdge(size_t edge_idx)
Definition: edgeInfo.h:70
int64_t end_id() const
int64_t edgeID() const
Definition: edgeInfo.h:57
int64_t edge
Definition: path_t.h:38
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
int64_t id
Definition: pgr_edge_t.h:59
int64_t node
Definition: path_t.h:37
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
int64_t startNode() const
Definition: edgeInfo.h:49
int initialize_restrictions(const std::vector< Rule > &ruleList)
int64_t renumber_edges(pgr_edge_t *edges, const size_t edge_count) const
Definition: path_t.h:36
int64_t start_id() const
Book keeping class for swapping orders between vehicles.
Definition: basic_edge.cpp:28
Assertions Handling.
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)
void clear()
std::vector< Predecessor > m_parent
double r_cost() const
Definition: edgeInfo.h:59
size_t idx() const
Definition: edgeInfo.h:47