pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 #pragma once
26 
27 #if defined(__MINGW32__) || defined(_MSC_VER)
28 #include <winsock2.h>
29 #include <windows.h>
30 #ifdef unlink
31 #undef unlink
32 #endif
33 #endif
34 
35 #include <sstream>
36 #include <deque>
37 #include <vector>
38 #include <set>
39 #include "./../../dijkstra/src/pgr_dijkstra.hpp"
40 #include "./../../common/src/basePath_SSEC.hpp"
41 
42 template < class G >
43 class Pgr_ksp {
44  public:
45  std::deque<Path> Yen(G &graph, int64_t source, int64_t target, int K, bool heap_paths);
46  void clear();
47 
48  private:
49  class compPaths {
50  public:
51  bool operator()(const Path &p1, const Path &p2) const {
52  if (p1.tot_cost() != p2.tot_cost())
53  return (p1.tot_cost() < p2.tot_cost());
54 
55  // paths costs are equal now we check by length
56  if (p1.size() < p2.size())
57  return (p1.size() < p2.size());
58 
59  // paths weights & lengths are equal now we check by ID
60  unsigned int i;
61  for (i = 0; i < p1.size(); i++) {
62  if (p1[i].node != p2[i].node)
63  return (p1[i].node < p2[i].node);
64  }
65 
66  // we got here and everything is equal
67  return false;
68  }
69  };
70 
72  void executeYen(G &graph, int top_k);
73 
75 
78  void getFirstSolution(G &graph);
80  void doNextCycle(G &graph);
82  void removeVertices(G &graph, const Path &path);
84 
85  private:
87  typedef typename G::V V;
91  int64_t m_start;
92  int64_t m_end;
93 
95 
96  typedef std::set<Path, compPaths> pSet;
99 };
100 
101 #include "./pgr_ksp.cpp"
102 
V v_source
source descriptor
Definition: pgr_ksp.hpp:89
void clear()
Definition: pgr_ksp.cpp:38
V v_target
target descriptor
Definition: pgr_ksp.hpp:90
Path curr_result_path
storage for the current result
Definition: pgr_ksp.hpp:94
pSet m_Heap
the heap
Definition: pgr_ksp.hpp:98
G::V V
Definition: pgr_ksp.hpp:88
int64_t m_start
source id
Definition: pgr_ksp.hpp:91
std::set< Path, compPaths > pSet
Definition: pgr_ksp.hpp:96
CGAL::Filtered_kernel< SC > K
double tot_cost() const
int64_t m_end
target id
Definition: pgr_ksp.hpp:92
void getFirstSolution(G &graph)
Performs the first Dijkstra of the algorithm.
Definition: pgr_ksp.cpp:43
path_element_t * path
Definition: BDATester.cpp:49
bool operator()(const Path &p1, const Path &p2) const
Definition: pgr_ksp.hpp:51
void doNextCycle(G &graph)
Performs the next cycle of the algorithm.
Definition: pgr_ksp.cpp:92
std::deque< Path > Yen(G &graph, int64_t source, int64_t target, int K, bool heap_paths)
Definition: pgr_ksp.cpp:56
pSet m_ResultSet
ordered set of shortest paths
Definition: pgr_ksp.hpp:97
size_t size() const
void removeVertices(G &graph, const Path &path)
stores in subPath the first i elements of path
Definition: pgr_ksp.cpp:86
void executeYen(G &graph, int top_k)
the actual algorithm
Definition: pgr_ksp.cpp:134