GISCup 2015
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Macros
Classes | Macros | Functions | Variables
ALT.hpp File Reference

Go to the source code of this file.

Classes

class  landmark_t
 landmark_t is a container for the data representing a landmark. More...

Macros

#define LATE(fmt,...)   {}
#define ALT_USE_TIGHTEST_SUBSET
#define LATE(fmt,...)   {}
#define ALT_USE_TIGHTEST_SUBSET

Functions

double WebMercatorEdge (mygraph_t::vertex_descriptor s, mygraph_t::vertex_descriptor e)
 WebMercatorEdge is a helper function returning the length of an edge given by vertex descriptors.
bool recreateLandmark (size_t which, size_t where)
 recreateLandmark recalculates landmark which at where
bool createLandmark (size_t which, size_t where)
 cretaeLandmark calculates landmark with id which from vertex where
bool localCheckFeasibility (mygraph_t::vertex_descriptor t)
 localCheckFeasibility checks feasibility of landmark-induced potential on complete graph for a single vertex
template<class vd >
double pi (vd v, vd w)
 pi calculates the potential
template<class vd >
double select_tightest (vd v, vd w, size_t num)
 select_tightest creates a landmark selection.
bool preprocess_ALT (size_t numLandmarks=25)
 preprocess_ALT creates landmark set
std::pair< bool, double > search_ALT (size_t s, size_t end)
 search_ALT performs ALT search

Variables

std::vector< landmark_tlandmarks
 Store landmark data.
std::vector< size_t > landmark_selection
 store landmark selection.

Macro Definition Documentation

#define ALT_USE_TIGHTEST_SUBSET
#define ALT_USE_TIGHTEST_SUBSET
#define LATE (   fmt,
  ... 
)    {}
#define LATE (   fmt,
  ... 
)    {}

Function Documentation

bool createLandmark ( size_t  which,
size_t  where 
)

cretaeLandmark calculates landmark with id which from vertex where

< the reverse graph to get from and to distances.

bool localCheckFeasibility ( mygraph_t::vertex_descriptor  t)

localCheckFeasibility checks feasibility of landmark-induced potential on complete graph for a single vertex

Feasibility of a potential is essentially the consistency of the distance estimation. With feasibility, the algorithm finds the shortest path, without feasibility, this is not clear.

template<class vd >
double pi ( vd  v,
vd  w 
)

pi calculates the potential

This is the central trick for ALT: Distance estimation is given as the maximum of several estimates coming from triangle inequality. In order to have ALT not depend on the number of landmarks, we use some selected landmarks from landmark_selection if ALT_USE_TIGHTEST_SUBSET is true. Otherwise, we use all landmarks (will be slow...)

bool preprocess_ALT ( size_t  numLandmarks = 25)

preprocess_ALT creates landmark set

Can make use of OpenMP parallelism while creating landmarks. Just compile with -fopenmp to exploit all cores.

bool recreateLandmark ( size_t  which,
size_t  where 
)

recreateLandmark recalculates landmark which at where

std::pair<bool, double> search_ALT ( size_t  s,
size_t  end 
)

search_ALT performs ALT search

It is a slightly extended / modified version of the explicit A* implementation in astar.hpp

template<class vd >
double select_tightest ( vd  v,
vd  w,
size_t  num 
)

select_tightest creates a landmark selection.

Note that the ALT implementation will crash if there are too few landmarks. Checking the availability of landmarks would have been reasonable practice, however, would also slow down the invocation of the algorithm...

double WebMercatorEdge ( mygraph_t::vertex_descriptor  s,
mygraph_t::vertex_descriptor  e 
)

WebMercatorEdge is a helper function returning the length of an edge given by vertex descriptors.

Variable Documentation

std::vector<size_t> landmark_selection

store landmark selection.

std::vector<landmark_t> landmarks

Store landmark data.