#include "pgr_ksp.hpp"

Inheritance diagram for pgrouting::yen::Pgr_ksp< G >:

Collaboration diagram for pgrouting::yen::Pgr_ksp< G >:

[legend]

Classes
class	Visitor

Public Member Functions
	Pgr_ksp ()

	~Pgr_ksp ()

void	clear ()

std::string	get_error () const
	get_error More...

std::string	get_log () const
	get_log More...

std::string	get_notice () const
	get_notice More...

bool	has_error () const
	get_error More...

std::deque< Path >	Yen (G &graph, int64_t start_vertex, int64_t end_vertex, size_t K, bool heap_paths)

Public Attributes
std::ostringstream	error
	Stores the error information. More...

std::ostringstream	log
	Stores the hint information. More...

std::ostringstream	notice
	Stores the notice information. More...

Protected Member Functions
void	executeYen (G &graph)
	the actual algorithm More...

Private Types
typedef std::set< Path, compPathsLess >	pSet

typedef G::V	V

members
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...

size_t	m_K

bool	m_heap_paths

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...

Visitor *	m_vis

Detailed Description

template<class G>
class pgrouting::yen::Pgr_ksp< G >

Definition at line 47 of file pgr_ksp.hpp.

Member Typedef Documentation

◆ pSet

template<class G >

typedef std::set<Path, compPathsLess> pgrouting::yen::Pgr_ksp< G >::pSet

private

Definition at line 49 of file pgr_ksp.hpp.

◆ V

template<class G >

typedef G::V pgrouting::yen::Pgr_ksp< G >::V

private

Definition at line 48 of file pgr_ksp.hpp.

Constructor & Destructor Documentation

◆ Pgr_ksp()

template<class G >

pgrouting::yen::Pgr_ksp< G >::Pgr_ksp ( )

inline

Definition at line 52 of file pgr_ksp.hpp.

                :
          m_K(0),
          m_heap_paths(false) {
              m_vis = new Visitor;
          }

References pgrouting::yen::Pgr_ksp< G >::m_vis.

◆ ~Pgr_ksp()

template<class G >

pgrouting::yen::Pgr_ksp< G >::~Pgr_ksp ( )

inline

Definition at line 57 of file pgr_ksp.hpp.

                 {
          delete m_vis;
      }

References pgrouting::yen::Pgr_ksp< G >::m_vis.

Member Function Documentation

◆ clear()

template<class G >

void pgrouting::yen::Pgr_ksp< G >::clear ( )

inline

Definition at line 104 of file pgr_ksp.hpp.

                   {
          m_Heap.clear();
          m_ResultSet.clear();
      }

References pgrouting::yen::Pgr_ksp< G >::m_Heap, and pgrouting::yen::Pgr_ksp< G >::m_ResultSet.

Referenced by pgrouting::yen::Pgr_turnRestrictedPath< G >::clear(), pgrouting::yen::Pgr_ksp< G >::executeYen(), and pgrouting::yen::Pgr_ksp< G >::Yen().

◆ doNextCycle()

template<class G >

void pgrouting::yen::Pgr_ksp< G >::doNextCycle ( G & graph )

inlineprotected

Performs the next cycle of the algorithm.

Definition at line 163 of file pgr_ksp.hpp.

                                 {
          for (unsigned int i = 0; i < curr_result_path.size(); ++i) {
              int64_t spurNodeId = curr_result_path[i].node;
  
              auto rootPath = curr_result_path.getSubpath(i);
  
              for (const auto &path : m_ResultSet) {
                  if (path.isEqual(rootPath)) {
                      if (path.size() > i + 1) {
                          graph.disconnect_edge(path[i].node,     // from
                                  path[i + 1].node);  // to
                      }
                  }
              }
  
              removeVertices(graph, rootPath);
  
              Pgr_dijkstra< G > fn_dijkstra;
              auto spurPath = fn_dijkstra.dijkstra(graph, spurNodeId, m_end);
  
              if (spurPath.size() > 0) {
                  rootPath.appendPath(spurPath);
                  m_Heap.insert(rootPath);
                  m_vis->on_insert_to_heap(rootPath);
              }
  
              graph.restore_graph();
          }
      }

References Path::appendPath(), pgrouting::yen::Pgr_ksp< G >::curr_result_path, pgrouting::Pgr_dijkstra< G >::dijkstra(), Path::getSubpath(), pgrouting::yen::Pgr_ksp< G >::m_end, pgrouting::yen::Pgr_ksp< G >::m_Heap, pgrouting::yen::Pgr_ksp< G >::m_ResultSet, pgrouting::yen::Pgr_ksp< G >::m_vis, pgrouting::yen::Pgr_ksp< G >::Visitor::on_insert_to_heap(), pgrouting::yen::Pgr_ksp< G >::removeVertices(), and Path::size().

Referenced by pgrouting::yen::Pgr_ksp< G >::executeYen().

◆ executeYen()

template<class G >

void pgrouting::yen::Pgr_ksp< G >::executeYen ( G & graph )

inlineprotected

the actual algorithm

Definition at line 126 of file pgr_ksp.hpp.

                                {
          clear();
          curr_result_path = getFirstSolution(graph);
          m_vis->on_insert_first_solution(curr_result_path);
  
          if (m_ResultSet.size() == 0) return;  // no path found
  
          while (m_ResultSet.size() <  m_K) {
              doNextCycle(graph);
              if (m_Heap.empty()) break;
              curr_result_path = *m_Heap.begin();
              curr_result_path.recalculate_agg_cost();
              m_ResultSet.insert(curr_result_path);
              m_Heap.erase(m_Heap.begin());
          }
      }

References pgrouting::yen::Pgr_ksp< G >::clear(), pgrouting::yen::Pgr_ksp< G >::curr_result_path, pgrouting::yen::Pgr_ksp< G >::doNextCycle(), pgrouting::yen::Pgr_ksp< G >::getFirstSolution(), pgrouting::yen::Pgr_ksp< G >::m_Heap, pgrouting::yen::Pgr_ksp< G >::m_K, pgrouting::yen::Pgr_ksp< G >::m_ResultSet, pgrouting::yen::Pgr_ksp< G >::m_vis, pgrouting::yen::Pgr_ksp< G >::Visitor::on_insert_first_solution(), and Path::recalculate_agg_cost().

Referenced by pgrouting::yen::Pgr_ksp< G >::Yen(), and pgrouting::yen::Pgr_turnRestrictedPath< G >::Yen().

◆ get_error()

std::string pgrouting::Pgr_messages::get_error ( ) const

inherited

get_error

Returns: the current contents of the log and clears the log

Definition at line 53 of file pgr_messages.cpp.

                               {
     auto str = error.str();
     return str;
 }

References pgrouting::Pgr_messages::error.

Referenced by do_pgr_many_withPointsDD(), do_pgr_pickDeliver(), do_pgr_pickDeliverEuclidean(), do_pgr_withPoints(), do_pgr_withPointsKsp(), and pgrouting::vrp::Pgr_pickDeliver::Pgr_pickDeliver().

◆ get_log()

std::string pgrouting::Pgr_messages::get_log ( ) const

inherited

get_log

Returns: the current contents of the log and clears the log

Definition at line 36 of file pgr_messages.cpp.

                             {
     auto str = log.str();
     return str;
 }

References pgrouting::Pgr_messages::log.

Referenced by do_pgr_bipartite(), do_pgr_boyerMyrvold(), do_pgr_LTDTree(), do_pgr_makeConnected(), do_pgr_many_withPointsDD(), do_pgr_pickDeliver(), do_pgr_pickDeliverEuclidean(), do_pgr_withPoints(), do_pgr_withPointsKsp(), pgr_bellman_ford(), pgr_dijkstraTR(), and pgrouting::vrp::Pgr_pickDeliver::Pgr_pickDeliver().

◆ get_notice()

std::string pgrouting::Pgr_messages::get_notice ( ) const

inherited

get_notice

Returns: the current contents of the log and clears the log

Definition at line 42 of file pgr_messages.cpp.

                                {
     auto str = notice.str();
     return str;
 }

References pgrouting::Pgr_messages::notice.

◆ get_results()

template<class G >

std::deque<Path> pgrouting::yen::Pgr_ksp< G >::get_results ( )

inlineprotected

Definition at line 200 of file pgr_ksp.hpp.

                                   {
          if (this->m_ResultSet.empty()) {
              return std::deque<Path>();
          }
  
          std::deque<Path> paths(m_ResultSet.begin(), m_ResultSet.end());
  
          if (m_heap_paths && !m_Heap.empty()) {
             paths.insert(paths.end(), m_Heap.begin(), m_Heap.end());
          }
          pgassert(!paths.empty());
  
          std::sort(paths.begin(), paths.end(), compPathsLess());
  
          return paths;
      }

References pgrouting::yen::Pgr_ksp< G >::m_Heap, pgrouting::yen::Pgr_ksp< G >::m_heap_paths, pgrouting::yen::Pgr_ksp< G >::m_ResultSet, and pgassert.

Referenced by pgrouting::yen::Pgr_ksp< G >::Yen(), and pgrouting::yen::Pgr_turnRestrictedPath< G >::Yen().

◆ getFirstSolution()

template<class G >

Path pgrouting::yen::Pgr_ksp< G >::getFirstSolution ( G & graph )

inlineprotected

Performs the first Dijkstra of the algorithm.

Definition at line 148 of file pgr_ksp.hpp.

                                      {
          Path path;
  
          Pgr_dijkstra< G > fn_dijkstra;
          path = fn_dijkstra.dijkstra(graph, m_start, m_end);
          path.recalculate_agg_cost();
  
          if (path.empty()) return path;
          m_ResultSet.insert(path);
          return path;
      }

References pgrouting::Pgr_dijkstra< G >::dijkstra(), Path::empty(), pgrouting::yen::Pgr_ksp< G >::m_end, pgrouting::yen::Pgr_ksp< G >::m_ResultSet, pgrouting::yen::Pgr_ksp< G >::m_start, and Path::recalculate_agg_cost().

Referenced by pgrouting::yen::Pgr_ksp< G >::executeYen().

◆ has_error()

bool pgrouting::Pgr_messages::has_error ( ) const

inherited

get_error

Returns: the current contents of the log and clears the log

Definition at line 48 of file pgr_messages.cpp.

                               {
     return  !error.str().empty();
 }

References pgrouting::Pgr_messages::error.

Referenced by do_pgr_many_withPointsDD(), do_pgr_withPoints(), and do_pgr_withPointsKsp().

◆ removeVertices()

template<class G >

void pgrouting::yen::Pgr_ksp< G >::removeVertices	(	G &	graph,
		const Path &	subpath
	)

inlineprotected

stores in subPath the first i elements of path

Definition at line 195 of file pgr_ksp.hpp.

                                                         {
          for (const auto &e : subpath)
              graph.disconnect_vertex(e.node);
      }

Referenced by pgrouting::yen::Pgr_ksp< G >::doNextCycle().

◆ Yen()

template<class G >

std::deque<Path> pgrouting::yen::Pgr_ksp< G >::Yen	(	G &	graph,
		int64_t	start_vertex,
		int64_t	end_vertex,
		size_t	K,
		bool	heap_paths
	)

inline

Definition at line 61 of file pgr_ksp.hpp.

                               {
          /*
           * No path: already in destination
           */
          if ((start_vertex == end_vertex) || (K == 0)) {
              return std::deque<Path>();
          }
  
          /*
           * no path: disconnected vertices
           */
          if (!graph.has_vertex(start_vertex)
                  || !graph.has_vertex(end_vertex)) {
              return std::deque<Path>();
          }
  
          /*
           * clean up containers
           */
          clear();
  
  
          v_source = graph.get_V(start_vertex);
          v_target = graph.get_V(end_vertex);
          m_start = start_vertex;
          m_end = end_vertex;
          m_K = K;
          m_heap_paths = heap_paths;
  
  
          executeYen(graph);
  
          auto paths = get_results();
          if (!m_heap_paths && paths.size() > m_K) paths.resize(m_K);
  
          return paths;
      }