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-2017 German Aerospace Center (DLR) and others.
4 /****************************************************************************/
5 //
6 // This program and the accompanying materials
7 // are made available under the terms of the Eclipse Public License v2.0
8 // which accompanies this distribution, and is available at
9 // http://www.eclipse.org/legal/epl-v20.html
10 //
11 /****************************************************************************/
19 // Dijkstra shortest path algorithm using travel time or other values
20 /****************************************************************************/
21 #ifndef DijkstraRouter_h
22 #define DijkstraRouter_h
23 
24 
25 // ===========================================================================
26 // included modules
27 // ===========================================================================
28 #ifdef _MSC_VER
29 #include <windows_config.h>
30 #else
31 #include <config.h>
32 #endif
33 
34 #include <cassert>
35 #include <string>
36 #include <functional>
37 #include <vector>
38 #include <set>
39 #include <limits>
40 #include <algorithm>
41 #include <iterator>
42 #include <utils/common/ToString.h>
44 #include <utils/common/StdDefs.h>
45 #include "SUMOAbstractRouter.h"
46 
47 //#define DijkstraRouter_DEBUG_QUERY
48 //#define DijkstraRouter_DEBUG_QUERY_PERF
49 
50 // ===========================================================================
51 // class definitions
52 // ===========================================================================
68 template<class E, class V, class PF>
69 class DijkstraRouter : public SUMOAbstractRouter<E, V>, public PF {
70 
71 public:
72  typedef double(* Operation)(const E* const, const V* const, double);
73 
79  class EdgeInfo {
80  public:
82  EdgeInfo(const E* const e)
83  : edge(e), effort(std::numeric_limits<double>::max()), leaveTime(0), prev(0), visited(false) {}
84 
86  const E* const edge;
87 
89  double effort;
90 
92  double leaveTime;
93 
95  const EdgeInfo* prev;
96 
98  bool visited;
99 
100  inline void reset() {
101  effort = std::numeric_limits<double>::max();
102  visited = false;
103  }
104 
105  private:
107  EdgeInfo& operator=(const EdgeInfo& s) = delete;
108 
109  };
110 
116  public:
118  bool operator()(const EdgeInfo* nod1, const EdgeInfo* nod2) const {
119  if (nod1->effort == nod2->effort) {
120  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
121  }
122  return nod1->effort > nod2->effort;
123  }
124  };
125 
126 
128  DijkstraRouter(const std::vector<E*>& edges, bool unbuildIsWarning, Operation effortOperation, Operation ttOperation = nullptr) :
129  SUMOAbstractRouter<E, V>(effortOperation, "DijkstraRouter"), myTTOperation(ttOperation),
130  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()) {
131  for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
132  myEdgeInfos.push_back(EdgeInfo(*i));
133  }
134  }
135 
137  virtual ~DijkstraRouter() { }
138 
141  }
142 
143  inline double getTravelTime(const E* const e, const V* const v, const double t, const double effort) const {
144  return myTTOperation == nullptr ? effort : (*myTTOperation)(e, v, t);
145  }
146 
147  void init() {
148  // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
149  for (typename std::vector<EdgeInfo*>::iterator i = myFrontierList.begin(); i != myFrontierList.end(); i++) {
150  (*i)->reset();
151  }
152  myFrontierList.clear();
153  for (typename std::vector<EdgeInfo*>::iterator i = myFound.begin(); i != myFound.end(); i++) {
154  (*i)->reset();
155  }
156  myFound.clear();
157  }
158 
159 
162  virtual bool compute(const E* from, const E* to, const V* const vehicle,
163  SUMOTime msTime, std::vector<const E*>& into) {
164  assert(from != 0 && (vehicle == 0 || to != 0));
165  // check whether from and to can be used
166  if (PF::operator()(from, vehicle)) {
167  myErrorMsgHandler->inform("Vehicle '" + vehicle->getID() + "' is not allowed on source edge '" + from->getID() + "'.");
168  return false;
169  }
170  if (PF::operator()(to, vehicle)) {
171  myErrorMsgHandler->inform("Vehicle '" + vehicle->getID() + "' is not allowed on destination edge '" + to->getID() + "'.");
172  return false;
173  }
174  this->startQuery();
175 #ifdef DijkstraRouter_DEBUG_QUERY
176  std::cout << "DEBUG: starting search for '" << vehicle->getID() << "' time: " << STEPS2TIME(msTime) << "\n";
177 #endif
178  const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
179  if (this->myBulkMode) {
180  const EdgeInfo& toInfo = myEdgeInfos[to->getNumericalID()];
181  if (toInfo.visited) {
182  buildPathFrom(&toInfo, into);
183  this->endQuery(1);
184  return true;
185  }
186  } else {
187  init();
188  // add begin node
189  EdgeInfo* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
190  fromInfo->effort = 0;
191  fromInfo->prev = 0;
192  fromInfo->leaveTime = STEPS2TIME(msTime);
193  myFrontierList.push_back(fromInfo);
194  }
195  // loop
196  int num_visited = 0;
197  while (!myFrontierList.empty()) {
198  num_visited += 1;
199  // use the node with the minimal length
200  EdgeInfo* const minimumInfo = myFrontierList.front();
201  const E* const minEdge = minimumInfo->edge;
202  // check whether the destination node was already reached
203  if (minEdge == to) {
204  buildPathFrom(minimumInfo, into);
205  this->endQuery(num_visited);
206 #ifdef DijkstraRouter_DEBUG_QUERY_PERF
207  std::cout << "visited " + toString(num_visited) + " edges (final path length=" + toString(into.size()) + " edges=" + toString(into) + ")\n";
208 #endif
209  return true;
210  }
211  pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
212  myFrontierList.pop_back();
213  myFound.push_back(minimumInfo);
214  minimumInfo->visited = true;
215 #ifdef DijkstraRouter_DEBUG_QUERY
216  std::cout << "DEBUG: hit '" << minEdge->getID() << "' Eff: " << minimumInfo->effort << ", TT: " << minimumInfo->leaveTime << " Q: ";
217  for (typename std::vector<EdgeInfo*>::iterator it = myFrontierList.begin(); it != myFrontierList.end(); it++) {
218  std::cout << (*it)->effort << "," << (*it)->edge->getID() << " ";
219  }
220  std::cout << "\n";
221 #endif
222  const double effortDelta = this->getEffort(minEdge, vehicle, minimumInfo->leaveTime);
223  const double effort = minimumInfo->effort + effortDelta;
224  const double leaveTime = minimumInfo->leaveTime + getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
225  // check all ways from the node with the minimal length
226  const std::vector<E*>& successors = minEdge->getSuccessors(vClass);
227  for (typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
228  const E* const follower = *it;
229  EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]);
230  // check whether it can be used
231  if (PF::operator()(follower, vehicle)) {
232  continue;
233  }
234  const double oldEffort = followerInfo->effort;
235  if (!followerInfo->visited && effort < oldEffort) {
236  followerInfo->effort = effort;
237  followerInfo->leaveTime = leaveTime;
238  followerInfo->prev = minimumInfo;
239  if (oldEffort == std::numeric_limits<double>::max()) {
240  myFrontierList.push_back(followerInfo);
241  push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
242  } else {
243  push_heap(myFrontierList.begin(),
244  find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
245  myComparator);
246  }
247  }
248  }
249  }
250  this->endQuery(num_visited);
251 #ifdef DijkstraRouter_DEBUG_QUERY_PERF
252  std::cout << "visited " + toString(num_visited) + " edges (unsuccesful path length: " + toString(into.size()) + ")\n";
253 #endif
254  if (to != 0) {
255  myErrorMsgHandler->inform("No connection between edge '" + from->getID() + "' and edge '" + to->getID() + "' found.");
256  }
257  return false;
258  }
259 
260 
261  double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime) const {
262  double costs = 0;
263  double t = STEPS2TIME(msTime);
264  for (const E* const e : edges) {
265  if (PF::operator()(e, v)) {
266  return -1;
267  }
268  const double effortDelta = this->getEffort(e, v, t);
269  costs += effortDelta;
270  t += getTravelTime(e, v, t, effortDelta);
271  }
272  return costs;
273  }
274 
276  void buildPathFrom(const EdgeInfo* rbegin, std::vector<const E*>& edges) {
277  std::vector<const E*> tmp;
278  while (rbegin != 0) {
279  tmp.push_back(rbegin->edge);
280  rbegin = rbegin->prev;
281  }
282  std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
283  }
284 
285  const EdgeInfo& getEdgeInfo(int index) const {
286  return myEdgeInfos[index];
287  }
288 
289 private:
290  DijkstraRouter(const std::vector<EdgeInfo>& edgeInfos, bool unbuildIsWarning, Operation effortOperation, Operation ttOperation) :
291  SUMOAbstractRouter<E, V>(effortOperation, "DijkstraRouter"), myTTOperation(ttOperation),
292  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()) {
293  for (const EdgeInfo& ei : edgeInfos) {
294  myEdgeInfos.push_back(EdgeInfo(ei.edge));
295  }
296  }
297 
298 private:
301 
303  std::vector<EdgeInfo> myEdgeInfos;
304 
306  std::vector<EdgeInfo*> myFrontierList;
308  std::vector<EdgeInfo*> myFound;
309 
311 
314 };
315 
316 
317 #endif
318 
319 /****************************************************************************/
320 
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:66
double getEffort(const E *const e, const V *const v, double t) const
void buildPathFrom(const EdgeInfo *rbegin, std::vector< const E *> &edges)
Builds the path from marked edges.
bool visited
The previous edge.
MsgHandler *const myErrorMsgHandler
the handler for routing errors
EdgeInfo(const E *const e)
Constructor.
EdgeInfo & operator=(const EdgeInfo &s)=delete
Invalidated assignment operator.
const EdgeInfo & getEdgeInfo(int index) const
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
double recomputeCosts(const std::vector< const E *> &edges, const V *const v, SUMOTime msTime) const
std::vector< EdgeInfo * > myFound
list of visited Edges (for resetting)
Operation myTTOperation
The object&#39;s operation to perform for travel times.
virtual ~DijkstraRouter()
Destructor.
double leaveTime
The time the vehicle leaves the edge.
const E *const edge
The current edge.
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:55
double getTravelTime(const E *const e, const V *const v, const double t, const double effort) const
Computes the shortest path through a network using the Dijkstra algorithm.
DijkstraRouter(const std::vector< E *> &edges, bool unbuildIsWarning, Operation effortOperation, Operation ttOperation=nullptr)
Constructor.
double(* Operation)(const E *const, const V *const, double)
bool myBulkMode
whether we are currently operating several route queries in a bulk
#define STEPS2TIME(x)
Definition: SUMOTime.h:64
Operation myOperation
The object&#39;s operation to perform.
DijkstraRouter(const std::vector< EdgeInfo > &edgeInfos, bool unbuildIsWarning, Operation effortOperation, Operation ttOperation)
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E *> &into)
Builds the route between the given edges using the minimum effort at the given time The definition of...
EdgeInfoByEffortComparator myComparator
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:84
std::vector< EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
void endQuery(int visits)
long long int SUMOTime
Definition: TraCIDefs.h:51
bool operator()(const EdgeInfo *nod1, const EdgeInfo *nod2) const
Comparing method.
virtual SUMOAbstractRouter< E, V > * clone()
vehicles ignoring classes
const EdgeInfo * prev
The previous edge.
double effort
Effort to reach the edge.