Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2006-2024 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 6428662 : EdgeInfo(const E* const e)
57 6428662 : : edge(e), effort(std::numeric_limits<double>::max()),
58 6428662 : heuristicEffort(std::numeric_limits<double>::max()),
59 6428662 : leaveTime(0.), prev(nullptr), visited(false), prohibited(false) {}
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 : inline void reset() {
84 75131674 : effort = std::numeric_limits<double>::max();
85 75131674 : heuristicEffort = std::numeric_limits<double>::max();
86 70020973 : visited = false;
87 : }
88 :
89 : };
90 :
91 : /// Type of the function that is used to retrieve the edge effort.
92 : typedef double(* Operation)(const E* const, const V* const, double);
93 :
94 : /// Constructor
95 64372 : SUMOAbstractRouter(const std::string& type, bool unbuildIsWarning, Operation operation, Operation ttOperation,
96 : const bool havePermissions, const bool haveRestrictions) :
97 64372 : myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
98 64372 : myOperation(operation), myTTOperation(ttOperation),
99 64372 : myBulkMode(false),
100 64372 : myAutoBulkMode(false),
101 64372 : myHavePermissions(havePermissions),
102 64372 : myHaveRestrictions(haveRestrictions),
103 64372 : myType(type),
104 64372 : myQueryVisits(0),
105 64372 : myNumQueries(0),
106 64372 : myQueryStartTime(0),
107 64372 : myQueryTimeSum(0) {
108 64372 : }
109 :
110 : /// Copy Constructor
111 313 : SUMOAbstractRouter(SUMOAbstractRouter* other) :
112 313 : myErrorMsgHandler(other->myErrorMsgHandler),
113 313 : myOperation(other->myOperation), myTTOperation(other->myTTOperation),
114 313 : myBulkMode(false),
115 313 : myAutoBulkMode(false),
116 313 : myHavePermissions(other->myHavePermissions),
117 313 : myHaveRestrictions(other->myHaveRestrictions),
118 313 : myType(other->myType),
119 313 : myQueryVisits(0),
120 313 : myNumQueries(0),
121 313 : myQueryStartTime(0),
122 626 : myQueryTimeSum(0) { }
123 :
124 :
125 :
126 : /// Destructor
127 64680 : virtual ~SUMOAbstractRouter() {
128 64680 : if (myNumQueries > 0) {
129 88448 : WRITE_MESSAGE(myType + " answered " + toString(myNumQueries) + " queries and explored " + toString((double)myQueryVisits / (double)myNumQueries) + " edges on average.");
130 88448 : WRITE_MESSAGE(myType + " spent " + elapsedMs2string(myQueryTimeSum) + " answering queries (" + toString((double)myQueryTimeSum / (double)myNumQueries) + "ms on average).");
131 : }
132 86792 : }
133 :
134 : virtual SUMOAbstractRouter* clone() = 0;
135 :
136 3934598 : inline void init(const int edgeID, const SUMOTime msTime) {
137 : // if (!myAmClean) {
138 : // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
139 15518734 : for (auto& edgeInfo : myFrontierList) {
140 11584136 : edgeInfo->reset();
141 : }
142 : myFrontierList.clear();
143 66035555 : for (auto& edgeInfo : myFound) {
144 62100957 : edgeInfo->reset();
145 : }
146 : myFound.clear();
147 3934598 : if (edgeID > -1) {
148 : // add begin node
149 3934598 : auto& fromInfo = myEdgeInfos[edgeID];
150 3934598 : fromInfo.effort = 0.;
151 3934598 : fromInfo.heuristicEffort = 0.;
152 3934598 : fromInfo.prev = nullptr;
153 3934598 : fromInfo.leaveTime = STEPS2TIME(msTime);
154 3934598 : myFrontierList.push_back(&fromInfo);
155 : }
156 3934598 : myAmClean = true;
157 : // }
158 3934598 : }
159 :
160 : /// reset internal caches, used by CHRouter
161 3966 : virtual void reset(const V* const vehicle) {
162 : UNUSED_PARAMETER(vehicle);
163 3966 : }
164 :
165 : const std::string& getType() const {
166 : return myType;
167 : }
168 :
169 : inline const typename SUMOAbstractRouter<E, V>::EdgeInfo& getEdgeInfo(int index) const {
170 56 : return myEdgeInfos[index];
171 : }
172 :
173 : /** @brief Builds the route between the given edges using the minimum effort at the given time
174 : The definition of the effort depends on the wished routing scheme */
175 : virtual bool compute(const E* from, const E* to, const V* const vehicle,
176 : SUMOTime msTime, std::vector<const E*>& into, bool silent = false) = 0;
177 :
178 :
179 : /** @brief Builds the route between the given edges using the minimum effort at the given time,
180 : * also taking into account position along the edges to ensure currect
181 : * handling of looped routes
182 : * The definition of the effort depends on the wished routing scheme */
183 50325 : inline bool compute(
184 : const E* from, double fromPos,
185 : const E* to, double toPos,
186 : const V* const vehicle,
187 : SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
188 50325 : if (from != to || fromPos <= toPos) {
189 49614 : return compute(from, to, vehicle, msTime, into, silent);
190 : } else {
191 711 : return computeLooped(from, to, vehicle, msTime, into, silent);
192 : }
193 : }
194 :
195 :
196 : /** @brief Builds the route between the given edges using the minimum effort at the given time
197 : * if from == to, return the shortest looped route */
198 58711 : inline bool computeLooped(const E* from, const E* to, const V* const vehicle,
199 : SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
200 58711 : if (from != to) {
201 57736 : return compute(from, to, vehicle, msTime, into, silent);
202 : }
203 : double minEffort = std::numeric_limits<double>::max();
204 : std::vector<const E*> best;
205 975 : const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
206 3307 : for (const std::pair<const E*, const E*>& follower : from->getViaSuccessors(vClass)) {
207 : std::vector<const E*> tmp;
208 1166 : compute(follower.first, to, vehicle, msTime, tmp, true);
209 1166 : if (tmp.size() > 0) {
210 670 : double effort = recomputeCosts(tmp, vehicle, msTime);
211 670 : if (effort < minEffort) {
212 : minEffort = effort;
213 586 : best = tmp;
214 : }
215 : }
216 : }
217 975 : if (minEffort != std::numeric_limits<double>::max()) {
218 479 : into.push_back(from);
219 : std::copy(best.begin(), best.end(), std::back_inserter(into));
220 : return true;
221 496 : } else if (!silent && myErrorMsgHandler != nullptr) {
222 48 : myErrorMsgHandler->informf(TL("No connection between edge '%' and edge '%' found."), from->getID(), to->getID());
223 : }
224 : return false;
225 975 : }
226 :
227 47656580 : inline bool isProhibited(const E* const edge, const V* const vehicle) const {
228 152469029 : return (myHavePermissions && edge->prohibits(vehicle)) || (myHaveRestrictions && edge->restricts(vehicle));
229 : }
230 :
231 : inline double getTravelTime(const E* const e, const V* const v, const double t, const double effort) const {
232 62574947 : return myTTOperation == nullptr ? effort : (*myTTOperation)(e, v, t);
233 : }
234 :
235 151630330 : inline void updateViaEdgeCost(const E* viaEdge, const V* const v, double& time, double& effort, double& length) const {
236 208976570 : while (viaEdge != nullptr && viaEdge->isInternal()) {
237 57346240 : const double viaEffortDelta = this->getEffort(viaEdge, v, time);
238 57346240 : time += getTravelTime(viaEdge, v, time, viaEffortDelta);
239 57346240 : effort += viaEffortDelta;
240 57346240 : length += viaEdge->getLength();
241 57346240 : viaEdge = viaEdge->getViaSuccessors().front().second;
242 : }
243 151630330 : }
244 :
245 16740760 : inline void updateViaCost(const E* const prev, const E* const e, const V* const v, double& time, double& effort, double& length) const {
246 16740760 : if (prev != nullptr) {
247 19677897 : for (const std::pair<const E*, const E*>& follower : prev->getViaSuccessors()) {
248 19674523 : if (follower.first == e) {
249 12906335 : updateViaEdgeCost(follower.second, v, time, effort, length);
250 : break;
251 : }
252 : }
253 : }
254 16740760 : const double effortDelta = this->getEffort(e, v, time);
255 16740760 : effort += effortDelta;
256 16740760 : time += getTravelTime(e, v, time, effortDelta);
257 16740760 : length += e->getLength();
258 16740760 : }
259 :
260 : bool isValid(const std::vector<const E*>& edges, const V* const v) const {
261 2271547 : for (const E* const e : edges) {
262 1965118 : if (isProhibited(e, v)) {
263 : return false;
264 : }
265 : }
266 : return true;
267 : }
268 :
269 3648410 : virtual double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime, double* lengthp = nullptr) const {
270 3648410 : double time = STEPS2TIME(msTime);
271 3648410 : double effort = 0.;
272 3648410 : double length = 0.;
273 3648410 : if (lengthp == nullptr) {
274 : lengthp = &length;
275 : } else {
276 5407 : *lengthp = 0.;
277 : }
278 : const E* prev = nullptr;
279 18657155 : for (const E* const e : edges) {
280 15008745 : updateViaCost(prev, e, v, time, effort, *lengthp);
281 : prev = e;
282 : }
283 3648410 : return effort;
284 : }
285 :
286 :
287 1138 : inline double recomputeCostsPos(const std::vector<const E*>& edges, const V* const v, double fromPos, double toPos, SUMOTime msTime, double* lengthp = nullptr) const {
288 1138 : double effort = recomputeCosts(edges, v, msTime, lengthp);
289 1138 : if (!edges.empty()) {
290 1138 : double firstEffort = this->getEffort(edges.front(), v, STEPS2TIME(msTime));
291 1138 : double lastEffort = this->getEffort(edges.back(), v, STEPS2TIME(msTime));
292 1138 : effort -= firstEffort * fromPos / edges.front()->getLength();
293 1138 : effort -= lastEffort * (edges.back()->getLength() - toPos) / edges.back()->getLength();
294 : }
295 1138 : return effort;
296 : }
297 :
298 :
299 : 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) {
300 : double time = STEPS2TIME(msTime);
301 : double effort = 0.;
302 : double length = 0.;
303 : const EdgeInfo* prev = &myEdgeInfos[(*routeBegin)->getNumericalID()];
304 : init((*routeBegin)->getNumericalID(), msTime);
305 : for (auto e = routeBegin + 1; e != routeEnd; ++e) {
306 : if (isProhibited(*e, v)) {
307 : return -1;
308 : }
309 : auto& edgeInfo = myEdgeInfos[(*e)->getNumericalID()];
310 : edgeInfo.heuristicEffort = effort;
311 : edgeInfo.prev = prev;
312 : updateViaCost(prev->edge, *e, v, time, effort, length);
313 : edgeInfo.effort = effort;
314 : edgeInfo.leaveTime = time;
315 : myFound.push_back(&edgeInfo);
316 : prev = &edgeInfo;
317 : #ifdef ROUTER_DEBUG_HINT
318 : if (ROUTER_DEBUG_COND) {
319 : std::cout << "DEBUG: hit=" << (*e)->getID()
320 : << " TT=" << edgeInfo.effort
321 : << " EF=" << this->getEffort(*e, v, edgeInfo.leaveTime)
322 : << " HT=" << edgeInfo.heuristicEffort << "\n";
323 : }
324 : #endif
325 : }
326 : return effort;
327 : }
328 :
329 :
330 : inline double getEffort(const E* const e, const V* const v, double t) const {
331 140272523 : return (*myOperation)(e, v, t);
332 : }
333 :
334 : inline void startQuery() {
335 3984837 : myNumQueries++;
336 3984837 : myQueryStartTime = SysUtils::getCurrentMillis();
337 : }
338 :
339 : inline void endQuery(int visits) {
340 3984837 : myQueryVisits += visits;
341 3984837 : myQueryTimeSum += (SysUtils::getCurrentMillis() - myQueryStartTime);
342 : }
343 :
344 52841 : virtual void setBulkMode(const bool mode) {
345 53129 : myBulkMode = mode;
346 52841 : }
347 :
348 : inline void setAutoBulkMode(const bool mode) {
349 2290 : myAutoBulkMode = mode;
350 2 : }
351 :
352 1520174 : virtual void prohibit(const std::vector<E*>& toProhibit) {
353 3144902 : for (E* const edge : this->myProhibited) {
354 1624728 : myEdgeInfos[edge->getNumericalID()].prohibited = false;
355 : }
356 3150504 : for (E* const edge : toProhibit) {
357 1630330 : myEdgeInfos[edge->getNumericalID()].prohibited = true;
358 : }
359 1520174 : this->myProhibited = toProhibit;
360 1520174 : }
361 :
362 :
363 : /// Builds the path from marked edges
364 3964880 : void buildPathFrom(const typename SUMOAbstractRouter<E, V>::EdgeInfo* rbegin, std::vector<const E*>& edges) {
365 : std::vector<const E*> tmp;
366 21691470 : while (rbegin != nullptr) {
367 17726590 : tmp.push_back(rbegin->edge);
368 17726590 : rbegin = rbegin->prev;
369 : }
370 : std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
371 3964880 : }
372 :
373 : protected:
374 : /// @brief the handler for routing errors
375 : MsgHandler* const myErrorMsgHandler;
376 :
377 : /// @brief The object's operation to perform.
378 : Operation myOperation;
379 :
380 : /// @brief The object's operation to perform for travel times
381 : Operation myTTOperation;
382 :
383 : /// @brief whether we are currently operating several route queries in a bulk
384 : bool myBulkMode;
385 :
386 : /// @brief whether we are currently trying to detect bulk mode automatically
387 : bool myAutoBulkMode;
388 :
389 : /// @brief whether we are already initialized
390 : bool myAmClean;
391 :
392 : /// @brief whether edge permissions need to be considered
393 : const bool myHavePermissions;
394 :
395 : /// @brief whether edge restrictions need to be considered
396 : const bool myHaveRestrictions;
397 :
398 : /// The list of explicitly prohibited edges
399 : std::vector<E*> myProhibited;
400 :
401 : /// The container of edge information
402 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo> myEdgeInfos;
403 :
404 : /// A container for reusage of the min edge heap
405 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFrontierList;
406 : /// @brief list of visited Edges (for resetting)
407 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFound;
408 :
409 : private:
410 : /// @brief the type of this router
411 : const std::string myType;
412 :
413 : /// @brief counters for performance logging
414 : long long int myQueryVisits;
415 : long long int myNumQueries;
416 : /// @brief the time spent querying in milliseconds
417 : long long int myQueryStartTime;
418 : long long int myQueryTimeSum;
419 :
420 : private:
421 : /// @brief Invalidated assignment operator
422 : SUMOAbstractRouter& operator=(const SUMOAbstractRouter& s) = delete;
423 : };
|
