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