T_Dijkstra_shortest_paths_with_landmarks< Graph, IsLandmark > Class Template Reference

brief todo More...

#include <Dijkstra_shortest_paths_with_landmarks.hpp>

Public Types
enum	Color { WHITE , GRAY , BLACK }
typedef T_Dijkstra_shortest_paths_with_landmarks< Graph, IsLandmark >	Self
typedef boost::graph_traits< Graph >::vertex_descriptor	Vertex
typedef boost::graph_traits< Graph >::edge_descriptor	Edge
typedef boost::graph_traits< Graph >::vertex_iterator	vertex_iterator
typedef boost::graph_traits< Graph >::vertices_size_type	vertices_size_type
typedef boost::graph_traits< Graph >::adjacency_iterator	adjacency_iterator

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...
template<class PredecessorMap , class DistanceMap , class WeightMap >
void	operator() (Graph &G, Vertex origin, PredecessorMap &pred, DistanceMap &dist, WeightMap &weights, unsigned k=0) const
template<class PredecessorMap , class DistanceMap >
void	operator() (Graph &G, Vertex origin, PredecessorMap &pred, DistanceMap &dist, const IsLandmark &is_landmark, unsigned k=0) const
template<class PredecessorMap , class DistanceMap >
void	operator() (Graph &G, Vertex origin, PredecessorMap &pred, DistanceMap &dist, unsigned k=0) const

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...
template<class DistanceMap , class OutputIterator >
static OutputIterator	get_landmark_shortest_distances (Graph &G, Vertex u, DistanceMap &dist, const IsLandmark &is_landmark, OutputIterator out)
template<class DistanceMap , class OutputIterator >
static OutputIterator	get_landmark_shortest_distances (Graph &G, Vertex u, DistanceMap &dist, OutputIterator out)
template<class PredecessorMap , class OutputIterator >
static OutputIterator	get_shortest_path_to_landmark (Graph &G, Vertex u, Vertex v, PredecessorMap &pred, const IsLandmark &is_landmark, OutputIterator out)
template<class PredecessorMap , class OutputIterator >
static OutputIterator	get_shortest_path_to_landmark (Graph &G, Vertex u, Vertex v, PredecessorMap &pred, OutputIterator out)

Detailed Description

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

brief todo

details todo.

Member Typedef Documentation

adjacency_iterator

typedef boost::graph_traits<Graph>::adjacency_iterator adjacency_iterator

Edge

typedef boost::graph_traits<Graph>::edge_descriptor Edge

Self

typedef T_Dijkstra_shortest_paths_with_landmarks<Graph, IsLandmark> Self

Vertex

typedef boost::graph_traits<Graph>::vertex_descriptor Vertex

vertex_iterator

typedef boost::graph_traits<Graph>::vertex_iterator vertex_iterator

vertices_size_type

typedef boost::graph_traits<Graph>::vertices_size_type vertices_size_type

Member Enumeration Documentation

Color

enum Color

Enumerator
WHITE
GRAY
BLACK

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_landmark_shortest_distances() [1/2]

OutputIterator get_landmark_shortest_distances ( Graph &  G, Vertex  u, DistanceMap &  dist, const IsLandmark &  is_landmark, OutputIterator  out  )

inlinestatic

get_landmark_shortest_distances() [2/2]

static OutputIterator get_landmark_shortest_distances ( Graph &  G, Vertex  u, DistanceMap &  dist, OutputIterator  out  )

inlinestatic

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

get_shortest_path_to_landmark() [1/2]

OutputIterator get_shortest_path_to_landmark ( Graph &  G, Vertex  u, Vertex  v, PredecessorMap &  pred, const IsLandmark &  is_landmark, OutputIterator  out  )

inlinestatic

get_shortest_path_to_landmark() [2/2]

static OutputIterator get_shortest_path_to_landmark ( Graph &  G, Vertex  u, Vertex  v, PredecessorMap &  pred, OutputIterator  out  )

inlinestatic

operator()() [1/4]

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

inline

operator()() [2/4]

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

operator()() [3/4]

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

inline

operator()() [4/4]

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

inline