GISCup 2015
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Macros
Classes | Public Types | Public Member Functions | Public Attributes | List of all members
VariousSearchEngines Class Reference

VariousSearchEngines. More...

#include <giscup.hpp>

Classes

class  astar_goal_visitor
 astar_goal_visitor terminates the search on the goal and counts edge examinations More...
class  dijkstra_goal_visitor
 dijkstra_goal_visitor ends the search by throwing an expception at the goal vertex and counts edge examinations. More...
class  distance_heuristic
 distance_heuristic provides distance heuristic for the A* search using WebMercatorDistance method More...
struct  found_goal
class  landmark_t
 landmark_t is a container for the data representing a landmark. More...
struct  queue_compare
 a comparation functional to sort with smallest priority first More...

Public Types

typedef std::pair< double,
mygraph_t::vertex_descriptor > 
queue_element
 The type of a queue element, essentially a pair of priority and vertex index.
typedef std::priority_queue
< queue_element, std::vector
< queue_element >
, queue_compare
queue_t
 The priority queue.

Public Member Functions

size_t nearestVertex (double x, double y)
 returns the nearest vertex, if any
std::string default_stats ()
 returns the default stat string using class-global variables
 VariousSearchEngines ()
 Constructor setting the default search algorithm to REFERENCE_AStar.
double getDistance ()
 calculates distance of shortest_path global variable and asserst, that all edges exist
double getTime ()
 calculates Time of shortest_path global variable and asserst, that all edges exist
edge_descriptor myadd_edge (mygraph_t::vertex_descriptor s, mygraph_t::vertex_descriptor e, double w)
 myadd_edge adds an edge to the graph and assigns all needed properties
mygraph_t::vertex_descriptor getVertexIndexFromLocation (cost x, cost y, double eps=0.01)
 Return vertex index from location.
void createFromSimplifiedShapeCollection (NewShapeCollection &shapes)
 Creates all data in the graph from a NewShapeCollection document.
void activateTime ()
 activateTime pulls time information into the graph weightmap
void activateDistance ()
 activateDistance pulls distance information into the graph weightmap
void applyPolygonalRestrictions (std::vector< polygon > &restrictions)
 applyPolygonalRestrictions enforces restrictions from polygon set
mygraph_t::vertex_descriptor random_v ()
 Utility to return a random vertex.
std::pair< bool, double > search (size_t start, size_t end)
 search using the given algorithm
std::pair< bool, double > search ()
 search using given algorithm and last parameters to search
std::pair< bool, double > search_reference (size_t start, size_t end)
 search_reference performs the BGL A* search using WebMercatorDistance implementation
std::pair< bool, double > search_explicit (size_t s, size_t end)
 search_explicit is a clean A* implementation
std::pair< bool, double > search_dijkstra (size_t s, size_t end)
 search_dijkstra searches from vertex s until vertex end is reached using Dijkstra's algorithm
std::pair< bool, double > search_boostdijkstra (size_t start, size_t end)
 search_boostdijkstra searches from vertex s until vertex end is reached using Dijkstra's algorithm as implemented in the Boost Graph Library
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
void renderGL (bool showDirected=true)
 renderGL renders the graph
void renderShortest ()
 renderShortest renders shortest path
void glJet (double v, double vmin, double vmax, double alpha=1)
 glJet sets color according to value v in [v_min, v_max] using Jet colormap (blue ==> red)
void renderLandmark (size_t which)
 renderLandmark

Public Attributes

size_t search_algorithm
 The search algorithm to be used in next calls to search.
mygraph_t g
 The graph g.
std::vector< double > f
 the priorities in the queue, stored at vertices.
WeightMap weightmap
 the edge weightmap
vector
< mygraph_t::vertex_descriptor > 
p
 the default predecessor map
vector< costd
 the default distance map
vector< default_color_type > colors
 the default color map
vector
< mygraph_t::vertex_descriptor > 
p1
vector
< mygraph_t::vertex_descriptor > 
p2
vector< costf1
vector< costf2
vector< costd1
vector< costd2
vector< default_color_type > colors1
vector< default_color_type > colors2
std::vector< double > Time
 the original weights for time mapped to edges over edge_index property represented by edgeidmap member variable
std::vector< double > Length
 the original weights for length, use edgeid member to map edges to ids
IndexMap edgeidmap
 we manually assign indizes to edges in order to use vectors sometimes. This transforms from edge_descriptors to indizes
vector< unsigned long > vertex_ids
 Stores the vertex IDs as they had been modelled in the shapefiles. Might become useful when outputting shortest paths or initiating searches.
std::vector< locationlocations
 The vertex locations.
std::map
< mygraph_t::edge_descriptor,
linestring
ls_roads
 The road geometry (if needed) as a boost::geometry::linestring.
list
< mygraph_t::vertex_descriptor > 
shortest_path
 the shortest path of the last search, empty if no path found
mygraph_t::vertex_descriptor lastStart
mygraph_t::vertex_descriptor lastGoal
 the last start vertex and end vertex
bgi::rtree< value, bgi::rstar< 16, 4 > > vertex_rtree
 an R*-tree on vertices. Used to transform quickly and to cleanup error in the data.
size_t stat_examines
 a class-global counter for edge examinations, reset in search()
size_t g_edge_index
 global counter for the edge index
std::vector< landmark_tlandmarks
 Store landmark data.
std::vector< size_t > landmark_selection
 store landmark selection.

Detailed Description

VariousSearchEngines.

Class containing search engine data and implementations.

Member Typedef Documentation

typedef std::pair<double,mygraph_t::vertex_descriptor> VariousSearchEngines::queue_element

The type of a queue element, essentially a pair of priority and vertex index.

typedef std::priority_queue<queue_element, std::vector<queue_element>, queue_compare> VariousSearchEngines::queue_t

The priority queue.

Constructor & Destructor Documentation

VariousSearchEngines::VariousSearchEngines ( )
inline

Constructor setting the default search algorithm to REFERENCE_AStar.

Member Function Documentation

void VariousSearchEngines::activateDistance ( )
inline

activateDistance pulls distance information into the graph weightmap

After that, each search uses clean Length information from the Shapefile, without polygonal restrictions in place. See and use applyPolygonalRestrictions for that after calling this function.

void VariousSearchEngines::activateTime ( )
inline

activateTime pulls time information into the graph weightmap

After that, each search uses clean Time information from the Shapefile, without polygonal restrictions in place. See and use applyPolygonalRestrictions for that after calling this function.

void VariousSearchEngines::applyPolygonalRestrictions ( std::vector< polygon > &  restrictions)
inline

applyPolygonalRestrictions enforces restrictions from polygon set

This function checks each edge road linestring and restriction polygon for an intersection and sets weightmap to infinity for those cases. Should be called after activateDistance or activateTime Should only be used occasionally as it iterates over ALL edges and ALL polygons. But, obstructions should change seldom enough to do it this way.

void VariousSearchEngines::createFromSimplifiedShapeCollection ( NewShapeCollection shapes)
inline

Creates all data in the graph from a NewShapeCollection document.

Therefore fills vertices, edges, property maps, Time and Weight maps ls_roads and spatial index on vertices. Furthermore allocates global search variables (p,f,d,etc.) to the size of the novel graph. Also records vertex_ids, which represent the SHP attribute ID field for each vertex.

bool VariousSearchEngines::createLandmark ( size_t  which,
size_t  where 
)
inline

cretaeLandmark calculates landmark with id which from vertex where

< the reverse graph to get from and to distances.

std::string VariousSearchEngines::default_stats ( )
inline

returns the default stat string using class-global variables

Therefore calls stat and returns the JSON string containing all information relevant for the last search. Some statistics might be outdated, if the algorithm does not employ the global variables colors, shortest_path, examines

double VariousSearchEngines::getDistance ( )
inline

calculates distance of shortest_path global variable and asserst, that all edges exist

Some searches don't return the distance, e.g., two-sided. So we recalculate in this case

double VariousSearchEngines::getTime ( )
inline

calculates Time of shortest_path global variable and asserst, that all edges exist

Some searches don't return the distance, e.g., two-sided. So we recalculate in this case

mygraph_t::vertex_descriptor VariousSearchEngines::getVertexIndexFromLocation ( cost  x,
cost  y,
double  eps = 0.01 
)
inline

Return vertex index from location.

If there is already a vertex at given location (in Euclidean distance smaller epsilon) return this index. Otherwise create a new vertex, create location data and add it to the vertex rtree. This method speeds up reading graph data from the prescribed edge format considerably and suppresses errors due to multiple nodes at the same location.

void VariousSearchEngines::glJet ( double  v,
double  vmin,
double  vmax,
double  alpha = 1 
)
inline

glJet sets color according to value v in [v_min, v_max] using Jet colormap (blue ==> red)

bool VariousSearchEngines::localCheckFeasibility ( mygraph_t::vertex_descriptor  t)
inline

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.

edge_descriptor VariousSearchEngines::myadd_edge ( mygraph_t::vertex_descriptor  s,
mygraph_t::vertex_descriptor  e,
double  w 
)
inline

myadd_edge adds an edge to the graph and assigns all needed properties

Creates a new edge in the graph, sets edge_id and weights in edgeidmap and weightmap.

size_t VariousSearchEngines::nearestVertex ( double  x,
double  y 
)
inline

returns the nearest vertex, if any

Uses R*-tree, crashes, if rtree is empty by acessing unavailable result

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

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 VariousSearchEngines::preprocess_ALT ( size_t  numLandmarks = 25)
inline

preprocess_ALT creates landmark set

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

mygraph_t::vertex_descriptor VariousSearchEngines::random_v ( )
inline

Utility to return a random vertex.

Returns a random vertex using boost generator mt19937. This function would be problematic with Microsoft compilers, which do not fully support local statics. However, you could remove the static declaration for the generator.

bool VariousSearchEngines::recreateLandmark ( size_t  which,
size_t  where 
)
inline

recreateLandmark recalculates landmark which at where

void VariousSearchEngines::renderGL ( bool  showDirected = true)
inline

renderGL renders the graph

Renders the graph (directed in form of central arrows) using OpenGL If you don't have / need openGL, define GISCUP_NO_OPENGL

void VariousSearchEngines::renderLandmark ( size_t  which)
inline

renderLandmark

renders a landmark distance map as a Jet colored set of points.

void VariousSearchEngines::renderShortest ( )
inline

renderShortest renders shortest path

This renders the shortest path in the graph

std::pair<bool, double> VariousSearchEngines::search ( size_t  start,
size_t  end 
)
inline

search using the given algorithm

cleans stat_examines and shortest_path and then calls the appropriate search algorithm in the algorithms/* header.

std::pair<bool,double> VariousSearchEngines::search ( )
inline

search using given algorithm and last parameters to search

Shorthand for search(lastStart,lastGoal)

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

search_ALT performs ALT search

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

std::pair<bool, double> VariousSearchEngines::search_boostdijkstra ( size_t  start,
size_t  end 
)
inline

search_boostdijkstra searches from vertex s until vertex end is reached using Dijkstra's algorithm as implemented in the Boost Graph Library

A slight inconsistency in BGL has led to using the non-named parameter call, which is a bit long and unreadable. See the comment and try out whether the commented-out call works in future versions of Boost...

std::pair<bool, double> VariousSearchEngines::search_dijkstra ( size_t  s,
size_t  end 
)
inline

search_dijkstra searches from vertex s until vertex end is reached using Dijkstra's algorithm

This implementation is suitable only when vertex_descriptors are size_t (e.g., for vecS storage in the graph).

std::pair<bool, double> VariousSearchEngines::search_explicit ( size_t  s,
size_t  end 
)
inline

search_explicit is a clean A* implementation

A trick is used in order not to update the elements of the queue. This pays off in road networks, where updates are seldom enough. Therefore, the last queue valuation of each vertex is recorded and a vertex from the priority queue is ignored, if it does not fit the stored last value...

It uses the distance_heuristics from the boost_astar.hpp header for consistency.

std::pair<bool, double> VariousSearchEngines::search_reference ( size_t  start,
size_t  end 
)
inline

search_reference performs the BGL A* search using WebMercatorDistance implementation

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

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 VariousSearchEngines::WebMercatorEdge ( mygraph_t::vertex_descriptor  s,
mygraph_t::vertex_descriptor  e 
)
inline

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

Member Data Documentation

vector<default_color_type> VariousSearchEngines::colors

the default color map

vector<default_color_type> VariousSearchEngines::colors1
vector<default_color_type> VariousSearchEngines::colors2
vector<cost> VariousSearchEngines::d

the default distance map

vector<cost> VariousSearchEngines::d1
vector<cost> VariousSearchEngines::d2
IndexMap VariousSearchEngines::edgeidmap

we manually assign indizes to edges in order to use vectors sometimes. This transforms from edge_descriptors to indizes

std::vector<double> VariousSearchEngines::f

the priorities in the queue, stored at vertices.

vector<cost> VariousSearchEngines::f1
vector<cost> VariousSearchEngines::f2
mygraph_t VariousSearchEngines::g

The graph g.

size_t VariousSearchEngines::g_edge_index

global counter for the edge index

std::vector<size_t> VariousSearchEngines::landmark_selection

store landmark selection.

std::vector<landmark_t> VariousSearchEngines::landmarks

Store landmark data.

mygraph_t::vertex_descriptor VariousSearchEngines::lastGoal

the last start vertex and end vertex

mygraph_t::vertex_descriptor VariousSearchEngines::lastStart
std::vector<double> VariousSearchEngines::Length

the original weights for length, use edgeid member to map edges to ids

std::vector<location> VariousSearchEngines::locations

The vertex locations.

std::map<mygraph_t::edge_descriptor,linestring> VariousSearchEngines::ls_roads

The road geometry (if needed) as a boost::geometry::linestring.

vector<mygraph_t::vertex_descriptor> VariousSearchEngines::p

the default predecessor map

vector<mygraph_t::vertex_descriptor> VariousSearchEngines::p1
vector<mygraph_t::vertex_descriptor> VariousSearchEngines::p2
size_t VariousSearchEngines::search_algorithm

The search algorithm to be used in next calls to search.

list<mygraph_t::vertex_descriptor> VariousSearchEngines::shortest_path

the shortest path of the last search, empty if no path found

size_t VariousSearchEngines::stat_examines

a class-global counter for edge examinations, reset in search()

std::vector<double> VariousSearchEngines::Time

the original weights for time mapped to edges over edge_index property represented by edgeidmap member variable

vector<unsigned long> VariousSearchEngines::vertex_ids

Stores the vertex IDs as they had been modelled in the shapefiles. Might become useful when outputting shortest paths or initiating searches.

bgi::rtree< value, bgi::rstar<16, 4> > VariousSearchEngines::vertex_rtree

an R*-tree on vertices. Used to transform quickly and to cleanup error in the data.

WeightMap VariousSearchEngines::weightmap

the edge weightmap


The documentation for this class was generated from the following files: