Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-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 DijkstraRouter.h
15 : /// @author Daniel Krajzewicz
16 : /// @author Jakob Erdmann
17 : /// @author Michael Behrisch
18 : /// @date Mon, 25 July 2005
19 : ///
20 : // Dijkstra shortest path algorithm using travel time or other values
21 : /****************************************************************************/
22 : #pragma once
23 : #include <config.h>
24 :
25 : #include <cassert>
26 : #include <string>
27 : #include <functional>
28 : #include <vector>
29 : #include <set>
30 : #include <limits>
31 : #include <algorithm>
32 : #include <iterator>
33 : #include <utils/common/ToString.h>
34 : #include <utils/common/MsgHandler.h>
35 : #include <utils/common/StdDefs.h>
36 : #include "EffortCalculator.h"
37 : #include "SUMOAbstractRouter.h"
38 :
39 : //#define DijkstraRouter_DEBUG_QUERY
40 : //#define DijkstraRouter_DEBUG_QUERY_FRONTIER
41 : //#define DijkstraRouter_DEBUG_QUERY_VISITED
42 : //#define DijkstraRouter_DEBUG_QUERY_PERF
43 : //#define DijkstraRouter_DEBUG_BULKMODE
44 :
45 : #define DijkstraRouter_DEBUG_QUERY_VISITED_OUT std::cerr
46 :
47 : // ===========================================================================
48 : // class definitions
49 : // ===========================================================================
50 : /**
51 : * @class DijkstraRouter
52 : * @brief Computes the shortest path through a network using the Dijkstra algorithm.
53 : *
54 : * The template parameters are:
55 : * @param E The edge class to use (MSEdge/ROEdge)
56 : * @param V The vehicle class to use (MSVehicle/ROVehicle)
57 : *
58 : * The router is edge-based. It must know the number of edges for internal reasons
59 : * and whether a missing connection between two given edges (unbuild route) shall
60 : * be reported as an error or as a warning.
61 : *
62 : */
63 : template<class E, class V>
64 : class DijkstraRouter : public SUMOAbstractRouter<E, V> {
65 : public:
66 : /**
67 : * @class EdgeInfoByEffortComparator
68 : * Class to compare (and so sort) nodes by their effort
69 : */
70 : class EdgeInfoByEffortComparator {
71 : public:
72 : /// Comparing method
73 28878 : bool operator()(const typename SUMOAbstractRouter<E, V>::EdgeInfo* nod1, const typename SUMOAbstractRouter<E, V>::EdgeInfo* nod2) const {
74 360145118 : if (nod1->effort == nod2->effort) {
75 73745715 : return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
76 : }
77 286413325 : return nod1->effort > nod2->effort;
78 : }
79 : };
80 :
81 :
82 : /// Constructor
83 23075 : DijkstraRouter(const std::vector<E*>& edges, bool unbuildIsWarning, typename SUMOAbstractRouter<E, V>::Operation effortOperation,
84 : typename SUMOAbstractRouter<E, V>::Operation ttOperation = nullptr, bool silent = false, EffortCalculator* calc = nullptr,
85 : const bool havePermissions = false, const bool haveRestrictions = false) :
86 : SUMOAbstractRouter<E, V>("DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
87 46150 : mySilent(silent), myExternalEffort(calc) {
88 5737332 : for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
89 5714257 : this->myEdgeInfos.push_back(typename SUMOAbstractRouter<E, V>::EdgeInfo(*i));
90 : }
91 23075 : }
92 :
93 : /// Destructor
94 25586 : virtual ~DijkstraRouter() { }
95 :
96 2528 : virtual SUMOAbstractRouter<E, V>* clone() {
97 5056 : auto clone = new DijkstraRouter<E, V>(this->myEdgeInfos, this->myErrorMsgHandler == MsgHandler::getWarningInstance(),
98 2528 : this->myOperation, this->myTTOperation, mySilent, myExternalEffort,
99 2528 : this->myHavePermissions, this->myHaveRestrictions);
100 2528 : clone->setAutoBulkMode(this->myAutoBulkMode);
101 2528 : return clone;
102 : }
103 :
104 : /** @brief Builds the route between the given edges using the minimum effort at the given time
105 : The definition of the effort depends on the wished routing scheme */
106 4244859 : bool compute(const E* from, const E* to, const V* const vehicle,
107 : SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
108 : assert(from != nullptr && (vehicle == nullptr || to != nullptr));
109 : // check whether from and to can be used
110 4244859 : if (this->myEdgeInfos[from->getNumericalID()].prohibited || this->isProhibited(from, vehicle)) {
111 102 : if (!silent) {
112 288 : this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on source edge '" + from->getID() + "'.");
113 : }
114 102 : return false;
115 : }
116 4244757 : if (to != nullptr && (this->myEdgeInfos[to->getNumericalID()].prohibited || this->isProhibited(to, vehicle))) {
117 52 : if (!silent) {
118 138 : this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on destination edge '" + to->getID() + "'.");
119 : }
120 52 : return false;
121 : }
122 4244361 : double length = 0.; // dummy for the via edge cost update
123 : this->startQuery();
124 : #ifdef DijkstraRouter_DEBUG_QUERY
125 : std::cout << "DEBUG: starting search for '" << Named::getIDSecure(vehicle) << "' from '" << Named::getIDSecure(from) << "' to '" << Named::getIDSecure(to) << "' time: " << STEPS2TIME(msTime) << "\n";
126 : #endif
127 4244705 : const SUMOVehicleClass vClass = vehicle == nullptr ? SVC_IGNORING : vehicle->getVClass();
128 2835991 : const bool ignoreTransient = vehicle == nullptr ? false : vehicle->ignoreTransientPermissions();
129 : std::tuple<const E*, const V*, SUMOTime> query = std::make_tuple(from, vehicle, msTime);
130 4249073 : if ((this->myBulkMode || (this->myAutoBulkMode && query == myLastQuery)) && !this->myAmClean) {
131 : #ifdef DijkstraRouter_DEBUG_BULKMODE
132 : if (query != myLastQuery) {
133 : std::cout << " invalid bulk mode. myLastQuery="
134 : << std::get<0>(myLastQuery)->getID() << ","
135 : << std::get<1>(myLastQuery)->getID() << ","
136 : << time2string(std::get<2>(myLastQuery))
137 : << " query="
138 : << std::get<0>(query)->getID() << ","
139 : << std::get<1>(query)->getID() << ","
140 : << time2string(std::get<2>(query))
141 : << "\n";
142 : } else {
143 : std::cout << " using bulk mode\n";
144 : }
145 : #endif
146 33486 : const auto& toInfo = this->myEdgeInfos[to->getNumericalID()];
147 33486 : if (toInfo.visited) {
148 22991 : this->buildPathFrom(&toInfo, into);
149 : this->endQuery(1);
150 : #ifdef DijkstraRouter_DEBUG_QUERY_PERF
151 : std::cout << " instant bulk success for vehicle " << vehicle->getID() << "\n";
152 : #endif
153 22991 : return true;
154 : }
155 : } else {
156 4211219 : this->init(from->getNumericalID(), msTime);
157 4211219 : if (myExternalEffort != nullptr) {
158 0 : myExternalEffort->setInitialState(from->getNumericalID());
159 : }
160 4211219 : this->myAmClean = false;
161 : }
162 : myLastQuery = query;
163 : // loop
164 : int num_visited = 0;
165 : #ifdef DijkstraRouter_DEBUG_QUERY_VISITED
166 : DijkstraRouter_DEBUG_QUERY_VISITED_OUT << "<edgeData>\n <interval begin=\"" << time2string(msTime) << "\" end=\"" << toString(msTime + 1000) << "\" id=\"" << Named::getIDSecure(vehicle) << "\">\n";
167 : #endif
168 79593497 : while (!this->myFrontierList.empty()) {
169 79573570 : num_visited += 1;
170 : // use the node with the minimal length
171 79573570 : auto* const minimumInfo = this->myFrontierList.front();
172 79573570 : const E* const minEdge = minimumInfo->edge;
173 : #ifdef DijkstraRouter_DEBUG_QUERY
174 : std::cout << "DEBUG: hit=" << minEdge->getID()
175 : << " TT=" << minimumInfo->effort
176 : << " EF=" << this->getEffort(minEdge, vehicle, minimumInfo->leaveTime)
177 : << " Leave: " << minimumInfo->leaveTime << " Q: ";
178 : #ifdef DijkstraRouter_DEBUG_QUERY_FRONTIER
179 : for (const auto& edgeInfo : this->myFrontierList) {
180 : std::cout << "\n " << edgeInfo->effort << ", " << edgeInfo->edge->getID();
181 : }
182 : #endif
183 : std::cout << "\n";
184 : #endif
185 : #ifdef DijkstraRouter_DEBUG_QUERY_VISITED
186 : DijkstraRouter_DEBUG_QUERY_VISITED_OUT << " <edge id=\"" << minEdge->getID() << "\" index=\"" << num_visited << "\" cost=\"" << minimumInfo->effort << "\" time=\"" << minimumInfo->leaveTime << "\"/>\n";
187 : #endif
188 79573570 : minimumInfo->visited = true;
189 : // check whether the destination node was already reached
190 79573570 : if (minEdge == to) {
191 : //propagate last external effort state to destination edge
192 4201787 : if (myExternalEffort != nullptr) {
193 0 : myExternalEffort->update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
194 : }
195 4201787 : this->buildPathFrom(minimumInfo, into);
196 : this->endQuery(num_visited);
197 : #ifdef DijkstraRouter_DEBUG_QUERY_PERF
198 : const double cost = this->recomputeCosts(into, vehicle, msTime);
199 : std::cout << "visited " + toString(num_visited) + " edges (final path length=" + toString(into.size()) + " cost=" << cost << " edges=" + toString(into) + ")\n";
200 : #endif
201 : #ifdef DijkstraRouter_DEBUG_QUERY_VISITED
202 : DijkstraRouter_DEBUG_QUERY_VISITED_OUT << " </interval>\n</edgeData>\n";
203 : #endif
204 4201787 : return true;
205 : }
206 75371783 : std::pop_heap(this->myFrontierList.begin(), this->myFrontierList.end(), myComparator);
207 : this->myFrontierList.pop_back();
208 75371783 : this->myFound.push_back(minimumInfo);
209 75371783 : const double effortDelta = this->getEffort(minEdge, vehicle, minimumInfo->leaveTime);
210 75371783 : const double leaveTime = minimumInfo->leaveTime + this->getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
211 75371783 : if (myExternalEffort != nullptr) {
212 0 : myExternalEffort->update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
213 : }
214 : // check all ways from the node with the minimal length
215 246426208 : for (const std::pair<const E*, const E*>& follower : minEdge->getViaSuccessors(vClass, ignoreTransient)) {
216 171054425 : auto& followerInfo = this->myEdgeInfos[follower.first->getNumericalID()];
217 : // check whether it can be used
218 171054425 : if (followerInfo.prohibited || this->isProhibited(follower.first, vehicle)) {
219 4069308 : continue;
220 : }
221 166985117 : double effort = minimumInfo->effort + effortDelta;
222 166957675 : double time = leaveTime;
223 166957675 : this->updateViaEdgeCost(follower.second, vehicle, time, effort, length);
224 : assert(effort >= minimumInfo->effort);
225 : assert(time >= minimumInfo->leaveTime);
226 166985117 : const double oldEffort = followerInfo.effort;
227 166985117 : if (!followerInfo.visited && effort < oldEffort) {
228 88724340 : followerInfo.effort = effort;
229 88724340 : followerInfo.leaveTime = time;
230 88724340 : followerInfo.prev = minimumInfo;
231 88724340 : if (oldEffort == std::numeric_limits<double>::max()) {
232 84318882 : this->myFrontierList.push_back(&followerInfo);
233 : std::push_heap(this->myFrontierList.begin(), this->myFrontierList.end(), myComparator);
234 : } else {
235 : std::push_heap(this->myFrontierList.begin(),
236 4405458 : std::find(this->myFrontierList.begin(), this->myFrontierList.end(), &followerInfo) + 1,
237 : myComparator);
238 : }
239 : }
240 : }
241 : }
242 : this->endQuery(num_visited);
243 : #ifdef DijkstraRouter_DEBUG_QUERY_PERF
244 : std::cout << "visited " + toString(num_visited) + " edges (unsuccessful path length: " + toString(into.size()) + ")\n";
245 : #endif
246 19927 : if (to != nullptr && !mySilent && !silent) {
247 51690 : this->myErrorMsgHandler->informf(TL("No connection between edge '%' and edge '%' found."), from->getID(), to->getID());
248 : }
249 : #ifdef DijkstraRouter_DEBUG_QUERY_VISITED
250 : DijkstraRouter_DEBUG_QUERY_VISITED_OUT << " </interval>\n</edgeData>\n";
251 : #endif
252 : return false;
253 : }
254 :
255 : private:
256 2528 : DijkstraRouter(const std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo>& edgeInfos, bool unbuildIsWarning,
257 : typename SUMOAbstractRouter<E, V>::Operation effortOperation, typename SUMOAbstractRouter<E, V>::Operation ttOperation, bool silent, EffortCalculator* calc,
258 : const bool havePermissions, const bool haveRestrictions) :
259 : SUMOAbstractRouter<E, V>("DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
260 2528 : mySilent(silent),
261 5056 : myExternalEffort(calc) {
262 224963 : for (const auto& edgeInfo : edgeInfos) {
263 222435 : this->myEdgeInfos.push_back(typename SUMOAbstractRouter<E, V>::EdgeInfo(edgeInfo.edge));
264 : }
265 2528 : }
266 :
267 : private:
268 : /// @brief whether to suppress warning/error if no route was found
269 : bool mySilent;
270 :
271 : /// cache of the last query to enable automated bulk routing
272 : std::tuple<const E*, const V*, SUMOTime> myLastQuery;
273 :
274 : EffortCalculator* const myExternalEffort;
275 :
276 : EdgeInfoByEffortComparator myComparator;
277 : };
|
