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 6579659 : EdgeInfo(const E* const e)
57 6579659 : : edge(e), effort(std::numeric_limits<double>::max()),
58 6579659 : heuristicEffort(std::numeric_limits<double>::max()),
59 6579659 : 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 80223064 : effort = std::numeric_limits<double>::max();
88 80223064 : heuristicEffort = std::numeric_limits<double>::max();
89 74847135 : 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 65968 : SUMOAbstractRouter(const std::string& type, bool unbuildIsWarning, Operation operation, Operation ttOperation,
102 : const bool havePermissions, const bool haveRestrictions) :
103 65968 : myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
104 65968 : myOperation(operation), myTTOperation(ttOperation),
105 65968 : myBulkMode(false),
106 65968 : myAutoBulkMode(false),
107 65968 : myHavePermissions(havePermissions),
108 65968 : myHaveRestrictions(haveRestrictions),
109 65968 : myType(type),
110 65968 : myQueryVisits(0),
111 65968 : myNumQueries(0),
112 65968 : myQueryStartTime(0),
113 65968 : myQueryTimeSum(0) {
114 65968 : }
115 :
116 : /// Copy Constructor
117 343 : SUMOAbstractRouter(SUMOAbstractRouter* other) :
118 343 : myErrorMsgHandler(other->myErrorMsgHandler),
119 343 : myOperation(other->myOperation), myTTOperation(other->myTTOperation),
120 343 : myBulkMode(false),
121 343 : myAutoBulkMode(false),
122 343 : myHavePermissions(other->myHavePermissions),
123 343 : myHaveRestrictions(other->myHaveRestrictions),
124 343 : myType(other->myType),
125 343 : myQueryVisits(0),
126 343 : myNumQueries(0),
127 343 : myQueryStartTime(0),
128 686 : myQueryTimeSum(0) { }
129 :
130 :
131 :
132 : /// Destructor
133 66309 : virtual ~SUMOAbstractRouter() {
134 66309 : if (myNumQueries > 0) {
135 88684 : WRITE_MESSAGE(myType + " answered " + toString(myNumQueries) + " queries and explored " + toString((double)myQueryVisits / (double)myNumQueries) + " edges on average.");
136 88684 : WRITE_MESSAGE(myType + " spent " + elapsedMs2string(myQueryTimeSum) + " answering queries (" + toString((double)myQueryTimeSum / (double)myNumQueries) + "ms on average).");
137 : }
138 88480 : }
139 :
140 : virtual SUMOAbstractRouter* clone() = 0;
141 :
142 4074531 : inline void init(const int edgeID, const SUMOTime msTime) {
143 : // if (!myAmClean) {
144 : // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
145 16725823 : for (auto& edgeInfo : myFrontierList) {
146 12651292 : edgeInfo->reset();
147 : }
148 : myFrontierList.clear();
149 68751746 : for (auto& edgeInfo : myFound) {
150 64677215 : edgeInfo->reset();
151 : }
152 : myFound.clear();
153 4074531 : if (edgeID > -1) {
154 : // add begin node
155 4074531 : auto& fromInfo = myEdgeInfos[edgeID];
156 4074531 : fromInfo.effort = 0.;
157 4074531 : fromInfo.heuristicEffort = 0.;
158 4074531 : fromInfo.prev = nullptr;
159 4074531 : fromInfo.leaveTime = STEPS2TIME(msTime);
160 4074531 : myFrontierList.push_back(&fromInfo);
161 : }
162 4074531 : myAmClean = true;
163 : // }
164 4074531 : }
165 :
166 : /// reset internal caches, used by CHRouter
167 4134 : virtual void reset(const V* const vehicle) {
168 : UNUSED_PARAMETER(vehicle);
169 4134 : }
170 :
171 : const std::string& getType() const {
172 : return myType;
173 : }
174 :
175 : inline const typename SUMOAbstractRouter<E, V>::EdgeInfo& getEdgeInfo(int index) const {
176 56 : return myEdgeInfos[index];
177 : }
178 :
179 : /** @brief Builds the route between the given edges using the minimum effort at the given time
180 : The definition of the effort depends on the wished routing scheme */
181 : virtual bool compute(const E* from, const E* to, const V* const vehicle,
182 : SUMOTime msTime, std::vector<const E*>& into, bool silent = false) = 0;
183 :
184 :
185 : /** @brief Builds the route between the given edges using the minimum effort at the given time,
186 : * also taking into account position along the edges to ensure currect
187 : * handling of looped routes
188 : * The definition of the effort depends on the wished routing scheme */
189 64343 : inline bool compute(
190 : const E* from, double fromPos,
191 : const E* to, double toPos,
192 : const V* const vehicle,
193 : SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
194 64343 : if (from != to || fromPos <= toPos) {
195 61600 : return compute(from, to, vehicle, msTime, into, silent);
196 : } else {
197 2743 : return computeLooped(from, to, vehicle, msTime, into, silent);
198 : }
199 : }
200 :
201 :
202 : /** @brief Builds the route between the given edges using the minimum effort at the given time
203 : * if from == to, return the shortest looped route */
204 86125 : inline bool computeLooped(const E* from, const E* to, const V* const vehicle,
205 : SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
206 86125 : if (from != to) {
207 83110 : return compute(from, to, vehicle, msTime, into, silent);
208 : }
209 : double minEffort = std::numeric_limits<double>::max();
210 : std::vector<const E*> best;
211 3015 : const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
212 9479 : for (const std::pair<const E*, const E*>& follower : from->getViaSuccessors(vClass)) {
213 : std::vector<const E*> tmp;
214 3232 : compute(follower.first, to, vehicle, msTime, tmp, true);
215 3232 : if (tmp.size() > 0) {
216 2735 : double effort = recomputeCosts(tmp, vehicle, msTime);
217 2735 : if (effort < minEffort) {
218 : minEffort = effort;
219 2633 : best = tmp;
220 : }
221 : }
222 : }
223 3015 : if (minEffort != std::numeric_limits<double>::max()) {
224 2518 : into.push_back(from);
225 : std::copy(best.begin(), best.end(), std::back_inserter(into));
226 : return true;
227 497 : } else if (!silent && myErrorMsgHandler != nullptr) {
228 50 : myErrorMsgHandler->informf(TL("No connection between edge '%' and edge '%' found."), from->getID(), to->getID());
229 : }
230 : return false;
231 3015 : }
232 :
233 49933394 : inline bool isProhibited(const E* const edge, const V* const vehicle) const {
234 158833834 : return (myHavePermissions && edge->prohibits(vehicle)) || (myHaveRestrictions && edge->restricts(vehicle));
235 : }
236 :
237 : inline double getTravelTime(const E* const e, const V* const v, const double t, const double effort) const {
238 65151458 : return myTTOperation == nullptr ? effort : (*myTTOperation)(e, v, t);
239 : }
240 :
241 158808033 : inline void updateViaEdgeCost(const E* viaEdge, const V* const v, double& time, double& effort, double& length) const {
242 217938445 : while (viaEdge != nullptr && viaEdge->isInternal()) {
243 59130412 : const double viaEffortDelta = this->getEffort(viaEdge, v, time);
244 59130412 : time += getTravelTime(viaEdge, v, time, viaEffortDelta);
245 59130412 : effort += viaEffortDelta;
246 59130412 : length += viaEdge->getLength();
247 59130412 : viaEdge = viaEdge->getViaSuccessors().front().second;
248 : }
249 158808033 : }
250 :
251 18623253 : inline void updateViaCost(const E* const prev, const E* const e, const V* const v, double& time, double& effort, double& length) const {
252 18623253 : if (prev != nullptr) {
253 22060014 : for (const std::pair<const E*, const E*>& follower : prev->getViaSuccessors()) {
254 22056327 : if (follower.first == e) {
255 14474731 : updateViaEdgeCost(follower.second, v, time, effort, length);
256 : break;
257 : }
258 : }
259 : }
260 18623253 : const double effortDelta = this->getEffort(e, v, time);
261 18623253 : effort += effortDelta;
262 18623253 : time += getTravelTime(e, v, time, effortDelta);
263 18623253 : length += e->getLength();
264 18623253 : }
265 :
266 : bool isValid(const std::vector<const E*>& edges, const V* const v) const {
267 2293772 : for (const E* const e : edges) {
268 1985607 : if (isProhibited(e, v)) {
269 : return false;
270 : }
271 : }
272 : return true;
273 : }
274 :
275 3952025 : virtual double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime, double* lengthp = nullptr) const {
276 3952025 : double time = STEPS2TIME(msTime);
277 3952025 : double effort = 0.;
278 3952025 : double length = 0.;
279 3952025 : if (lengthp == nullptr) {
280 : lengthp = &length;
281 : } else {
282 5392 : *lengthp = 0.;
283 : }
284 : const E* prev = nullptr;
285 20766410 : for (const E* const e : edges) {
286 16814385 : updateViaCost(prev, e, v, time, effort, *lengthp);
287 : prev = e;
288 : }
289 3952025 : return effort;
290 : }
291 :
292 :
293 167810 : inline double recomputeCostsPos(const std::vector<const E*>& edges, const V* const v, double fromPos, double toPos, SUMOTime msTime, double* lengthp = nullptr) const {
294 167810 : double effort = recomputeCosts(edges, v, msTime, lengthp);
295 167810 : if (!edges.empty()) {
296 167810 : double firstEffort = this->getEffort(edges.front(), v, STEPS2TIME(msTime));
297 167810 : double lastEffort = this->getEffort(edges.back(), v, STEPS2TIME(msTime));
298 167810 : effort -= firstEffort * fromPos / edges.front()->getLength();
299 167810 : effort -= lastEffort * (edges.back()->getLength() - toPos) / edges.back()->getLength();
300 : }
301 167810 : return effort;
302 : }
303 :
304 :
305 : 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) {
306 : double time = STEPS2TIME(msTime);
307 : double effort = 0.;
308 : double length = 0.;
309 : const EdgeInfo* prev = &myEdgeInfos[(*routeBegin)->getNumericalID()];
310 : init((*routeBegin)->getNumericalID(), msTime);
311 : for (auto e = routeBegin + 1; e != routeEnd; ++e) {
312 : if (isProhibited(*e, v)) {
313 : return -1;
314 : }
315 : auto& edgeInfo = myEdgeInfos[(*e)->getNumericalID()];
316 : edgeInfo.heuristicEffort = effort;
317 : edgeInfo.prev = prev;
318 : updateViaCost(prev->edge, *e, v, time, effort, length);
319 : edgeInfo.effort = effort;
320 : edgeInfo.leaveTime = time;
321 : myFound.push_back(&edgeInfo);
322 : prev = &edgeInfo;
323 : #ifdef ROUTER_DEBUG_HINT
324 : if (ROUTER_DEBUG_COND) {
325 : std::cout << "DEBUG: hit=" << (*e)->getID()
326 : << " TT=" << edgeInfo.effort
327 : << " EF=" << this->getEffort(*e, v, edgeInfo.leaveTime)
328 : << " HT=" << edgeInfo.heuristicEffort << "\n";
329 : }
330 : #endif
331 : }
332 : return effort;
333 : }
334 :
335 :
336 146944043 : inline double getEffort(const E* const e, const V* const v, double t) const {
337 146944043 : if (this->myProhibited.size() > 0 && myEdgeInfos.size() > 0 && myEdgeInfos[e->getNumericalID()].prohibitionEnd > 0) {
338 : // pass edge after prohibition ends
339 15 : return (myEdgeInfos[e->getNumericalID()].prohibitionEnd - t) + (*myOperation)(e, v, myEdgeInfos[e->getNumericalID()].prohibitionEnd);
340 : } else {
341 146944028 : return (*myOperation)(e, v, t);
342 : }
343 : }
344 :
345 : inline void startQuery() {
346 4136471 : myNumQueries++;
347 4136471 : myQueryStartTime = SysUtils::getCurrentMillis();
348 : }
349 :
350 : inline void endQuery(int visits) {
351 4136471 : myQueryVisits += visits;
352 4136471 : myQueryTimeSum += (SysUtils::getCurrentMillis() - myQueryStartTime);
353 : }
354 :
355 53142 : virtual void setBulkMode(const bool mode) {
356 53430 : myBulkMode = mode;
357 53142 : }
358 :
359 : inline void setAutoBulkMode(const bool mode) {
360 2443 : myAutoBulkMode = mode;
361 4 : }
362 :
363 1585258 : virtual void prohibit(const Prohibitions& toProhibit) {
364 3244115 : for (auto item : this->myProhibited) {
365 1658857 : myEdgeInfos[item.first->getNumericalID()].prohibited = false;
366 1658857 : myEdgeInfos[item.first->getNumericalID()].prohibitionEnd = 0;
367 : }
368 3249390 : for (auto item : toProhibit) {
369 1664132 : if (item.second >= 0 && item.second != std::numeric_limits<double>::max()) {
370 3 : myEdgeInfos[item.first->getNumericalID()].prohibitionEnd = item.second;
371 : } else {
372 1664129 : myEdgeInfos[item.first->getNumericalID()].prohibited = true;
373 : }
374 : }
375 : this->myProhibited = toProhibit;
376 1585258 : }
377 :
378 :
379 : /// Builds the path from marked edges
380 4105270 : void buildPathFrom(const typename SUMOAbstractRouter<E, V>::EdgeInfo* rbegin, std::vector<const E*>& edges) {
381 : std::vector<const E*> tmp;
382 22435703 : while (rbegin != nullptr) {
383 18330433 : tmp.push_back(rbegin->edge);
384 18330433 : rbegin = rbegin->prev;
385 : }
386 : std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
387 4105270 : }
388 :
389 : protected:
390 : /// @brief the handler for routing errors
391 : MsgHandler* const myErrorMsgHandler;
392 :
393 : /// @brief The object's operation to perform.
394 : Operation myOperation;
395 :
396 : /// @brief The object's operation to perform for travel times
397 : Operation myTTOperation;
398 :
399 : /// @brief whether we are currently operating several route queries in a bulk
400 : bool myBulkMode;
401 :
402 : /// @brief whether we are currently trying to detect bulk mode automatically
403 : bool myAutoBulkMode;
404 :
405 : /// @brief whether we are already initialized
406 : bool myAmClean;
407 :
408 : /// @brief whether edge permissions need to be considered
409 : const bool myHavePermissions;
410 :
411 : /// @brief whether edge restrictions need to be considered
412 : const bool myHaveRestrictions;
413 :
414 : /// The list of explicitly prohibited edges and estimated end time of prohibition
415 : Prohibitions myProhibited;
416 :
417 : /// The container of edge information
418 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo> myEdgeInfos;
419 :
420 : /// A container for reusage of the min edge heap
421 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFrontierList;
422 : /// @brief list of visited Edges (for resetting)
423 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFound;
424 :
425 : private:
426 : /// @brief the type of this router
427 : const std::string myType;
428 :
429 : /// @brief counters for performance logging
430 : long long int myQueryVisits;
431 : long long int myNumQueries;
432 : /// @brief the time spent querying in milliseconds
433 : long long int myQueryStartTime;
434 : long long int myQueryTimeSum;
435 :
436 : private:
437 : /// @brief Invalidated assignment operator
438 : SUMOAbstractRouter& operator=(const SUMOAbstractRouter& s) = delete;
439 : };
|
