PGROUTING  2.4
 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 #include "./../../dijkstra/src/pgr_dijkstra.hpp"
28 
29 #include <sstream>
30 #include <deque>
31 #include <vector>
32 #include <set>
33 #include <limits>
34 
35 #include "./../../common/src/pgr_assert.h"
36 #include "./../../common/src/basePath_SSEC.hpp"
37 
38 template < class G >
39 class Pgr_ksp {
40  public:
41  std::deque<Path> Yen(G &graph, int64_t source, int64_t target, int K, bool heap_paths);
42  void clear();
43 
44  private:
45  class compPaths {
46  public:
47  bool operator()(const Path &p1, const Path &p2) const {
48  /*
49  * less cost is best
50  */
51  if (p1.tot_cost() > p2.tot_cost())
52  return false;
53  if (p1.tot_cost() < p2.tot_cost())
54  return true;
55 
56  pgassert(p1.tot_cost() == p2.tot_cost());
57 
58  // paths costs are equal now check by length
59  if (p1.size() > p2.size())
60  return false;
61  if (p1.size() < p2.size())
62  return true;
63 
64  pgassert(p1.tot_cost() == p2.tot_cost());
65  pgassert(p1.size() == p2.size());
66 
67  // paths weights & lengths are equal now check by node ID
68  unsigned int i;
69  for (i = 0; i < p1.size(); i++) {
70  if (p1[i].node > p2[i].node)
71  return false;
72  if (p1[i].node < p2[i].node)
73  return true;
74  }
75 
76  pgassert(p1.tot_cost() == p2.tot_cost());
77  pgassert(p1.size() == p2.size());
78 #ifdef NDEBUG
79  for (i = 0; i < p1.size(); i++) {
80  pgassert(p1[i].node == p2[i].node);
81  }
82 #endif
83 
84  // we got here and everything is equal
85  return false;
86  }
87  };
88 
90  void executeYen(G &graph, int top_k);
91 
93 
96  void getFirstSolution(G &graph);
98  void doNextCycle(G &graph);
100  void removeVertices(G &graph, const Path &path);
102 
103  private:
105  typedef typename G::V V;
109  int64_t m_start;
110  int64_t m_end;
111 
113 
114  typedef std::set<Path, compPaths> pSet;
117 
118  std::ostringstream log;
119 };
120 
121 #include "./pgr_ksp.cpp"
122 
V v_source
source descriptor
Definition: pgr_ksp.hpp:107
void clear()
Definition: pgr_ksp.cpp:33
V v_target
target descriptor
Definition: pgr_ksp.hpp:108
Path curr_result_path
storage for the current result
Definition: pgr_ksp.hpp:112
pSet m_Heap
the heap
Definition: pgr_ksp.hpp:116
G::V V
Definition: pgr_ksp.hpp:106
int64_t m_start
source id
Definition: pgr_ksp.hpp:109
std::set< Path, compPaths > pSet
Definition: pgr_ksp.hpp:114
CGAL::Filtered_kernel< SC > K
double tot_cost() const
int64_t m_end
target id
Definition: pgr_ksp.hpp:110
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
void getFirstSolution(G &graph)
Performs the first Dijkstra of the algorithm.
Definition: pgr_ksp.cpp:38
path_element_t * path
Definition: BDATester.cpp:49
bool operator()(const Path &p1, const Path &p2) const
Definition: pgr_ksp.hpp:47
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
pSet m_ResultSet
ordered set of shortest paths
Definition: pgr_ksp.hpp:115
size_t size() const
std::ostringstream log
Definition: pgr_ksp.hpp:118
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