33 #define UNREACHABLE (std::numeric_limits<double>::max() / 1000.0)
58 template<
class E,
class V>
62 virtual double lowerBound(
const E* from,
const E* to,
double speed,
double speedFactor,
double fromEffort,
double toEffort)
const = 0;
69 template<
class E,
class V>
74 std::ifstream strm(filename.c_str());
75 for (
int i = 0; i < size; i++) {
76 for (
int j = 0; j < size; j++) {
87 double lowerBound(
const E* from,
const E* to,
double ,
double speedFactor,
double ,
double )
const {
88 return myTable[from->getNumericalID()][to->getNumericalID()] / speedFactor;
96 std::vector<std::vector<double> >
myTable;
100 template<
class E,
class V>
105 const V* defaultVehicle,
const std::string& outfile,
const int maxNumThreads) {
107 std::map<std::string, int> numericID;
109 if (!e->isInternal()) {
117 zstr::ifstream strm(filename.c_str(), std::fstream::in | std::fstream::binary);
119 std::ifstream strm(filename.c_str());
122 throw ProcessError(
"Could not load landmark-lookup-table from '" + filename +
"'.");
125 int numLandMarks = 0;
126 while (std::getline(strm, line)) {
132 if (st.
size() == 1) {
133 const std::string lm = st.
get(0);
137 }
else if (st.
size() == 4) {
139 const std::string lm = st.
get(0);
140 const std::string edge = st.
get(1);
142 WRITE_WARNING(
"Unknown or unordered edge '" + edge +
"' in landmark file.");
149 assert((
int)st.
size() == 2 * numLandMarks + 1);
150 const std::string edge = st.
get(0);
152 WRITE_WARNING(
"Unknown or unordered edge '" + edge +
"' in landmark file.");
154 for (
int i = 0; i < numLandMarks; i++) {
163 WRITE_WARNING(
"No landmarks in '" + filename +
"', falling back to standard A*.");
168 std::vector<RoutingTask*> currentTasks;
170 std::vector<const E*> landmarks;
171 for (
int i = 0; i < numLandMarks; ++i) {
174 const E* landmark =
nullptr;
176 for (
const E*
const edge : edges) {
177 if (edge->getID() == landmarkID) {
179 landmarks.push_back(edge);
183 if (landmark ==
nullptr) {
184 WRITE_WARNING(
"Landmark edge '" + landmarkID +
"' does not exist in the network.");
187 if (!outfile.empty()) {
188 WRITE_WARNING(
"Not all network edges were found in the lookup table '" + filename +
"' for landmark edge '" + landmarkID +
"'. Saving new matrix to '" + outfile +
"'.");
191 WRITE_WARNING(
"No lookup table for landmark edge '" + landmarkID +
"', recalculating.");
193 throw ProcessError(
"Not all network edges were found in the lookup table '" + filename +
"' for landmark edge '" + landmarkID +
"'.");
197 if (maxNumThreads > 0) {
198 const double lmCost = router->
recomputeCosts({landmark}, defaultVehicle, 0);
200 if (threadPool.
size() == 0) {
201 if (reverseRouter ==
nullptr) {
204 std::vector<const E*> route;
205 router->
compute(landmark, landmark, defaultVehicle, 0, route);
207 reverseRouter->setAutoBulkMode(
true);
209 while ((
int)threadPool.
size() < maxNumThreads) {
210 auto revClone = reverseRouter ==
nullptr ? nullptr : reverseRouter->clone();
211 new WorkerThread(threadPool, router->
clone(), revClone, defaultVehicle);
215 const E*
const edge = edges[j];
216 if (landmark != edge) {
217 const double sourceDestCost = lmCost + router->
recomputeCosts({edge}, defaultVehicle, 0);
218 currentTasks.push_back(
new RoutingTask(landmark, edge, sourceDestCost));
219 threadPool.
add(currentTasks.back(), i % maxNumThreads);
230 for (
int i = 0; i < numLandMarks; ++i) {
232 const E* landmark = landmarks[i];
233 const double lmCost = router->
recomputeCosts({landmark}, defaultVehicle, 0);
235 const E* edge = edges[j];
236 double distFrom = -1;
238 if (landmark == edge) {
242 if (maxNumThreads > 0) {
244 distFrom = currentTasks[taskIndex]->getFromCost();
245 distTo = currentTasks[taskIndex]->getToCost();
246 delete currentTasks[taskIndex++];
249 const double sourceDestCost = lmCost + router->
recomputeCosts({edge}, defaultVehicle, 0);
250 std::vector<const E*> route;
251 std::vector<const ReversedEdge<E, V>*> reversedRoute;
253 if (edge->getPredecessors().size() > 0 && landmark->getSuccessors().size() > 0) {
254 if (router->
compute(landmark, edge, defaultVehicle, 0, route)) {
255 distFrom =
MAX2(0.0, router->
recomputeCosts(route, defaultVehicle, 0) - sourceDestCost);
260 if (landmark->getPredecessors().size() > 0 && edge->getSuccessors().size() > 0) {
261 if (router->
compute(edge, landmark, defaultVehicle, 0, route)) {
262 distTo =
MAX2(0.0, router->
recomputeCosts(route, defaultVehicle, 0) - sourceDestCost);
273 if (!outfile.empty()) {
274 std::ostream* ostrm =
nullptr;
280 ostrm =
new std::ofstream(outfile.c_str());
284 if (!ostrm->good()) {
286 throw ProcessError(
"Could not open file '" + outfile +
"' for writing.");
288 for (
int i = 0; i < numLandMarks; ++i) {
293 for (
int i = 0; i < numLandMarks; ++i) {
305 double lowerBound(
const E* from,
const E* to,
double speed,
double speedFactor,
double fromEffort,
double toEffort)
const {
306 double result = from->getDistanceTo(to) / speed;
307 #ifdef ASTAR_DEBUG_LOOKUPTABLE
308 if (from->getID() == ASTAR_DEBUG_LOOKUPTABLE_FROM) {
309 std::cout <<
" lowerBound to=" << to->getID() <<
" result1=" << result <<
"\n";
312 for (
int i = 0; i < (int)
myLandmarks.size(); ++i) {
316 if (fl >= 0 && tl >= 0) {
317 const double bound = (fl - tl - toEffort) / speedFactor;
318 #ifdef ASTAR_DEBUG_LOOKUPTABLE
319 if (from->getID() == ASTAR_DEBUG_LOOKUPTABLE_FROM && result < bound) {
320 std::cout <<
" landmarkTo=" <<
getLandmark(i) <<
" result2=" << bound
321 <<
" fl=" << fl <<
" tl=" << tl <<
"\n";
324 result =
MAX2(result, bound);
328 if (lt >= 0 && lf >= 0) {
329 const double bound = (lt - lf - fromEffort) / speedFactor;
330 #ifdef ASTAR_DEBUG_LOOKUPTABLE
331 if (from->getID() == ASTAR_DEBUG_LOOKUPTABLE_FROM && result < bound) {
332 std::cout <<
" landmarkFrom=" <<
getLandmark(i) <<
" result3=" << bound
333 <<
" lt=" << lt <<
" lf=" << lf <<
"\n";
336 result =
MAX2(result, bound);
338 if ((tl >= 0 && fl < 0)
339 || (lf >= 0 && lt < 0)) {
341 #ifdef ASTAR_DEBUG_UNREACHABLE
342 std::cout <<
" unreachable: from=" << from->getID() <<
" to=" << to->getID() <<
" landmark=" <<
getLandmark(i) <<
" "
343 << ((tl >= 0 && fl < 0) ?
" (toLandmark)" :
" (fromLandmark)")
344 <<
" fl=" << fl <<
" tl=" << tl <<
" lt=" << lt <<
" lf=" << lf
370 :
FXWorkerThread(pool), myRouter(router), myReversedRouter(reverseRouter), myVehicle(vehicle) {}
372 virtual ~WorkerThread() {
376 const std::pair<double, double> compute(
const E* src,
const E* dest,
const double costOff) {
377 double fromResult = -1.;
378 if (myRouter->compute(src, dest, myVehicle, 0, myRoute)) {
379 fromResult =
MAX2(0.0, myRouter->recomputeCosts(myRoute, myVehicle, 0) + costOff);
382 double toResult = -1.;
383 if (myReversedRouter !=
nullptr) {
384 if (myReversedRouter->compute(src->getReversedRoutingEdge(), dest->getReversedRoutingEdge(), myVehicle, 0, myReversedRoute)) {
385 toResult =
MAX2(0.0, myReversedRouter->recomputeCosts(myReversedRoute, myVehicle, 0) + costOff);
386 myReversedRoute.clear();
389 if (myRouter->compute(dest, src, myVehicle, 0, myRoute)) {
390 toResult =
MAX2(0.0, myRouter->recomputeCosts(myRoute, myVehicle, 0) + costOff);
394 return std::make_pair(fromResult, toResult);
401 std::vector<const E*> myRoute;
402 std::vector<const ReversedEdge<E, V>*> myReversedRoute;
407 RoutingTask(
const E* src,
const E* dest,
const double costOff)
408 : mySrc(src), myDest(dest), myCostOff(-costOff) {}
410 myCost = ((WorkerThread*)context)->compute(mySrc, myDest, myCostOff);
412 double getFromCost() {
416 return myCost.second;
419 const E*
const mySrc;
420 const E*
const myDest;
421 const double myCostOff;
422 std::pair<double, double> myCost;
425 RoutingTask& operator=(
const RoutingTask&) =
delete;
433 for (std::map<std::string, int>::const_iterator it =
myLandmarks.begin(); it !=
myLandmarks.end(); ++it) {
434 if (it->second == i) {
#define WRITE_WARNING(msg)
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 bool consistent() const =0
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 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.
void waitAll(const bool deleteFinished=true)
waits for all tasks to be finished
Abstract superclass of a task to be run with an index to keep track of pending tasks.
A thread repeatingly calculating incoming tasks.
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...
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.