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>
33 #include <utils/common/ToString.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 // ===========================================================================
62 template<class E, class V>
63 class DijkstraRouter : public SUMOAbstractRouter<E, V> {
64 public:
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,
225  myComparator);
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 
243 private:
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 
255 private:
257  bool mySilent;
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:35
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...
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.
virtual SUMOAbstractRouter< E, V > * clone()
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)