PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgr_ksp.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 File: pgr_ksp.cpp
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 
26 #include <deque>
27 #include <set>
28 
29 #include "./../../common/src/pgr_assert.h"
30 #include "./../../common/src/basePath_SSEC.hpp"
31 
32 template < class G >
34  m_Heap.clear();
35 }
36 
37 template < class G >
39  Path path;
40 
41  Pgr_dijkstra< G > fn_dijkstra;
42  path = fn_dijkstra.dijkstra(graph, m_start, m_end);
43 
44  if (path.empty()) return;
45  curr_result_path = path;
46  m_ResultSet.insert(curr_result_path);
47 }
48 
49 template < class G>
50 std::deque<Path>
52  int64_t start_vertex, int64_t end_vertex, int K, bool heap_paths) {
53  /*
54  * No path: already in destination
55  */
56  if ((start_vertex == end_vertex) || (K == 0)) {
57  return std::deque<Path>();
58  }
59  /*
60  * no path: disconnected vertices
61  */
62  if (!graph.has_vertex(start_vertex)
63  || !graph.has_vertex(end_vertex)) {
64  return std::deque<Path>();
65  }
66  m_ResultSet.clear();
67  m_Heap.clear();
68 
69  v_source = graph.get_V(start_vertex);
70  v_target = graph.get_V(end_vertex);
71  m_start = start_vertex;
72  m_end = end_vertex;
73  executeYen(graph, K);
74 
75  while (!m_ResultSet.empty()) {
76  m_Heap.insert(*m_ResultSet.begin());
77  m_ResultSet.erase(m_ResultSet.begin());
78  }
79  std::deque<Path> l_ResultList(m_Heap.begin(), m_Heap.end());
80 
81  std::stable_sort(l_ResultList.begin(), l_ResultList.end(),
82  [](const Path &left, const Path &right) -> bool {
83  for (size_t i = 0 ; i < (std::min)(left.size(), right.size()); ++i) {
84  if (left[i].node < right[i].node) return true;
85  if (left[i].node > right[i].node) return false;
86  }
87  return false;
88  });
89 
90  std::stable_sort(l_ResultList.begin(), l_ResultList.end(),
91  [](const Path &left, const Path &right) {
92  return left.size() < right.size();});
93 
94  if (!heap_paths && l_ResultList.size() > (size_t) K)
95  l_ResultList.resize(K);
96 
97  return l_ResultList;
98 }
99 
100 
101 template < class G >
102 void Pgr_ksp< G >::removeVertices(G &graph, const Path &subpath) {
103  for (const auto &e : subpath)
104  graph.disconnect_vertex(e.node);
105 }
106 
107 template < class G >
109 
110 
111  int64_t spurNodeId;
112 
113 
114  for (unsigned int i = 0; i < curr_result_path.size(); ++i) {
115 
116  spurNodeId = curr_result_path[i].node;
117 
118  auto rootPath = curr_result_path.getSubpath(i);
119 
120  for (const auto &path : m_ResultSet) {
121  if (path.isEqual(rootPath)) {
122  if (path.size() > i + 1) {
123  graph.disconnect_edge(path[i].node, // from
124  path[i + 1].node); // to
125  }
126  }
127  }
128 
129  removeVertices(graph, rootPath);
130 
131  Pgr_dijkstra< G > fn_dijkstra;
132  auto spurPath = fn_dijkstra.dijkstra(graph, spurNodeId, m_end);
133 
134  if (spurPath.size() > 0) {
135  rootPath.appendPath(spurPath);
136  m_Heap.insert(rootPath);
137  }
138 
139  graph.restore_graph();
140  }
141 }
142 
143 template < class G >
144 void Pgr_ksp< G >::executeYen(G &graph, int K) {
145  clear();
146  getFirstSolution(graph);
147 
148  if (m_ResultSet.size() == 0) return; // no path found
149 
150  while (m_ResultSet.size() < (unsigned int) K) {
151  doNextCycle(graph);
152  if (m_Heap.empty()) break;
153  curr_result_path = *m_Heap.begin();
154  m_ResultSet.insert(curr_result_path);
155  m_Heap.erase(m_Heap.begin());
156  /*
157  * without the next line withpointsKSP hungs with:
158  * c++ 4.6
159  * Debug mode
160  */
161 #ifndef NDEBUG
162  log << "end of while heap size" << m_Heap.size();
163 #endif
164  }
165 }
void clear()
Definition: pgr_ksp.cpp:33
CGAL::Filtered_kernel< SC > K
Path dijkstra(G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
one to one
void getFirstSolution(G &graph)
Performs the first Dijkstra of the algorithm.
Definition: pgr_ksp.cpp:38
bool empty() const
path_element_t * path
Definition: BDATester.cpp:49
void doNextCycle(G &graph)
Performs the next cycle of the algorithm.
Definition: pgr_ksp.cpp:108
std::deque< Path > Yen(G &graph, int64_t source, int64_t target, int K, bool heap_paths)
Definition: pgr_ksp.cpp:51
size_t size() const
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.cpp:102
void executeYen(G &graph, int top_k)
the actual algorithm
Definition: pgr_ksp.cpp:144