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

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

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()

template<class Graph, class IsLandmark>

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]

template<class Graph, class IsLandmark>

template<class OutputIterator>

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]

template<class Graph, class IsLandmark>

template<class OutputIterator>

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()()

template<class Graph, class IsLandmark>

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

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