Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2006-2026 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 : /****************************************************************************/
14 : /// @file SUMOAbstractRouter.h
15 : /// @author Daniel Krajzewicz
16 : /// @author Michael Behrisch
17 : /// @author Jakob Erdmann
18 : /// @date 25.Jan 2006
19 : ///
20 : // An abstract router base class
21 : /****************************************************************************/
22 : #pragma once
23 : #include <config.h>
24 :
25 : #include <iostream>
26 : #include <string>
27 : #include <vector>
28 : #include <algorithm>
29 : #include <iterator>
30 : #include <assert.h>
31 : #include <utils/common/SysUtils.h>
32 : #include <utils/common/MsgHandler.h>
33 : #include <utils/common/SUMOTime.h>
34 : #include <utils/common/ToString.h>
35 :
36 : //#define ROUTER_DEBUG_HINT
37 : //#define ROUTER_DEBUG_COND (true)
38 :
39 :
40 : // ===========================================================================
41 : // class definitions
42 : // ===========================================================================
43 :
44 : /// Prohibitions and their estimated end time
45 2443439 : struct RouterProhibition {
46 : double begin = 0;
47 : double end = std::numeric_limits<double>::max();
48 : SVCPermissions permissions = SVC_IGNORING;
49 : };
50 :
51 : /**
52 : * @class SUMOAbstractRouter
53 : * The interface for routing the vehicles over the network.
54 : */
55 : template<class E, class V>
56 : class SUMOAbstractRouter {
57 : public:
58 : /**
59 : * @class EdgeInfo
60 : * A definition about a route's edge with the effort needed to reach it and
61 : * the information about the previous edge.
62 : */
63 : class EdgeInfo {
64 : public:
65 : /// Constructor
66 21946327 : EdgeInfo(const E* const e)
67 21946327 : : edge(e), effort(std::numeric_limits<double>::max()),
68 21946327 : heuristicEffort(std::numeric_limits<double>::max()),
69 21946327 : leaveTime(0.), prev(nullptr), visited(false), prohibitedPermissions(SVCAll), prohibitionBegin(-1), prohibitionEnd(-1) {}
70 :
71 : /// The current edge
72 : const E* const edge;
73 :
74 : /// Effort to reach the edge
75 : double effort;
76 :
77 : /// Estimated effort to reach the edge (effort + lower bound on remaining effort)
78 : // only used by A*
79 : double heuristicEffort;
80 :
81 : /// The time the vehicle leaves the edge
82 : double leaveTime;
83 :
84 : /// The previous edge
85 : const EdgeInfo* prev;
86 :
87 : /// whether the edge was already evaluated
88 : bool visited;
89 :
90 : /// temporary permission change
91 : SVCPermissions prohibitedPermissions;
92 :
93 : /// the time at which a temporary prohibition begins
94 : double prohibitionBegin;
95 :
96 : /// the time at which a temporary prohibition ends
97 : double prohibitionEnd;
98 :
99 : inline void reset() {
100 87900224 : effort = std::numeric_limits<double>::max();
101 87900224 : heuristicEffort = std::numeric_limits<double>::max();
102 2991030 : visited = false;
103 : }
104 :
105 : };
106 :
107 : /// Type of the function that is used to retrieve the edge effort.
108 : typedef double(* Operation)(const E* const, const V* const, double);
109 :
110 : typedef std::map<const E*, RouterProhibition> Prohibitions;
111 :
112 : /// Constructor
113 67561 : SUMOAbstractRouter(const std::string& type, bool unbuildIsWarning, Operation operation, Operation ttOperation,
114 : const bool havePermissions, const bool haveRestrictions) :
115 67561 : myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
116 67561 : myOperation(operation), myTTOperation(ttOperation),
117 67561 : myBulkMode(false),
118 67561 : myAutoBulkMode(false),
119 67561 : myAmClean(true),
120 67561 : myHavePermissions(havePermissions),
121 67561 : myHaveRestrictions(haveRestrictions),
122 67561 : myType(type),
123 67561 : myQueryVisits(0),
124 67561 : myNumQueries(0),
125 67561 : myQueryStartTime(0),
126 67561 : myQueryTimeSum(0) {
127 67561 : }
128 :
129 : /// Copy Constructor
130 516 : SUMOAbstractRouter(SUMOAbstractRouter* other) :
131 516 : myErrorMsgHandler(other->myErrorMsgHandler),
132 516 : myOperation(other->myOperation), myTTOperation(other->myTTOperation),
133 516 : myBulkMode(false),
134 516 : myAutoBulkMode(false),
135 516 : myAmClean(true),
136 516 : myHavePermissions(other->myHavePermissions),
137 516 : myHaveRestrictions(other->myHaveRestrictions),
138 516 : myType(other->myType),
139 516 : myQueryVisits(0),
140 516 : myNumQueries(0),
141 516 : myQueryStartTime(0),
142 1032 : myQueryTimeSum(0) { }
143 :
144 :
145 :
146 : /// Destructor
147 68072 : virtual ~SUMOAbstractRouter() {
148 68072 : if (myNumQueries > 0) {
149 84684 : WRITE_MESSAGE(myType + " answered " + toString(myNumQueries) + " queries and explored " + toString((double)myQueryVisits / (double)myNumQueries) + " edges on average.");
150 84684 : WRITE_MESSAGE(myType + " spent " + elapsedMs2string(myQueryTimeSum) + " answering queries (" + toString((double)myQueryTimeSum / (double)myNumQueries) + "ms on average).");
151 : }
152 89243 : }
153 :
154 : virtual SUMOAbstractRouter* clone() = 0;
155 :
156 4178341 : inline void init(const int edgeID, const SUMOTime msTime) {
157 : // if (!myAmClean) {
158 : // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
159 18317115 : for (auto& edgeInfo : myFrontierList) {
160 14138774 : edgeInfo->reset();
161 : }
162 : myFrontierList.clear();
163 74958851 : for (auto& edgeInfo : myFound) {
164 70780510 : edgeInfo->reset();
165 : }
166 : myFound.clear();
167 4178341 : if (edgeID > -1) {
168 : // add begin node
169 4178341 : auto& fromInfo = myEdgeInfos[edgeID];
170 4178341 : fromInfo.effort = 0.;
171 4178341 : fromInfo.heuristicEffort = 0.;
172 4178341 : fromInfo.prev = nullptr;
173 4178341 : fromInfo.leaveTime = STEPS2TIME(msTime);
174 4178341 : myFrontierList.push_back(&fromInfo);
175 : }
176 4178341 : myAmClean = true;
177 : // }
178 4178341 : }
179 :
180 : /// reset internal caches, used by CHRouter
181 4312 : virtual void reset(const V* const vehicle) {
182 : UNUSED_PARAMETER(vehicle);
183 4312 : }
184 :
185 269390 : virtual void setMsgHandler(MsgHandler* const errorMsgHandler) {
186 274117 : myErrorMsgHandler = errorMsgHandler;
187 269390 : }
188 :
189 : const std::string& getType() const {
190 : return myType;
191 : }
192 :
193 : inline const typename SUMOAbstractRouter<E, V>::EdgeInfo& getEdgeInfo(int index) const {
194 56 : return myEdgeInfos[index];
195 : }
196 :
197 : /** @brief Builds the route between the given edges using the minimum effort at the given time
198 : The definition of the effort depends on the wished routing scheme */
199 : virtual bool compute(const E* from, const E* to, const V* const vehicle,
200 : SUMOTime msTime, std::vector<const E*>& into, bool silent = false) = 0;
201 :
202 :
203 : /** @brief Builds the route between the given edges using the minimum effort at the given time,
204 : * also taking into account position along the edges to ensure currect
205 : * handling of looped routes
206 : * The definition of the effort depends on the wished routing scheme */
207 2989979 : inline bool compute(
208 : const E* from, double fromPos,
209 : const E* to, double toPos,
210 : const V* const vehicle,
211 : SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
212 2989979 : if (from != to || fromPos <= toPos) {
213 2981819 : return compute(from, to, vehicle, msTime, into, silent);
214 : } else {
215 8160 : return computeLooped(from, to, vehicle, msTime, into, silent);
216 : }
217 : }
218 :
219 :
220 : /** @brief Builds the route between the given edges using the minimum effort at the given time
221 : * if from == to, return the shortest looped route */
222 8650 : inline bool computeLooped(const E* from, const E* to, const V* const vehicle,
223 : SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
224 8650 : if (from != to) {
225 0 : return compute(from, to, vehicle, msTime, into, silent);
226 : }
227 : double minEffort = std::numeric_limits<double>::max();
228 0 : std::vector<const E*> best;
229 8650 : const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
230 29440 : for (const std::pair<const E*, const E*>& follower : from->getViaSuccessors(vClass)) {
231 0 : std::vector<const E*> tmp;
232 10395 : compute(follower.first, to, vehicle, msTime, tmp, true);
233 10395 : if (tmp.size() > 0) {
234 9802 : double effort = recomputeCosts(tmp, vehicle, msTime);
235 9802 : if (effort < minEffort) {
236 : minEffort = effort;
237 9378 : best = tmp;
238 : }
239 : }
240 : }
241 8650 : if (minEffort != std::numeric_limits<double>::max()) {
242 8103 : into.push_back(from);
243 : std::copy(best.begin(), best.end(), std::back_inserter(into));
244 : return true;
245 547 : } else if (!silent && myErrorMsgHandler != nullptr) {
246 144 : myErrorMsgHandler->informf(TL("No connection between edge '%' and edge '%' found."), from->getID(), to->getID());
247 : }
248 : return false;
249 8650 : }
250 :
251 180425799 : inline bool isProhibited(const E* const edge, const V* const vehicle, double t) const {
252 : return (myProhibited.size() > 0
253 20897312 : && (myEdgeInfos[edge->getNumericalID()].prohibitedPermissions & vehicle->getVClass()) != vehicle->getVClass()
254 837579 : && myEdgeInfos[edge->getNumericalID()].prohibitionBegin <= t
255 837574 : && myEdgeInfos[edge->getNumericalID()].prohibitionEnd == std::numeric_limits<double>::max())
256 200497735 : || (myHavePermissions && edge->prohibits(vehicle)) || (myHaveRestrictions && edge->restricts(vehicle));
257 : }
258 :
259 : inline double getTravelTime(const E* const e, const V* const v, const double t, const double effort) const {
260 71685511 : return myTTOperation == nullptr ? effort : (*myTTOperation)(e, v, t);
261 : }
262 :
263 188005582 : inline void updateViaEdgeCost(const E* viaEdge, const V* const v, double& time, double& effort, double& length) const {
264 315346847 : while (viaEdge != nullptr && viaEdge->isInternal()) {
265 127341265 : const double viaEffortDelta = this->getEffort(viaEdge, v, time);
266 127341265 : time += getTravelTime(viaEdge, v, time, viaEffortDelta);
267 127341265 : effort += viaEffortDelta;
268 127341265 : length += viaEdge->getLength();
269 127341265 : viaEdge = viaEdge->getViaSuccessors().front().second;
270 : }
271 188005582 : }
272 :
273 29253869 : inline void updateViaCost(const E* const prev, const E* const e, const V* const v, double& time, double& effort, double& length) const {
274 29253869 : if (prev != nullptr) {
275 35971063 : for (const std::pair<const E*, const E*>& follower : prev->getViaSuccessors()) {
276 35966228 : if (follower.first == e) {
277 22426637 : updateViaEdgeCost(follower.second, v, time, effort, length);
278 : break;
279 : }
280 : }
281 : }
282 29253869 : const double effortDelta = this->getEffort(e, v, time);
283 29253869 : effort += effortDelta;
284 29253869 : time += getTravelTime(e, v, time, effortDelta);
285 29253869 : length += e->getLength();
286 29253869 : }
287 :
288 : bool isValid(const std::vector<const E*>& edges, const V* const v, double t) const {
289 2889525 : for (const E* const e : edges) {
290 2447410 : if (isProhibited(e, v, t)) {
291 : return false;
292 : }
293 : }
294 : return true;
295 : }
296 :
297 6649158 : virtual double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime, double* lengthp = nullptr) const {
298 6649158 : double time = STEPS2TIME(msTime);
299 6649158 : double effort = 0.;
300 6649158 : double length = 0.;
301 6649158 : if (lengthp == nullptr) {
302 : lengthp = &length;
303 : } else {
304 6047 : *lengthp = 0.;
305 : }
306 : const E* prev = nullptr;
307 34220080 : for (const E* const e : edges) {
308 27570922 : updateViaCost(prev, e, v, time, effort, *lengthp);
309 : prev = e;
310 : }
311 6649158 : return effort;
312 : }
313 :
314 :
315 2881428 : inline double recomputeCostsPos(const std::vector<const E*>& edges, const V* const v, double fromPos, double toPos, SUMOTime msTime, double* lengthp = nullptr) const {
316 2881428 : double effort = recomputeCosts(edges, v, msTime, lengthp);
317 2881428 : if (!edges.empty()) {
318 2881428 : const E* first = edges.front();
319 2881428 : if (first->getLength() == 0) {
320 465926 : if (edges.size() > 1 && edges[1]->getLength() > 0) {
321 : first = edges[1];
322 : } else {
323 : return effort;
324 : }
325 : }
326 2881428 : const E* last = edges.back();
327 2881428 : if (last->getLength() == 0) {
328 465968 : if (edges.size() > 1 && edges[edges.size() - 2]->getLength() > 0) {
329 : last = edges[edges.size() - 2];
330 : } else {
331 : return effort;
332 : }
333 : }
334 : assert(first->getLength() > 0);
335 : assert(last->getLength() > 0);
336 2881428 : double firstEffort = this->getEffort(first, v, STEPS2TIME(msTime));
337 2881428 : double lastEffort = this->getEffort(last, v, STEPS2TIME(msTime));
338 2881428 : effort -= firstEffort * fromPos / first->getLength();
339 2881428 : effort -= lastEffort * (last->getLength() - toPos) / last->getLength();
340 2881428 : if (lengthp != nullptr) {
341 6047 : (*lengthp) -= fromPos + last->getLength() - toPos;
342 : }
343 : }
344 : return effort;
345 : }
346 :
347 :
348 : 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) {
349 : double time = STEPS2TIME(msTime);
350 : double effort = 0.;
351 : double length = 0.;
352 : const EdgeInfo* prev = &myEdgeInfos[(*routeBegin)->getNumericalID()];
353 : init((*routeBegin)->getNumericalID(), msTime);
354 : for (auto e = routeBegin + 1; e != routeEnd; ++e) {
355 : if (isProhibited(*e, v)) {
356 : return -1;
357 : }
358 : auto& edgeInfo = myEdgeInfos[(*e)->getNumericalID()];
359 : edgeInfo.heuristicEffort = effort;
360 : edgeInfo.prev = prev;
361 : updateViaCost(prev->edge, *e, v, time, effort, length);
362 : edgeInfo.effort = effort;
363 : edgeInfo.leaveTime = time;
364 : myFound.push_back(&edgeInfo);
365 : prev = &edgeInfo;
366 : #ifdef ROUTER_DEBUG_HINT
367 : if (ROUTER_DEBUG_COND) {
368 : std::cout << "DEBUG: hit=" << (*e)->getID()
369 : << " TT=" << edgeInfo.effort
370 : << " EF=" << this->getEffort(*e, v, edgeInfo.leaveTime)
371 : << " HT=" << edgeInfo.heuristicEffort << "\n";
372 : }
373 : #endif
374 : }
375 : return effort;
376 : }
377 :
378 :
379 237770718 : inline double getEffort(const E* const e, const V* const v, double t) const {
380 13901547 : if (this->myProhibited.size() > 0 && myEdgeInfos.size() > 0
381 13901232 : && myEdgeInfos[e->getNumericalID()].prohibitionEnd > t
382 1965 : && myEdgeInfos[e->getNumericalID()].prohibitionBegin <= t
383 237772684 : && (myEdgeInfos[e->getNumericalID()].prohibitedPermissions & v->getVClass()) != v->getVClass()) {
384 : // pass edge after prohibition ends
385 1911 : return (myEdgeInfos[e->getNumericalID()].prohibitionEnd - t) + (*myOperation)(e, v, myEdgeInfos[e->getNumericalID()].prohibitionEnd);
386 : } else {
387 237768807 : return (*myOperation)(e, v, t);
388 : }
389 : }
390 :
391 : inline void startQuery() {
392 4321019 : myNumQueries++;
393 4321019 : myQueryStartTime = SysUtils::getCurrentMillis();
394 : }
395 :
396 : inline void endQuery(int visits) {
397 4320853 : myQueryVisits += visits;
398 4321019 : myQueryTimeSum += (SysUtils::getCurrentMillis() - myQueryStartTime);
399 : }
400 :
401 83127 : virtual void setBulkMode(const bool mode) {
402 84039 : myBulkMode = mode;
403 83127 : }
404 :
405 : inline void setAutoBulkMode(const bool mode) {
406 4722 : myAutoBulkMode = mode;
407 4 : }
408 :
409 1773832 : virtual void prohibit(const Prohibitions& toProhibit) {
410 3397554 : for (auto item : this->myProhibited) {
411 1623722 : myEdgeInfos[item.first->getNumericalID()].prohibitedPermissions = SVCAll;
412 1623722 : myEdgeInfos[item.first->getNumericalID()].prohibitionBegin = -1;
413 1623722 : myEdgeInfos[item.first->getNumericalID()].prohibitionEnd = -1;
414 : }
415 3403129 : for (auto item : toProhibit) {
416 1629297 : myEdgeInfos[item.first->getNumericalID()].prohibitionBegin = item.second.begin;
417 1629297 : myEdgeInfos[item.first->getNumericalID()].prohibitionEnd = item.second.end;
418 1629297 : myEdgeInfos[item.first->getNumericalID()].prohibitedPermissions = item.second.permissions;
419 : //std::cout << item.first->getID() << " " << item.second.begin << " " << item.second.end << " (" << getVehicleClassNames(item.second.permissions) << ")\n";
420 : }
421 : this->myProhibited = toProhibit;
422 1773832 : }
423 :
424 : bool hasProhibitions() const {
425 : return this->myProhibited.size() > 0;
426 : }
427 :
428 20 : virtual bool supportsProhibitions() const {
429 20 : return true;
430 : }
431 :
432 : /// Builds the path from marked edges
433 4191666 : void buildPathFrom(const typename SUMOAbstractRouter<E, V>::EdgeInfo* rbegin, std::vector<const E*>& edges) {
434 289852 : std::vector<const E*> tmp;
435 22629557 : while (rbegin != nullptr) {
436 18437891 : tmp.push_back(rbegin->edge);
437 18437891 : rbegin = rbegin->prev;
438 : }
439 : std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
440 4191666 : }
441 :
442 : protected:
443 : /// @brief the handler for routing errors
444 : MsgHandler* myErrorMsgHandler;
445 :
446 : /// @brief The object's operation to perform.
447 : Operation myOperation;
448 :
449 : /// @brief The object's operation to perform for travel times
450 : Operation myTTOperation;
451 :
452 : /// @brief whether we are currently operating several route queries in a bulk
453 : bool myBulkMode;
454 :
455 : /// @brief whether we are currently trying to detect bulk mode automatically
456 : bool myAutoBulkMode;
457 :
458 : /// @brief whether we are already initialized
459 : bool myAmClean;
460 :
461 : /// @brief whether edge permissions need to be considered
462 : const bool myHavePermissions;
463 :
464 : /// @brief whether edge restrictions need to be considered
465 : const bool myHaveRestrictions;
466 :
467 : /// The list of explicitly prohibited edges and estimated end time of prohibition
468 : Prohibitions myProhibited;
469 :
470 : /// The container of edge information
471 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo> myEdgeInfos;
472 :
473 : /// A container for reusage of the min edge heap
474 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFrontierList;
475 : /// @brief list of visited Edges (for resetting)
476 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFound;
477 :
478 : private:
479 : /// @brief the type of this router
480 : const std::string myType;
481 :
482 : /// @brief counters for performance logging
483 : long long int myQueryVisits;
484 : long long int myNumQueries;
485 : /// @brief the time spent querying in milliseconds
486 : long long int myQueryStartTime;
487 : long long int myQueryTimeSum;
488 :
489 : private:
490 : /// @brief Invalidated assignment operator
491 : SUMOAbstractRouter& operator=(const SUMOAbstractRouter& s) = delete;
492 : };
|
