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(
TLF(
"Could not load landmark-lookup-table from '%'.", filename));
127 std::vector<const E*> landmarks;
128 int numLandMarks = 0;
129 bool haveData =
false;
130 while (std::getline(strm, line)) {
135 if (st.
size() == 1) {
136 const std::string lm = st.
get(0);
141 const auto& it = numericID.find(lm);
142 if (it == numericID.end()) {
143 throw ProcessError(
TLF(
"Landmark edge '%' does not exist in the network.", lm));
149 }
else if (st.
size() == 4) {
151 const std::string lm = st.
get(0);
152 const std::string edge = st.
get(1);
154 throw ProcessError(
TLF(
"Unknown or unordered edge '%' in landmark file.", edge));
162 const std::string edge = st.
get(0);
163 if ((
int)st.
size() != 2 * numLandMarks + 1) {
164 throw ProcessError(
TLF(
"Broken landmark file, unexpected number of entries (%) for edge '%'.", st.
size() - 1, edge));
167 throw ProcessError(
TLF(
"Unknown or unordered edge '%' in landmark file.", edge));
169 for (
int i = 0; i < numLandMarks; i++) {
179 WRITE_WARNINGF(
"No landmarks in '%', falling back to standard A*.", filename);
184 std::vector<RoutingTask*> currentTasks;
189 for (
int i = 0; i < numLandMarks; ++i) {
191 const E*
const landmark = landmarks[i];
194 WRITE_WARNINGF(
TL(
"No lookup table for landmark edge '%', recalculating."), landmark->getID());
196 throw ProcessError(
TLF(
"Not all network edges were found in the lookup table '%' for landmark edge '%'.", filename, landmark->getID()));
200 if (maxNumThreads > 0) {
201 const double lmCost = router->
recomputeCosts({landmark}, defaultVehicle, 0);
203 if (threadPool.
size() == 0) {
204 if (reverseRouter ==
nullptr) {
207 std::vector<const E*> route;
208 router->
compute(landmark, landmark, defaultVehicle, 0, route);
210 reverseRouter->setAutoBulkMode(
true);
212 while ((
int)threadPool.
size() < maxNumThreads) {
213 auto revClone = reverseRouter ==
nullptr ? nullptr : reverseRouter->clone();
214 new WorkerThread(threadPool, router->
clone(), revClone, defaultVehicle);
218 const E*
const edge = edges[j];
219 if (landmark != edge) {
220 const double sourceDestCost = lmCost + router->
recomputeCosts({edge}, defaultVehicle, 0);
221 currentTasks.push_back(
new RoutingTask(landmark, edge, sourceDestCost));
222 threadPool.
add(currentTasks.back(), i % maxNumThreads);
235 for (
int i = 0; i < numLandMarks; ++i) {
237 const E* landmark = landmarks[i];
238 const double lmCost = router->
recomputeCosts({landmark}, defaultVehicle, 0);
240 const E* edge = edges[j];
241 double distFrom = -1;
243 if (landmark == edge) {
247 if (maxNumThreads > 0) {
249 distFrom = currentTasks[taskIndex]->getFromCost();
250 distTo = currentTasks[taskIndex]->getToCost();
251 delete currentTasks[taskIndex++];
254 const double sourceDestCost = lmCost + router->
recomputeCosts({edge}, defaultVehicle, 0);
255 std::vector<const E*> route;
256 std::vector<const ReversedEdge<E, V>*> reversedRoute;
258 if (edge->getPredecessors().size() > 0 && landmark->getSuccessors().size() > 0) {
259 if (router->
compute(landmark, edge, defaultVehicle, 0, route)) {
260 distFrom =
MAX2(0.0, router->
recomputeCosts(route, defaultVehicle, 0) - sourceDestCost);
265 if (landmark->getPredecessors().size() > 0 && edge->getSuccessors().size() > 0) {
266 if (router->
compute(edge, landmark, defaultVehicle, 0, route)) {
267 distTo =
MAX2(0.0, router->
recomputeCosts(route, defaultVehicle, 0) - sourceDestCost);
278 if (!outfile.empty()) {
279 std::ostream* ostrm =
nullptr;
285 ostrm =
new std::ofstream(outfile.c_str());
289 if (!ostrm->good()) {
291 throw ProcessError(
TLF(
"Could not open file '%' for writing.", outfile));
294 for (
int i = 0; i < numLandMarks; ++i) {
299 for (
int i = 0; i < numLandMarks; ++i) {
311 double lowerBound(
const E* from,
const E* to,
double speed,
double speedFactor,
double fromEffort,
double toEffort)
const {
312 double result = from->getDistanceTo(to) / speed;
313#ifdef ASTAR_DEBUG_LOOKUPTABLE
314 if (from->getID() == ASTAR_DEBUG_LOOKUPTABLE_FROM) {
315 std::cout <<
" lowerBound to=" << to->getID() <<
" result1=" << result <<
"\n";
318 for (
int i = 0; i < (int)
myLandmarks.size(); ++i) {
322 if (fl >= 0 && tl >= 0) {
323 const double bound = (fl - tl - toEffort) / speedFactor;
324#ifdef ASTAR_DEBUG_LOOKUPTABLE
325 if (from->getID() == ASTAR_DEBUG_LOOKUPTABLE_FROM && result < bound) {
326 std::cout <<
" landmarkTo=" <<
getLandmark(i) <<
" result2=" << bound
327 <<
" fl=" << fl <<
" tl=" << tl <<
"\n";
330 result =
MAX2(result, bound);
334 if (lt >= 0 && lf >= 0) {
335 const double bound = (lt - lf - fromEffort) / speedFactor;
336#ifdef ASTAR_DEBUG_LOOKUPTABLE
337 if (from->getID() == ASTAR_DEBUG_LOOKUPTABLE_FROM && result < bound) {
338 std::cout <<
" landmarkFrom=" <<
getLandmark(i) <<
" result3=" << bound
339 <<
" lt=" << lt <<
" lf=" << lf <<
"\n";
342 result =
MAX2(result, bound);
344 if ((tl >= 0 && fl < 0)
345 || (lf >= 0 && lt < 0)) {
347#ifdef ASTAR_DEBUG_UNREACHABLE
348 std::cout <<
" unreachable: from=" << from->getID() <<
" to=" << to->getID() <<
" landmark=" <<
getLandmark(i) <<
" "
349 << ((tl >= 0 && fl < 0) ?
" (toLandmark)" :
" (fromLandmark)")
350 <<
" fl=" << fl <<
" tl=" << tl <<
" lt=" << lt <<
" lf=" << lf