Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2026 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 7583 : bool operator()(const typename SUMOAbstractRouter<E, V>::EdgeInfo* nod1, const typename SUMOAbstractRouter<E, V>::EdgeInfo* nod2) const {
74 351055987 : if (nod1->effort == nod2->effort) {
75 70110704 : return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
76 : }
77 280950983 : return nod1->effort > nod2->effort;
78 : }
79 : };
80 :
81 :
82 : /// Constructor
83 24112 : 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 48224 : mySilent(silent), myExternalEffort(calc) {
88 5919714 : for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
89 5895602 : this->myEdgeInfos.push_back(typename SUMOAbstractRouter<E, V>::EdgeInfo(*i));
90 : }
91 24112 : }
92 :
93 : /// Destructor
94 26788 : virtual ~DijkstraRouter() { }
95 :
96 2696 : virtual SUMOAbstractRouter<E, V>* clone() {
97 5392 : auto clone = new DijkstraRouter<E, V>(this->myEdgeInfos, this->myErrorMsgHandler == MsgHandler::getWarningInstance(),
98 2696 : this->myOperation, this->myTTOperation, mySilent, myExternalEffort,
99 2696 : this->myHavePermissions, this->myHaveRestrictions);
100 2696 : clone->setAutoBulkMode(this->myAutoBulkMode);
101 2696 : 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 4506565 : 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 4506565 : if (this->isProhibited(from, vehicle, STEPS2TIME(msTime))) {
111 96 : if (!silent) {
112 288 : this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on source edge '" + from->getID() + "'.");
113 : }
114 96 : return false;
115 : }
116 : // technically, a temporary permission might be lifted by the time of arrival
117 4506469 : if (to != nullptr && this->isProhibited(to, vehicle, STEPS2TIME(msTime))) {
118 139 : if (!silent) {
119 138 : this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on destination edge '" + to->getID() + "'.");
120 : }
121 139 : return false;
122 : }
123 4506020 : double length = 0.; // dummy for the via edge cost update
124 : this->startQuery();
125 : #ifdef DijkstraRouter_DEBUG_QUERY
126 : std::cout << "DEBUG: starting search for '" << Named::getIDSecure(vehicle) << "' from '" << Named::getIDSecure(from) << "' to '" << Named::getIDSecure(to) << "' time: " << STEPS2TIME(msTime) << "\n";
127 : #endif
128 4506330 : const SUMOVehicleClass vClass = vehicle == nullptr ? SVC_IGNORING : vehicle->getVClass();
129 3124288 : const bool ignoreTransient = vehicle == nullptr ? false : vehicle->ignoreTransientPermissions();
130 : std::tuple<const E*, const V*, SUMOTime> query = std::make_tuple(from, vehicle, msTime);
131 4510698 : if ((this->myBulkMode || (this->myAutoBulkMode && query == myLastQuery)) && !this->myAmClean) {
132 : #ifdef DijkstraRouter_DEBUG_BULKMODE
133 : if (query != myLastQuery) {
134 : std::cout << " invalid bulk mode. myLastQuery="
135 : << std::get<0>(myLastQuery)->getID() << ","
136 : << std::get<1>(myLastQuery)->getID() << ","
137 : << time2string(std::get<2>(myLastQuery))
138 : << " query="
139 : << std::get<0>(query)->getID() << ","
140 : << std::get<1>(query)->getID() << ","
141 : << time2string(std::get<2>(query))
142 : << "\n";
143 : } else {
144 : std::cout << " using bulk mode\n";
145 : }
146 : #endif
147 33486 : const auto& toInfo = this->myEdgeInfos[to->getNumericalID()];
148 33486 : if (toInfo.visited) {
149 22991 : this->buildPathFrom(&toInfo, into);
150 : this->endQuery(1);
151 : #ifdef DijkstraRouter_DEBUG_QUERY_PERF
152 : std::cout << " instant bulk success for vehicle " << vehicle->getID() << "\n";
153 : #endif
154 22991 : return true;
155 : }
156 : } else {
157 4472844 : this->init(from->getNumericalID(), msTime);
158 4472844 : if (myExternalEffort != nullptr) {
159 0 : myExternalEffort->setInitialState(from->getNumericalID());
160 : }
161 4472844 : this->myAmClean = false;
162 : }
163 : myLastQuery = query;
164 : // loop
165 : int num_visited = 0;
166 : #ifdef DijkstraRouter_DEBUG_QUERY_VISITED
167 : DijkstraRouter_DEBUG_QUERY_VISITED_OUT << "<edgeData>\n <interval begin=\"" << time2string(msTime) << "\" end=\"" << toString(msTime + 1000) << "\" id=\"" << Named::getIDSecure(vehicle) << "\">\n";
168 : #endif
169 77170137 : while (!this->myFrontierList.empty()) {
170 77150180 : num_visited += 1;
171 : // use the node with the minimal length
172 77150180 : auto* const minimumInfo = this->myFrontierList.front();
173 77150180 : const E* const minEdge = minimumInfo->edge;
174 : #ifdef DijkstraRouter_DEBUG_QUERY
175 : std::cout << "DEBUG: hit=" << minEdge->getID()
176 : << " TT=" << minimumInfo->effort
177 : << " EF=" << this->getEffort(minEdge, vehicle, minimumInfo->leaveTime)
178 : << " Leave: " << minimumInfo->leaveTime << " Q: ";
179 : #ifdef DijkstraRouter_DEBUG_QUERY_FRONTIER
180 : for (const auto& edgeInfo : this->myFrontierList) {
181 : std::cout << "\n " << edgeInfo->effort << ", " << edgeInfo->edge->getID();
182 : }
183 : #endif
184 : std::cout << "\n";
185 : #endif
186 : #ifdef DijkstraRouter_DEBUG_QUERY_VISITED
187 : DijkstraRouter_DEBUG_QUERY_VISITED_OUT << " <edge id=\"" << minEdge->getID() << "\" index=\"" << num_visited << "\" cost=\"" << minimumInfo->effort << "\" time=\"" << minimumInfo->leaveTime << "\"/>\n";
188 : #endif
189 77150180 : minimumInfo->visited = true;
190 : // check whether the destination node was already reached
191 77150180 : if (minEdge == to) {
192 : //propagate last external effort state to destination edge
193 4463382 : if (myExternalEffort != nullptr) {
194 0 : myExternalEffort->update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
195 : }
196 4463382 : this->buildPathFrom(minimumInfo, into);
197 : this->endQuery(num_visited);
198 : #ifdef DijkstraRouter_DEBUG_QUERY_PERF
199 : const double cost = this->recomputeCosts(into, vehicle, msTime);
200 : std::cout << "visited " + toString(num_visited) + " edges (final path length=" + toString(into.size()) + " cost=" << cost << " edges=" + toString(into) + ")\n";
201 : #endif
202 : #ifdef DijkstraRouter_DEBUG_QUERY_VISITED
203 : DijkstraRouter_DEBUG_QUERY_VISITED_OUT << " </interval>\n</edgeData>\n";
204 : #endif
205 4463382 : return true;
206 : }
207 72686798 : std::pop_heap(this->myFrontierList.begin(), this->myFrontierList.end(), myComparator);
208 : this->myFrontierList.pop_back();
209 72686798 : this->myFound.push_back(minimumInfo);
210 72686798 : const double effortDelta = this->getEffort(minEdge, vehicle, minimumInfo->leaveTime);
211 72686798 : const double leaveTime = minimumInfo->leaveTime + this->getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
212 72686798 : if (myExternalEffort != nullptr) {
213 0 : myExternalEffort->update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
214 : }
215 : // check all ways from the node with the minimal length
216 239989547 : for (const std::pair<const E*, const E*>& follower : minEdge->getViaSuccessors(vClass, ignoreTransient)) {
217 167302749 : auto& followerInfo = this->myEdgeInfos[follower.first->getNumericalID()];
218 : // check whether it can be used
219 167290946 : if (this->isProhibited(follower.first, vehicle, leaveTime)) {
220 4126593 : continue;
221 : }
222 163176156 : double effort = minimumInfo->effort + effortDelta;
223 163164353 : double time = leaveTime;
224 163164353 : this->updateViaEdgeCost(follower.second, vehicle, time, effort, length);
225 : assert(effort >= minimumInfo->effort);
226 : assert(time >= minimumInfo->leaveTime);
227 163176156 : const double oldEffort = followerInfo.effort;
228 163176156 : if (!followerInfo.visited && effort < oldEffort) {
229 85898099 : followerInfo.effort = effort;
230 85898099 : followerInfo.leaveTime = time;
231 85898099 : followerInfo.prev = minimumInfo;
232 85898099 : if (oldEffort == std::numeric_limits<double>::max()) {
233 81483572 : this->myFrontierList.push_back(&followerInfo);
234 : std::push_heap(this->myFrontierList.begin(), this->myFrontierList.end(), myComparator);
235 : } else {
236 : std::push_heap(this->myFrontierList.begin(),
237 4414527 : std::find(this->myFrontierList.begin(), this->myFrontierList.end(), &followerInfo) + 1,
238 : myComparator);
239 : }
240 : }
241 : }
242 : }
243 : this->endQuery(num_visited);
244 : #ifdef DijkstraRouter_DEBUG_QUERY_PERF
245 : std::cout << "visited " + toString(num_visited) + " edges (unsuccessful path length: " + toString(into.size()) + ")\n";
246 : #endif
247 19957 : if (to != nullptr && !mySilent && !silent) {
248 51690 : this->myErrorMsgHandler->informf(TL("No connection between edge '%' and edge '%' found."), from->getID(), to->getID());
249 : }
250 : #ifdef DijkstraRouter_DEBUG_QUERY_VISITED
251 : DijkstraRouter_DEBUG_QUERY_VISITED_OUT << " </interval>\n</edgeData>\n";
252 : #endif
253 : return false;
254 : }
255 :
256 : private:
257 2696 : DijkstraRouter(const std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo>& edgeInfos, bool unbuildIsWarning,
258 : typename SUMOAbstractRouter<E, V>::Operation effortOperation, typename SUMOAbstractRouter<E, V>::Operation ttOperation, bool silent, EffortCalculator* calc,
259 : const bool havePermissions, const bool haveRestrictions) :
260 : SUMOAbstractRouter<E, V>("DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
261 2696 : mySilent(silent),
262 5392 : myExternalEffort(calc) {
263 242177 : for (const auto& edgeInfo : edgeInfos) {
264 239481 : this->myEdgeInfos.push_back(typename SUMOAbstractRouter<E, V>::EdgeInfo(edgeInfo.edge));
265 : }
266 2696 : }
267 :
268 : private:
269 : /// @brief whether to suppress warning/error if no route was found
270 : bool mySilent;
271 :
272 : /// cache of the last query to enable automated bulk routing
273 : std::tuple<const E*, const V*, SUMOTime> myLastQuery;
274 :
275 : EffortCalculator* const myExternalEffort;
276 :
277 : EdgeInfoByEffortComparator myComparator;
278 : };
|
