Eclipse SUMO - Simulation of Urban MObility
Loading...
Searching...
No Matches
AFRouter.h
Go to the documentation of this file.
1/****************************************************************************/
2// Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3// Copyright (C) 2012-2024 German Aerospace Center (DLR) and others.
4// This program and the accompanying materials are made available under the
5// terms of the Eclipse Public License 2.0 which is available at
6// https://www.eclipse.org/legal/epl-2.0/
7// This Source Code may also be made available under the following Secondary
8// Licenses when the conditions for such availability set forth in the Eclipse
9// Public License 2.0 are satisfied: GNU General Public License, version 2
10// or later which is available at
11// https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12// SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13/****************************************************************************/
18// Realizes an arc flag routing algorithm (Hilger et al.) in its multi-level variant
19// (also called "stripped SHARC" by Delling et al.)
20/****************************************************************************/
21#pragma once
22#include <config.h>
23
24#include <cassert>
25#include <string>
26#include <functional>
27#include <vector>
28#include <set>
29#include <limits>
30#include <algorithm>
31#include <iterator>
32#include <map>
33#include <iostream>
34#include <memory>
35#include <stdexcept>
36#include <cstddef>
43#include "AStarLookupTable.h"
44#include "SUMOAbstractRouter.h"
45#include "KDTreePartition.h"
46#include "FlippedEdge.h"
47#include "AFInfo.h"
48#include "AFBuilder.h"
49
50#define UNREACHABLE (std::numeric_limits<double>::max() / 1000.0)
51#define AFRO_WRITE_QGIS_FILTERS
52
53//#define AFRO_DEBUG_LEVEL_0
54//#define AFRO_DEBUG_LEVEL_1
55//#define AFRO_DEBUG_LEVEL_2
56//#define AFRO_DEBUG_LEVEL_3
57
58#ifdef AFRO_DEBUG_LEVEL_3
59#define AFRO_DEBUG_LEVEL_2
60#endif
61
62#ifdef AFRO_DEBUG_LEVEL_2
63#define AFRO_DEBUG_LEVEL_1
64#endif
65
66#ifdef AFRO_DEBUG_LEVEL_1
67#define AFRO_DEBUG_LEVEL_0
68#endif
69
70// ===========================================================================
71// class definitions
72// ===========================================================================
90template<class E, class N, class V, class M>
91class AFRouter : public SUMOAbstractRouter<E, V> {
92public:
95 typedef typename AFInfo<E>::FlagInfo FlagInfo;
97
103 typename SUMOAbstractRouter<E, V>::EdgeInfo* edgeInfo(const E* const edge) {
104 return &(this->myEdgeInfos[edge->getNumericalID()]);
105 }
106
112 const typename SUMOAbstractRouter<E, V>::EdgeInfo* edgeInfo(const E* const edge) const {
113 return &(this->myEdgeInfos[edge->getNumericalID()]);
114 }
115
122 public:
130 bool operator()(const typename SUMOAbstractRouter<E, V>::EdgeInfo* edgeInfo1, const typename SUMOAbstractRouter<E, V>::EdgeInfo* edgeInfo2) const {
131 if (edgeInfo1->heuristicEffort == edgeInfo2->heuristicEffort) {
132 return edgeInfo1->edge->getNumericalID() > edgeInfo2->edge->getNumericalID();
133 }
134 return edgeInfo1->heuristicEffort > edgeInfo2->heuristicEffort;
135 }
136 };
137
150 AFRouter(const std::vector<E*>& edges,
151 const KDTreePartition<E, N, V>* partition,
152 bool unbuildIsWarning,
153 typename SUMOAbstractRouter<E, V>::Operation operation, typename SUMOAbstractRouter<FlippedEdge<E, N, V>, V>::Operation flippedOperation,
154 SUMOTime weightPeriod, const std::shared_ptr<const LookupTable> lookup = nullptr,
155 const std::shared_ptr<const FlippedLookupTable> flippedLookup = nullptr,
156 const bool havePermissions = false, const bool haveRestrictions = false) :
157 SUMOAbstractRouter<E, V>("arcFlagRouter", unbuildIsWarning, operation, nullptr, havePermissions, haveRestrictions),
158 myFlagInfos(nullptr),
159 myPartition(partition),
160 myLookupTable(lookup),
161 myMaxSpeed(NUMERICAL_EPS),
162 myWeightPeriod(weightPeriod),
163 myValidUntil(0),
164 myBuilder(new AFBuilder<E, N, V, M>(myPartition->getNumberOfLevels(), edges, unbuildIsWarning,
165 flippedOperation, flippedLookup, havePermissions, haveRestrictions)),
166 myType("arcFlagRouter"),
167 myQueryVisits(0),
168 myNumQueries(0),
171#ifdef AFRO_DEBUG_LEVEL_2
172 myFlagContextStartTime(0),
173 myFlagContextTimeSum(0),
174#endif
175 myLastSettledEdgeCell(nullptr),
176 myTargetEdgeCellLevel0(nullptr) {
177 for (const E* const edge : edges) {
178 this->myEdgeInfos.push_back(typename SUMOAbstractRouter<E, V>::EdgeInfo(edge));
179 myMaxSpeed = MAX2(myMaxSpeed, edge->getSpeedLimit() * MAX2(1.0, edge->getLengthGeometryFactor()));
180 }
181 }
182
195 AFRouter(const std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo>& edgeInfos,
196 const std::vector<E*>& edges,
197 const KDTreePartition<E, N, V>* partition,
198 bool unbuildIsWarning,
199 typename SUMOAbstractRouter<E, V>::Operation operation,
200 typename SUMOAbstractRouter<FlippedEdge<E, N, V>, V>::Operation flippedOperation,
201 SUMOTime weightPeriod, const std::shared_ptr<const LookupTable> lookup = nullptr,
202 const std::shared_ptr<const FlippedLookupTable> flippedLookup = nullptr,
203 const bool havePermissions = false, const bool haveRestrictions = false) :
204 SUMOAbstractRouter<E, V>("arcFlagRouter", unbuildIsWarning, operation, nullptr, havePermissions, haveRestrictions),
205 myFlagInfos(nullptr),
206 myPartition(partition),
207 myLookupTable(lookup),
208 myMaxSpeed(NUMERICAL_EPS),
209 myWeightPeriod(weightPeriod),
210 myValidUntil(0),
211 myBuilder(new AFBuilder<E, N, V, M>(myPartition->getNumberOfLevels(), edges, unbuildIsWarning,
212 flippedOperation, flippedLookup, havePermissions, haveRestrictions)),
213 myType("arcFlagRouter"),
214 myQueryVisits(0),
215 myNumQueries(0),
218#ifdef AFRO_DEBUG_LEVEL_2
219 myFlagContextStartTime(0),
220 myFlagContextTimeSum(0),
221#endif
222 myLastSettledEdgeCell(nullptr),
223 myTargetEdgeCellLevel0(nullptr) {
224 for (const auto& edgeInfo : edgeInfos) {
226 myMaxSpeed = MAX2(myMaxSpeed, edgeInfo.edge->getSpeedLimit() * edgeInfo.edge->getLengthGeometryFactor());
227 }
228 }
229
240 AFRouter(const std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo>& edgeInfos,
241 const KDTreePartition<E, N, V>* partition,
242 bool unbuildIsWarning, typename SUMOAbstractRouter<E, V>::Operation operation,
243 std::vector<FlagInfo*>* flagInfos,
244 const std::shared_ptr<const LookupTable> lookup = nullptr,
245 const bool havePermissions = false, const bool haveRestrictions = false) :
246 SUMOAbstractRouter<E, V>("arcFlagRouterClone", unbuildIsWarning, operation, nullptr, havePermissions, haveRestrictions),
247 myFlagInfos(flagInfos),
248 myPartition(partition),
249 myLookupTable(lookup),
250 myMaxSpeed(NUMERICAL_EPS),
253 myBuilder(nullptr),
254 myType("arcFlagRouterClone"),
255 myQueryVisits(0),
256 myNumQueries(0),
259#ifdef AFRO_DEBUG_LEVEL_2
260 myFlagContextStartTime(0),
261 myFlagContextTimeSum(0),
262#endif
263 myLastSettledEdgeCell(nullptr),
264 myTargetEdgeCellLevel0(nullptr) {
265 for (const auto& edgeInfo : edgeInfos) {
267 myMaxSpeed = MAX2(myMaxSpeed, edgeInfo.edge->getSpeedLimit() * edgeInfo.edge->getLengthGeometryFactor());
268 }
269 }
270
272 virtual ~AFRouter() {
273 delete myBuilder;
274 }
275
278 // I am either a clone myself, or I am already initialized and time-independent
279 // (i.e., I have been created with a maximum weight period)
280 if (myWeightPeriod == SUMOTime_MAX && myFlagInfos != nullptr) {
281 // we only need the arc infos once:
284 }
285 // I am not a clone: I am either uninitialized, or initialized but time-dependent:
286 // create another such guy (also flagged as a non-clone)
287 return new AFRouter(this->myEdgeInfos, myBuilder->getEdges(), myPartition,
288 this->myErrorMsgHandler == MsgHandler::getWarningInstance(),
289 this->myOperation, myBuilder->getArcFlagBuild()->getFlippedOperation(),
290 myWeightPeriod, myLookupTable, myBuilder->getArcFlagBuild()->getFlippedLookup(),
291 this->myHavePermissions, this->myHaveRestrictions);
292 }
293
299 static int partitionLevel2SHARCLevel(int partitionLevel, int numberOfPartitionLevels) {
300 // heads up: partition levels must start at zero, with zero being an illegal argument
301 // (since it would corresponds to level L = V, which is not a valid SHARC level)
302 if (partitionLevel <= 0) {
303 throw std::invalid_argument("partitionLevel2SHARCLevel: given partition level is zero (0) or below. This does not correspond to a valid SHARC level. Partition levels valid for conversion to SHARC levels go from one to number of partition levels minus one.");
304 }
305 // heads up: partition levels must start at zero
306 if (partitionLevel > numberOfPartitionLevels - 1) {
307 throw std::invalid_argument("partitionLevel2SHARCLevel: given partition level exceeds the number of partition levels minus one. Most likely you did not start the partition level numbering at zero (0), which is required here.");
308 }
309 return (numberOfPartitionLevels - 1) - partitionLevel;
310 }
311
317 static int sHARCLevel2PartitionLevel(int sHARCLevel, int numberOfPartitionLevels) {
318 int numberOfSHARCLevels = numberOfPartitionLevels - 1;
319 if (sHARCLevel < 0) {
320 throw std::invalid_argument("sHARCLevel2PartitionLevel: given SHARC level is negative.");
321 }
322 // heads up: SHARC levels must start at zero (0),
323 // and end at number of partition levels minus two
324 if (sHARCLevel > numberOfSHARCLevels - 1) {
325 throw std::invalid_argument("sHARCLevel2PartitionLevel: given SHARC level exceeds the number of SHARC levels minus one. Most likely you did not start the SHARC level numbering at zero (0), which is required here.");
326 }
327 return numberOfSHARCLevels - sHARCLevel;
328 }
329
335 static bool flag(const FlagInfo* flagInfo, const std::tuple<int, int, bool> flagContext) {
336 assert(flagInfo);
337 return flagInfo->arcFlags.empty() ? true : /* play it safe */
338 (flagInfo->arcFlags)[std::get<0>(flagContext) /* assumed to be the SHARC level */ * 2
339 + std::get<1>(flagContext) /* assumed to be the cell index */];
340
341 }
342
347 std::vector<bool>& flags(const E* edge);
348
352 virtual void reset(const V* const vehicle) {
353 if (myValidUntil == 0) {
355 }
356 assert(myBuilder);
357#ifdef AFRO_DEBUG_LEVEL_0
358 long long int firstCallStart = 0;
359 long long int firstCallTime = 0;
360 firstCallStart = SysUtils::getCurrentMillis();
361 std::cout << "Calling arc flag router for the first time during current weight period (arc flags build). This might take a while... " << std::endl;
362#endif
363 myFlagInfos = &(myBuilder->build(myValidUntil - myWeightPeriod, vehicle));
364#ifdef AFRO_DEBUG_LEVEL_0
365 firstCallTime = (SysUtils::getCurrentMillis() - firstCallStart);
366 std::cout << "Time spent for arc flags build: " << elapsedMs2string(firstCallTime) << std::endl;
367#endif
368 }
369
374 void init(const int edgeID, const SUMOTime msTime);
379 std::tuple<int, int, bool> flagContext(const E* settledEdge, const E* targetEdge);
381 std::tuple<int, int, bool> flagContextNaive(const E* settledEdge, const E* targetEdge);
382
391 bool compute(const E* from, const E* to, const V* const vehicle,
392 SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
393 assert(from != nullptr && to != nullptr);
394 // check whether from and to can be used
395 if (this->myEdgeInfos[from->getNumericalID()].prohibited || this->isProhibited(from, vehicle)) {
396 if (!silent) {
397 this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on source edge '" + from->getID() + "'.");
398 }
399 return false;
400 }
401 if (this->myEdgeInfos[to->getNumericalID()].prohibited || this->isProhibited(to, vehicle)) {
402 if (!silent) {
403 this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on destination edge '" + to->getID() + "'.");
404 }
405 return false;
406 }
407
408 if (msTime >= myValidUntil) {
409 assert(myBuilder != nullptr); // only time independent clones do not have a builder
410 while (msTime >= myValidUntil) {
412 }
413 reset(vehicle);
414 }
415 // rewind routing start time to building time (this can only be a gross approximation
416 // of time-dependent routing)
417 msTime = myValidUntil - myWeightPeriod;
418
419 double length = 0.; // dummy for the via edge cost update
420 this->startQuery();
421 const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
422 this->init(from->getNumericalID(), msTime);
423 this->myAmClean = false;
424 // loop
425 int num_visited = 0;
426#ifdef AFRO_DEBUG_LEVEL_1
427 int numberOfFollowers = 0;
428 int numberOfAvoidedFollowers = 0;
429 int numberOfEmptyFlagVectors = 0;
430#endif
431 const bool mayRevisit = myLookupTable != nullptr && !myLookupTable->consistent();
432 const double speed = vehicle == nullptr ? myMaxSpeed : MIN2(vehicle->getMaxSpeed(), myMaxSpeed * vehicle->getChosenSpeedFactor());
433
434 while (!this->myFrontierList.empty()) {
435 num_visited += 1;
436 // use the edge with the minimal length
437 auto* const minimumInfo = this->myFrontierList.front();
438 const E* const minEdge = minimumInfo->edge;
439 // check whether the destination edge was already reached
440 if (minEdge == to) {
441 this->buildPathFrom(minimumInfo, into);
442 this->endQuery(num_visited);
443#ifdef AFRO_DEBUG_LEVEL_1
444 std::cout << "Found to, to->getID(): " << to->getID() << std::endl;
445 std::cout << static_cast<double>(numberOfFollowers - numberOfAvoidedFollowers) / static_cast<double>(num_visited)
446 << " followers considered (out of " << static_cast<double>(numberOfFollowers) / static_cast<double>(num_visited) << ") on average." << std::endl;
447 std::cout << static_cast<double>(numberOfFollowers - numberOfAvoidedFollowers)
448 << " followers considered (out of " << static_cast<double>(numberOfFollowers) << ")." << std::endl;
449 std::cout << numberOfEmptyFlagVectors << " out of " << numberOfFollowers << " flag vectors of followers were unassigned (i.e., empty)." << std::endl;
450 std::cout << "num_visited: " << num_visited << std::endl;
451#endif
452 return true;
453 }
454 std::pop_heap(this->myFrontierList.begin(), this->myFrontierList.end(), myComparator);
455 this->myFrontierList.pop_back();
456 this->myFound.push_back(minimumInfo);
457 minimumInfo->visited = true;
458
459 const double effortDelta = this->getEffort(minEdge, vehicle, minimumInfo->leaveTime);
460 const double leaveTime = minimumInfo->leaveTime + this->getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
461
462 // admissible A* heuristic: straight line distance at maximum speed
463 // this is calculated from the end of minEdge so it possibly includes via efforts to the followers
464 double heuristic_remaining = 0.;
465 double heuristicEffort = minimumInfo->effort + effortDelta + heuristic_remaining;
466 // check all ways from the edge with the minimal length
467 for (const std::pair<const E*, const E*>& follower : minEdge->getViaSuccessors(vClass)) {
468 auto& followerInfo = this->myEdgeInfos[follower.first->getNumericalID()];
469 const FlagInfo* followerFlagInfo = (*myFlagInfos)[follower.first->getNumericalID()];
470 // check whether it can be used
471 if (followerInfo.prohibited || this->isProhibited(follower.first, vehicle)) {
472 continue;
473 }
474#ifdef AFRO_DEBUG_LEVEL_1
475 numberOfFollowers++;
476 if (followerFlagInfo->arcFlags.empty()) {
477 numberOfEmptyFlagVectors++;
478 }
479#endif
480#ifdef AFRO_DEBUG_LEVEL_2
481 myFlagContextStartTime = SysUtils::getCurrentMillis();
482#endif
483 std::tuple<int, int, bool> flagContext = this->flagContext(follower.first, to);
484 //std::tuple<int, int, bool> flagContext = this->flagContextNaive(follower.first, to);
485#ifdef AFRO_DEBUG_LEVEL_2
486 myFlagContextTimeSum += (SysUtils::getCurrentMillis() - myFlagContextStartTime);
487#endif
488 if (!flag(followerFlagInfo, flagContext)) {
489#ifdef AFRO_DEBUG_LEVEL_1
490 numberOfAvoidedFollowers++;
491#endif
492 continue;
493 }
494
495 // admissible A* heuristic: straight line distance at maximum speed
496 // this is calculated from the end of minEdge so it possibly includes via efforts to the followers
497 if (heuristic_remaining == 0 && std::get<0>(flagContext) == 0 && std::get<2>(flagContext)) {
498 // arrived at the target cell at level 0? use heuristic
499 heuristic_remaining =
500 (myLookupTable == nullptr ? minEdge->getDistanceTo(to) / speed :
501 myLookupTable->lowerBound(minEdge, to, speed, vehicle->getChosenSpeedFactor(),
502 minEdge->getMinimumTravelTime(nullptr), to->getMinimumTravelTime(nullptr)));
503 if (heuristic_remaining == UNREACHABLE) {
504 break; // -> skip remaining followers, continue with next min heap element
505 }
506 heuristicEffort += heuristic_remaining;
507 }
508
509 double effort = minimumInfo->effort + effortDelta;
510 double time = leaveTime;
511 this->updateViaEdgeCost(follower.second, vehicle, time, effort, length);
512 const double oldEffort = followerInfo.effort;
513 if ((!followerInfo.visited || mayRevisit) && effort < oldEffort) {
514 followerInfo.effort = effort;
515 // if we use the effort including the via effort below we would count the via twice as shown by the ticket676 test
516 // but we should never get below the real effort, see #12463
517 followerInfo.heuristicEffort = MAX2(MIN2(heuristicEffort, followerInfo.heuristicEffort), effort);
518 followerInfo.leaveTime = time;
519 followerInfo.prev = minimumInfo;
520 if (oldEffort == std::numeric_limits<double>::max()) {
521 this->myFrontierList.push_back(&followerInfo);
522 std::push_heap(this->myFrontierList.begin(), this->myFrontierList.end(), myComparator);
523 } else {
524 auto fi = std::find(this->myFrontierList.begin(), this->myFrontierList.end(), &followerInfo);
525 if (fi == this->myFrontierList.end()) {
526 assert(mayRevisit);
527 this->myFrontierList.push_back(&followerInfo);
528 std::push_heap(this->myFrontierList.begin(), this->myFrontierList.end(), myComparator);
529 } else {
530 std::push_heap(this->myFrontierList.begin(), fi + 1, myComparator);
531 }
532 }
533 }
534 } // for followers
535 }
536 this->endQuery(num_visited);
537#ifdef AFRO_DEBUG_LEVEL_1
538 std::cout << "Queue ran empty, no solution." << std::endl;
539 std::cout << static_cast<double>(numberOfFollowers - numberOfAvoidedFollowers) / static_cast<double>(num_visited)
540 << " followers considered (out of " << static_cast<double>(numberOfFollowers) / static_cast<double>(num_visited) << ") on average." << std::endl;
541 std::cout << static_cast<double>(numberOfFollowers - numberOfAvoidedFollowers)
542 << " followers considered (out of " << static_cast<double>(numberOfFollowers) << ")." << std::endl;
543 std::cout << numberOfEmptyFlagVectors << " out of " << numberOfFollowers << " flag vectors of followers were unassigned (i.e., empty)." << std::endl;
544 std::cout << "num_visited: " << num_visited << std::endl;
545#endif
546 if (!silent) {
547 this->myErrorMsgHandler->informf("No connection between edge '%' and edge '%' found.", from->getID(), to->getID());
548 }
549 return false;
550 }
551
553 void startQuery();
555 void endQuery(int visits);
557 void reportStatistics();
559 void resetStatistics();
561 virtual void setBulkMode(const bool mode) {
562 UNUSED_PARAMETER(mode);
563 throw std::runtime_error("Bulk mode is not supported by the arc flag router.");
564 }
565
566protected:
568 std::vector<FlagInfo*>* myFlagInfos;
574 const std::shared_ptr<const LookupTable> myLookupTable;
585 const std::string myType;
588 long long int myQueryVisits;
589 long long int myNumQueries;
592 long long int myQueryStartTime;
593 long long int myQueryTimeSum;
594#ifdef AFRO_DEBUG_LEVEL_2
596 long long int myFlagContextStartTime;
597 long long int myFlagContextTimeSum;
598#endif
599private:
603 std::tuple<int, int, bool> myLastFlagContext;
606};
607
608// ===========================================================================
609// method definitions
610// ===========================================================================
611
612template<class E, class N, class V, class M>
613std::vector<bool>& AFRouter<E, N, V, M>::flags(const E* edge) {
614 assert(edge);
615 if (!myFlagInfos) {
616 throw std::runtime_error("flag infos not initialized, call compute() at least once before calling flags().");
617 }
618 return ((*myFlagInfos)[edge->getNumericalID()])->arcFlags;
619}
620
621template<class E, class N, class V, class M>
622void AFRouter<E, N, V, M>::init(const int edgeID, const SUMOTime msTime) {
623 // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
624 myTargetEdgeCellLevel0 = nullptr;
625 for (auto& edgeInfo : this->myFrontierList) {
626 edgeInfo->reset();
627 }
628 this->myFrontierList.clear();
629 for (auto& edgeInfo : this->myFound) {
630 edgeInfo->reset();
631 }
632 this->myFound.clear();
633 if (edgeID > -1) {
634 // add begin node
635 auto& fromInfo = this->myEdgeInfos[edgeID];
636 fromInfo.heuristicEffort = 0.;
637 fromInfo.effort = 0.;
638 fromInfo.leaveTime = STEPS2TIME(msTime);
639 fromInfo.prev = nullptr;
640 this->myFrontierList.push_back(&fromInfo);
641 }
642}
643
644template<class E, class N, class V, class M>
645std::tuple<int, int, bool> AFRouter<E, N, V, M>::flagContextNaive(const E* settledEdge, const E* targetEdge) {
646 assert(settledEdge != nullptr && targetEdge != nullptr);
647 int sHARCLevel;
648 for (sHARCLevel = 0; sHARCLevel < myPartition->getNumberOfLevels() - 1; sHARCLevel++) {
649 int partitionLevel = sHARCLevel2PartitionLevel(sHARCLevel, myPartition->getNumberOfLevels());
650 const std::vector<const Cell*>& levelCells = myPartition->getCellsAtLevel(partitionLevel);
651 typename std::vector<const Cell*>::const_iterator first = levelCells.begin();
652 typename std::vector<const Cell*>::const_iterator last = levelCells.end();
653 typename std::vector<const Cell*>::const_iterator iter;
654 const Cell* settledEdgeCell = nullptr;
655 const Cell* targetEdgeCell = nullptr;
656 // go through the cells of the level
657 for (iter = first; iter != last; iter++) {
658 // myPartition is assumed to partition a non-reversed (forward) graph
659 if (!settledEdgeCell && (*iter)->contains(settledEdge->getFromJunction())) {
660 settledEdgeCell = *iter;
661 }
662 if (!targetEdgeCell && (*iter)->contains(targetEdge->getFromJunction())) {
663 targetEdgeCell = *iter;
664 }
665 if (settledEdgeCell && targetEdgeCell) {
666 break;
667 }
668 }
669 assert(settledEdgeCell && targetEdgeCell); // we should find both edges on each level
670 if (settledEdgeCell->getSupercell() == targetEdgeCell->getSupercell()) {
671 return std::make_tuple(sHARCLevel, targetEdgeCell->isLeftOrLowerCell() ? 0 : 1,
672 settledEdgeCell == targetEdgeCell);
673 }
674 }
675 // we should never arrive here
676 throw std::runtime_error("flagContext: relevant level could not be determined.");
677}
678
679template<class E, class N, class V, class M>
680std::tuple<int, int, bool> AFRouter<E, N, V, M>::flagContext(const E* settledEdge, const E* targetEdge) {
681 assert(settledEdge != nullptr && targetEdge != nullptr);
682 int sHARCLevel = 0; // lowest level with smallest cells
683 const Cell* settledEdgeCell = nullptr;
684 const Cell* targetEdgeCell = nullptr;
685 if (myLastSettledEdgeCell
686 && myLastSettledEdgeCell->contains(settledEdge->getFromJunction())) {
687 // exploit the partial locality of Dijkstra's algorithm: settled edge is still
688 // in the same cell as the last one? Then we can simply return the
689 // last flagContext tuple again.
690 return myLastFlagContext;
691 }
692 int numberOfPartitionLevels = myPartition->getNumberOfLevels();
693 if (numberOfPartitionLevels <= 4) { // small number of bottom cells -> go through them, no use of k-d tree
694 int partitionLevel = sHARCLevel2PartitionLevel(sHARCLevel, myPartition->getNumberOfLevels());
695 const std::vector<const Cell*>& levelCells = myPartition->getCellsAtLevel(partitionLevel);
696 typename std::vector<const Cell*>::const_iterator first = levelCells.begin();
697 typename std::vector<const Cell*>::const_iterator last = levelCells.end();
698 typename std::vector<const Cell*>::const_iterator iter;
699 // go through the cells of the level
700 for (iter = first; iter != last; iter++) {
701 // myPartition is assumed to partition a non-reversed (forward) graph
702 if (!settledEdgeCell
703 && (*iter)->contains(settledEdge->getFromJunction())) {
704 settledEdgeCell = *iter;
705 }
706 if (!targetEdgeCell && myTargetEdgeCellLevel0) {
707 targetEdgeCell = myTargetEdgeCellLevel0;
708 } else if (!targetEdgeCell
709 && (*iter)->contains(targetEdge->getFromJunction())) {
710 myTargetEdgeCellLevel0 = *iter;
711 targetEdgeCell = myTargetEdgeCellLevel0;
712 }
713 if (settledEdgeCell && targetEdgeCell) {
714 assert(myTargetEdgeCellLevel0);
715 break;
716 }
717 }
718 } else { // larger number of bottom cells -> use a k-d tree
719 settledEdgeCell = myPartition->searchNode(settledEdge->getFromJunction());
720 if (!targetEdgeCell && myTargetEdgeCellLevel0) {
721 // search only once per query
722 targetEdgeCell = myTargetEdgeCellLevel0;
723 } else if (!targetEdgeCell) {
724 myTargetEdgeCellLevel0 = myPartition->searchNode(targetEdge->getFromJunction());
725 targetEdgeCell = myTargetEdgeCellLevel0; // myTargetEdgeCellLevel0 is reset in init()
726 }
727 }
728 assert(settledEdgeCell && targetEdgeCell); // we should find both edges on each level
729 while (settledEdgeCell->getSupercell() != targetEdgeCell->getSupercell()) {
730 settledEdgeCell = settledEdgeCell->getSupercell();
731 targetEdgeCell = targetEdgeCell->getSupercell();
732 sHARCLevel++;
733 }
734 myLastSettledEdgeCell = settledEdgeCell;
735 std::tuple<int, int, bool> flagContext = std::make_tuple(sHARCLevel, targetEdgeCell->isLeftOrLowerCell() ? 0 : 1,
736 settledEdgeCell == targetEdgeCell);
737 myLastFlagContext = flagContext;
738 return flagContext;
739}
740
741template<class E, class N, class V, class M>
743 myNumQueries++;
744 myQueryStartTime = SysUtils::getCurrentMillis();
746}
747
748template<class E, class N, class V, class M>
750 myQueryVisits += visits;
751 myQueryTimeSum += (SysUtils::getCurrentMillis() - myQueryStartTime);
753}
754
755template<class E, class N, class V, class M>
757 if (myNumQueries > 0) {
758 WRITE_MESSAGE(myType + " answered " + toString(myNumQueries) + " queries and explored " + toString((double)myQueryVisits / (double)myNumQueries) + " edges on average.");
759 WRITE_MESSAGE(myType + " spent " + elapsedMs2string(myQueryTimeSum) + " answering queries (" + toString((double)myQueryTimeSum / (double)myNumQueries) + " ms on average).");
760#ifdef AFRO_DEBUG_LEVEL_2
761 WRITE_MESSAGE("flagContext spent " + elapsedMs2string(myFlagContextTimeSum) + " (" + toString((double)myFlagContextTimeSum / (double)myNumQueries) + " ms on average).");
762#endif
763 }
764}
765
766template<class E, class N, class V, class M>
768 myNumQueries = 0;
769 myQueryVisits = 0;
770 myQueryTimeSum = 0;
771 myQueryStartTime = 0;
772}
#define UNREACHABLE
Definition AFRouter.h:50
long long int SUMOTime
Definition GUI.h:36
#define WRITE_MESSAGE(msg)
Definition MsgHandler.h:297
std::string elapsedMs2string(long long int t)
convert ms to string for log output
Definition SUMOTime.cpp:123
#define STEPS2TIME(x)
Definition SUMOTime.h:55
#define SUMOTime_MAX
Definition SUMOTime.h:34
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types.
@ SVC_IGNORING
vehicles ignoring classes
#define UNUSED_PARAMETER(x)
Definition StdDefs.h:30
T MIN2(T a, T b)
Definition StdDefs.h:76
T MAX2(T a, T b)
Definition StdDefs.h:82
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition ToString.h:46
Builds arc flags for shortest path search with the arc flag router.
Definition AFBuilder.h:51
std::vector< bool > arcFlags
The arc flags.
Definition AFInfo.h:67
bool operator()(const typename SUMOAbstractRouter< E, V >::EdgeInfo *edgeInfo1, const typename SUMOAbstractRouter< E, V >::EdgeInfo *edgeInfo2) const
Comparing method.
Definition AFRouter.h:130
long long int myQueryTimeSum
Definition AFRouter.h:593
SUMOTime myValidUntil
The validity duration of the current flag infos (exclusive)
Definition AFRouter.h:580
static int sHARCLevel2PartitionLevel(int sHARCLevel, int numberOfPartitionLevels)
Converts a SHARC level number to a partition level number.
Definition AFRouter.h:317
AFRouter(const std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > &edgeInfos, const KDTreePartition< E, N, V > *partition, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation operation, std::vector< FlagInfo * > *flagInfos, const std::shared_ptr< const LookupTable > lookup=nullptr, const bool havePermissions=false, const bool haveRestrictions=false)
Special cloning constructor, only for time-independent instances which never rebuild arc infos.
Definition AFRouter.h:240
const std::string myType
The type of this router.
Definition AFRouter.h:585
virtual ~AFRouter()
Destructor.
Definition AFRouter.h:272
std::vector< bool > & flags(const E *edge)
Returns the arc flags of the passed edge.
Definition AFRouter.h:613
const Cell * myLastSettledEdgeCell
The cell of the last settled edge.
Definition AFRouter.h:601
long long int myQueryVisits
Counters for performance logging.
Definition AFRouter.h:588
KDTreePartition< E, N, V >::Cell Cell
Definition AFRouter.h:94
const SUMOTime myWeightPeriod
The validity duration of one weight interval.
Definition AFRouter.h:578
AFRouter(const std::vector< E * > &edges, const KDTreePartition< E, N, V > *partition, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation operation, typename SUMOAbstractRouter< FlippedEdge< E, N, V >, V >::Operation flippedOperation, SUMOTime weightPeriod, const std::shared_ptr< const LookupTable > lookup=nullptr, const std::shared_ptr< const FlippedLookupTable > flippedLookup=nullptr, const bool havePermissions=false, const bool haveRestrictions=false)
Constructor.
Definition AFRouter.h:150
AbstractLookupTable< FlippedEdge< E, N, V >, V > FlippedLookupTable
Definition AFRouter.h:96
void endQuery(int visits)
Stop timer for query time sum.
Definition AFRouter.h:749
std::tuple< int, int, bool > flagContextNaive(const E *settledEdge, const E *targetEdge)
Kept for runtime comparisons.
Definition AFRouter.h:645
virtual void setBulkMode(const bool mode)
Bulk mode is not supported.
Definition AFRouter.h:561
std::vector< FlagInfo * > * myFlagInfos
Edge infos containing the associated edge and its arc flags.
Definition AFRouter.h:568
void reportStatistics()
Report query time statistics.
Definition AFRouter.h:756
bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false)
Builds the route between the given edges using the minimum travel time param[in] from The from-/start...
Definition AFRouter.h:391
AFInfo< E >::FlagInfo FlagInfo
Definition AFRouter.h:95
virtual void reset(const V *const vehicle)
Trigger arc flags rebuild.
Definition AFRouter.h:352
static int partitionLevel2SHARCLevel(int partitionLevel, int numberOfPartitionLevels)
Converts a partition level number to a SHARC level number.
Definition AFRouter.h:299
const KDTreePartition< E, N, V > * myPartition
The partition.
Definition AFRouter.h:570
void resetStatistics()
Reset query time statistics.
Definition AFRouter.h:767
EdgeInfoComparator myComparator
The comparator for edge information.
Definition AFRouter.h:572
void startQuery()
Start timer for query time sum.
Definition AFRouter.h:742
const Cell * myTargetEdgeCellLevel0
The cell of the target edge at SHARC level 0.
Definition AFRouter.h:605
void init(const int edgeID, const SUMOTime msTime)
Initialize the arc flag router param[in] edgeID The edge id(entifier) param[in] msTime The start time...
Definition AFRouter.h:622
AbstractLookupTable< E, V > LookupTable
Definition AFRouter.h:93
static bool flag(const FlagInfo *flagInfo, const std::tuple< int, int, bool > flagContext)
Returns the arc flag of the edge in flagInfo wrt flagContext.
Definition AFRouter.h:335
std::tuple< int, int, bool > flagContext(const E *settledEdge, const E *targetEdge)
Returns the flag context for a route query from given settled edge to the target edge.
Definition AFRouter.h:680
long long int myQueryStartTime
The time spent querying in milliseconds.
Definition AFRouter.h:592
const std::shared_ptr< const LookupTable > myLookupTable
The lookup table for travel time heuristics.
Definition AFRouter.h:574
AFBuilder< E, N, V, M > * myBuilder
The builder.
Definition AFRouter.h:582
long long int myNumQueries
Definition AFRouter.h:589
std::tuple< int, int, bool > myLastFlagContext
The last flag context.
Definition AFRouter.h:603
const SUMOAbstractRouter< E, V >::EdgeInfo * edgeInfo(const E *const edge) const
Returns the edge information for the passed edge.
Definition AFRouter.h:112
AFRouter(const std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > &edgeInfos, const std::vector< E * > &edges, const KDTreePartition< E, N, V > *partition, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation operation, typename SUMOAbstractRouter< FlippedEdge< E, N, V >, V >::Operation flippedOperation, SUMOTime weightPeriod, const std::shared_ptr< const LookupTable > lookup=nullptr, const std::shared_ptr< const FlippedLookupTable > flippedLookup=nullptr, const bool havePermissions=false, const bool haveRestrictions=false)
"Normal" cloning constructor for uninitialized or time-dependent instances
Definition AFRouter.h:195
virtual SUMOAbstractRouter< E, V > * clone()
Cloning method.
Definition AFRouter.h:277
double myMaxSpeed
The maximum speed in the network.
Definition AFRouter.h:576
SUMOAbstractRouter< E, V >::EdgeInfo * edgeInfo(const E *const edge)
Returns the edge information for the passed edge.
Definition AFRouter.h:103
The edge type representing backward edges with flipped nodes.
Definition FlippedEdge.h:43
Represents an element of the node partition (i.e. a node set)
bool contains(const N *node) const
Tests whether the given node belongs to the cell.
const Cell * getSupercell() const
Returns the supercell.
bool isLeftOrLowerCell() const
Returns the boolean flag indicating whether this cell is a left or lower cell or not.
Partitions the router's network wrt a k-d tree subdivision scheme.
virtual void inform(std::string msg, bool addType=true)
adds a new error to the list
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
void informf(const std::string &format, T value, Targs... Fargs)
adds a new formatted message
Definition MsgHandler.h:122
static std::string getIDSecure(const T *obj, const std::string &fallBack="NULL")
get an identifier for Named-like object which may be Null
Definition Named.h:67
const E *const edge
The current edge.
double heuristicEffort
Estimated effort to reach the edge (effort + lower bound on remaining effort)
MsgHandler *const myErrorMsgHandler
the handler for routing errors
const bool myHavePermissions
whether edge permissions need to be considered
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > myEdgeInfos
The container of edge information.
double(* Operation)(const E *const, const V *const, double)
Type of the function that is used to retrieve the edge effort.
Operation myOperation
The object's operation to perform.
double getTravelTime(const E *const e, const V *const v, const double t, const double effort) const
double getEffort(const E *const e, const V *const v, double t) const
void updateViaEdgeCost(const E *viaEdge, const V *const v, double &time, double &effort, double &length) const
bool myAmClean
whether we are already initialized
const bool myHaveRestrictions
whether edge restrictions need to be considered
void buildPathFrom(const typename SUMOAbstractRouter< E, V >::EdgeInfo *rbegin, std::vector< const E * > &edges)
Builds the path from marked edges.
void endQuery(int visits)
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFound
list of visited Edges (for resetting)
static long getCurrentMillis()
Returns the current time in milliseconds.
Definition SysUtils.cpp:44