pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
pgr_ksp.hpp
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 #ifdef __MINGW32__
28 #include <winsock2.h>
29 #include <windows.h>
30 #ifdef unlink
31 #undef unlink
32 #endif
33 #endif
34 
35 
36 #include <deque>
37 #include <set>
38 #include "./../../common/src/basePath_SSEC.hpp"
39 #include "./../../dijkstra/src/pgr_dijkstra.hpp"
40 
41 template < class G >
42 class Pgr_ksp {
43  public:
44  std::deque<Path> Yen(G &graph, int64_t source, int64_t target, int K, bool heap_paths);
45  void clear();
46 
47  private:
48  class compPaths {
49  public:
50  bool operator()(const Path &p1, const Path &p2) const {
51  if (p1.tot_cost() != p2.tot_cost())
52  return (p1.tot_cost() < p2.tot_cost());
53 
54  // paths costs are equal now we check by length
55  if (p1.size() < p2.size())
56  return (p1.size() < p2.size());
57 
58  // paths weights & lengths are equal now we check by ID
59  unsigned int i;
60  for (i = 0; i < p1.size(); i++) {
61  if (p1[i].node != p2[i].node)
62  return (p1[i].node < p2[i].node);
63  }
64 
65  // we got here and everything is equal
66  return false;
67  }
68  };
69 
71  void executeYen(G &graph, int top_k);
72 
74 
77  void getFirstSolution(G &graph);
79  void doNextCycle(G &graph);
81  void removeVertices(G &graph, const Path &path);
83 
84  private:
86  typedef typename G::V V;
90  int64_t m_start;
91  int64_t m_end;
92 
94 
95  typedef typename std::set<Path, compPaths> pSet;
96  pSet m_ResultSet;
97  pSet m_Heap;
98 };
99 
100 #include "./pgr_ksp.cpp"
101 
V v_source
source descriptor
Definition: pgr_ksp.hpp:88
V v_target
target descriptor
Definition: pgr_ksp.hpp:89
Path curr_result_path
storage for the current result
Definition: pgr_ksp.hpp:93
pSet m_Heap
the heap
Definition: pgr_ksp.hpp:97
int64_t m_start
source id
Definition: pgr_ksp.hpp:90
int64_t m_end
target id
Definition: pgr_ksp.hpp:91
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
pSet m_ResultSet
ordered set of shortest paths
Definition: pgr_ksp.hpp:96
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