T_Dijkstra_shortest_paths_with_landmarks< Graph, IsLandmark > Class Template Reference

brief todo More...

#include <Dijkstra_shortest_paths_with_landmarks.hpp>

Public Member Functions
template<class PredecessorMap , class DistanceMap , class WeightMap >
void	operator() (Graph &G, Vertex origin, PredecessorMap &pred, DistanceMap &dist, const IsLandmark &is_landmark, WeightMap &weights, unsigned k=0) const
	if k = 0, it stops when all other landmarks were visited More...

Static Public Member Functions
template<class OutputIterator >
static OutputIterator	get_landmarks (Graph &G, const IsLandmark &is_landmark, OutputIterator out)
	this is useful to preallocate the result to structure to be used in k_dijkstra_on_landmarks More...
template<class OutputIterator >
static OutputIterator	get_landmarks (Graph &G, OutputIterator out)
	this is useful to preallocate the result to structure to be used in k_dijkstra_on_landmarks More...
static unsigned	count_landmarks (Graph &G, const IsLandmark &is_landmark=IsLandmark())
	this is useful to preallocate the result to structure to be used in k_dijkstra_on_landmarks More...

Detailed Description

template<class Graph, class IsLandmark>
class SBL::CADS::T_Dijkstra_shortest_paths_with_landmarks< Graph, IsLandmark >

brief todo

details todo.

Member Function Documentation

count_landmarks()

static unsigned count_landmarks ( Graph &  G, const IsLandmark &  is_landmark = IsLandmark()  )

inlinestatic

this is useful to preallocate the result to structure to be used in k_dijkstra_on_landmarks

get_landmarks() [1/2]

static OutputIterator get_landmarks ( Graph &  G, const IsLandmark &  is_landmark, OutputIterator  out  )

inlinestatic

this is useful to preallocate the result to structure to be used in k_dijkstra_on_landmarks

get_landmarks() [2/2]

static OutputIterator get_landmarks ( Graph &  G, OutputIterator  out  )

inlinestatic

this is useful to preallocate the result to structure to be used in k_dijkstra_on_landmarks

operator()()

void operator() ( Graph &  G, Vertex  origin, PredecessorMap &  pred, DistanceMap &  dist, const IsLandmark &  is_landmark, WeightMap &  weights, unsigned  k = 0  ) const

inline

if k = 0, it stops when all other landmarks were visited

main function computes the k shortest distances to other landmarks from each landmark and outputs the result to an ostream it uses for each landmark a truncated version of dijkstra's algorithm that stops when k other landmarks where visited the greedy-optimal nature of dijkstra's algorithm guarantees that the distances to these k landmarks are indeed the shortest ones