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 /****************************************************************************/
17 // Dijkstra shortest path algorithm using travel time or other values
18 /****************************************************************************/
19 #ifndef DijkstraRouter_h
20 #define DijkstraRouter_h
21 
22 
23 // ===========================================================================
24 // included modules
25 // ===========================================================================
26 #include <config.h>
27 
28 #include <cassert>
29 #include <string>
30 #include <functional>
31 #include <vector>
32 #include <set>
33 #include <limits>
34 #include <algorithm>
35 #include <iterator>
36 #include <utils/common/ToString.h>
38 #include <utils/common/StdDefs.h>
39 #include "EffortCalculator.h"
40 #include "SUMOAbstractRouter.h"
41 
42 //#define DijkstraRouter_DEBUG_QUERY
43 //#define DijkstraRouter_DEBUG_QUERY_PERF
44 
45 // ===========================================================================
46 // class definitions
47 // ===========================================================================
62 template<class E, class V, class BASE>
63 class DijkstraRouter : public BASE {
64 public:
70  public:
72  bool operator()(const typename BASE::EdgeInfo* nod1, const typename BASE::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 BASE::Operation effortOperation,
83  typename BASE::Operation ttOperation = nullptr, bool silent = false, EffortCalculator* calc = nullptr) :
84  BASE("DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation),
85  mySilent(silent), myExternalEffort(calc) {
86  for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
87  myEdgeInfos.push_back(typename BASE::EdgeInfo(*i));
88  }
89  }
90 
92  virtual ~DijkstraRouter() { }
93 
95  return new DijkstraRouter<E, V, BASE>(myEdgeInfos, this->myErrorMsgHandler == MsgHandler::getWarningInstance(), this->myOperation, this->myTTOperation, mySilent, myExternalEffort);
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  virtual 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 != 0 && (vehicle == 0 || to != 0));
116  // check whether from and to can be used
117  if (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 (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 (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->inform("No connection between edge '" + from->getID() + "' and edge '" + to->getID() + "' found.");
224  }
225  return false;
226  }
227 
228 
230  void buildPathFrom(const typename BASE::EdgeInfo* rbegin, std::vector<const E*>& edges) {
231  std::vector<const E*> tmp;
232  while (rbegin != 0) {
233  tmp.push_back(rbegin->edge);
234  rbegin = rbegin->prev;
235  }
236  std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
237  }
238 
239  const typename BASE::EdgeInfo& getEdgeInfo(int index) const {
240  return myEdgeInfos[index];
241  }
242 
243 private:
244  DijkstraRouter(const std::vector<typename BASE::EdgeInfo>& edgeInfos, bool unbuildIsWarning,
245  typename BASE::Operation effortOperation, typename BASE::Operation ttOperation, bool silent, EffortCalculator* calc) :
246  BASE("DijkstraRouter", unbuildIsWarning, effortOperation, ttOperation),
247  mySilent(silent),
248  myExternalEffort(calc) {
249  for (const auto& edgeInfo : edgeInfos) {
250  myEdgeInfos.push_back(typename BASE::EdgeInfo(edgeInfo.edge));
251  }
252  }
253 
254 private:
256  bool mySilent;
257 
259 
261  std::vector<typename BASE::EdgeInfo> myEdgeInfos;
262 
264  std::vector<typename BASE::EdgeInfo*> myFrontierList;
266  std::vector<typename BASE::EdgeInfo*> myFound;
267 
269 };
270 
271 
272 #endif
273 
274 /****************************************************************************/
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:72
long long int SUMOTime
Definition: SUMOTime.h:35
std::vector< typename BASE::EdgeInfo * > myFound
list of visited Edges (for resetting)
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
void buildPathFrom(const typename BASE::EdgeInfo *rbegin, std::vector< const E *> &edges)
Builds the path from marked edges.
DijkstraRouter(const std::vector< typename BASE::EdgeInfo > &edgeInfos, bool unbuildIsWarning, typename BASE::Operation effortOperation, typename BASE::Operation ttOperation, bool silent, EffortCalculator *calc)
bool operator()(const typename BASE::EdgeInfo *nod1, const typename BASE::EdgeInfo *nod2) const
Comparing method.
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:70
virtual SUMOAbstractRouter< E, V > * clone()
std::vector< typename BASE::EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
the effort calculator interface
EffortCalculator *const myExternalEffort
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:48
virtual void update(const int edge, const int prev, const double length)=0
Computes the shortest path through a network using the Dijkstra algorithm.
std::vector< typename BASE::EdgeInfo > myEdgeInfos
The container of edge information.
#define STEPS2TIME(x)
Definition: SUMOTime.h:57
double getTravelTime(const ROEdge *const edge, const ROVehicle *const, double)
EdgeInfoByEffortComparator myComparator
const BASE::EdgeInfo & getEdgeInfo(int index) const
virtual 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 BASE::Operation effortOperation, typename BASE::Operation ttOperation=nullptr, bool silent=false, EffortCalculator *calc=nullptr)
Constructor.
virtual ~DijkstraRouter()
Destructor.
bool mySilent
whether to supress warning/error if no route was found
virtual void setInitialState(const int edge)=0
vehicles ignoring classes