Eclipse SUMO - Simulation of Urban MObility
SUMOAbstractRouter.h
Go to the documentation of this file.
1/****************************************************************************/
2// Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3// Copyright (C) 2006-2022 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/****************************************************************************/
20// An abstract router base class
21/****************************************************************************/
22#pragma once
23#include <config.h>
24
25#include <string>
26#include <vector>
27#include <algorithm>
28#include <iterator>
29#include <assert.h>
34//#define ROUTER_DEBUG_HINT
35//#define ROUTER_DEBUG_COND (true)
36
37
38// ===========================================================================
39// class definitions
40// ===========================================================================
45template<class E, class V>
47public:
53 class EdgeInfo {
54 public:
56 EdgeInfo(const E* const e)
57 : edge(e), effort(std::numeric_limits<double>::max()),
58 heuristicEffort(std::numeric_limits<double>::max()),
59 leaveTime(0.), prev(nullptr), visited(false), prohibited(false) {}
60
62 const E* const edge;
63
65 double effort;
66
68 // only used by A*
70
72 double leaveTime;
73
75 const EdgeInfo* prev;
76
78 bool visited;
79
82
83 inline void reset() {
84 effort = std::numeric_limits<double>::max();
85 heuristicEffort = std::numeric_limits<double>::max();
86 visited = false;
87 }
88
89 };
90
92 typedef double(* Operation)(const E* const, const V* const, double);
93
95 SUMOAbstractRouter(const std::string& type, bool unbuildIsWarning, Operation operation, Operation ttOperation,
96 const bool havePermissions, const bool haveRestrictions) :
97 myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
98 myOperation(operation), myTTOperation(ttOperation),
99 myBulkMode(false),
100 myAutoBulkMode(false),
101 myHavePermissions(havePermissions),
102 myHaveRestrictions(haveRestrictions),
103 myType(type),
104 myQueryVisits(0),
105 myNumQueries(0),
107 myQueryTimeSum(0) {
108 }
109
114 myBulkMode(false),
115 myAutoBulkMode(false),
118 myType(other->myType),
119 myQueryVisits(0),
120 myNumQueries(0),
122 myQueryTimeSum(0) { }
123
124
125
128 if (myNumQueries > 0) {
129 WRITE_MESSAGE(myType + " answered " + toString(myNumQueries) + " queries and explored " + toString((double)myQueryVisits / (double)myNumQueries) + " edges on average.");
130 WRITE_MESSAGE(myType + " spent " + elapsedMs2string(myQueryTimeSum) + " answering queries (" + toString((double)myQueryTimeSum / (double)myNumQueries) + "ms on average).");
131 }
132 }
133
134 virtual SUMOAbstractRouter* clone() = 0;
135
136 inline void init(const int edgeID, const SUMOTime msTime) {
137// if (!myAmClean) {
138 // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
139 for (auto& edgeInfo : myFrontierList) {
140 edgeInfo->reset();
141 }
142 myFrontierList.clear();
143 for (auto& edgeInfo : myFound) {
144 edgeInfo->reset();
145 }
146 myFound.clear();
147 if (edgeID > -1) {
148 // add begin node
149 auto& fromInfo = myEdgeInfos[edgeID];
150 fromInfo.effort = 0.;
151 fromInfo.heuristicEffort = 0.;
152 fromInfo.prev = nullptr;
153 fromInfo.leaveTime = STEPS2TIME(msTime);
154 myFrontierList.push_back(&fromInfo);
155 }
156 myAmClean = true;
157// }
158 }
159
161 virtual void reset(const V* const vehicle) {
162 UNUSED_PARAMETER(vehicle);
163 }
164
165 const std::string& getType() const {
166 return myType;
167 }
168
169 inline const typename SUMOAbstractRouter<E, V>::EdgeInfo& getEdgeInfo(int index) const {
170 return myEdgeInfos[index];
171 }
172
175 virtual bool compute(const E* from, const E* to, const V* const vehicle,
176 SUMOTime msTime, std::vector<const E*>& into, bool silent = false) = 0;
177
178
183 inline bool compute(
184 const E* from, double fromPos,
185 const E* to, double toPos,
186 const V* const vehicle,
187 SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
188 if (from != to || fromPos <= toPos) {
189 return compute(from, to, vehicle, msTime, into, silent);
190 } else {
191 return computeLooped(from, to, vehicle, msTime, into, silent);
192 }
193 }
194
195
198 inline bool computeLooped(const E* from, const E* to, const V* const vehicle,
199 SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
200 if (from != to) {
201 return compute(from, to, vehicle, msTime, into, silent);
202 }
203 double minEffort = std::numeric_limits<double>::max();
204 std::vector<const E*> best;
205 const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
206 for (const std::pair<const E*, const E*>& follower : from->getViaSuccessors(vClass)) {
207 std::vector<const E*> tmp;
208 compute(follower.first, to, vehicle, msTime, tmp, true);
209 if (tmp.size() > 0) {
210 double effort = recomputeCosts(tmp, vehicle, msTime);
211 if (effort < minEffort) {
212 minEffort = effort;
213 best = tmp;
214 }
215 }
216 }
217 if (minEffort != std::numeric_limits<double>::max()) {
218 into.push_back(from);
219 std::copy(best.begin(), best.end(), std::back_inserter(into));
220 return true;
221 } else if (!silent && myErrorMsgHandler != nullptr) {
222 myErrorMsgHandler->informf("No connection between edge '%' and edge '%' found.", from->getID(), to->getID());
223 }
224 return false;
225 }
226
227 inline bool isProhibited(const E* const edge, const V* const vehicle) const {
228 return (myHavePermissions && edge->prohibits(vehicle)) || (myHaveRestrictions && edge->restricts(vehicle));
229 }
230
231 inline double getTravelTime(const E* const e, const V* const v, const double t, const double effort) const {
232 return myTTOperation == nullptr ? effort : (*myTTOperation)(e, v, t);
233 }
234
235 inline void updateViaEdgeCost(const E* viaEdge, const V* const v, double& time, double& effort, double& length) const {
236 while (viaEdge != nullptr && viaEdge->isInternal()) {
237 const double viaEffortDelta = this->getEffort(viaEdge, v, time);
238 time += getTravelTime(viaEdge, v, time, viaEffortDelta);
239 effort += viaEffortDelta;
240 length += viaEdge->getLength();
241 viaEdge = viaEdge->getViaSuccessors().front().second;
242 }
243 }
244
245 inline void updateViaCost(const E* const prev, const E* const e, const V* const v, double& time, double& effort, double& length) const {
246 if (prev != nullptr) {
247 for (const std::pair<const E*, const E*>& follower : prev->getViaSuccessors()) {
248 if (follower.first == e) {
249 updateViaEdgeCost(follower.second, v, time, effort, length);
250 break;
251 }
252 }
253 }
254 const double effortDelta = this->getEffort(e, v, time);
255 effort += effortDelta;
256 time += getTravelTime(e, v, time, effortDelta);
257 length += e->getLength();
258 }
259
260
261 inline double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime, double* lengthp = nullptr) const {
262 double time = STEPS2TIME(msTime);
263 double effort = 0.;
264 double length = 0.;
265 if (lengthp == nullptr) {
266 lengthp = &length;
267 } else {
268 *lengthp = 0.;
269 }
270 const E* prev = nullptr;
271 for (const E* const e : edges) {
272 if (isProhibited(e, v)) {
273 return -1;
274 }
275 updateViaCost(prev, e, v, time, effort, *lengthp);
276 prev = e;
277 }
278 return effort;
279 }
280
281
282 inline double recomputeCosts(const std::vector<const E*>& edges, const V* const v, double fromPos, double toPos, SUMOTime msTime, double* lengthp = nullptr) const {
283 double effort = recomputeCosts(edges, v, msTime, lengthp);
284 if (!edges.empty()) {
285 double firstEffort = this->getEffort(edges.front(), v, STEPS2TIME(msTime));
286 double lastEffort = this->getEffort(edges.back(), v, STEPS2TIME(msTime));
287 effort -= firstEffort * fromPos / edges.front()->getLength();
288 effort -= lastEffort * (edges.back()->getLength() - toPos) / edges.back()->getLength();
289 }
290 return effort;
291 }
292
293
294 inline double setHint(const typename std::vector<const E*>::const_iterator routeBegin, const typename std::vector<const E*>::const_iterator routeEnd, const V* const v, SUMOTime msTime) {
295 double time = STEPS2TIME(msTime);
296 double effort = 0.;
297 double length = 0.;
298 const EdgeInfo* prev = &myEdgeInfos[(*routeBegin)->getNumericalID()];
299 init((*routeBegin)->getNumericalID(), msTime);
300 for (auto e = routeBegin + 1; e != routeEnd; ++e) {
301 if (isProhibited(*e, v)) {
302 return -1;
303 }
304 auto& edgeInfo = myEdgeInfos[(*e)->getNumericalID()];
305 edgeInfo.heuristicEffort = effort;
306 edgeInfo.prev = prev;
307 updateViaCost(prev->edge, *e, v, time, effort, length);
308 edgeInfo.effort = effort;
309 edgeInfo.leaveTime = time;
310 myFound.push_back(&edgeInfo);
311 prev = &edgeInfo;
312#ifdef ROUTER_DEBUG_HINT
313 if (ROUTER_DEBUG_COND) {
314 std::cout << "DEBUG: hit=" << (*e)->getID()
315 << " TT=" << edgeInfo.effort
316 << " EF=" << this->getEffort(*e, v, edgeInfo.leaveTime)
317 << " HT=" << edgeInfo.heuristicEffort << "\n";
318 }
319#endif
320 }
321 return effort;
322 }
323
324
325 inline double getEffort(const E* const e, const V* const v, double t) const {
326 return (*myOperation)(e, v, t);
327 }
328
329 inline void startQuery() {
330 myNumQueries++;
332 }
333
334 inline void endQuery(int visits) {
335 myQueryVisits += visits;
337 }
338
339 virtual void setBulkMode(const bool mode) {
340 myBulkMode = mode;
341 }
342
343 inline void setAutoBulkMode(const bool mode) {
344 myAutoBulkMode = mode;
345 }
346
347 virtual void prohibit(const std::vector<E*>& toProhibit) {
348 for (E* const edge : this->myProhibited) {
349 myEdgeInfos[edge->getNumericalID()].prohibited = false;
350 }
351 for (E* const edge : toProhibit) {
352 myEdgeInfos[edge->getNumericalID()].prohibited = true;
353 }
354 this->myProhibited = toProhibit;
355 }
356
357
359 void buildPathFrom(const typename SUMOAbstractRouter<E, V>::EdgeInfo* rbegin, std::vector<const E*>& edges) {
360 std::vector<const E*> tmp;
361 while (rbegin != nullptr) {
362 tmp.push_back(rbegin->edge);
363 rbegin = rbegin->prev;
364 }
365 std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
366 }
367
368protected:
371
374
377
380
383
386
389
392
394 std::vector<E*> myProhibited;
395
397 std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo> myEdgeInfos;
398
400 std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFrontierList;
402 std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFound;
403
404private:
406 const std::string myType;
407
409 long long int myQueryVisits;
410 long long int myNumQueries;
412 long long int myQueryStartTime;
413 long long int myQueryTimeSum;
414
415private:
418};
long long int SUMOTime
Definition: GUI.h:36
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:267
std::string elapsedMs2string(long long int t)
convert ms to string for log output
Definition: SUMOTime.cpp:110
#define STEPS2TIME(x)
Definition: SUMOTime.h:54
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
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:46
void informf(const std::string &format, T value, Targs... Fargs)
adds a new formatted message
Definition: MsgHandler.h:120
bool visited
whether the edge was already evaluated
EdgeInfo(const E *const e)
Constructor.
const E *const edge
The current edge.
double leaveTime
The time the vehicle leaves the edge.
double effort
Effort to reach the edge.
bool prohibited
whether the edge is currently not allowed
const EdgeInfo * prev
The previous edge.
double heuristicEffort
Estimated effort to reach the edge (effort + lower bound on remaining effort)
Operation myTTOperation
The object's operation to perform for travel times.
long long int myNumQueries
MsgHandler *const myErrorMsgHandler
the handler for routing errors
std::vector< E * > myProhibited
The list of explicitly prohibited edges.
bool isProhibited(const E *const edge, const V *const vehicle) const
const bool myHavePermissions
whether edge permissions need to be considered
bool myBulkMode
whether we are currently operating several route queries in a bulk
long long int myQueryVisits
counters for performance logging
bool computeLooped(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 effort at the given time if from == to,...
virtual SUMOAbstractRouter * clone()=0
double recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime, double *lengthp=nullptr) const
long long int myQueryStartTime
the time spent querying in milliseconds
virtual void setBulkMode(const bool mode)
SUMOAbstractRouter & operator=(const SUMOAbstractRouter &s)=delete
Invalidated assignment operator.
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > myEdgeInfos
The container of edge information.
bool compute(const E *from, double fromPos, const E *to, double toPos, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false)
Builds the route between the given edges using the minimum effort at the given time,...
SUMOAbstractRouter(SUMOAbstractRouter *other)
Copy Constructor.
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
virtual void prohibit(const std::vector< E * > &toProhibit)
long long int myQueryTimeSum
void updateViaCost(const E *const prev, const E *const e, const V *const v, double &time, double &effort, double &length) const
virtual void reset(const V *const vehicle)
reset internal caches, used by CHRouter
const std::string & getType() const
double getEffort(const E *const e, const V *const v, double t) const
SUMOAbstractRouter(const std::string &type, bool unbuildIsWarning, Operation operation, Operation ttOperation, const bool havePermissions, const bool haveRestrictions)
Constructor.
void updateViaEdgeCost(const E *viaEdge, const V *const v, double &time, double &effort, double &length) const
double setHint(const typename std::vector< const E * >::const_iterator routeBegin, const typename std::vector< const E * >::const_iterator routeEnd, const V *const v, SUMOTime msTime)
void init(const int edgeID, const SUMOTime msTime)
double recomputeCosts(const std::vector< const E * > &edges, const V *const v, double fromPos, double toPos, SUMOTime msTime, double *lengthp=nullptr) const
void setAutoBulkMode(const bool mode)
bool myAmClean
whether we are already initialized
const bool myHaveRestrictions
whether edge restrictions need to be considered
const SUMOAbstractRouter< E, V >::EdgeInfo & getEdgeInfo(int index) const
void buildPathFrom(const typename SUMOAbstractRouter< E, V >::EdgeInfo *rbegin, std::vector< const E * > &edges)
Builds the path from marked edges.
bool myAutoBulkMode
whether we are currently trying to detect bulk mode automatically
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...
void endQuery(int visits)
virtual ~SUMOAbstractRouter()
Destructor.
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)
const std::string myType
the type of this router
static long getCurrentMillis()
Returns the current time in milliseconds.
Definition: SysUtils.cpp:47
Definition: json.hpp:4471