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-2019 German Aerospace Center (DLR) and others.
4 // This program and the accompanying materials
5 // are made available under the terms of the Eclipse Public License v2.0
6 // which accompanies this distribution, and is available at
7 // http://www.eclipse.org/legal/epl-v20.html
8 // SPDX-License-Identifier: EPL-2.0
9 /****************************************************************************/
16 // Dijkstra shortest path algorithm using travel time or other values
17 /****************************************************************************/
18 #ifndef DijkstraRouter_h
19 #define DijkstraRouter_h
20 
21 
22 // ===========================================================================
23 // included modules
24 // ===========================================================================
25 #include <config.h>
26 
27 #include <cassert>
28 #include <string>
29 #include <functional>
30 #include <vector>
31 #include <set>
32 #include <limits>
33 #include <algorithm>
34 #include <iterator>
35 #include <utils/common/ToString.h>
37 #include <utils/common/StdDefs.h>
38 #include "EffortCalculator.h"
39 #include "SUMOAbstractRouter.h"
40 
41 //#define DijkstraRouter_DEBUG_QUERY
42 //#define DijkstraRouter_DEBUG_QUERY_PERF
43 
44 // ===========================================================================
45 // class definitions
46 // ===========================================================================
60 template<class E, class V>
61 class DijkstraRouter : public SUMOAbstractRouter<E, V> {
62 public:
68  public:
70  bool operator()(const typename SUMOAbstractRouter<E, V>::EdgeInfo* nod1, const typename SUMOAbstractRouter<E, V>::EdgeInfo* nod2) const {
71  if (nod1->effort == nod2->effort) {
72  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
73  }
74  return nod1->effort > nod2->effort;
75  }
76  };
77 
78 
80  DijkstraRouter(const std::vector<E*>& edges, bool unbuildIsWarning, typename SUMOAbstractRouter<E, V>::Operation effortOperation,
81  typename SUMOAbstractRouter<E, V>::Operation ttOperation = nullptr, bool silent = false, EffortCalculator* calc = nullptr,
82  const bool havePermissions = false, const bool haveRestrictions = false) :
83  SUMOAbstractRouter<E, V>("DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
84  mySilent(silent), myExternalEffort(calc) {
85  for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
86  myEdgeInfos.push_back(typename SUMOAbstractRouter<E, V>::EdgeInfo(*i));
87  }
88  }
89 
91  virtual ~DijkstraRouter() { }
92 
96  }
97 
98  void init() {
99  // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
100  for (auto& edgeInfo : myFrontierList) {
101  edgeInfo->reset();
102  }
103  myFrontierList.clear();
104  for (auto& edgeInfo : myFound) {
105  edgeInfo->reset();
106  }
107  myFound.clear();
108  }
109 
110 
113  bool compute(const E* from, const E* to, const V* const vehicle,
114  SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
115  assert(from != nullptr && (vehicle == nullptr || to != nullptr));
116  // check whether from and to can be used
117  if (myEdgeInfos[from->getNumericalID()].prohibited || this->isProhibited(from, vehicle)) {
118  if (!silent) {
119  this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on source edge '" + from->getID() + "'.");
120  }
121  return false;
122  }
123  if (to != nullptr && (myEdgeInfos[to->getNumericalID()].prohibited || this->isProhibited(to, vehicle))) {
124  if (!silent) {
125  this->myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on destination edge '" + to->getID() + "'.");
126  }
127  return false;
128  }
129  double length = 0.; // dummy for the via edge cost update
130  this->startQuery();
131 #ifdef DijkstraRouter_DEBUG_QUERY
132  std::cout << "DEBUG: starting search for '" << Named::getIDSecure(vehicle) << "' time: " << STEPS2TIME(msTime) << "\n";
133 #endif
134  const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
135  if (this->myBulkMode) {
136  const auto& toInfo = myEdgeInfos[to->getNumericalID()];
137  if (toInfo.visited) {
138  buildPathFrom(&toInfo, into);
139  this->endQuery(1);
140  return true;
141  }
142  } else {
143  init();
144  // add begin node
145  auto* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
146  fromInfo->effort = 0.;
147  fromInfo->prev = nullptr;
148  fromInfo->leaveTime = STEPS2TIME(msTime);
149  if (myExternalEffort != nullptr) {
150  myExternalEffort->setInitialState(fromInfo->edge->getNumericalID());
151  }
152  myFrontierList.push_back(fromInfo);
153  }
154  // loop
155  int num_visited = 0;
156  while (!myFrontierList.empty()) {
157  num_visited += 1;
158  // use the node with the minimal length
159  auto* const minimumInfo = myFrontierList.front();
160  const E* const minEdge = minimumInfo->edge;
161 #ifdef DijkstraRouter_DEBUG_QUERY
162  std::cout << "DEBUG: hit '" << minEdge->getID() << "' Eff: " << minimumInfo->effort << ", Leave: " << minimumInfo->leaveTime << " Q: ";
163  for (auto& it : myFrontierList) {
164  std::cout << it->effort << "," << it->edge->getID() << " ";
165  }
166  std::cout << "\n";
167 #endif
168  // check whether the destination node was already reached
169  if (minEdge == to) {
170  //propagate last external effort state to destination edge
171  if (myExternalEffort != nullptr) {
172  myExternalEffort->update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
173  }
174  buildPathFrom(minimumInfo, into);
175  this->endQuery(num_visited);
176 #ifdef DijkstraRouter_DEBUG_QUERY_PERF
177  std::cout << "visited " + toString(num_visited) + " edges (final path length=" + toString(into.size()) + " edges=" + toString(into) + ")\n";
178 #endif
179  return true;
180  }
181  std::pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
182  myFrontierList.pop_back();
183  myFound.push_back(minimumInfo);
184  minimumInfo->visited = true;
185  const double effortDelta = this->getEffort(minEdge, vehicle, minimumInfo->leaveTime);
186  const double leaveTime = minimumInfo->leaveTime + this->getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
187  if (myExternalEffort != nullptr) {
188  myExternalEffort->update(minEdge->getNumericalID(), minimumInfo->prev->edge->getNumericalID(), minEdge->getLength());
189  }
190  // check all ways from the node with the minimal length
191  for (const std::pair<const E*, const E*>& follower : minEdge->getViaSuccessors(vClass)) {
192  auto* const followerInfo = &(myEdgeInfos[follower.first->getNumericalID()]);
193  // check whether it can be used
194  if (followerInfo->prohibited || this->isProhibited(follower.first, vehicle)) {
195  continue;
196  }
197  double effort = minimumInfo->effort + effortDelta;
198  double time = leaveTime;
199  this->updateViaEdgeCost(follower.second, vehicle, time, effort, length);
200  assert(effort >= minimumInfo->effort);
201  assert(time >= minimumInfo->leaveTime);
202  const double oldEffort = followerInfo->effort;
203  if (!followerInfo->visited && effort < oldEffort) {
204  followerInfo->effort = effort;
205  followerInfo->leaveTime = time;
206  followerInfo->prev = minimumInfo;
207  if (oldEffort == std::numeric_limits<double>::max()) {
208  myFrontierList.push_back(followerInfo);
209  std::push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
210  } else {
211  std::push_heap(myFrontierList.begin(),
212  std::find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
213  myComparator);
214  }
215  }
216  }
217  }
218  this->endQuery(num_visited);
219 #ifdef DijkstraRouter_DEBUG_QUERY_PERF
220  std::cout << "visited " + toString(num_visited) + " edges (unsuccessful path length: " + toString(into.size()) + ")\n";
221 #endif
222  if (to != 0 && !mySilent && !silent) {
223  this->myErrorMsgHandler->informf("No connection between edge '%' and edge '%' found.", from->getID(), to->getID());
224  }
225  return false;
226  }
227 
228 
229  void prohibit(const std::vector<E*>& toProhibit) {
230  for (E* const edge : this->myProhibited) {
231  myEdgeInfos[edge->getNumericalID()].prohibited = false;
232  }
233  for (E* const edge : toProhibit) {
234  myEdgeInfos[edge->getNumericalID()].prohibited = true;
235  }
236  this->myProhibited = toProhibit;
237  }
238 
239 
241  void buildPathFrom(const typename SUMOAbstractRouter<E, V>::EdgeInfo* rbegin, std::vector<const E*>& edges) {
242  std::vector<const E*> tmp;
243  while (rbegin != 0) {
244  tmp.push_back(rbegin->edge);
245  rbegin = rbegin->prev;
246  }
247  std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
248  }
249 
250  const typename SUMOAbstractRouter<E, V>::EdgeInfo& getEdgeInfo(int index) const {
251  return myEdgeInfos[index];
252  }
253 
254 private:
255  DijkstraRouter(const std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo>& edgeInfos, bool unbuildIsWarning,
256  typename SUMOAbstractRouter<E, V>::Operation effortOperation, typename SUMOAbstractRouter<E, V>::Operation ttOperation, bool silent, EffortCalculator* calc,
257  const bool havePermissions, const bool haveRestrictions) :
258  SUMOAbstractRouter<E, V>("DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
259  mySilent(silent),
260  myExternalEffort(calc) {
261  for (const auto& edgeInfo : edgeInfos) {
262  myEdgeInfos.push_back(typename SUMOAbstractRouter<E, V>::EdgeInfo(edgeInfo.edge));
263  }
264  }
265 
266 private:
268  bool mySilent;
269 
271 
273  std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo> myEdgeInfos;
274 
276  std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFrontierList;
278  std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFound;
279 
281 };
282 
283 
284 #endif
285 
286 /****************************************************************************/
DijkstraRouter::EdgeInfoByEffortComparator
Definition: DijkstraRouter.h:67
SUMOVehicleClass
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types.
Definition: SUMOVehicleClass.h:133
ToString.h
DijkstraRouter::~DijkstraRouter
virtual ~DijkstraRouter()
Destructor.
Definition: DijkstraRouter.h:91
SUMOAbstractRouter::myHavePermissions
const bool myHavePermissions
whether edge permissions need to be considered
Definition: SUMOAbstractRouter.h:248
DijkstraRouter::myFound
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFound
list of visited Edges (for resetting)
Definition: DijkstraRouter.h:278
MsgHandler.h
SUMOAbstractRouter::getEffort
double getEffort(const E *const e, const V *const v, double t) const
Definition: SUMOAbstractRouter.h:216
MsgHandler::inform
virtual void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:118
SUMOTime
long long int SUMOTime
Definition: SUMOTime.h:34
SUMOAbstractRouter::myProhibited
std::vector< E * > myProhibited
Definition: SUMOAbstractRouter.h:253
DijkstraRouter::myComparator
EdgeInfoByEffortComparator myComparator
Definition: DijkstraRouter.h:280
SUMOAbstractRouter::startQuery
void startQuery()
Definition: SUMOAbstractRouter.h:220
DijkstraRouter::DijkstraRouter
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.
Definition: DijkstraRouter.h:80
SUMOAbstractRouter::EdgeInfo::effort
double effort
Effort to reach the edge.
Definition: SUMOAbstractRouter.h:65
SUMOAbstractRouter::myOperation
Operation myOperation
The object's operation to perform.
Definition: SUMOAbstractRouter.h:239
DijkstraRouter
Computes the shortest path through a network using the Dijkstra algorithm.
Definition: DijkstraRouter.h:61
DijkstraRouter::mySilent
bool mySilent
whether to supress warning/error if no route was found
Definition: DijkstraRouter.h:268
DijkstraRouter::buildPathFrom
void buildPathFrom(const typename SUMOAbstractRouter< E, V >::EdgeInfo *rbegin, std::vector< const E * > &edges)
Builds the path from marked edges.
Definition: DijkstraRouter.h:241
DijkstraRouter::init
void init()
Definition: DijkstraRouter.h:98
MsgHandler::getWarningInstance
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:68
EffortCalculator::update
virtual void update(const int edge, const int prev, const double length)=0
STEPS2TIME
#define STEPS2TIME(x)
Definition: SUMOTime.h:56
DijkstraRouter::EdgeInfoByEffortComparator::operator()
bool operator()(const typename SUMOAbstractRouter< E, V >::EdgeInfo *nod1, const typename SUMOAbstractRouter< E, V >::EdgeInfo *nod2) const
Comparing method.
Definition: DijkstraRouter.h:70
SUMOAbstractRouter::myHaveRestrictions
const bool myHaveRestrictions
whether edge restrictions need to be considered
Definition: SUMOAbstractRouter.h:251
DijkstraRouter::DijkstraRouter
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)
Definition: DijkstraRouter.h:255
DijkstraRouter::compute
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...
Definition: DijkstraRouter.h:113
SUMOAbstractRouter::EdgeInfo
Definition: SUMOAbstractRouter.h:53
DijkstraRouter::myFrontierList
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
Definition: DijkstraRouter.h:276
SUMOAbstractRouter::EdgeInfo::prev
const EdgeInfo * prev
The previous edge.
Definition: SUMOAbstractRouter.h:75
DijkstraRouter::getEdgeInfo
const SUMOAbstractRouter< E, V >::EdgeInfo & getEdgeInfo(int index) const
Definition: DijkstraRouter.h:250
EffortCalculator.h
SUMOAbstractRouter::EdgeInfo::edge
const E *const edge
The current edge.
Definition: SUMOAbstractRouter.h:62
SUMOAbstractRouter::myBulkMode
bool myBulkMode
whether we are currently operating several route queries in a bulk
Definition: SUMOAbstractRouter.h:245
SUMOAbstractRouter::getTravelTime
double getTravelTime(const E *const e, const V *const v, const double t, const double effort) const
Definition: SUMOAbstractRouter.h:165
SUMOAbstractRouter
Definition: SUMOAbstractRouter.h:46
SUMOAbstractRouter::endQuery
void endQuery(int visits)
Definition: SUMOAbstractRouter.h:225
toString
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:47
DijkstraRouter::prohibit
void prohibit(const std::vector< E * > &toProhibit)
Definition: DijkstraRouter.h:229
SUMOAbstractRouter::myErrorMsgHandler
MsgHandler *const myErrorMsgHandler
the handler for routing errors
Definition: SUMOAbstractRouter.h:236
SUMOAbstractRouter::updateViaEdgeCost
void updateViaEdgeCost(const E *viaEdge, const V *const v, double &time, double &effort, double &length) const
Definition: SUMOAbstractRouter.h:169
EffortCalculator
the effort calculator interface
Definition: EffortCalculator.h:32
MsgHandler::informf
void informf(const std::string &format, T value, Targs... Fargs)
adds a new formatted message
Definition: MsgHandler.h:115
config.h
Named::getIDSecure
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:69
StdDefs.h
DijkstraRouter::myExternalEffort
EffortCalculator *const myExternalEffort
Definition: DijkstraRouter.h:270
EffortCalculator::setInitialState
virtual void setInitialState(const int edge)=0
SVC_IGNORING
@ SVC_IGNORING
vehicles ignoring classes
Definition: SUMOVehicleClass.h:135
SUMOAbstractRouter.h
DijkstraRouter::clone
virtual SUMOAbstractRouter< E, V > * clone()
Definition: DijkstraRouter.h:93
SUMOAbstractRouter::myTTOperation
Operation myTTOperation
The object's operation to perform for travel times.
Definition: SUMOAbstractRouter.h:242
DijkstraRouter::myEdgeInfos
std::vector< typename SUMOAbstractRouter< E, V >::EdgeInfo > myEdgeInfos
The container of edge information.
Definition: DijkstraRouter.h:273