30 #define UNREACHABLE (std::numeric_limits<double>::max() / 1000.0)
55 template<
class E,
class V>
59 virtual double lowerBound(
const E* from,
const E* to,
double speed,
double speedFactor,
double fromEffort,
double toEffort)
const = 0;
66 template<
class E,
class V>
71 std::ifstream strm(filename.c_str());
72 for (
int i = 0; i < size; i++) {
73 for (
int j = 0; j < size; j++) {
84 double lowerBound(
const E* from,
const E* to,
double ,
double speedFactor,
double ,
double )
const {
85 return myTable[from->getNumericalID()][to->getNumericalID()] / speedFactor;
93 std::vector<std::vector<double> >
myTable;
97 template<
class E,
class V>
102 const V* defaultVehicle,
const std::string& outfile,
const int maxNumThreads) {
104 std::map<std::string, int> numericID;
106 if (!e->isInternal()) {
113 std::ifstream strm(filename.c_str());
115 throw ProcessError(
"Could not load landmark-lookup-table from '" + filename +
"'.");
117 std::ofstream* ostrm =
nullptr;
118 if (!outfile.empty()) {
119 ostrm =
new std::ofstream(outfile.c_str());
120 if (!ostrm->good()) {
121 throw ProcessError(
"Could not open file '" + outfile +
"' for writing.");
125 int numLandMarks = 0;
126 while (std::getline(strm, line)) {
132 if (st.
size() == 1) {
133 const std::string lm = st.
get(0);
137 if (ostrm !=
nullptr) {
138 (*ostrm) << lm <<
"\n";
141 assert(st.
size() == 4);
142 const std::string lm = st.
get(0);
143 const std::string edge = st.
get(1);
145 WRITE_WARNING(
"Unknown or unordered edge '" + edge +
"' in landmark file.");
154 WRITE_WARNING(
"No landmarks in '" + filename +
"', falling back to standard A*.");
160 std::vector<RoutingTask*> currentTasks;
162 std::vector<const E*> landmarks;
163 for (
int i = 0; i < (int)
myLandmarks.size(); ++i) {
166 const E* landmark =
nullptr;
168 for (
const E*
const edge : edges) {
169 if (edge->getID() == landmarkID) {
171 landmarks.push_back(edge);
175 if (landmark ==
nullptr) {
176 WRITE_WARNING(
"Landmark '" + landmarkID +
"' does not exist in the network.");
179 if (router !=
nullptr) {
180 const std::string missing = outfile.empty() ? filename +
".missing" : outfile;
181 WRITE_WARNING(
"Not all network edges were found in the lookup table '" + filename +
"' for landmark '" + landmarkID +
"'. Saving missing values to '" + missing +
"'.");
182 if (ostrm ==
nullptr) {
183 ostrm =
new std::ofstream(missing.c_str());
184 if (!ostrm->good()) {
185 throw ProcessError(
"Could not open file '" + missing +
"' for writing.");
189 throw ProcessError(
"Not all network edges were found in the lookup table '" + filename +
"' for landmark '" + landmarkID +
"'.");
192 if (maxNumThreads > 0) {
193 const double lmCost = router->
recomputeCosts({landmark}, defaultVehicle, 0);
195 if (threadPool.
size() == 0) {
196 if (reverseRouter ==
nullptr) {
199 std::vector<const E*> route;
200 router->
compute(landmark, landmark, defaultVehicle, 0, route);
202 reverseRouter->setAutoBulkMode(
true);
204 while ((
int)threadPool.
size() < maxNumThreads) {
205 auto revClone = reverseRouter ==
nullptr ? nullptr : reverseRouter->clone();
206 new WorkerThread(threadPool, router->
clone(), revClone, defaultVehicle);
210 const E*
const edge = edges[j];
211 if (landmark != edge) {
212 const double sourceDestCost = lmCost + router->
recomputeCosts({edge}, defaultVehicle, 0);
213 currentTasks.push_back(
new RoutingTask(landmark, edge, sourceDestCost));
214 threadPool.
add(currentTasks.back(), i % maxNumThreads);
225 for (
int i = 0; i < (int)
myLandmarks.size(); ++i) {
227 const E* landmark = landmarks[i];
228 const double lmCost = router->
recomputeCosts({landmark}, defaultVehicle, 0);
230 const E* edge = edges[j];
231 double distFrom = -1;
233 if (landmark == edge) {
237 if (maxNumThreads > 0) {
239 distFrom = currentTasks[taskIndex]->getFromCost();
240 distTo = currentTasks[taskIndex]->getToCost();
241 delete currentTasks[taskIndex++];
244 const double sourceDestCost = lmCost + router->
recomputeCosts({edge}, defaultVehicle, 0);
245 std::vector<const E*> route;
246 std::vector<const ReversedEdge<E, V>*> reversedRoute;
248 if (edge->getPredecessors().size() > 0 && landmark->getSuccessors().size() > 0) {
249 if (router->
compute(landmark, edge, defaultVehicle, 0, route)) {
250 distFrom =
MAX2(0.0, router->
recomputeCosts(route, defaultVehicle, 0) - sourceDestCost);
255 if (landmark->getPredecessors().size() > 0 && edge->getSuccessors().size() > 0) {
256 if (router->
compute(edge, landmark, defaultVehicle, 0, route)) {
257 distTo =
MAX2(0.0, router->
recomputeCosts(route, defaultVehicle, 0) - sourceDestCost);
265 (*ostrm) << landmark->getID() <<
" " << edge->getID() <<
" " << distFrom <<
" " << distTo <<
"\n";
275 double lowerBound(
const E* from,
const E* to,
double speed,
double speedFactor,
double fromEffort,
double toEffort)
const {
276 double result = from->getDistanceTo(to) / speed;
277 #ifdef ASTAR_DEBUG_LOOKUPTABLE
278 if (from->getID() == ASTAR_DEBUG_LOOKUPTABLE_FROM) {
279 std::cout <<
" lowerBound to=" << to->getID() <<
" result1=" << result <<
"\n";
282 for (
int i = 0; i < (int)
myLandmarks.size(); ++i) {
286 if (fl >= 0 && tl >= 0) {
287 const double bound = (fl - tl - toEffort) / speedFactor;
288 #ifdef ASTAR_DEBUG_LOOKUPTABLE
289 if (from->getID() == ASTAR_DEBUG_LOOKUPTABLE_FROM && result < bound) {
290 std::cout <<
" landmarkTo=" <<
getLandmark(i) <<
" result2=" << bound
291 <<
" fl=" << fl <<
" tl=" << tl <<
"\n";
294 result =
MAX2(result, bound);
298 if (lt >= 0 && lf >= 0) {
299 const double bound = (lt - lf - fromEffort) / speedFactor;
300 #ifdef ASTAR_DEBUG_LOOKUPTABLE
301 if (from->getID() == ASTAR_DEBUG_LOOKUPTABLE_FROM && result < bound) {
302 std::cout <<
" landmarkFrom=" <<
getLandmark(i) <<
" result3=" << bound
303 <<
" lt=" << lt <<
" lf=" << lf <<
"\n";
306 result =
MAX2(result, bound);
308 if ((tl >= 0 && fl < 0)
309 || (lf >= 0 && lt < 0)) {
311 #ifdef ASTAR_DEBUG_UNREACHABLE
312 std::cout <<
" unreachable: from=" << from->getID() <<
" to=" << to->getID() <<
" landmark=" <<
getLandmark(i) <<
" "
313 << ((tl >= 0 && fl < 0) ?
" (toLandmark)" :
" (fromLandmark)")
314 <<
" fl=" << fl <<
" tl=" << tl <<
" lt=" << lt <<
" lf=" << lf
340 :
FXWorkerThread(pool), myRouter(router), myReversedRouter(reverseRouter), myVehicle(vehicle) {}
342 virtual ~WorkerThread() {
346 const std::pair<double, double> compute(
const E* src,
const E* dest,
const double costOff) {
347 double fromResult = -1.;
348 if (myRouter->compute(src, dest, myVehicle, 0, myRoute)) {
349 fromResult =
MAX2(0.0, myRouter->recomputeCosts(myRoute, myVehicle, 0) + costOff);
352 double toResult = -1.;
353 if (myReversedRouter !=
nullptr) {
354 if (myReversedRouter->compute(src->getReversedRoutingEdge(), dest->getReversedRoutingEdge(), myVehicle, 0, myReversedRoute)) {
355 toResult =
MAX2(0.0, myReversedRouter->recomputeCosts(myReversedRoute, myVehicle, 0) + costOff);
356 myReversedRoute.clear();
359 if (myRouter->compute(dest, src, myVehicle, 0, myRoute)) {
360 toResult =
MAX2(0.0, myRouter->recomputeCosts(myRoute, myVehicle, 0) + costOff);
364 return std::make_pair(fromResult, toResult);
371 std::vector<const E*> myRoute;
372 std::vector<const ReversedEdge<E, V>*> myReversedRoute;
377 RoutingTask(
const E* src,
const E* dest,
const double costOff)
378 : mySrc(src), myDest(dest), myCostOff(-costOff) {}
380 myCost = ((WorkerThread*)context)->compute(mySrc, myDest, myCostOff);
382 double getFromCost() {
386 return myCost.second;
389 const E*
const mySrc;
390 const E*
const myDest;
391 const double myCostOff;
392 std::pair<double, double> myCost;
395 RoutingTask& operator=(
const RoutingTask&) =
delete;
403 for (std::map<std::string, int>::const_iterator it =
myLandmarks.begin(); it !=
myLandmarks.end(); ++it) {
404 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