pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
pgr_ksp.cpp
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 #ifdef __MINGW32__
25 #include <winsock2.h>
26 #include <windows.h>
27 #ifdef unlink
28 #undef unlink
29 #endif
30 #endif
31 
32 
33 #include <deque>
34 #include <set>
35 #include "./../../common/src/basePath_SSEC.hpp"
36 
37 template < class G >
38 void Pgr_ksp< G >::clear() {
39  m_Heap.clear();
40 }
41 
42 template < class G >
44  Path path;
45 
46  Pgr_dijkstra< G > fn_dijkstra;
47  fn_dijkstra.dijkstra(graph, path, m_start, m_end);
48 
49  if (path.empty()) return;
50  curr_result_path = path;
51  m_ResultSet.insert(curr_result_path);
52 }
53 
54 template < class G>
55 std::deque<Path>
56 Pgr_ksp< G >::Yen(G &graph,
57  int64_t start_vertex, int64_t end_vertex, int K, bool heap_paths) {
58  m_ResultSet.clear();
59  m_Heap.clear();
60  if ((start_vertex != end_vertex) && (K > 0)) {
61  if (!graph.get_gVertex(start_vertex, v_source)
62  || !graph.get_gVertex(end_vertex, v_target)) {
63  std::deque<Path> l_ResultList;
64  return l_ResultList;
65  }
66  m_start = start_vertex;
67  m_end = end_vertex;
68  executeYen(graph, K);
69  }
70 
71  while (!m_ResultSet.empty()) {
72  m_Heap.insert(*m_ResultSet.begin());
73  m_ResultSet.erase(m_ResultSet.begin());
74  }
75  std::deque<Path> l_ResultList(m_Heap.begin(), m_Heap.end());
76  if (!heap_paths && l_ResultList.size() > (size_t) K)
77  l_ResultList.resize(K);
78  return l_ResultList;
79 }
80 
81 
82 template < class G >
83 void Pgr_ksp< G >::removeVertices(G &graph, const Path &subpath) {
84  for (const auto &e : subpath)
85  graph.disconnect_vertex(e.node);
86 }
87 
88 template < class G >
89 void Pgr_ksp< G >::doNextCycle(G &graph) {
90  // REG_SIGINT
91 
92 
93  int64_t spurNodeId;
94  Path rootPath;
95  Path spurPath;
96 
97  for (unsigned int i = 0; i < curr_result_path.size() ; ++i) {
98  spurNodeId = curr_result_path[i].node;
99 
100  rootPath = curr_result_path.getSubpath(i);
101 
102  for (const auto &path : m_ResultSet) {
103  if (path.isEqual(rootPath)) {
104  graph.disconnect_edge(path[i].node, // from
105  path[i + 1].node); // to
106  }
107  }
108  removeVertices(graph, rootPath);
109 
110 
111  // THROW_ON_SIGINT
112  Pgr_dijkstra< G > fn_dijkstra;
113  fn_dijkstra.dijkstra(graph, spurPath, spurNodeId, m_end);
114  //this->dijkstra(spurPath, spurNodeId , m_end);
115  // THROW_ON_SIGINT
116 
117  if (spurPath.size() > 0) {
118  rootPath.appendPath(spurPath);
119  m_Heap.insert(rootPath);
120  }
121 
122  graph.restore_graph();
123  rootPath.clear();
124  spurPath.clear();
125  }
126 }
127 
128 template < class G >
129 void Pgr_ksp< G >::executeYen(G &graph, int K) {
130  clear();
131  getFirstSolution(graph);
132 
133  if (m_ResultSet.size() == 0) return; // no path found
134 
135  while ( m_ResultSet.size() < (unsigned int) K ) {
136  doNextCycle(graph);
137  if ( m_Heap.empty() ) break;
138  curr_result_path = *m_Heap.begin();
139  m_ResultSet.insert(curr_result_path);
140  m_Heap.erase(m_Heap.begin());
141  }
142 }
void getFirstSolution(G &graph)
Performs the first Dijkstra of the algorithm.
Definition: pgr_ksp.cpp:43
void doNextCycle(G &graph)
Performs the next cycle of the algorithm.
Definition: pgr_ksp.cpp:89
void dijkstra(G &graph, Path &path, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
one to one
void removeVertices(G &graph, const Path &path)
stores in subPath the first i elements of path
Definition: pgr_ksp.cpp:83
void executeYen(G &graph, int top_k)
the actual algorithm
Definition: pgr_ksp.cpp:129