PGROUTING  2.6-dev
pgr_dijkstraVia.hpp
Go to the documentation of this file.
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 
37 
38 #include "cpp_common/pgr_assert.h"
39 
40 
41 namespace pgRouting {
42 
43 template <class G>
44 void
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_
std::deque< Path > pgr_dijkstra(G &graph, std::vector< int64_t > sources, std::vector< int64_t > targets, bool only_cost, bool normal)
bool empty() const
Assertions Handling.
size_t size() const
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)