1 /*PGR-GNU*****************************************************************
2 File: pgr_dijkstraVia.hpp
3
4 Generated with Template by:
5 Copyright (c) 2015 pgRouting developers
6
7 Function's developer:
8 Copyright (c) 2015 Celia Virginia Vergara Castillo
9
10 ------
11
12 This program is free software; you can redistribute it and/or modify
13 it under the terms of the GNU General Public License as published by
14 the Free Software Foundation; either version 2 of the License, or
15 (at your option) any later version.
16
17 This program is distributed in the hope that it will be useful,
18 but WITHOUT ANY WARRANTY; without even the implied warranty of
19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 GNU General Public License for more details.
21
22 You should have received a copy of the GNU General Public License
23 along with this program; if not, write to the Free Software
24 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
25
26 ********************************************************************PGR-GNU*/
27
28 #ifndef INCLUDE_DIJKSTRA_PGR_DIJKSTRAVIA_HPP_
29 #define INCLUDE_DIJKSTRA_PGR_DIJKSTRAVIA_HPP_
30 #pragma once
31
32 #include <sstream>
33 #include <deque>
34 #include <vector>
35
36 #include "dijkstra/pgr_dijkstra.hpp"
37
38 #include "cpp_common/pgr_assert.h"
39
40
41 namespace pgRouting {
42
43 template <class G>
44 void
pgr_dijkstraVia(G & graph,const std::vector<int64_t> & via_vertices,std::deque<Path> & paths,bool strict,bool U_turn_on_edge,std::ostringstream & log)45 pgr_dijkstraVia(
46 G &graph,
47 const std::vector< int64_t > &via_vertices,
48 std::deque< Path > &paths,
49 bool strict,
50 bool U_turn_on_edge,
51 std::ostringstream &log) {
52 if (via_vertices.size() == 0) {
53 return;
54 }
55
56 paths.clear();
57 int64_t prev_vertex = via_vertices[0];
58 Path path;
59
60 int64_t i = 0;
61 for (const auto &vertex : via_vertices) {
62 if (i == 0) {
63 prev_vertex = vertex; ++i;
64 continue;
65 }
66
67 // Delete U Turn edges only valid for paths that are not the first path
68 if (!U_turn_on_edge && i > 1) {
69 /*
70 * Can only delete if there was a path,
71 * that is at least one edge size
72 */
73 if (path.size() > 1) {
74 /*
75 * Delete from the graph the last edge if its outgoing also
76 * edge to be removed = second to last edge path[i].edge;
77 */
78 int64_t edge_to_be_removed = path[path.size() - 2].edge;
79 int64_t last_vertex_of_path = prev_vertex;
80
81 // and the current vertex is not a dead end
82 if (graph.out_degree(last_vertex_of_path) > 1) {
83 log << "\ndeparting from " << last_vertex_of_path
84 << " deleting edge " << edge_to_be_removed << "\n";
85 graph.disconnect_out_going_edge(
86 last_vertex_of_path,
87 edge_to_be_removed);
88 }
89 }
90 }
91
92 log << "\nfrom " << prev_vertex << " to " << vertex;
93 path = pgr_dijkstra(graph, prev_vertex, vertex);
94
95 if (!U_turn_on_edge && i > 1) {
96 graph.restore_graph();
97 if (path.empty()) {
98 /*
99 * no path was found with the deleted edge
100 * try with the edge back in the graph
101 */
102 log << "\nEmpty so again from "
103 << prev_vertex << " to " << vertex;
104 path = pgr_dijkstra(graph, prev_vertex, vertex);
105 }
106 }
107
108 if (strict && path.empty()) {
109 paths.clear();
110 return;
111 }
112 paths.push_back(path);
113
114 /*
115 * got to the next
116 */
117 prev_vertex = vertex; ++i;
118 }
119 }
120
121
122 } // namespace pgRouting
123
124 #endif // INCLUDE_DIJKSTRA_PGR_DIJKSTRAVIA_HPP_
125