PGROUTING  2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Pgr_ksp< G > Class Template Reference

#include "pgr_ksp.hpp"

Collaboration diagram for Pgr_ksp< G >:

Classes

class  compPaths
 

Public Member Functions

void clear ()
 
std::deque< PathYen (G &graph, int64_t source, int64_t target, int K, bool heap_paths)
 

Private Member Functions

void executeYen (G &graph, int top_k)
 the actual algorithm More...
 
Auxiliary function for yen's algorithm
void getFirstSolution (G &graph)
 Performs the first Dijkstra of the algorithm. More...
 
void doNextCycle (G &graph)
 Performs the next cycle of the algorithm. More...
 
void removeVertices (G &graph, const Path &path)
 stores in subPath the first i elements of path More...
 

members

typedef G::V V
 
typedef std::set< Path, compPathspSet
 
V v_source
 source descriptor More...
 
V v_target
 target descriptor More...
 
int64_t m_start
 source id More...
 
int64_t m_end
 target id More...
 
Path curr_result_path
 storage for the current result More...
 
pSet m_ResultSet
 ordered set of shortest paths More...
 
pSet m_Heap
 the heap More...
 
std::ostringstream log
 

Detailed Description

template<class G>
class Pgr_ksp< G >

Definition at line 41 of file pgr_ksp.hpp.

Member Typedef Documentation

template<class G>
typedef std::set<Path, compPaths> Pgr_ksp< G >::pSet
private

Definition at line 121 of file pgr_ksp.hpp.

template<class G>
typedef G::V Pgr_ksp< G >::V
private

Definition at line 113 of file pgr_ksp.hpp.

Member Function Documentation

template<class G >
void Pgr_ksp< G >::clear ( )

Definition at line 130 of file pgr_ksp.hpp.

130  {
131  m_Heap.clear();
132 }
pSet m_Heap
the heap
Definition: pgr_ksp.hpp:123
template<class G >
void Pgr_ksp< G >::doNextCycle ( G &  graph)
private

Performs the next cycle of the algorithm.

Definition at line 207 of file pgr_ksp.hpp.

References Path::appendPath(), and Pgr_dijkstra< G >::dijkstra().

207  {
208  int64_t spurNodeId;
209 
210 
211  for (unsigned int i = 0; i < curr_result_path.size(); ++i) {
212  spurNodeId = curr_result_path[i].node;
213 
214  auto rootPath = curr_result_path.getSubpath(i);
215 
216  for (const auto &path : m_ResultSet) {
217  if (path.isEqual(rootPath)) {
218  if (path.size() > i + 1) {
219  graph.disconnect_edge(path[i].node, // from
220  path[i + 1].node); // to
221  }
222  }
223  }
224 
225  removeVertices(graph, rootPath);
226 
227  Pgr_dijkstra< G > fn_dijkstra;
228  auto spurPath = fn_dijkstra.dijkstra(graph, spurNodeId, m_end);
229 
230  if (spurPath.size() > 0) {
231  rootPath.appendPath(spurPath);
232  m_Heap.insert(rootPath);
233  }
234 
235  graph.restore_graph();
236  }
237 }
Path curr_result_path
storage for the current result
Definition: pgr_ksp.hpp:119
pSet m_Heap
the heap
Definition: pgr_ksp.hpp:123
int64_t m_end
target id
Definition: pgr_ksp.hpp:117
Path dijkstra(G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
Dijkstra 1 to 1.
Path getSubpath(unsigned int j) const
pSet m_ResultSet
ordered set of shortest paths
Definition: pgr_ksp.hpp:122
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.hpp:201

Here is the call graph for this function:

template<class G >
void Pgr_ksp< G >::executeYen ( G &  graph,
int  top_k 
)
private

the actual algorithm

Definition at line 240 of file pgr_ksp.hpp.

240  {
241  clear();
242  getFirstSolution(graph);
243 
244  if (m_ResultSet.size() == 0) return; // no path found
245 
246  while (m_ResultSet.size() < (unsigned int) K) {
247  doNextCycle(graph);
248  if (m_Heap.empty()) break;
249  curr_result_path = *m_Heap.begin();
251  m_Heap.erase(m_Heap.begin());
252  /*
253  * without the next line withpointsKSP hungs with:
254  * c++ 4.6
255  * Debug mode
256  */
257 #ifndef NDEBUG
258  log << "end of while heap size" << m_Heap.size();
259 #endif
260  }
261 }
void clear()
Definition: pgr_ksp.hpp:130
Path curr_result_path
storage for the current result
Definition: pgr_ksp.hpp:119
pSet m_Heap
the heap
Definition: pgr_ksp.hpp:123
CGAL::Filtered_kernel< SC > K
void getFirstSolution(G &graph)
Performs the first Dijkstra of the algorithm.
Definition: pgr_ksp.hpp:135
void doNextCycle(G &graph)
Performs the next cycle of the algorithm.
Definition: pgr_ksp.hpp:207
pSet m_ResultSet
ordered set of shortest paths
Definition: pgr_ksp.hpp:122
std::ostringstream log
Definition: pgr_ksp.hpp:125
template<class G >
void Pgr_ksp< G >::getFirstSolution ( G &  graph)
private

Performs the first Dijkstra of the algorithm.

Definition at line 135 of file pgr_ksp.hpp.

References Pgr_dijkstra< G >::dijkstra(), and Path::empty().

135  {
136  Path path;
137 
138  Pgr_dijkstra< G > fn_dijkstra;
139  path = fn_dijkstra.dijkstra(graph, m_start, m_end);
140 
141  if (path.empty()) return;
142  curr_result_path = path;
144 }
Path curr_result_path
storage for the current result
Definition: pgr_ksp.hpp:119
int64_t m_start
source id
Definition: pgr_ksp.hpp:116
int64_t m_end
target id
Definition: pgr_ksp.hpp:117
Path dijkstra(G &graph, int64_t start_vertex, int64_t end_vertex, bool only_cost=false)
Dijkstra 1 to 1.
bool empty() const
pSet m_ResultSet
ordered set of shortest paths
Definition: pgr_ksp.hpp:122

Here is the call graph for this function:

template<class G >
void Pgr_ksp< G >::removeVertices ( G &  graph,
const Path path 
)
private

stores in subPath the first i elements of path

Definition at line 201 of file pgr_ksp.hpp.

201  {
202  for (const auto &e : subpath)
203  graph.disconnect_vertex(e.node);
204 }
template<class G >
std::deque< Path > Pgr_ksp< G >::Yen ( G &  graph,
int64_t  source,
int64_t  target,
int  K,
bool  heap_paths 
)

Definition at line 148 of file pgr_ksp.hpp.

References Path::size().

Referenced by do_pgr_ksp(), do_pgr_withPointsKsp(), and process_ksp().

149  {
150  /*
151  * No path: already in destination
152  */
153  if ((start_vertex == end_vertex) || (K == 0)) {
154  return std::deque<Path>();
155  }
156  /*
157  * no path: disconnected vertices
158  */
159  if (!graph.has_vertex(start_vertex)
160  || !graph.has_vertex(end_vertex)) {
161  return std::deque<Path>();
162  }
163  m_ResultSet.clear();
164  m_Heap.clear();
165 
166  v_source = graph.get_V(start_vertex);
167  v_target = graph.get_V(end_vertex);
168  m_start = start_vertex;
169  m_end = end_vertex;
170  executeYen(graph, K);
171 
172  while (!m_ResultSet.empty()) {
173  m_Heap.insert(*m_ResultSet.begin());
174  m_ResultSet.erase(m_ResultSet.begin());
175  }
176  std::deque<Path> l_ResultList(m_Heap.begin(), m_Heap.end());
177 
178  std::stable_sort(l_ResultList.begin(), l_ResultList.end(),
179  [](const Path &left, const Path &right) -> bool {
180  for (size_t i = 0;
181  i < (std::min)(left.size(), right.size());
182  ++i) {
183  if (left[i].node < right[i].node) return true;
184  if (left[i].node > right[i].node) return false;
185  }
186  return false;
187  });
188 
189  std::stable_sort(l_ResultList.begin(), l_ResultList.end(),
190  [](const Path &left, const Path &right) {
191  return left.size() < right.size();});
192 
193  if (!heap_paths && l_ResultList.size() > (size_t) K)
194  l_ResultList.resize(K);
195 
196  return l_ResultList;
197 }
V v_source
source descriptor
Definition: pgr_ksp.hpp:114
V v_target
target descriptor
Definition: pgr_ksp.hpp:115
pSet m_Heap
the heap
Definition: pgr_ksp.hpp:123
int64_t m_start
source id
Definition: pgr_ksp.hpp:116
CGAL::Filtered_kernel< SC > K
int64_t m_end
target id
Definition: pgr_ksp.hpp:117
pSet m_ResultSet
ordered set of shortest paths
Definition: pgr_ksp.hpp:122
size_t size() const
void executeYen(G &graph, int top_k)
the actual algorithm
Definition: pgr_ksp.hpp:240

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

template<class G>
Path Pgr_ksp< G >::curr_result_path
private

storage for the current result

Definition at line 119 of file pgr_ksp.hpp.

template<class G>
std::ostringstream Pgr_ksp< G >::log
private

Definition at line 125 of file pgr_ksp.hpp.

template<class G>
int64_t Pgr_ksp< G >::m_end
private

target id

Definition at line 117 of file pgr_ksp.hpp.

template<class G>
pSet Pgr_ksp< G >::m_Heap
private

the heap

Definition at line 123 of file pgr_ksp.hpp.

template<class G>
pSet Pgr_ksp< G >::m_ResultSet
private

ordered set of shortest paths

Definition at line 122 of file pgr_ksp.hpp.

template<class G>
int64_t Pgr_ksp< G >::m_start
private

source id

Definition at line 116 of file pgr_ksp.hpp.

template<class G>
V Pgr_ksp< G >::v_source
private

source descriptor

Definition at line 114 of file pgr_ksp.hpp.

template<class G>
V Pgr_ksp< G >::v_target
private

target descriptor

Definition at line 115 of file pgr_ksp.hpp.


The documentation for this class was generated from the following file: