PGROUTING  2.6
pgr_ksp.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_ksp.hpp
3 
4 Copyright (c) 2015 Celia Virginia Vergara Castillo
5 Mail: vicky_vergara@hotmail.com
6 
7 ------
8 
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2 of the License, or
12 (at your option) any later version.
13 
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18 
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22 
23 ********************************************************************PGR-GNU*/
24 
25 #ifndef INCLUDE_YEN_PGR_KSP_HPP_
26 #define INCLUDE_YEN_PGR_KSP_HPP_
27 #pragma once
28 
30 
31 #include <sstream>
32 #include <deque>
33 #include <vector>
34 #include <set>
35 #include <limits>
36 
37 #include "cpp_common/pgr_assert.h"
39 
40 template < class G >
41 class Pgr_ksp {
42  public:
43  std::deque<Path> Yen(
44  G &graph,
45  int64_t source,
46  int64_t target,
47  int K,
48  bool heap_paths);
49  void clear();
50 
51  private:
52  class compPaths {
53  public:
54  bool operator()(const Path &p1, const Path &p2) const {
55  /*
56  * less cost is best
57  */
58  if (p1.tot_cost() > p2.tot_cost())
59  return false;
60  if (p1.tot_cost() < p2.tot_cost())
61  return true;
62 
63  pgassert(p1.tot_cost() == p2.tot_cost());
64 
65  // paths costs are equal now check by length
66  if (p1.size() > p2.size())
67  return false;
68  if (p1.size() < p2.size())
69  return true;
70 
71  pgassert(p1.tot_cost() == p2.tot_cost());
72  pgassert(p1.size() == p2.size());
73 
74  // paths weights & lengths are equal now check by node ID
75  unsigned int i;
76  for (i = 0; i < p1.size(); i++) {
77  if (p1[i].node > p2[i].node)
78  return false;
79  if (p1[i].node < p2[i].node)
80  return true;
81  }
82 
83  pgassert(p1.tot_cost() == p2.tot_cost());
84  pgassert(p1.size() == p2.size());
85 #ifdef NDEBUG
86  for (i = 0; i < p1.size(); i++) {
87  pgassert(p1[i].node == p2[i].node);
88  }
89 #endif
90 
91  // we got here and everything is equal
92  return false;
93  }
94  };
95 
97  void executeYen(G &graph, int top_k);
98 
100 
103  void getFirstSolution(G &graph);
105  void doNextCycle(G &graph);
107  void removeVertices(G &graph, const Path &path);
109 
110  private:
112  typedef typename G::V V;
116  int64_t m_start;
117  int64_t m_end;
118 
120 
121  typedef std::set<Path, compPaths> pSet;
122  pSet m_ResultSet;
123  pSet m_Heap;
124 
125  std::ostringstream log;
126 };
127 
128 
129 template < class G >
131  m_Heap.clear();
132 }
133 
134 template < class G >
136  Path path;
137 
138  Pgr_dijkstra< G > fn_dijkstra;
139  path = fn_dijkstra.dijkstra(graph, m_start, m_end);
140 
141  if (path.empty()) return;
142  curr_result_path = path;
144 }
145 
146 template < class G>
147 std::deque<Path>
149  int64_t start_vertex, int64_t end_vertex, int K, bool heap_paths) {
150  /*
151  * No path: already in destination
152  */
153  if ((start_vertex == end_vertex) || (K == 0)) {
154  return std::deque<Path>();
155  }
156  /*
157  * no path: disconnected vertices
158  */
159  if (!graph.has_vertex(start_vertex)
160  || !graph.has_vertex(end_vertex)) {
161  return std::deque<Path>();
162  }
163  m_ResultSet.clear();
164  m_Heap.clear();
165 
166  v_source = graph.get_V(start_vertex);
167  v_target = graph.get_V(end_vertex);
168  m_start = start_vertex;
169  m_end = end_vertex;
170  executeYen(graph, K);
171 
172  while (!m_ResultSet.empty()) {
173  m_Heap.insert(*m_ResultSet.begin());
174  m_ResultSet.erase(m_ResultSet.begin());
175  }
176  std::deque<Path> l_ResultList(m_Heap.begin(), m_Heap.end());
177 
178  std::stable_sort(l_ResultList.begin(), l_ResultList.end(),
179  [](const Path &left, const Path &right) -> bool {
180  for (size_t i = 0;
181  i < (std::min)(left.size(), right.size());
182  ++i) {
183  if (left[i].node < right[i].node) return true;
184  if (left[i].node > right[i].node) return false;
185  }
186  return false;
187  });
188 
189  std::stable_sort(l_ResultList.begin(), l_ResultList.end(),
190  [](const Path &left, const Path &right) {
191  return left.size() < right.size();});
192 
193  if (!heap_paths && l_ResultList.size() > (size_t) K)
194  l_ResultList.resize(K);
195 
196  return l_ResultList;
197 }
198 
199 
200 template < class G >
201 void Pgr_ksp< G >::removeVertices(G &graph, const Path &subpath) {
202  for (const auto &e : subpath)
203  graph.disconnect_vertex(e.node);
204 }
205 
206 template < class G >
208  int64_t spurNodeId;
209 
210 
211  for (unsigned int i = 0; i < curr_result_path.size(); ++i) {
212  spurNodeId = curr_result_path[i].node;
213 
214  auto rootPath = curr_result_path.getSubpath(i);
215 
216  for (const auto &path : m_ResultSet) {
217  if (path.isEqual(rootPath)) {
218  if (path.size() > i + 1) {
219  graph.disconnect_edge(path[i].node, // from
220  path[i + 1].node); // to
221  }
222  }
223  }
224 
225  removeVertices(graph, rootPath);
226 
227  Pgr_dijkstra< G > fn_dijkstra;
228  auto spurPath = fn_dijkstra.dijkstra(graph, spurNodeId, m_end);
229 
230  if (spurPath.size() > 0) {
231  rootPath.appendPath(spurPath);
232  m_Heap.insert(rootPath);
233  }
234 
235  graph.restore_graph();
236  }
237 }
238 
239 template < class G >
240 void Pgr_ksp< G >::executeYen(G &graph, int K) {
241  clear();
242  getFirstSolution(graph);
243 
244  if (m_ResultSet.size() == 0) return; // no path found
245 
246  while (m_ResultSet.size() < (unsigned int) K) {
247  doNextCycle(graph);
248  if (m_Heap.empty()) break;
249  curr_result_path = *m_Heap.begin();
251  m_Heap.erase(m_Heap.begin());
252  /*
253  * without the next line withpointsKSP hungs with:
254  * c++ 4.6
255  * Debug mode
256  */
257 #ifndef NDEBUG
258  log << "end of while heap size" << m_Heap.size();
259 #endif
260  }
261 }
262 
263 #endif // INCLUDE_YEN_PGR_KSP_HPP_
V v_source
source descriptor
Definition: pgr_ksp.hpp:114
void clear()
Definition: pgr_ksp.hpp:130
V v_target
target descriptor
Definition: pgr_ksp.hpp:115
Path curr_result_path
storage for the current result
Definition: pgr_ksp.hpp:119
pSet m_Heap
the heap
Definition: pgr_ksp.hpp:123
G::V V
Definition: pgr_ksp.hpp:113
int64_t m_start
source id
Definition: pgr_ksp.hpp:116
std::set< Path, compPaths > pSet
Definition: pgr_ksp.hpp:121
CGAL::Filtered_kernel< SC > K
double tot_cost() const
int64_t m_end
target id
Definition: pgr_ksp.hpp:117
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
Path dijkstra(G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
Dijkstra 1 to 1.
void getFirstSolution(G &graph)
Performs the first Dijkstra of the algorithm.
Definition: pgr_ksp.hpp:135
bool empty() const
Assertions Handling.
Path getSubpath(unsigned int j) const
bool operator()(const Path &p1, const Path &p2) const
Definition: pgr_ksp.hpp:54
void doNextCycle(G &graph)
Performs the next cycle of the algorithm.
Definition: pgr_ksp.hpp:207
std::deque< Path > Yen(G &graph, int64_t source, int64_t target, int K, bool heap_paths)
Definition: pgr_ksp.hpp:148
pSet m_ResultSet
ordered set of shortest paths
Definition: pgr_ksp.hpp:122
size_t size() const
std::ostringstream log
Definition: pgr_ksp.hpp:125
void appendPath(const Path &o_path)
void removeVertices(G &graph, const Path &path)
stores in subPath the first i elements of path
Definition: pgr_ksp.hpp:201
void executeYen(G &graph, int top_k)
the actual algorithm
Definition: pgr_ksp.hpp:240