Eclipse SUMO - Simulation of Urban MObility
DijkstraRouter.h
Go to the documentation of this file.
1/****************************************************************************/
2// Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3// Copyright (C) 2001-2022 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/****************************************************************************/
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>
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// ===========================================================================
62template<class E, class V>
63class DijkstraRouter : public SUMOAbstractRouter<E, V> {
64public:
70 public:
72 bool operator()(const typename SUMOAbstractRouter<E, V>::EdgeInfo* nod1, const typename SUMOAbstractRouter<E, V>::EdgeInfo* nod2) const {
73 if (nod1->effort == nod2->effort) {
74 return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
75 }
76 return nod1->effort > nod2->effort;
77 }
78 };
79
80
82 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 mySilent(silent), myExternalEffort(calc) {
87 for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
88 this->myEdgeInfos.push_back(typename SUMOAbstractRouter<E, V>::EdgeInfo(*i));
89 }
90 }
91
93 virtual ~DijkstraRouter() { }
94
99 clone->setAutoBulkMode(this->myAutoBulkMode);
100 return clone;
101 }
102
105 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 if (this->myEdgeInfos[from->getNumericalID()].prohibited || this->isProhibited(from, vehicle)) {
110 if (!silent) {
111 this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on source edge '" + from->getID() + "'.");
112 }
113 return false;
114 }
115 if (to != nullptr && (this->myEdgeInfos[to->getNumericalID()].prohibited || this->isProhibited(to, vehicle))) {
116 if (!silent) {
117 this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on destination edge '" + to->getID() + "'.");
118 }
119 return false;
120 }
121 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) << "' time: " << STEPS2TIME(msTime) << "\n";
125#endif
126 const SUMOVehicleClass vClass = vehicle == nullptr ? SVC_IGNORING : vehicle->getVClass();
127 std::tuple<const E*, const V*, SUMOTime> query = std::make_tuple(from, vehicle, msTime);
128 if ((this->myBulkMode || (this->myAutoBulkMode && query == myLastQuery)) && !this->myAmClean) {
129#ifdef DijkstraRouter_DEBUG_BULKMODE
130 if (query != myLastQuery) {
131 std::cout << " invalid bulk mode. myLastQuery="
132 << std::get<0>(myLastQuery)->getID() << ","
133 << std::get<1>(myLastQuery)->getID() << ","
134 << time2string(std::get<2>(myLastQuery))
135 << " query="
136 << std::get<0>(query)->getID() << ","
137 << std::get<1>(query)->getID() << ","
138 << time2string(std::get<2>(query))
139 << "\n";
140 }
141#endif
142 const auto& toInfo = this->myEdgeInfos[to->getNumericalID()];
143 if (toInfo.visited) {
144 this->buildPathFrom(&toInfo, into);
145 this->endQuery(1);
146 return true;
147 }
148 } else {
149 this->init(from->getNumericalID(), msTime);
150 if (myExternalEffort != nullptr) {
151 myExternalEffort->setInitialState(from->getNumericalID());
152 }
153 this->myAmClean = false;
154 }
155 myLastQuery = query;
156 // loop
157 int num_visited = 0;
158#ifdef DijkstraRouter_DEBUG_QUERY_VISITED
159 DijkstraRouter_DEBUG_QUERY_VISITED_OUT << "<edgeData>\n <interval begin=\"" << time2string(msTime) << "\" end=\"" << toString(msTime + 1000) << "\">\n";
160#endif
161 while (!this->myFrontierList.empty()) {
162 num_visited += 1;
163 // use the node with the minimal length
164 auto* const minimumInfo = this->myFrontierList.front();
165 const E* const minEdge = minimumInfo->edge;
166#ifdef DijkstraRouter_DEBUG_QUERY
167 std::cout << "DEBUG: hit '" << minEdge->getID() << "' Eff: " << minimumInfo->effort << ", Leave: " << minimumInfo->leaveTime << " Q: ";
168 for (auto& it : this->myFrontierList) {
169 std::cout << "\n " << it->effort << ", " << it->edge->getID();
170 }
171 std::cout << "\n";
172#endif
173#ifdef DijkstraRouter_DEBUG_QUERY_VISITED
174 DijkstraRouter_DEBUG_QUERY_VISITED_OUT << " <edge id=\"" << minEdge->getID() << "\" index=\"" << num_visited << "\" cost=\"" << minimumInfo->effort << "\" time=\"" << minimumInfo->leaveTime << "\"/>\n";
175#endif
176 // check whether the destination node was already reached
177 if (minEdge == to) {
178 //propagate last external effort state to destination edge
179 if (myExternalEffort != nullptr) {
180 myExternalEffort->update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
181 }
182 this->buildPathFrom(minimumInfo, into);
183 this->endQuery(num_visited);
184#ifdef DijkstraRouter_DEBUG_QUERY_PERF
185 const double cost = this->recomputeCosts(into, vehicle, msTime);
186 std::cout << "visited " + toString(num_visited) + " edges (final path length=" + toString(into.size()) + " cost=" << cost << " edges=" + toString(into) + ")\n";
187#endif
188#ifdef DijkstraRouter_DEBUG_QUERY_VISITED
189 DijkstraRouter_DEBUG_QUERY_VISITED_OUT << " </interval>\n</edgeData>\n";
190#endif
191 return true;
192 }
193 std::pop_heap(this->myFrontierList.begin(), this->myFrontierList.end(), myComparator);
194 this->myFrontierList.pop_back();
195 this->myFound.push_back(minimumInfo);
196 minimumInfo->visited = true;
197 const double effortDelta = this->getEffort(minEdge, vehicle, minimumInfo->leaveTime);
198 const double leaveTime = minimumInfo->leaveTime + this->getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
199 if (myExternalEffort != nullptr) {
200 myExternalEffort->update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
201 }
202 // check all ways from the node with the minimal length
203 for (const std::pair<const E*, const E*>& follower : minEdge->getViaSuccessors(vClass)) {
204 auto& followerInfo = this->myEdgeInfos[follower.first->getNumericalID()];
205 // check whether it can be used
206 if (followerInfo.prohibited || this->isProhibited(follower.first, vehicle)) {
207 continue;
208 }
209 double effort = minimumInfo->effort + effortDelta;
210 double time = leaveTime;
211 this->updateViaEdgeCost(follower.second, vehicle, time, effort, length);
212 assert(effort >= minimumInfo->effort);
213 assert(time >= minimumInfo->leaveTime);
214 const double oldEffort = followerInfo.effort;
215 if (!followerInfo.visited && effort < oldEffort) {
216 followerInfo.effort = effort;
217 followerInfo.leaveTime = time;
218 followerInfo.prev = minimumInfo;
219 if (oldEffort == std::numeric_limits<double>::max()) {
220 this->myFrontierList.push_back(&followerInfo);
221 std::push_heap(this->myFrontierList.begin(), this->myFrontierList.end(), myComparator);
222 } else {
223 std::push_heap(this->myFrontierList.begin(),
224 std::find(this->myFrontierList.begin(), this->myFrontierList.end(), &followerInfo) + 1,
226 }
227 }
228 }
229 }
230 this->endQuery(num_visited);
231#ifdef DijkstraRouter_DEBUG_QUERY_PERF
232 std::cout << "visited " + toString(num_visited) + " edges (unsuccessful path length: " + toString(into.size()) + ")\n";
233#endif
234 if (to != nullptr && !mySilent && !silent) {
235 this->myErrorMsgHandler->informf("No connection between edge '%' and edge '%' found.", from->getID(), to->getID());
236 }
237#ifdef DijkstraRouter_DEBUG_QUERY_VISITED
238 DijkstraRouter_DEBUG_QUERY_VISITED_OUT << " </interval>\n</edgeData>\n";
239#endif
240 return false;
241 }
242
243private:
244 DijkstraRouter(const std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo>& edgeInfos, bool unbuildIsWarning,
245 typename SUMOAbstractRouter<E, V>::Operation effortOperation, typename SUMOAbstractRouter<E, V>::Operation ttOperation, bool silent, EffortCalculator* calc,
246 const bool havePermissions, const bool haveRestrictions) :
247 SUMOAbstractRouter<E, V>("DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
248 mySilent(silent),
249 myExternalEffort(calc) {
250 for (const auto& edgeInfo : edgeInfos) {
251 this->myEdgeInfos.push_back(typename SUMOAbstractRouter<E, V>::EdgeInfo(edgeInfo.edge));
252 }
253 }
254
255private:
258
260 std::tuple<const E*, const V*, SUMOTime> myLastQuery;
261
263
265};
#define DijkstraRouter_DEBUG_QUERY_VISITED_OUT
long long int SUMOTime
Definition: GUI.h:36
std::string time2string(SUMOTime t)
convert SUMOTime to string
Definition: SUMOTime.cpp:68
#define STEPS2TIME(x)
Definition: SUMOTime.h:54
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types.
@ SVC_IGNORING
vehicles ignoring classes
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:46
bool operator()(const typename SUMOAbstractRouter< E, V >::EdgeInfo *nod1, const typename SUMOAbstractRouter< E, V >::EdgeInfo *nod2) const
Comparing method.
Computes the shortest path through a network using the Dijkstra algorithm.
bool mySilent
whether to suppress warning/error if no route was found
std::tuple< const E *, const V *, SUMOTime > myLastQuery
cache of the last query to enable automated bulk routing
EffortCalculator *const myExternalEffort
bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false)
Builds the route between the given edges using the minimum effort at the given time The definition of...
virtual SUMOAbstractRouter< E, V > * clone()
DijkstraRouter(const std::vector< E * > &edges, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation effortOperation, typename SUMOAbstractRouter< E, V >::Operation ttOperation=nullptr, bool silent=false, EffortCalculator *calc=nullptr, const bool havePermissions=false, const bool haveRestrictions=false)
Constructor.
EdgeInfoByEffortComparator myComparator
virtual ~DijkstraRouter()
Destructor.
DijkstraRouter(const std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > &edgeInfos, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation effortOperation, typename SUMOAbstractRouter< E, V >::Operation ttOperation, bool silent, EffortCalculator *calc, const bool havePermissions, const bool haveRestrictions)
the effort calculator interface
virtual void setInitialState(const int edge)=0
virtual void update(const int edge, const int prev, const double length)=0
virtual void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:116
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:66
void informf(const std::string &format, T value, Targs... Fargs)
adds a new formatted message
Definition: MsgHandler.h:120
static std::string getIDSecure(const T *obj, const std::string &fallBack="NULL")
get an identifier for Named-like object which may be Null
Definition: Named.h:67
const E *const edge
The current edge.
double effort
Effort to reach the edge.
Operation myTTOperation
The object's operation to perform for travel times.
MsgHandler *const myErrorMsgHandler
the handler for routing errors
const bool myHavePermissions
whether edge permissions need to be considered
bool myBulkMode
whether we are currently operating several route queries in a bulk
double recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime, double *lengthp=nullptr) const
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > myEdgeInfos
The container of edge information.
Operation myOperation
The object's operation to perform.
double getTravelTime(const E *const e, const V *const v, const double t, const double effort) const
double getEffort(const E *const e, const V *const v, double t) const
void updateViaEdgeCost(const E *viaEdge, const V *const v, double &time, double &effort, double &length) const
void init(const int edgeID, const SUMOTime msTime)
bool myAmClean
whether we are already initialized
const bool myHaveRestrictions
whether edge restrictions need to be considered
void buildPathFrom(const typename SUMOAbstractRouter< E, V >::EdgeInfo *rbegin, std::vector< const E * > &edges)
Builds the path from marked edges.
bool myAutoBulkMode
whether we are currently trying to detect bulk mode automatically
void endQuery(int visits)
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFound
list of visited Edges (for resetting)