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 6878466 : EdgeInfo(const E* const e)
57 6878466 : : edge(e), effort(std::numeric_limits<double>::max()),
58 6878466 : heuristicEffort(std::numeric_limits<double>::max()),
59 6878466 : 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 94342534 : effort = std::numeric_limits<double>::max();
88 94342534 : heuristicEffort = std::numeric_limits<double>::max();
89 83344085 : 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 51363 : SUMOAbstractRouter(const std::string& type, bool unbuildIsWarning, Operation operation, Operation ttOperation,
102 : const bool havePermissions, const bool haveRestrictions) :
103 51363 : myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
104 51363 : myOperation(operation), myTTOperation(ttOperation),
105 51363 : myBulkMode(false),
106 51363 : myAutoBulkMode(false),
107 51363 : myAmClean(true),
108 51363 : myHavePermissions(havePermissions),
109 51363 : myHaveRestrictions(haveRestrictions),
110 51363 : myType(type),
111 51363 : myQueryVisits(0),
112 51363 : myNumQueries(0),
113 51363 : myQueryStartTime(0),
114 51363 : myQueryTimeSum(0) {
115 51363 : }
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 51725 : virtual ~SUMOAbstractRouter() {
136 51725 : if (myNumQueries > 0) {
137 71280 : WRITE_MESSAGE(myType + " answered " + toString(myNumQueries) + " queries and explored " + toString((double)myQueryVisits / (double)myNumQueries) + " edges on average.");
138 71280 : WRITE_MESSAGE(myType + " spent " + elapsedMs2string(myQueryTimeSum) + " answering queries (" + toString((double)myQueryTimeSum / (double)myNumQueries) + "ms on average).");
139 : }
140 69545 : }
141 :
142 : virtual SUMOAbstractRouter* clone() = 0;
143 :
144 4258270 : 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 18649952 : for (auto& edgeInfo : myFrontierList) {
148 14391682 : edgeInfo->reset();
149 : }
150 : myFrontierList.clear();
151 81316101 : for (auto& edgeInfo : myFound) {
152 77057831 : edgeInfo->reset();
153 : }
154 : myFound.clear();
155 4258270 : if (edgeID > -1) {
156 : // add begin node
157 4258270 : auto& fromInfo = myEdgeInfos[edgeID];
158 4258270 : fromInfo.effort = 0.;
159 4258270 : fromInfo.heuristicEffort = 0.;
160 4258270 : fromInfo.prev = nullptr;
161 4258270 : fromInfo.leaveTime = STEPS2TIME(msTime);
162 4258270 : myFrontierList.push_back(&fromInfo);
163 : }
164 4258270 : myAmClean = true;
165 : // }
166 4258270 : }
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 2876941 : 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 2876941 : if (from != to || fromPos <= toPos) {
197 2873610 : return compute(from, to, vehicle, msTime, into, silent);
198 : } else {
199 3331 : 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 3331 : 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 3331 : if (from != to) {
209 0 : return compute(from, to, vehicle, msTime, into, silent);
210 : }
211 : double minEffort = std::numeric_limits<double>::max();
212 : std::vector<const E*> best;
213 3331 : const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
214 10969 : for (const std::pair<const E*, const E*>& follower : from->getViaSuccessors(vClass)) {
215 : std::vector<const E*> tmp;
216 3819 : compute(follower.first, to, vehicle, msTime, tmp, true);
217 3819 : if (tmp.size() > 0) {
218 2900 : double effort = recomputeCosts(tmp, vehicle, msTime);
219 2900 : if (effort < minEffort) {
220 : minEffort = effort;
221 2754 : best = tmp;
222 : }
223 : }
224 : }
225 3331 : if (minEffort != std::numeric_limits<double>::max()) {
226 2623 : into.push_back(from);
227 : std::copy(best.begin(), best.end(), std::back_inserter(into));
228 : return true;
229 708 : } else if (!silent && myErrorMsgHandler != nullptr) {
230 472 : myErrorMsgHandler->informf(TL("No connection between edge '%' and edge '%' found."), from->getID(), to->getID());
231 : }
232 : return false;
233 3331 : }
234 :
235 61351714 : inline bool isProhibited(const E* const edge, const V* const vehicle) const {
236 187925468 : 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 77558165 : return myTTOperation == nullptr ? effort : (*myTTOperation)(e, v, t);
241 : }
242 :
243 206609914 : inline void updateViaEdgeCost(const E* viaEdge, const V* const v, double& time, double& effort, double& length) const {
244 298534961 : while (viaEdge != nullptr && viaEdge->isInternal()) {
245 91925047 : const double viaEffortDelta = this->getEffort(viaEdge, v, time);
246 91925047 : time += getTravelTime(viaEdge, v, time, viaEffortDelta);
247 91925047 : effort += viaEffortDelta;
248 91925047 : length += viaEdge->getLength();
249 91925047 : viaEdge = viaEdge->getViaSuccessors().front().second;
250 : }
251 206609914 : }
252 :
253 42641444 : inline void updateViaCost(const E* const prev, const E* const e, const V* const v, double& time, double& effort, double& length) const {
254 42641444 : if (prev != nullptr) {
255 53939463 : for (const std::pair<const E*, const E*>& follower : prev->getViaSuccessors()) {
256 53935431 : if (follower.first == e) {
257 32818861 : updateViaEdgeCost(follower.second, v, time, effort, length);
258 : break;
259 : }
260 : }
261 : }
262 42641444 : const double effortDelta = this->getEffort(e, v, time);
263 42641444 : effort += effortDelta;
264 42641444 : time += getTravelTime(e, v, time, effortDelta);
265 42641444 : length += e->getLength();
266 42641444 : }
267 :
268 : bool isValid(const std::vector<const E*>& edges, const V* const v) const {
269 2847534 : for (const E* const e : edges) {
270 2412549 : if (isProhibited(e, v)) {
271 : return false;
272 : }
273 : }
274 : return true;
275 : }
276 :
277 9607533 : virtual double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime, double* lengthp = nullptr) const {
278 9607533 : double time = STEPS2TIME(msTime);
279 9607533 : double effort = 0.;
280 9607533 : double length = 0.;
281 9607533 : if (lengthp == nullptr) {
282 : lengthp = &length;
283 : } else {
284 5427 : *lengthp = 0.;
285 : }
286 : const E* prev = nullptr;
287 50266269 : for (const E* const e : edges) {
288 40658736 : updateViaCost(prev, e, v, time, effort, *lengthp);
289 : prev = e;
290 : }
291 9607533 : return effort;
292 : }
293 :
294 :
295 5603785 : inline double recomputeCostsPos(const std::vector<const E*>& edges, const V* const v, double fromPos, double toPos, SUMOTime msTime, double* lengthp = nullptr) const {
296 5603785 : double effort = recomputeCosts(edges, v, msTime, lengthp);
297 5603785 : if (!edges.empty()) {
298 5603785 : double firstEffort = this->getEffort(edges.front(), v, STEPS2TIME(msTime));
299 5603785 : double lastEffort = this->getEffort(edges.back(), v, STEPS2TIME(msTime));
300 5603785 : effort -= firstEffort * fromPos / edges.front()->getLength();
301 5603785 : effort -= lastEffort * (edges.back()->getLength() - toPos) / edges.back()->getLength();
302 5603785 : if (lengthp != nullptr) {
303 5427 : (*lengthp) -= fromPos + edges.back()->getLength() - toPos;
304 : }
305 : }
306 5603785 : return effort;
307 : }
308 :
309 :
310 : 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) {
311 : double time = STEPS2TIME(msTime);
312 : double effort = 0.;
313 : double length = 0.;
314 : const EdgeInfo* prev = &myEdgeInfos[(*routeBegin)->getNumericalID()];
315 : init((*routeBegin)->getNumericalID(), msTime);
316 : for (auto e = routeBegin + 1; e != routeEnd; ++e) {
317 : if (isProhibited(*e, v)) {
318 : return -1;
319 : }
320 : auto& edgeInfo = myEdgeInfos[(*e)->getNumericalID()];
321 : edgeInfo.heuristicEffort = effort;
322 : edgeInfo.prev = prev;
323 : updateViaCost(prev->edge, *e, v, time, effort, length);
324 : edgeInfo.effort = effort;
325 : edgeInfo.leaveTime = time;
326 : myFound.push_back(&edgeInfo);
327 : prev = &edgeInfo;
328 : #ifdef ROUTER_DEBUG_HINT
329 : if (ROUTER_DEBUG_COND) {
330 : std::cout << "DEBUG: hit=" << (*e)->getID()
331 : << " TT=" << edgeInfo.effort
332 : << " EF=" << this->getEffort(*e, v, edgeInfo.leaveTime)
333 : << " HT=" << edgeInfo.heuristicEffort << "\n";
334 : }
335 : #endif
336 : }
337 : return effort;
338 : }
339 :
340 :
341 227252028 : inline double getEffort(const E* const e, const V* const v, double t) const {
342 227252028 : if (this->myProhibited.size() > 0 && myEdgeInfos.size() > 0 && myEdgeInfos[e->getNumericalID()].prohibitionEnd > 0) {
343 : // pass edge after prohibition ends
344 15 : return (myEdgeInfos[e->getNumericalID()].prohibitionEnd - t) + (*myOperation)(e, v, myEdgeInfos[e->getNumericalID()].prohibitionEnd);
345 : } else {
346 227252013 : return (*myOperation)(e, v, t);
347 : }
348 : }
349 :
350 : inline void startQuery() {
351 4320330 : myNumQueries++;
352 4320330 : myQueryStartTime = SysUtils::getCurrentMillis();
353 : }
354 :
355 : inline void endQuery(int visits) {
356 4320330 : myQueryVisits += visits;
357 4320330 : myQueryTimeSum += (SysUtils::getCurrentMillis() - myQueryStartTime);
358 : }
359 :
360 81234 : virtual void setBulkMode(const bool mode) {
361 81738 : myBulkMode = mode;
362 81234 : }
363 :
364 : inline void setAutoBulkMode(const bool mode) {
365 2596 : myAutoBulkMode = mode;
366 4 : }
367 :
368 1655457 : virtual void prohibit(const Prohibitions& toProhibit) {
369 3410063 : for (auto item : this->myProhibited) {
370 1754606 : myEdgeInfos[item.first->getNumericalID()].prohibited = false;
371 1754606 : myEdgeInfos[item.first->getNumericalID()].prohibitionEnd = 0;
372 : }
373 3415376 : for (auto item : toProhibit) {
374 1759919 : if (item.second >= 0 && item.second != std::numeric_limits<double>::max()) {
375 3 : myEdgeInfos[item.first->getNumericalID()].prohibitionEnd = item.second;
376 : } else {
377 1759916 : myEdgeInfos[item.first->getNumericalID()].prohibited = true;
378 : }
379 : }
380 : this->myProhibited = toProhibit;
381 1655457 : }
382 :
383 :
384 : /// Builds the path from marked edges
385 4271321 : void buildPathFrom(const typename SUMOAbstractRouter<E, V>::EdgeInfo* rbegin, std::vector<const E*>& edges) {
386 : std::vector<const E*> tmp;
387 23722859 : while (rbegin != nullptr) {
388 19451538 : tmp.push_back(rbegin->edge);
389 19451538 : rbegin = rbegin->prev;
390 : }
391 : std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
392 4271321 : }
393 :
394 : protected:
395 : /// @brief the handler for routing errors
396 : MsgHandler* const myErrorMsgHandler;
397 :
398 : /// @brief The object's operation to perform.
399 : Operation myOperation;
400 :
401 : /// @brief The object's operation to perform for travel times
402 : Operation myTTOperation;
403 :
404 : /// @brief whether we are currently operating several route queries in a bulk
405 : bool myBulkMode;
406 :
407 : /// @brief whether we are currently trying to detect bulk mode automatically
408 : bool myAutoBulkMode;
409 :
410 : /// @brief whether we are already initialized
411 : bool myAmClean;
412 :
413 : /// @brief whether edge permissions need to be considered
414 : const bool myHavePermissions;
415 :
416 : /// @brief whether edge restrictions need to be considered
417 : const bool myHaveRestrictions;
418 :
419 : /// The list of explicitly prohibited edges and estimated end time of prohibition
420 : Prohibitions myProhibited;
421 :
422 : /// The container of edge information
423 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo> myEdgeInfos;
424 :
425 : /// A container for reusage of the min edge heap
426 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFrontierList;
427 : /// @brief list of visited Edges (for resetting)
428 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFound;
429 :
430 : private:
431 : /// @brief the type of this router
432 : const std::string myType;
433 :
434 : /// @brief counters for performance logging
435 : long long int myQueryVisits;
436 : long long int myNumQueries;
437 : /// @brief the time spent querying in milliseconds
438 : long long int myQueryStartTime;
439 : long long int myQueryTimeSum;
440 :
441 : private:
442 : /// @brief Invalidated assignment operator
443 : SUMOAbstractRouter& operator=(const SUMOAbstractRouter& s) = delete;
444 : };
|
