Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2006-2025 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 : //#define ROUTER_DEBUG_HINT
35 : //#define ROUTER_DEBUG_COND (true)
36 :
37 :
38 : // ===========================================================================
39 : // class definitions
40 : // ===========================================================================
41 : /**
42 : * @class SUMOAbstractRouter
43 : * The interface for routing the vehicles over the network.
44 : */
45 : template<class E, class V>
46 : class SUMOAbstractRouter {
47 : public:
48 : /**
49 : * @class EdgeInfo
50 : * A definition about a route's edge with the effort needed to reach it and
51 : * the information about the previous edge.
52 : */
53 : class EdgeInfo {
54 : public:
55 : /// Constructor
56 6765352 : EdgeInfo(const E* const e)
57 6765352 : : edge(e), effort(std::numeric_limits<double>::max()),
58 6765352 : heuristicEffort(std::numeric_limits<double>::max()),
59 6765352 : leaveTime(0.), prev(nullptr), visited(false), prohibited(false), prohibitionEnd(0) {}
60 :
61 : /// The current edge
62 : const E* const edge;
63 :
64 : /// Effort to reach the edge
65 : double effort;
66 :
67 : /// Estimated effort to reach the edge (effort + lower bound on remaining effort)
68 : // only used by A*
69 : double heuristicEffort;
70 :
71 : /// The time the vehicle leaves the edge
72 : double leaveTime;
73 :
74 : /// The previous edge
75 : const EdgeInfo* prev;
76 :
77 : /// whether the edge was already evaluated
78 : bool visited;
79 :
80 : /// whether the edge is currently not allowed
81 : bool prohibited;
82 :
83 : /// the time at which a temporary prohibitione ends
84 : double prohibitionEnd;
85 :
86 : inline void reset() {
87 94249170 : effort = std::numeric_limits<double>::max();
88 94249170 : heuristicEffort = std::numeric_limits<double>::max();
89 83247965 : visited = false;
90 : }
91 :
92 : };
93 :
94 : /// Type of the function that is used to retrieve the edge effort.
95 : typedef double(* Operation)(const E* const, const V* const, double);
96 :
97 : /// Prohibitions and their estimated end time
98 : typedef std::map<const E*, double> Prohibitions;
99 :
100 : /// Constructor
101 50887 : SUMOAbstractRouter(const std::string& type, bool unbuildIsWarning, Operation operation, Operation ttOperation,
102 : const bool havePermissions, const bool haveRestrictions) :
103 50887 : myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
104 50887 : myOperation(operation), myTTOperation(ttOperation),
105 50887 : myBulkMode(false),
106 50887 : myAutoBulkMode(false),
107 50887 : myAmClean(true),
108 50887 : myHavePermissions(havePermissions),
109 50887 : myHaveRestrictions(haveRestrictions),
110 50887 : myType(type),
111 50887 : myQueryVisits(0),
112 50887 : myNumQueries(0),
113 50887 : myQueryStartTime(0),
114 50887 : myQueryTimeSum(0) {
115 50887 : }
116 :
117 : /// Copy Constructor
118 367 : SUMOAbstractRouter(SUMOAbstractRouter* other) :
119 367 : myErrorMsgHandler(other->myErrorMsgHandler),
120 367 : myOperation(other->myOperation), myTTOperation(other->myTTOperation),
121 367 : myBulkMode(false),
122 367 : myAutoBulkMode(false),
123 367 : myAmClean(true),
124 367 : myHavePermissions(other->myHavePermissions),
125 367 : myHaveRestrictions(other->myHaveRestrictions),
126 367 : myType(other->myType),
127 367 : myQueryVisits(0),
128 367 : myNumQueries(0),
129 367 : myQueryStartTime(0),
130 734 : myQueryTimeSum(0) { }
131 :
132 :
133 :
134 : /// Destructor
135 51249 : virtual ~SUMOAbstractRouter() {
136 51249 : if (myNumQueries > 0) {
137 71976 : WRITE_MESSAGE(myType + " answered " + toString(myNumQueries) + " queries and explored " + toString((double)myQueryVisits / (double)myNumQueries) + " edges on average.");
138 71976 : WRITE_MESSAGE(myType + " spent " + elapsedMs2string(myQueryTimeSum) + " answering queries (" + toString((double)myQueryTimeSum / (double)myNumQueries) + "ms on average).");
139 : }
140 69243 : }
141 :
142 : virtual SUMOAbstractRouter* clone() = 0;
143 :
144 4319095 : inline void init(const int edgeID, const SUMOTime msTime) {
145 : // if (!myAmClean) {
146 : // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
147 18741290 : for (auto& edgeInfo : myFrontierList) {
148 14422195 : edgeInfo->reset();
149 : }
150 : myFrontierList.clear();
151 81252479 : for (auto& edgeInfo : myFound) {
152 76933384 : edgeInfo->reset();
153 : }
154 : myFound.clear();
155 4319095 : if (edgeID > -1) {
156 : // add begin node
157 4319095 : auto& fromInfo = myEdgeInfos[edgeID];
158 4319095 : fromInfo.effort = 0.;
159 4319095 : fromInfo.heuristicEffort = 0.;
160 4319095 : fromInfo.prev = nullptr;
161 4319095 : fromInfo.leaveTime = STEPS2TIME(msTime);
162 4319095 : myFrontierList.push_back(&fromInfo);
163 : }
164 4319095 : myAmClean = true;
165 : // }
166 4319095 : }
167 :
168 : /// reset internal caches, used by CHRouter
169 4134 : virtual void reset(const V* const vehicle) {
170 : UNUSED_PARAMETER(vehicle);
171 4134 : }
172 :
173 : const std::string& getType() const {
174 : return myType;
175 : }
176 :
177 : inline const typename SUMOAbstractRouter<E, V>::EdgeInfo& getEdgeInfo(int index) const {
178 56 : return myEdgeInfos[index];
179 : }
180 :
181 : /** @brief Builds the route between the given edges using the minimum effort at the given time
182 : The definition of the effort depends on the wished routing scheme */
183 : virtual bool compute(const E* from, const E* to, const V* const vehicle,
184 : SUMOTime msTime, std::vector<const E*>& into, bool silent = false) = 0;
185 :
186 :
187 : /** @brief Builds the route between the given edges using the minimum effort at the given time,
188 : * also taking into account position along the edges to ensure currect
189 : * handling of looped routes
190 : * The definition of the effort depends on the wished routing scheme */
191 70955 : inline bool compute(
192 : const E* from, double fromPos,
193 : const E* to, double toPos,
194 : const V* const vehicle,
195 : SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
196 70955 : if (from != to || fromPos <= toPos) {
197 68174 : return compute(from, to, vehicle, msTime, into, silent);
198 : } else {
199 2781 : return computeLooped(from, to, vehicle, msTime, into, silent);
200 : }
201 : }
202 :
203 :
204 : /** @brief Builds the route between the given edges using the minimum effort at the given time
205 : * if from == to, return the shortest looped route */
206 78684 : inline bool computeLooped(const E* from, const E* to, const V* const vehicle,
207 : SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
208 78684 : if (from != to) {
209 75596 : return compute(from, to, vehicle, msTime, into, silent);
210 : }
211 : double minEffort = std::numeric_limits<double>::max();
212 : std::vector<const E*> best;
213 3088 : const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
214 9698 : for (const std::pair<const E*, const E*>& follower : from->getViaSuccessors(vClass)) {
215 : std::vector<const E*> tmp;
216 3305 : compute(follower.first, to, vehicle, msTime, tmp, true);
217 3305 : if (tmp.size() > 0) {
218 2806 : double effort = recomputeCosts(tmp, vehicle, msTime);
219 2806 : if (effort < minEffort) {
220 : minEffort = effort;
221 2704 : best = tmp;
222 : }
223 : }
224 : }
225 3088 : if (minEffort != std::numeric_limits<double>::max()) {
226 2589 : into.push_back(from);
227 : std::copy(best.begin(), best.end(), std::back_inserter(into));
228 : return true;
229 499 : } else if (!silent && myErrorMsgHandler != nullptr) {
230 50 : myErrorMsgHandler->informf(TL("No connection between edge '%' and edge '%' found."), from->getID(), to->getID());
231 : }
232 : return false;
233 3088 : }
234 :
235 61326063 : inline bool isProhibited(const E* const edge, const V* const vehicle) const {
236 189709194 : return (myHavePermissions && edge->prohibits(vehicle)) || (myHaveRestrictions && edge->restricts(vehicle));
237 : }
238 :
239 : inline double getTravelTime(const E* const e, const V* const v, const double t, const double effort) const {
240 77426054 : return myTTOperation == nullptr ? effort : (*myTTOperation)(e, v, t);
241 : }
242 :
243 188841125 : inline void updateViaEdgeCost(const E* viaEdge, const V* const v, double& time, double& effort, double& length) const {
244 268488147 : while (viaEdge != nullptr && viaEdge->isInternal()) {
245 79647022 : const double viaEffortDelta = this->getEffort(viaEdge, v, time);
246 79647022 : time += getTravelTime(viaEdge, v, time, viaEffortDelta);
247 79647022 : effort += viaEffortDelta;
248 79647022 : length += viaEdge->getLength();
249 79647022 : viaEdge = viaEdge->getViaSuccessors().front().second;
250 : }
251 188841125 : }
252 :
253 19600855 : inline void updateViaCost(const E* const prev, const E* const e, const V* const v, double& time, double& effort, double& length) const {
254 19600855 : if (prev != nullptr) {
255 23307284 : for (const std::pair<const E*, const E*>& follower : prev->getViaSuccessors()) {
256 23303456 : if (follower.first == e) {
257 15231341 : updateViaEdgeCost(follower.second, v, time, effort, length);
258 : break;
259 : }
260 : }
261 : }
262 19600855 : const double effortDelta = this->getEffort(e, v, time);
263 19600855 : effort += effortDelta;
264 19600855 : time += getTravelTime(e, v, time, effortDelta);
265 19600855 : length += e->getLength();
266 19600855 : }
267 :
268 : bool isValid(const std::vector<const E*>& edges, const V* const v) const {
269 2846076 : for (const E* const e : edges) {
270 2411336 : if (isProhibited(e, v)) {
271 : return false;
272 : }
273 : }
274 : return true;
275 : }
276 :
277 4154780 : virtual double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime, double* lengthp = nullptr) const {
278 4154780 : double time = STEPS2TIME(msTime);
279 4154780 : double effort = 0.;
280 4154780 : double length = 0.;
281 4154780 : if (lengthp == nullptr) {
282 : lengthp = &length;
283 : } else {
284 5392 : *lengthp = 0.;
285 : }
286 : const E* prev = nullptr;
287 21790379 : for (const E* const e : edges) {
288 17635599 : updateViaCost(prev, e, v, time, effort, *lengthp);
289 : prev = e;
290 : }
291 4154780 : return effort;
292 : }
293 :
294 :
295 152978 : inline double recomputeCostsPos(const std::vector<const E*>& edges, const V* const v, double fromPos, double toPos, SUMOTime msTime, double* lengthp = nullptr) const {
296 152978 : double effort = recomputeCosts(edges, v, msTime, lengthp);
297 152978 : if (!edges.empty()) {
298 152978 : double firstEffort = this->getEffort(edges.front(), v, STEPS2TIME(msTime));
299 152978 : double lastEffort = this->getEffort(edges.back(), v, STEPS2TIME(msTime));
300 152978 : effort -= firstEffort * fromPos / edges.front()->getLength();
301 152978 : effort -= lastEffort * (edges.back()->getLength() - toPos) / edges.back()->getLength();
302 : }
303 152978 : return effort;
304 : }
305 :
306 :
307 : 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) {
308 : double time = STEPS2TIME(msTime);
309 : double effort = 0.;
310 : double length = 0.;
311 : const EdgeInfo* prev = &myEdgeInfos[(*routeBegin)->getNumericalID()];
312 : init((*routeBegin)->getNumericalID(), msTime);
313 : for (auto e = routeBegin + 1; e != routeEnd; ++e) {
314 : if (isProhibited(*e, v)) {
315 : return -1;
316 : }
317 : auto& edgeInfo = myEdgeInfos[(*e)->getNumericalID()];
318 : edgeInfo.heuristicEffort = effort;
319 : edgeInfo.prev = prev;
320 : updateViaCost(prev->edge, *e, v, time, effort, length);
321 : edgeInfo.effort = effort;
322 : edgeInfo.leaveTime = time;
323 : myFound.push_back(&edgeInfo);
324 : prev = &edgeInfo;
325 : #ifdef ROUTER_DEBUG_HINT
326 : if (ROUTER_DEBUG_COND) {
327 : std::cout << "DEBUG: hit=" << (*e)->getID()
328 : << " TT=" << edgeInfo.effort
329 : << " EF=" << this->getEffort(*e, v, edgeInfo.leaveTime)
330 : << " HT=" << edgeInfo.heuristicEffort << "\n";
331 : }
332 : #endif
333 : }
334 : return effort;
335 : }
336 :
337 :
338 180883141 : inline double getEffort(const E* const e, const V* const v, double t) const {
339 180883141 : if (this->myProhibited.size() > 0 && myEdgeInfos.size() > 0 && myEdgeInfos[e->getNumericalID()].prohibitionEnd > 0) {
340 : // pass edge after prohibition ends
341 15 : return (myEdgeInfos[e->getNumericalID()].prohibitionEnd - t) + (*myOperation)(e, v, myEdgeInfos[e->getNumericalID()].prohibitionEnd);
342 : } else {
343 180883126 : return (*myOperation)(e, v, t);
344 : }
345 : }
346 :
347 : inline void startQuery() {
348 4381155 : myNumQueries++;
349 4381155 : myQueryStartTime = SysUtils::getCurrentMillis();
350 : }
351 :
352 : inline void endQuery(int visits) {
353 4381155 : myQueryVisits += visits;
354 4381155 : myQueryTimeSum += (SysUtils::getCurrentMillis() - myQueryStartTime);
355 : }
356 :
357 81532 : virtual void setBulkMode(const bool mode) {
358 82036 : myBulkMode = mode;
359 81532 : }
360 :
361 : inline void setAutoBulkMode(const bool mode) {
362 2527 : myAutoBulkMode = mode;
363 4 : }
364 :
365 1655075 : virtual void prohibit(const Prohibitions& toProhibit) {
366 3408771 : for (auto item : this->myProhibited) {
367 1753696 : myEdgeInfos[item.first->getNumericalID()].prohibited = false;
368 1753696 : myEdgeInfos[item.first->getNumericalID()].prohibitionEnd = 0;
369 : }
370 3414076 : for (auto item : toProhibit) {
371 1759001 : if (item.second >= 0 && item.second != std::numeric_limits<double>::max()) {
372 3 : myEdgeInfos[item.first->getNumericalID()].prohibitionEnd = item.second;
373 : } else {
374 1758998 : myEdgeInfos[item.first->getNumericalID()].prohibited = true;
375 : }
376 : }
377 : this->myProhibited = toProhibit;
378 1655075 : }
379 :
380 :
381 : /// Builds the path from marked edges
382 4332584 : void buildPathFrom(const typename SUMOAbstractRouter<E, V>::EdgeInfo* rbegin, std::vector<const E*>& edges) {
383 : std::vector<const E*> tmp;
384 23774508 : while (rbegin != nullptr) {
385 19441924 : tmp.push_back(rbegin->edge);
386 19441924 : rbegin = rbegin->prev;
387 : }
388 : std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
389 4332584 : }
390 :
391 : protected:
392 : /// @brief the handler for routing errors
393 : MsgHandler* const myErrorMsgHandler;
394 :
395 : /// @brief The object's operation to perform.
396 : Operation myOperation;
397 :
398 : /// @brief The object's operation to perform for travel times
399 : Operation myTTOperation;
400 :
401 : /// @brief whether we are currently operating several route queries in a bulk
402 : bool myBulkMode;
403 :
404 : /// @brief whether we are currently trying to detect bulk mode automatically
405 : bool myAutoBulkMode;
406 :
407 : /// @brief whether we are already initialized
408 : bool myAmClean;
409 :
410 : /// @brief whether edge permissions need to be considered
411 : const bool myHavePermissions;
412 :
413 : /// @brief whether edge restrictions need to be considered
414 : const bool myHaveRestrictions;
415 :
416 : /// The list of explicitly prohibited edges and estimated end time of prohibition
417 : Prohibitions myProhibited;
418 :
419 : /// The container of edge information
420 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo> myEdgeInfos;
421 :
422 : /// A container for reusage of the min edge heap
423 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFrontierList;
424 : /// @brief list of visited Edges (for resetting)
425 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFound;
426 :
427 : private:
428 : /// @brief the type of this router
429 : const std::string myType;
430 :
431 : /// @brief counters for performance logging
432 : long long int myQueryVisits;
433 : long long int myNumQueries;
434 : /// @brief the time spent querying in milliseconds
435 : long long int myQueryStartTime;
436 : long long int myQueryTimeSum;
437 :
438 : private:
439 : /// @brief Invalidated assignment operator
440 : SUMOAbstractRouter& operator=(const SUMOAbstractRouter& s) = delete;
441 : };
|
