SUMO - Simulation of Urban MObility
DijkstraRouterEffort.h
Go to the documentation of this file.
1 /****************************************************************************/
9 // Dijkstra shortest path algorithm using other values
10 /****************************************************************************/
11 // SUMO, Simulation of Urban MObility; see http://sumo.dlr.de/
12 // Copyright (C) 2001-2017 DLR (http://www.dlr.de/) and contributors
13 /****************************************************************************/
14 //
15 // This file is part of SUMO.
16 // SUMO is free software: you can redistribute it and/or modify
17 // it under the terms of the GNU General Public License as published by
18 // the Free Software Foundation, either version 3 of the License, or
19 // (at your option) any later version.
20 //
21 /****************************************************************************/
22 #ifndef DijkstraRouterEffort_h
23 #define DijkstraRouterEffort_h
24 
25 
26 // ===========================================================================
27 // included modules
28 // ===========================================================================
29 #ifdef _MSC_VER
30 #include <windows_config.h>
31 #else
32 #include <config.h>
33 #endif
34 
35 #include <cassert>
36 #include <string>
37 #include <functional>
38 #include <vector>
39 #include <set>
40 #include <limits>
41 #include <algorithm>
43 #include <utils/common/StdDefs.h>
44 #include "SUMOAbstractRouter.h"
45 
46 
47 // ===========================================================================
48 // class definitions
49 // ===========================================================================
65 template<class E, class V, class PF>
66 class DijkstraRouterEffort : public SUMOAbstractRouter<E, V>, public PF {
67 
68 public:
69  typedef double(* Operation)(const E* const, const V* const, double);
70 
76  class EdgeInfo {
77  public:
79  EdgeInfo(const E* e)
80  : edge(e), effort(std::numeric_limits<double>::max()), leaveTime(0), prev(0), visited(false) {}
81 
83  const E* edge;
84 
86  double effort;
87 
89  double leaveTime;
90 
93 
95  bool visited;
96 
97  inline void reset() {
99  visited = false;
100  }
101  };
102 
108  public:
110  bool operator()(EdgeInfo* nod1, EdgeInfo* nod2) const {
111  if (nod1->effort == nod2->effort) {
112  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
113  }
114  return nod1->effort > nod2->effort;
115  }
116  };
117 
118 
120  DijkstraRouterEffort(const std::vector<E*>& edges, bool unbuildIsWarning, Operation effortOperation, Operation ttOperation) :
121  SUMOAbstractRouter<E, V>(effortOperation, "DijkstraRouterEffort"), myTTOperation(ttOperation),
122  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()) {
123  for (typename std::vector<E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
124  myEdgeInfos.push_back(EdgeInfo(*i));
125  }
126  }
127 
128  DijkstraRouterEffort(const std::vector<EdgeInfo>& edgeInfos, bool unbuildIsWarning, Operation effortOperation, Operation ttOperation) :
129  SUMOAbstractRouter<E, V>(effortOperation, "DijkstraRouterEffort"), myTTOperation(ttOperation),
130  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()) {
131  for (typename std::vector<EdgeInfo>::const_iterator i = edgeInfos.begin(); i != edgeInfos.end(); ++i) {
132  myEdgeInfos.push_back(EdgeInfo(i->edge));
133  }
134  }
135 
137  virtual ~DijkstraRouterEffort() { }
138 
141  }
142 
143  inline double getTravelTime(const E* const e, const V* const v, double t) const {
144  return (*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 && 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  const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
176  if (this->myBulkMode) {
177  const EdgeInfo& toInfo = myEdgeInfos[to->getNumericalID()];
178  if (toInfo.visited) {
179  buildPathFrom(&toInfo, into);
180  this->endQuery(1);
181  return true;
182  }
183  } else {
184  init();
185  // add begin node
186  EdgeInfo* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
187  fromInfo->effort = 0;
188  fromInfo->prev = 0;
189  fromInfo->leaveTime = STEPS2TIME(msTime);
190  myFrontierList.push_back(fromInfo);
191  }
192  // loop
193  int num_visited = 0;
194  while (!myFrontierList.empty()) {
195  num_visited += 1;
196  // use the node with the minimal length
197  EdgeInfo* const minimumInfo = myFrontierList.front();
198  const E* const minEdge = minimumInfo->edge;
199  pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
200  myFrontierList.pop_back();
201  myFound.push_back(minimumInfo);
202  // check whether the destination node was already reached
203  if (minEdge == to) {
204  buildPathFrom(minimumInfo, into);
205  this->endQuery(num_visited);
206  return true;
207  }
208  minimumInfo->visited = true;
209  const double effort = minimumInfo->effort + this->getEffort(minEdge, vehicle, minimumInfo->leaveTime);
210  const double leaveTime = minimumInfo->leaveTime + getTravelTime(minEdge, vehicle, minimumInfo->leaveTime);
211  // check all ways from the node with the minimal length
212  const std::vector<E*>& successors = minEdge->getSuccessors(vClass);
213  for (typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
214  const E* const follower = *it;
215  EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]);
216  // check whether it can be used
217  if (PF::operator()(follower, vehicle)) {
218  continue;
219  }
220  const double oldEffort = followerInfo->effort;
221  if (!followerInfo->visited && effort < oldEffort) {
222  followerInfo->effort = effort;
223  followerInfo->leaveTime = leaveTime;
224  followerInfo->prev = minimumInfo;
225  if (oldEffort == std::numeric_limits<double>::max()) {
226  myFrontierList.push_back(followerInfo);
227  push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
228  } else {
229  push_heap(myFrontierList.begin(),
230  find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
231  myComparator);
232  }
233  }
234  }
235  }
236  this->endQuery(num_visited);
237  myErrorMsgHandler->inform("No connection between edge '" + from->getID() + "' and edge '" + to->getID() + "' found.");
238  return false;
239  }
240 
241 
242  double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime) const {
243  double costs = 0;
244  double t = STEPS2TIME(msTime);
245  for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
246  if (PF::operator()(*i, v)) {
247  return -1;
248  }
249  costs += this->getEffort(*i, v, t);
250  t += getTravelTime(*i, v, t);
251  }
252  return costs;
253  }
254 
255 public:
257  void buildPathFrom(const EdgeInfo* rbegin, std::vector<const E*>& edges) {
258  std::vector<const E*> tmp;
259  while (rbegin != 0) {
260  tmp.push_back(rbegin->edge);
261  rbegin = rbegin->prev;
262  }
263  std::copy(tmp.rbegin(), tmp.rend(), std::back_inserter(edges));
264  }
265 
266 private:
269 
271  std::vector<EdgeInfo> myEdgeInfos;
272 
274  std::vector<EdgeInfo*> myFrontierList;
276  std::vector<EdgeInfo*> myFound;
277 
279 
282 
283 };
284 
285 
286 #endif
287 
288 /****************************************************************************/
289 
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:67
DijkstraRouterEffort(const std::vector< E *> &edges, bool unbuildIsWarning, Operation effortOperation, Operation ttOperation)
Constructor.
double getEffort(const E *const e, const V *const v, double t) const
Computes the shortest path through a network using the Dijkstra algorithm.
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
void buildPathFrom(const EdgeInfo *rbegin, std::vector< const E *> &edges)
Builds the path from marked edges.
double getTravelTime(const E *const e, const V *const v, double t) const
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
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...
double(* Operation)(const E *const, const V *const, double)
MsgHandler *const myErrorMsgHandler
the handler for routing errors
EdgeInfo(const E *e)
Constructor.
double effort
Effort to reach the edge.
DijkstraRouterEffort(const std::vector< EdgeInfo > &edgeInfos, bool unbuildIsWarning, Operation effortOperation, Operation ttOperation)
#define max(a, b)
Definition: polyfonts.c:65
const E * edge
The current edge.
bool myBulkMode
whether we are currently operating several route queries in a bulk
std::vector< EdgeInfo * > myFound
list of visited Edges (for resetting)
#define STEPS2TIME(x)
Definition: SUMOTime.h:65
EdgeInfoByEffortComparator myComparator
Operation myOperation
The object&#39;s operation to perform.
bool visited
The previous edge.
double leaveTime
The time the vehicle leaves the edge.
virtual SUMOAbstractRouter< E, V > * clone()
bool operator()(EdgeInfo *nod1, EdgeInfo *nod2) const
Comparing method.
double recomputeCosts(const std::vector< const E *> &edges, const V *const v, SUMOTime msTime) const
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:85
void endQuery(int visits)
long long int SUMOTime
Definition: TraCIDefs.h:52
Operation myTTOperation
The object&#39;s operation to perform for travel times.
std::vector< EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
virtual ~DijkstraRouterEffort()
Destructor.
EdgeInfo * prev
The previous edge.
vehicles ignoring classes