25#include <unordered_set>
46template<
class E,
class N,
class V,
class M>
56 return &(this->
myEdgeInfos[edge->getNumericalID()]);
63 return &(this->
myEdgeInfos[edge->getNumericalID()]);
75 const std::shared_ptr<const LookupTable> lookup =
nullptr,
76 const bool havePermissions =
false,
const bool haveRestrictions =
false) :
77 AStarRouter<E, V,
M>(edges, unbuildIsWarning, operation, lookup, havePermissions, haveRestrictions) {
89 const bool havePermissions =
false,
const bool haveRestrictions =
false) :
90 AStarRouter<E, V,
M>(edgeInfos, unbuildIsWarning, operation, lookup, havePermissions, haveRestrictions) {
95 WRITE_MESSAGE(
"The following stats for AStarRouter (which might also be empty) belong to Node2EdgeRouter, a derived class:");
107 virtual void reset(
const V*
const vehicle) {
126 bool computeNode2Edges(
const N* fromNode,
const std::unordered_set<const E*>& toEdges,
const V*
const vehicle,
127 SUMOTime msTime,
bool silent =
false) {
128 assert(fromNode !=
nullptr);
131 bool allVisited =
true;
132 for (
const E* from : fromNode->getOutgoing()) {
133 if (from->isInternal()) {
148 const std::vector<const E*>& fromEdges = fromNode->getOutgoing();
150 if (fromEdges.empty() || toEdges.empty()) {
156#ifdef ASTAR_DEBUG_QUERY
157 if (ASTAR_DEBUG_COND) {
158 std::cout <<
"DEBUG: starting search for '" <<
Named::getIDSecure(vehicle) <<
"' speed: " <<
MIN2(vehicle->getMaxSpeed(),
myMaxSpeed * vehicle->getChosenSpeedFactor()) <<
" time: " <<
STEPS2TIME(msTime) <<
"\n";
163 init(fromEdges, vehicle, msTime);
171 const E*
const minEdge = minimumInfo->edge;
173 if (toEdges.count(minEdge)) {
174 for (
const E* to : toEdges) {
175 const auto& toInfo = this->
myEdgeInfos[to->getNumericalID()];
176 if (!toInfo.visited) {
186 std::pop_heap(this->
myFrontierList.begin(), this->myFrontierList.end(), this->myComparator);
188 this->
myFound.push_back(minimumInfo);
189 minimumInfo->visited =
true;
190 const double effortDelta = this->
getEffort(minEdge, vehicle, minimumInfo->leaveTime);
191 const double leaveTime = minimumInfo->leaveTime + this->
getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
193 const double heuristic_remaining = 0;
197 const double heuristicEffort = minimumInfo->effort + effortDelta + heuristic_remaining;
199 for (
const std::pair<const E*, const E*>& follower : minEdge->getViaSuccessors(vClass)) {
200 auto& followerInfo = this->
myEdgeInfos[follower.first->getNumericalID()];
202 if (followerInfo.prohibited || this->isProhibited(follower.first, vehicle)) {
205 double effort = minimumInfo->effort + effortDelta;
206 double time = leaveTime;
208 const double oldEffort = followerInfo.effort;
209 if ((!followerInfo.visited) && effort < oldEffort) {
210 followerInfo.effort = effort;
213 followerInfo.heuristicEffort =
MAX2(
MIN2(heuristicEffort, followerInfo.heuristicEffort), effort);
214 followerInfo.leaveTime = time;
215 followerInfo.prev = minimumInfo;
216 if (oldEffort == std::numeric_limits<double>::max()) {
218 std::push_heap(this->
myFrontierList.begin(), this->myFrontierList.end(), this->myComparator);
220 auto fi = std::find(this->
myFrontierList.begin(), this->myFrontierList.end(), &followerInfo);
222 std::push_heap(this->
myFrontierList.begin(), fi + 1, this->myComparator);
228 for (
const E* to : toEdges) {
229 const auto& toInfo = this->
myEdgeInfos[to->getNumericalID()];
230 if (toInfo.visited) {
232 this->
myErrorMsgHandler->
informf(
"Only some connections between node '%' and the given edges were found.", fromNode->getID());
238 this->
myErrorMsgHandler->
informf(
"No connections between node '%' and the given edges were found.", fromNode->getID());
252 SUMOTime msTime, std::vector<const E*>& into,
bool silent =
false) {
253 assert(fromNode !=
nullptr && to !=
nullptr);
256 for (
const E* from : fromNode->getOutgoing()) {
257 if (from->isInternal()) {
272 const std::vector<const E*>& fromEdges = fromNode->getOutgoing();
274 if (fromEdges.empty()) {
287 init(fromEdges, vehicle, msTime);
292 const double speed = vehicle ==
nullptr ? this->
myMaxSpeed :
MIN2(vehicle->getMaxSpeed(), this->myMaxSpeed * vehicle->getChosenSpeedFactor());
297 const E*
const minEdge = minimumInfo->edge;
304 std::pop_heap(this->
myFrontierList.begin(), this->myFrontierList.end(), this->myComparator);
306 this->
myFound.push_back(minimumInfo);
307 minimumInfo->visited =
true;
308 const double effortDelta = this->
getEffort(minEdge, vehicle, minimumInfo->leaveTime);
309 const double leaveTime = minimumInfo->leaveTime + this->
getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
313 const double heuristic_remaining = (this->
myLookupTable ==
nullptr ? minEdge->getDistanceTo(to) / speed :
314 this->
myLookupTable->lowerBound(minEdge, to, speed, vehicle->getChosenSpeedFactor(),
315 minEdge->getMinimumTravelTime(
nullptr), to->getMinimumTravelTime(
nullptr)));
320 const double heuristicEffort = minimumInfo->effort + effortDelta + heuristic_remaining;
322 for (
const std::pair<const E*, const E*>& follower : minEdge->getViaSuccessors(vClass)) {
323 auto& followerInfo = this->
myEdgeInfos[follower.first->getNumericalID()];
325 if (followerInfo.prohibited || this->isProhibited(follower.first, vehicle)) {
328 double effort = minimumInfo->effort + effortDelta;
329 double time = leaveTime;
331 const double oldEffort = followerInfo.effort;
332 if ((!followerInfo.visited || mayRevisit) && effort < oldEffort) {
333 followerInfo.effort = effort;
336 followerInfo.heuristicEffort =
MAX2(
MIN2(heuristicEffort, followerInfo.heuristicEffort), effort);
337 followerInfo.leaveTime = time;
338 followerInfo.prev = minimumInfo;
339 if (oldEffort == std::numeric_limits<double>::max()) {
341 std::push_heap(this->
myFrontierList.begin(), this->myFrontierList.end(), this->myComparator);
343 auto fi = std::find(this->
myFrontierList.begin(), this->myFrontierList.end(), &followerInfo);
347 std::push_heap(this->
myFrontierList.begin(), this->myFrontierList.end(), this->myComparator);
349 std::push_heap(this->
myFrontierList.begin(), fi + 1, this->myComparator);
357 this->
myErrorMsgHandler->
informf(
"No connection between node '%' and edge '%' found.", fromNode->getID(), to->getID());
370 void updateViaCostUpToEdge(
const E*
const prev,
const E*
const e,
const V*
const v,
double& time,
double& effort,
double& length)
const;
379 const E* lastEdge = edges.back();
383 if (lengthp ==
nullptr) {
388 const E* prev =
nullptr;
389 for (
const E*
const e : edges) {
406 throw std::runtime_error(
"Bulk mode is not supported by the node-to-edge router.");
415 void init(std::vector<const E*> fromEdges,
const V*
const vehicle,
const SUMOTime msTime);
422template<
class E,
class N,
class V,
class M>
425 for (
const std::pair<const E*, const E*>& follower : prev->getViaSuccessors()) {
426 if (follower.first == e) {
427 updateViaEdgeCost(follower.second, v, time, effort, length);
433template<
class E,
class N,
class V,
class M>
436 for (
auto& edgeInfo : this->myFrontierList) {
439 this->myFrontierList.clear();
440 for (
auto& edgeInfo : this->myFound) {
443 this->myFound.clear();
444 for (
const E* from : fromEdges) {
445 if (from->isInternal()) {
448 int edgeID = from->getNumericalID();
449 auto& fromInfo = this->myEdgeInfos[edgeID];
450 if (fromInfo.prohibited || this->isProhibited(from, vehicle)) {
453 fromInfo.effort = 0.;
454 fromInfo.heuristicEffort = 0.;
455 fromInfo.prev =
nullptr;
457 this->myFrontierList.push_back(&fromInfo);
#define WRITE_MESSAGE(msg)
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types.
@ SVC_IGNORING
vehicles ignoring classes
#define UNUSED_PARAMETER(x)
Computes the shortest path through a network using the A* algorithm.
const std::shared_ptr< const LookupTable > myLookupTable
the lookup table for travel time heuristics
double myMaxSpeed
maximum speed in the network
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
static std::string getIDSecure(const T *obj, const std::string &fallBack="NULL")
get an identifier for Named-like object which may be Null
void init(std::vector< const E * > fromEdges, const V *const vehicle, const SUMOTime msTime)
Initialize the node-to-edge router.
double recomputeCostsNoLastEdge(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime, double *lengthp=nullptr) const
Returns the recomputed cost for traversing the given edges, excluding the last one.
void updateViaCostUpToEdge(const E *const prev, const E *const e, const V *const v, double &time, double &effort, double &length) const
Updates the via cost up to a given edge.
Node2EdgeRouter(const std::vector< E * > &edges, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation operation, const std::shared_ptr< const LookupTable > lookup=nullptr, const bool havePermissions=false, const bool haveRestrictions=false)
Constructor.
SUMOAbstractRouter< E, V >::EdgeInfo * edgeInfo(const E *const edge)
Returns the edge information for the passed edge.
bool computeNode2Edge(const N *fromNode, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false)
Builds the route between the given node and edge using the minimum travel time.
virtual ~Node2EdgeRouter()
Destructor.
Node2EdgeRouter(const std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > &edgeInfos, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation operation, const std::shared_ptr< const LookupTable > lookup=nullptr, const bool havePermissions=false, const bool haveRestrictions=false)
Cloning constructor.
virtual void setBulkMode(const bool mode)
Bulk mode is not supported.
const SUMOAbstractRouter< E, V >::EdgeInfo * edgeInfo(const E *const edge) const
Returns the edge information for the passed edge.
bool computeNode2Edges(const N *fromNode, const std::unordered_set< const E * > &toEdges, const V *const vehicle, SUMOTime msTime, bool silent=false)
Builds the routes between the given node and all given edges using the minimum travel time.
virtual void reset(const V *const vehicle)
Reset method.
virtual SUMOAbstractRouter< E, V > * clone()
Cloning method.
AbstractLookupTable< E, V > LookupTable
MsgHandler *const myErrorMsgHandler
the handler for routing errors
bool isProhibited(const E *const edge, const V *const vehicle) const
const bool myHavePermissions
whether edge permissions need to be considered
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > myEdgeInfos
The container of edge information.
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
void updateViaCost(const E *const prev, const E *const e, const V *const v, double &time, double &effort, double &length) 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)