34 #define UNREACHABLE (std::numeric_limits<double>::max() / 1000.0)
59 template<
class E,
class V>
65 virtual double lowerBound(
const E* from,
const E* to,
double speed,
double speedFactor,
double fromEffort,
double toEffort)
const = 0;
72 template<
class E,
class V>
77 std::ifstream strm(filename.c_str());
78 for (
int i = 0; i < size; i++) {
79 for (
int j = 0; j < size; j++) {
90 double lowerBound(
const E* from,
const E* to,
double ,
double speedFactor,
double ,
double )
const {
91 return myTable[from->getNumericalID()][to->getNumericalID()] / speedFactor;
99 std::vector<std::vector<double> >
myTable;
103 template<
class E,
class V>
108 const V* defaultVehicle,
const std::string& outfile,
const int maxNumThreads) {
110 std::map<std::string, int> numericID;
112 if (!e->isInternal()) {
120 zstr::ifstream strm(filename.c_str(), std::fstream::in | std::fstream::binary);
122 std::ifstream strm(filename.c_str());
125 throw ProcessError(
TLF(
"Could not load landmark-lookup-table from '%'.", filename));
128 std::vector<const E*> landmarks;
129 int numLandMarks = 0;
130 bool haveData =
false;
131 while (std::getline(strm, line)) {
136 if (st.
size() == 1) {
137 const std::string lm = st.
get(0);
142 const auto& it = numericID.find(lm);
143 if (it == numericID.end()) {
144 throw ProcessError(
TLF(
"Landmark edge '%' does not exist in the network.", lm));
150 }
else if (st.
size() == 4) {
152 const std::string lm = st.
get(0);
153 const std::string edge = st.
get(1);
155 throw ProcessError(
TLF(
"Unknown or unordered edge '%' in landmark file.", edge));
163 const std::string edge = st.
get(0);
164 if ((
int)st.
size() != 2 * numLandMarks + 1) {
165 throw ProcessError(
TLF(
"Broken landmark file, unexpected number of entries (%) for edge '%'.", st.
size() - 1, edge));
168 throw ProcessError(
TLF(
"Unknown or unordered edge '%' in landmark file.", edge));
170 for (
int i = 0; i < numLandMarks; i++) {
180 WRITE_WARNINGF(
"No landmarks in '%', falling back to standard A*.", filename);
185 std::vector<RoutingTask*> currentTasks;
190 for (
int i = 0; i < numLandMarks; ++i) {
192 const E*
const landmark = landmarks[i];
195 WRITE_WARNINGF(
TL(
"No lookup table for landmark edge '%', recalculating."), landmark->getID());
197 throw ProcessError(
TLF(
"Not all network edges were found in the lookup table '%' for landmark edge '%'.", filename, landmark->getID()));
201 if (maxNumThreads > 0) {
202 const double lmCost = router->
recomputeCosts({landmark}, defaultVehicle, 0);
204 if (threadPool.
size() == 0) {
205 if (reverseRouter ==
nullptr) {
208 std::vector<const E*> route;
209 router->
compute(landmark, landmark, defaultVehicle, 0, route);
211 reverseRouter->setAutoBulkMode(
true);
213 while ((
int)threadPool.
size() < maxNumThreads) {
214 auto revClone = reverseRouter ==
nullptr ? nullptr : reverseRouter->clone();
215 new WorkerThread(threadPool, router->
clone(), revClone, defaultVehicle);
219 const E*
const edge = edges[j];
220 if (landmark != edge) {
221 const double sourceDestCost = lmCost + router->
recomputeCosts({edge}, defaultVehicle, 0);
222 currentTasks.push_back(
new RoutingTask(landmark, edge, sourceDestCost));
223 threadPool.
add(currentTasks.back(), i % maxNumThreads);
236 for (
int i = 0; i < numLandMarks; ++i) {
238 const E* landmark = landmarks[i];
239 const double lmCost = router->
recomputeCosts({landmark}, defaultVehicle, 0);
241 const E* edge = edges[j];
242 double distFrom = -1;
244 if (landmark == edge) {
248 if (maxNumThreads > 0) {
250 distFrom = currentTasks[taskIndex]->getFromCost();
251 distTo = currentTasks[taskIndex]->getToCost();
252 delete currentTasks[taskIndex++];
255 const double sourceDestCost = lmCost + router->
recomputeCosts({edge}, defaultVehicle, 0);
256 std::vector<const E*> route;
257 std::vector<const ReversedEdge<E, V>*> reversedRoute;
259 if (edge->getPredecessors().size() > 0 && landmark->getSuccessors().size() > 0) {
260 if (router->
compute(landmark, edge, defaultVehicle, 0, route)) {
261 distFrom =
MAX2(0.0, router->
recomputeCosts(route, defaultVehicle, 0) - sourceDestCost);
266 if (landmark->getPredecessors().size() > 0 && edge->getSuccessors().size() > 0) {
267 if (router->
compute(edge, landmark, defaultVehicle, 0, route)) {
268 distTo =
MAX2(0.0, router->
recomputeCosts(route, defaultVehicle, 0) - sourceDestCost);
279 if (!outfile.empty()) {
280 std::ostream* ostrm =
nullptr;
286 ostrm =
new std::ofstream(outfile.c_str());
290 if (!ostrm->good()) {
292 throw ProcessError(
TLF(
"Could not open file '%' for writing.", outfile));
295 for (
int i = 0; i < numLandMarks; ++i) {
300 for (
int i = 0; i < numLandMarks; ++i) {
312 double lowerBound(
const E* from,
const E* to,
double speed,
double speedFactor,
double fromEffort,
double toEffort)
const {
313 double result = from->getDistanceTo(to) / speed;
314 #ifdef ASTAR_DEBUG_LOOKUPTABLE
315 if (from->getID() == ASTAR_DEBUG_LOOKUPTABLE_FROM) {
316 std::cout <<
" lowerBound to=" << to->getID() <<
" result1=" << result <<
"\n";
319 for (
int i = 0; i < (int)
myLandmarks.size(); ++i) {
323 if (fl >= 0 && tl >= 0) {
324 const double bound = (fl - tl - toEffort) / speedFactor;
325 #ifdef ASTAR_DEBUG_LOOKUPTABLE
326 if (from->getID() == ASTAR_DEBUG_LOOKUPTABLE_FROM && result < bound) {
327 std::cout <<
" landmarkTo=" <<
getLandmark(i) <<
" result2=" << bound
328 <<
" fl=" << fl <<
" tl=" << tl <<
"\n";
331 result =
MAX2(result, bound);
335 if (lt >= 0 && lf >= 0) {
336 const double bound = (lt - lf - fromEffort) / speedFactor;
337 #ifdef ASTAR_DEBUG_LOOKUPTABLE
338 if (from->getID() == ASTAR_DEBUG_LOOKUPTABLE_FROM && result < bound) {
339 std::cout <<
" landmarkFrom=" <<
getLandmark(i) <<
" result3=" << bound
340 <<
" lt=" << lt <<
" lf=" << lf <<
"\n";
343 result =
MAX2(result, bound);
345 if ((tl >= 0 && fl < 0)
346 || (lf >= 0 && lt < 0)) {
348 #ifdef ASTAR_DEBUG_UNREACHABLE
349 std::cout <<
" unreachable: from=" << from->getID() <<
" to=" << to->getID() <<
" landmark=" <<
getLandmark(i) <<
" "
350 << ((tl >= 0 && fl < 0) ?
" (toLandmark)" :
" (fromLandmark)")
351 <<
" fl=" << fl <<
" tl=" << tl <<
" lt=" << lt <<
" lf=" << lf
377 :
MFXWorkerThread(pool), myRouter(router), myReversedRouter(reverseRouter), myVehicle(vehicle) {}
379 virtual ~WorkerThread() {
381 delete myReversedRouter;
384 const std::pair<double, double> compute(
const E* src,
const E* dest,
const double costOff) {
385 double fromResult = -1.;
386 if (myRouter->compute(src, dest, myVehicle, 0, myRoute)) {
387 fromResult =
MAX2(0.0, myRouter->recomputeCosts(myRoute, myVehicle, 0) + costOff);
390 double toResult = -1.;
391 if (myReversedRouter !=
nullptr) {
392 if (myReversedRouter->compute(src->getReversedRoutingEdge(), dest->getReversedRoutingEdge(), myVehicle, 0, myReversedRoute)) {
393 toResult =
MAX2(0.0, myReversedRouter->recomputeCosts(myReversedRoute, myVehicle, 0) + costOff);
394 myReversedRoute.clear();
397 if (myRouter->compute(dest, src, myVehicle, 0, myRoute)) {
398 toResult =
MAX2(0.0, myRouter->recomputeCosts(myRoute, myVehicle, 0) + costOff);
402 return std::make_pair(fromResult, toResult);
409 std::vector<const E*> myRoute;
410 std::vector<const ReversedEdge<E, V>*> myReversedRoute;
415 RoutingTask(
const E* src,
const E* dest,
const double costOff)
416 : mySrc(src), myDest(dest), myCostOff(-costOff) {}
418 myCost = ((WorkerThread*)context)->compute(mySrc, myDest, myCostOff);
420 double getFromCost() {
424 return myCost.second;
427 const E*
const mySrc;
428 const E*
const myDest;
429 const double myCostOff;
430 std::pair<double, double> myCost;
433 RoutingTask& operator=(
const RoutingTask&) =
delete;
441 for (std::map<std::string, int>::const_iterator it =
myLandmarks.begin(); it !=
myLandmarks.end(); ++it) {
442 if (it->second == i) {
#define WRITE_WARNINGF(...)
#define WRITE_MESSAGEF(...)
#define WRITE_MESSAGE(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
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...
virtual double recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime, double *lengthp=nullptr) const
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.