Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-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 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_VISITED
41 : //#define DijkstraRouter_DEBUG_QUERY_PERF
42 : //#define DijkstraRouter_DEBUG_BULKMODE
43 :
44 : #define DijkstraRouter_DEBUG_QUERY_VISITED_OUT std::cerr
45 :
46 : // ===========================================================================
47 : // class definitions
48 : // ===========================================================================
49 : /**
50 : * @class DijkstraRouter
51 : * @brief Computes the shortest path through a network using the Dijkstra algorithm.
52 : *
53 : * The template parameters are:
54 : * @param E The edge class to use (MSEdge/ROEdge)
55 : * @param V The vehicle class to use (MSVehicle/ROVehicle)
56 : *
57 : * The router is edge-based. It must know the number of edges for internal reasons
58 : * and whether a missing connection between two given edges (unbuild route) shall
59 : * be reported as an error or as a warning.
60 : *
61 : */
62 : template<class E, class V>
63 : class DijkstraRouter : public SUMOAbstractRouter<E, V> {
64 : public:
65 : /**
66 : * @class EdgeInfoByEffortComparator
67 : * Class to compare (and so sort) nodes by their effort
68 : */
69 : class EdgeInfoByEffortComparator {
70 : public:
71 : /// Comparing method
72 30399 : bool operator()(const typename SUMOAbstractRouter<E, V>::EdgeInfo* nod1, const typename SUMOAbstractRouter<E, V>::EdgeInfo* nod2) const {
73 259634292 : if (nod1->effort == nod2->effort) {
74 61659390 : return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
75 : }
76 197974902 : return nod1->effort > nod2->effort;
77 : }
78 : };
79 :
80 :
81 : /// Constructor
82 30185 : DijkstraRouter(const std::vector<E*>& edges, bool unbuildIsWarning, typename SUMOAbstractRouter<E, V>::Operation effortOperation,
83 : typename SUMOAbstractRouter<E, V>::Operation ttOperation = nullptr, bool silent = false, EffortCalculator* calc = nullptr,
84 : const bool havePermissions = false, const bool haveRestrictions = false) :
85 : SUMOAbstractRouter<E, V>("DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
86 60370 : mySilent(silent), myExternalEffort(calc) {
87 5510499 : for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
88 5480314 : this->myEdgeInfos.push_back(typename SUMOAbstractRouter<E, V>::EdgeInfo(*i));
89 : }
90 30185 : }
91 :
92 : /// Destructor
93 32460 : virtual ~DijkstraRouter() { }
94 :
95 2286 : virtual SUMOAbstractRouter<E, V>* clone() {
96 4572 : auto clone = new DijkstraRouter<E, V>(this->myEdgeInfos, this->myErrorMsgHandler == MsgHandler::getWarningInstance(),
97 2286 : this->myOperation, this->myTTOperation, mySilent, myExternalEffort,
98 2286 : this->myHavePermissions, this->myHaveRestrictions);
99 2286 : clone->setAutoBulkMode(this->myAutoBulkMode);
100 2286 : return clone;
101 : }
102 :
103 : /** @brief Builds the route between the given edges using the minimum effort at the given time
104 : The definition of the effort depends on the wished routing scheme */
105 3883396 : bool compute(const E* from, const E* to, const V* const vehicle,
106 : SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
107 : assert(from != nullptr && (vehicle == nullptr || to != nullptr));
108 : // check whether from and to can be used
109 3883396 : if (this->myEdgeInfos[from->getNumericalID()].prohibited || this->isProhibited(from, vehicle)) {
110 102 : if (!silent) {
111 288 : this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on source edge '" + from->getID() + "'.");
112 : }
113 102 : return false;
114 : }
115 3883294 : if (to != nullptr && (this->myEdgeInfos[to->getNumericalID()].prohibited || this->isProhibited(to, vehicle))) {
116 49 : if (!silent) {
117 138 : this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on destination edge '" + to->getID() + "'.");
118 : }
119 49 : return false;
120 : }
121 3882905 : double length = 0.; // dummy for the via edge cost update
122 : this->startQuery();
123 : #ifdef DijkstraRouter_DEBUG_QUERY
124 : std::cout << "DEBUG: starting search for '" << Named::getIDSecure(vehicle) << "' from '" << Named::getIDSecure(from) << "' to '" << Named::getIDSecure(to) << "' time: " << STEPS2TIME(msTime) << "\n";
125 : #endif
126 3883245 : const SUMOVehicleClass vClass = vehicle == nullptr ? SVC_IGNORING : vehicle->getVClass();
127 2696994 : const bool ignoreTransient = vehicle == nullptr ? false : vehicle->ignoreTransientPermissions();
128 : std::tuple<const E*, const V*, SUMOTime> query = std::make_tuple(from, vehicle, msTime);
129 3886109 : if ((this->myBulkMode || (this->myAutoBulkMode && query == myLastQuery)) && !this->myAmClean) {
130 : #ifdef DijkstraRouter_DEBUG_BULKMODE
131 : if (query != myLastQuery) {
132 : std::cout << " invalid bulk mode. myLastQuery="
133 : << std::get<0>(myLastQuery)->getID() << ","
134 : << std::get<1>(myLastQuery)->getID() << ","
135 : << time2string(std::get<2>(myLastQuery))
136 : << " query="
137 : << std::get<0>(query)->getID() << ","
138 : << std::get<1>(query)->getID() << ","
139 : << time2string(std::get<2>(query))
140 : << "\n";
141 : }
142 : #endif
143 31899 : const auto& toInfo = this->myEdgeInfos[to->getNumericalID()];
144 31899 : if (toInfo.visited) {
145 22162 : this->buildPathFrom(&toInfo, into);
146 : this->endQuery(1);
147 22162 : return true;
148 : }
149 : } else {
150 3851346 : this->init(from->getNumericalID(), msTime);
151 3851346 : if (myExternalEffort != nullptr) {
152 0 : myExternalEffort->setInitialState(from->getNumericalID());
153 : }
154 3851346 : this->myAmClean = false;
155 : }
156 : myLastQuery = query;
157 : // loop
158 : int num_visited = 0;
159 : #ifdef DijkstraRouter_DEBUG_QUERY_VISITED
160 : DijkstraRouter_DEBUG_QUERY_VISITED_OUT << "<edgeData>\n <interval begin=\"" << time2string(msTime) << "\" end=\"" << toString(msTime + 1000) << "\">\n";
161 : #endif
162 65078769 : while (!this->myFrontierList.empty()) {
163 65077217 : num_visited += 1;
164 : // use the node with the minimal length
165 65077217 : auto* const minimumInfo = this->myFrontierList.front();
166 65077217 : const E* const minEdge = minimumInfo->edge;
167 : #ifdef DijkstraRouter_DEBUG_QUERY
168 : std::cout << "DEBUG: hit=" << minEdge->getID()
169 : << " TT=" << minimumInfo->effort
170 : << " EF=" << this->getEffort(minEdge, vehicle, minimumInfo->leaveTime)
171 : << " Leave: " << minimumInfo->leaveTime << " Q: ";
172 : for (const auto& edgeInfo : this->myFrontierList) {
173 : std::cout << "\n " << edgeInfo->effort << ", " << edgeInfo->edge->getID();
174 : }
175 : std::cout << "\n";
176 : #endif
177 : #ifdef DijkstraRouter_DEBUG_QUERY_VISITED
178 : DijkstraRouter_DEBUG_QUERY_VISITED_OUT << " <edge id=\"" << minEdge->getID() << "\" index=\"" << num_visited << "\" cost=\"" << minimumInfo->effort << "\" time=\"" << minimumInfo->leaveTime << "\"/>\n";
179 : #endif
180 : // check whether the destination node was already reached
181 65077217 : if (minEdge == to) {
182 : //propagate last external effort state to destination edge
183 3859531 : if (myExternalEffort != nullptr) {
184 0 : myExternalEffort->update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
185 : }
186 3859531 : this->buildPathFrom(minimumInfo, into);
187 : this->endQuery(num_visited);
188 : #ifdef DijkstraRouter_DEBUG_QUERY_PERF
189 : const double cost = this->recomputeCosts(into, vehicle, msTime);
190 : std::cout << "visited " + toString(num_visited) + " edges (final path length=" + toString(into.size()) + " cost=" << cost << " edges=" + toString(into) + ")\n";
191 : #endif
192 : #ifdef DijkstraRouter_DEBUG_QUERY_VISITED
193 : DijkstraRouter_DEBUG_QUERY_VISITED_OUT << " </interval>\n</edgeData>\n";
194 : #endif
195 3859531 : return true;
196 : }
197 61217686 : std::pop_heap(this->myFrontierList.begin(), this->myFrontierList.end(), myComparator);
198 : this->myFrontierList.pop_back();
199 61217686 : this->myFound.push_back(minimumInfo);
200 61217686 : minimumInfo->visited = true;
201 61217686 : const double effortDelta = this->getEffort(minEdge, vehicle, minimumInfo->leaveTime);
202 61217686 : const double leaveTime = minimumInfo->leaveTime + this->getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
203 61217686 : if (myExternalEffort != nullptr) {
204 0 : myExternalEffort->update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
205 : }
206 : // check all ways from the node with the minimal length
207 199657875 : for (const std::pair<const E*, const E*>& follower : minEdge->getViaSuccessors(vClass, ignoreTransient)) {
208 138440189 : auto& followerInfo = this->myEdgeInfos[follower.first->getNumericalID()];
209 : // check whether it can be used
210 138440189 : if (followerInfo.prohibited || this->isProhibited(follower.first, vehicle)) {
211 3759047 : continue;
212 : }
213 134681142 : double effort = minimumInfo->effort + effortDelta;
214 134653769 : double time = leaveTime;
215 134653769 : this->updateViaEdgeCost(follower.second, vehicle, time, effort, length);
216 : assert(effort >= minimumInfo->effort);
217 : assert(time >= minimumInfo->leaveTime);
218 134681142 : const double oldEffort = followerInfo.effort;
219 134681142 : if (!followerInfo.visited && effort < oldEffort) {
220 71724479 : followerInfo.effort = effort;
221 71724479 : followerInfo.leaveTime = time;
222 71724479 : followerInfo.prev = minimumInfo;
223 71724479 : if (oldEffort == std::numeric_limits<double>::max()) {
224 68335318 : this->myFrontierList.push_back(&followerInfo);
225 : std::push_heap(this->myFrontierList.begin(), this->myFrontierList.end(), myComparator);
226 : } else {
227 : std::push_heap(this->myFrontierList.begin(),
228 3389161 : std::find(this->myFrontierList.begin(), this->myFrontierList.end(), &followerInfo) + 1,
229 : myComparator);
230 : }
231 : }
232 : }
233 : }
234 : this->endQuery(num_visited);
235 : #ifdef DijkstraRouter_DEBUG_QUERY_PERF
236 : std::cout << "visited " + toString(num_visited) + " edges (unsuccessful path length: " + toString(into.size()) + ")\n";
237 : #endif
238 1552 : if (to != nullptr && !mySilent && !silent) {
239 2154 : this->myErrorMsgHandler->informf(TL("No connection between edge '%' and edge '%' found."), from->getID(), to->getID());
240 : }
241 : #ifdef DijkstraRouter_DEBUG_QUERY_VISITED
242 : DijkstraRouter_DEBUG_QUERY_VISITED_OUT << " </interval>\n</edgeData>\n";
243 : #endif
244 : return false;
245 : }
246 :
247 : private:
248 2286 : DijkstraRouter(const std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo>& edgeInfos, bool unbuildIsWarning,
249 : typename SUMOAbstractRouter<E, V>::Operation effortOperation, typename SUMOAbstractRouter<E, V>::Operation ttOperation, bool silent, EffortCalculator* calc,
250 : const bool havePermissions, const bool haveRestrictions) :
251 : SUMOAbstractRouter<E, V>("DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
252 2286 : mySilent(silent),
253 4572 : myExternalEffort(calc) {
254 196816 : for (const auto& edgeInfo : edgeInfos) {
255 194530 : this->myEdgeInfos.push_back(typename SUMOAbstractRouter<E, V>::EdgeInfo(edgeInfo.edge));
256 : }
257 2286 : }
258 :
259 : private:
260 : /// @brief whether to suppress warning/error if no route was found
261 : bool mySilent;
262 :
263 : /// cache of the last query to enable automated bulk routing
264 : std::tuple<const E*, const V*, SUMOTime> myLastQuery;
265 :
266 : EffortCalculator* const myExternalEffort;
267 :
268 : EdgeInfoByEffortComparator myComparator;
269 : };
|
