The implementation Code of the search engine follows the following ideas:
-
It is a normal search engine (e.g., it holds distance map, predecessor map, color map, the map of function values (f-map)
-
It contains landmarks as a map (source vertex and associated distances)
-
It contains a dijkstra_landmark, lets see why. It is used as a fallback. Most likely an all zero landmark makes ALT behave like Dijkstra, but then init to zero is missing unless C++ guarantees it, which I don't believe? It should not be used. See Comment 1 below
-
A fast copy constructor (such that one engine per thread is fast and not redoing precomputations)
-
A costly dataset constructor getting a set of landmark vertices and computing landmark data per Dijkstra
-
The priority queue follows
-
An operator () that just computes a shortest path under penalties
** Comment 1: ** The dijkstra_landmark hack is okay along the following ideas: The engine is supposed to be used with all controllers are landmarks. The routes we need are all ending in controllers. That is, for each controller, we have a perfect landmark and landmark selection is done using find. It is actually a fault if the dijkstra_landmark is used during search. We should maybe throw an exception.