33#define UNREACHABLE (std::numeric_limits<double>::max() / 1000.0)
58template<
class E,
class V>
64 virtual double lowerBound(
const E* from,
const E* to,
double speed,
double speedFactor,
double fromEffort,
double toEffort)
const = 0;
71template<
class E,
class V>
76 std::ifstream strm(filename.c_str());
77 for (
int i = 0; i < size; i++) {
78 for (
int j = 0; j < size; j++) {
89 double lowerBound(
const E* from,
const E* to,
double ,
double speedFactor,
double ,
double )
const {
90 return myTable[from->getNumericalID()][to->getNumericalID()] / speedFactor;
98 std::vector<std::vector<double> >
myTable;
102template<
class E,
class V>
107 const V* defaultVehicle,
const std::string& outfile,
const int maxNumThreads) {
109 std::map<std::string, int> numericID;
111 if (!e->isInternal()) {
119 zstr::ifstream strm(filename.c_str(), std::fstream::in | std::fstream::binary);
121 std::ifstream strm(filename.c_str());
124 throw ProcessError(
"Could not load landmark-lookup-table from '" + filename +
"'.");
127 int numLandMarks = 0;
128 while (std::getline(strm, line)) {
134 if (st.
size() == 1) {
135 const std::string lm = st.
get(0);
139 }
else if (st.
size() == 4) {
141 const std::string lm = st.
get(0);
142 const std::string edge = st.
get(1);
144 WRITE_WARNING(
"Unknown or unordered edge '" + edge +
"' in landmark file.");
151 assert((
int)st.
size() == 2 * numLandMarks + 1);
152 const std::string edge = st.
get(0);
154 WRITE_WARNING(
"Unknown or unordered edge '" + edge +
"' in landmark file.");
156 for (
int i = 0; i < numLandMarks; i++) {
165 WRITE_WARNING(
"No landmarks in '" + filename +
"', falling back to standard A*.");
170 std::vector<RoutingTask*> currentTasks;
172 std::vector<const E*> landmarks;
173 for (
int i = 0; i < numLandMarks; ++i) {
176 const E* landmark =
nullptr;
178 for (
const E*
const edge : edges) {
179 if (edge->getID() == landmarkID) {
181 landmarks.push_back(edge);
185 if (landmark ==
nullptr) {
186 WRITE_WARNING(
"Landmark edge '" + landmarkID +
"' does not exist in the network.");
189 if (!outfile.empty()) {
190 WRITE_WARNING(
"Not all network edges were found in the lookup table '" + filename +
"' for landmark edge '" + landmarkID +
"'. Saving new matrix to '" + outfile +
"'.");
193 WRITE_WARNING(
"No lookup table for landmark edge '" + landmarkID +
"', recalculating.");
195 throw ProcessError(
"Not all network edges were found in the lookup table '" + filename +
"' for landmark edge '" + landmarkID +
"'.");
199 if (maxNumThreads > 0) {
200 const double lmCost = router->
recomputeCosts({landmark}, defaultVehicle, 0);
202 if (threadPool.
size() == 0) {
203 if (reverseRouter ==
nullptr) {
206 std::vector<const E*> route;
207 router->
compute(landmark, landmark, defaultVehicle, 0, route);
209 reverseRouter->setAutoBulkMode(
true);
211 while ((
int)threadPool.
size() < maxNumThreads) {
212 auto revClone = reverseRouter ==
nullptr ? nullptr : reverseRouter->clone();
213 new WorkerThread(threadPool, router->
clone(), revClone, defaultVehicle);
217 const E*
const edge = edges[j];
218 if (landmark != edge) {
219 const double sourceDestCost = lmCost + router->
recomputeCosts({edge}, defaultVehicle, 0);
220 currentTasks.push_back(
new RoutingTask(landmark, edge, sourceDestCost));
221 threadPool.
add(currentTasks.back(), i % maxNumThreads);
234 for (
int i = 0; i < numLandMarks; ++i) {
236 const E* landmark = landmarks[i];
237 const double lmCost = router->
recomputeCosts({landmark}, defaultVehicle, 0);
239 const E* edge = edges[j];
240 double distFrom = -1;
242 if (landmark == edge) {
246 if (maxNumThreads > 0) {
248 distFrom = currentTasks[taskIndex]->getFromCost();
249 distTo = currentTasks[taskIndex]->getToCost();
250 delete currentTasks[taskIndex++];
253 const double sourceDestCost = lmCost + router->
recomputeCosts({edge}, defaultVehicle, 0);
254 std::vector<const E*> route;
255 std::vector<const ReversedEdge<E, V>*> reversedRoute;
257 if (edge->getPredecessors().size() > 0 && landmark->getSuccessors().size() > 0) {
258 if (router->
compute(landmark, edge, defaultVehicle, 0, route)) {
259 distFrom =
MAX2(0.0, router->
recomputeCosts(route, defaultVehicle, 0) - sourceDestCost);
264 if (landmark->getPredecessors().size() > 0 && edge->getSuccessors().size() > 0) {
265 if (router->
compute(edge, landmark, defaultVehicle, 0, route)) {
266 distTo =
MAX2(0.0, router->
recomputeCosts(route, defaultVehicle, 0) - sourceDestCost);
277 if (!outfile.empty()) {
278 std::ostream* ostrm =
nullptr;
284 ostrm =
new std::ofstream(outfile.c_str());
288 if (!ostrm->good()) {
290 throw ProcessError(
"Could not open file '" + outfile +
"' for writing.");
292 for (
int i = 0; i < numLandMarks; ++i) {
297 for (
int i = 0; i < numLandMarks; ++i) {
309 double lowerBound(
const E* from,
const E* to,
double speed,
double speedFactor,
double fromEffort,
double toEffort)
const {
310 double result = from->getDistanceTo(to) / speed;
311#ifdef ASTAR_DEBUG_LOOKUPTABLE
312 if (from->getID() == ASTAR_DEBUG_LOOKUPTABLE_FROM) {
313 std::cout <<
" lowerBound to=" << to->getID() <<
" result1=" << result <<
"\n";
316 for (
int i = 0; i < (int)
myLandmarks.size(); ++i) {
320 if (fl >= 0 && tl >= 0) {
321 const double bound = (fl - tl - toEffort) / speedFactor;
322#ifdef ASTAR_DEBUG_LOOKUPTABLE
323 if (from->getID() == ASTAR_DEBUG_LOOKUPTABLE_FROM && result < bound) {
324 std::cout <<
" landmarkTo=" <<
getLandmark(i) <<
" result2=" << bound
325 <<
" fl=" << fl <<
" tl=" << tl <<
"\n";
328 result =
MAX2(result, bound);
332 if (lt >= 0 && lf >= 0) {
333 const double bound = (lt - lf - fromEffort) / speedFactor;
334#ifdef ASTAR_DEBUG_LOOKUPTABLE
335 if (from->getID() == ASTAR_DEBUG_LOOKUPTABLE_FROM && result < bound) {
336 std::cout <<
" landmarkFrom=" <<
getLandmark(i) <<
" result3=" << bound
337 <<
" lt=" << lt <<
" lf=" << lf <<
"\n";
340 result =
MAX2(result, bound);
342 if ((tl >= 0 && fl < 0)
343 || (lf >= 0 && lt < 0)) {
345#ifdef ASTAR_DEBUG_UNREACHABLE
346 std::cout <<
" unreachable: from=" << from->getID() <<
" to=" << to->getID() <<
" landmark=" <<
getLandmark(i) <<
" "
347 << ((tl >= 0 && fl < 0) ?
" (toLandmark)" :
" (fromLandmark)")
348 <<
" fl=" << fl <<
" tl=" << tl <<
" lt=" << lt <<
" lf=" << lf
374 :
MFXWorkerThread(pool), myRouter(router), myReversedRouter(reverseRouter), myVehicle(vehicle) {}
376 virtual ~WorkerThread() {
380 const std::pair<double, double> compute(
const E* src,
const E* dest,
const double costOff) {
381 double fromResult = -1.;
382 if (myRouter->compute(src, dest, myVehicle, 0, myRoute)) {
383 fromResult =
MAX2(0.0, myRouter->recomputeCosts(myRoute, myVehicle, 0) + costOff);
386 double toResult = -1.;
387 if (myReversedRouter !=
nullptr) {
388 if (myReversedRouter->compute(src->getReversedRoutingEdge(), dest->getReversedRoutingEdge(), myVehicle, 0, myReversedRoute)) {
389 toResult =
MAX2(0.0, myReversedRouter->recomputeCosts(myReversedRoute, myVehicle, 0) + costOff);
390 myReversedRoute.clear();
393 if (myRouter->compute(dest, src, myVehicle, 0, myRoute)) {
394 toResult =
MAX2(0.0, myRouter->recomputeCosts(myRoute, myVehicle, 0) + costOff);
398 return std::make_pair(fromResult, toResult);
405 std::vector<const E*> myRoute;
406 std::vector<const ReversedEdge<E, V>*> myReversedRoute;
411 RoutingTask(
const E* src,
const E* dest,
const double costOff)
412 : mySrc(src), myDest(dest), myCostOff(-costOff) {}
414 myCost = ((WorkerThread*)context)->compute(mySrc, myDest, myCostOff);
416 double getFromCost() {
420 return myCost.second;
423 const E*
const mySrc;
424 const E*
const myDest;
425 const double myCostOff;
426 std::pair<double, double> myCost;
429 RoutingTask& operator=(
const RoutingTask&) =
delete;
437 for (std::map<std::string, int>::const_iterator it =
myLandmarks.begin(); it !=
myLandmarks.end(); ++it) {
438 if (it->second == i) {
#define WRITE_WARNING(msg)
#define UNUSED_PARAMETER(x)
virtual double lowerBound(const E *from, const E *to, double speed, double speedFactor, double fromEffort, double toEffort) const =0
provide a lower bound on the distance between from and to (excluding traveltime of both edges)
virtual ~AbstractLookupTable()
virtual bool consistent() const =0
whether the heuristic ist consistent (found nodes are always visited on the shortest path the first t...
double lowerBound(const E *from, const E *to, double, double speedFactor, double, double) const
provide a lower bound on the distance between from and to (excluding traveltime of both edges)
bool consistent() const
whether the heuristic ist consistent (found nodes are always visited on the shortest path the first t...
std::vector< std::vector< double > > myTable
virtual ~FullLookupTable()
FullLookupTable(const std::string &filename, const int size)
Computes the shortest path through a network using the A* algorithm.
std::vector< std::vector< double > > myToLandmarkDists
double lowerBound(const E *from, const E *to, double speed, double speedFactor, double fromEffort, double toEffort) const
provide a lower bound on the distance between from and to (excluding traveltime of both edges)
std::map< std::string, int > myLandmarks
std::string getLandmark(int i) const
virtual ~LandmarkLookupTable()
LandmarkLookupTable(const std::string &filename, const std::vector< E * > &edges, SUMOAbstractRouter< E, V > *router, SUMOAbstractRouter< ReversedEdge< E, V >, V > *reverseRouter, const V *defaultVehicle, const std::string &outfile, const int maxNumThreads)
std::vector< std::vector< double > > myFromLandmarkDists
bool consistent() const
whether the heuristic ist consistent (found nodes are always visited on the shortest path the first t...
A pool of worker threads which distributes the tasks and collects the results.
void waitAll(const bool deleteFinished=true)
waits for all tasks to be finished
void add(Task *const t, int index=-1)
Gives a number to the given task and assigns it to the worker with the given index....
int size() const
Returns the number of threads in the pool.
Abstract superclass of a task to be run with an index to keep track of pending tasks.
A thread repeatingly calculating incoming tasks.
the edge type representing backward edges
virtual SUMOAbstractRouter * clone()=0
double recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime, double *lengthp=nullptr) const
void setAutoBulkMode(const bool mode)
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false)=0
Builds the route between the given edges using the minimum effort at the given time The definition of...
int size() const
returns the number of existing substrings
std::string get(int pos) const
returns the item at the given position
static double toDouble(const std::string &sData)
converts a string into the double value described by it by calling the char-type converter
static bool endsWith(const std::string &str, const std::string suffix)
Checks whether a given string ends with the suffix.