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