SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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-sim.org/
12 // Copyright (C) 2001-2014 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>
44 #include <utils/common/StdDefs.h>
45 #include "SUMOAbstractRouter.h"
46 
47 
48 // ===========================================================================
49 // class definitions
50 // ===========================================================================
66 template<class E, class V, class PF>
67 class DijkstraRouterEffortBase : public SUMOAbstractRouter<E, V>, public PF {
70 
71 public:
73  DijkstraRouterEffortBase(size_t noE, bool unbuildIsWarning) :
74  SUMOAbstractRouter<E, V>("DijkstraRouterEffort"),
75  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()) {
76  for (size_t i = 0; i < noE; i++) {
77  myEdgeInfos.push_back(EdgeInfo(i));
78  }
79  }
80 
83 
89  class EdgeInfo {
90  public:
92  EdgeInfo(size_t id)
93  : edge(E::dictionary(id)), effort(std::numeric_limits<SUMOReal>::max()), leaveTime(0), prev(0), visited(false) {}
94 
96  const E* edge;
97 
100 
103 
106 
108  bool visited;
109 
110  inline void reset() {
112  visited = false;
113  }
114  };
115 
121  public:
123  bool operator()(EdgeInfo* nod1, EdgeInfo* nod2) const {
124  if (nod1->effort == nod2->effort) {
125  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
126  }
127  return nod1->effort > nod2->effort;
128  }
129  };
130 
131  virtual SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const = 0;
132  virtual SUMOReal getTravelTime(const E* const e, const V* const v, SUMOReal t) const = 0;
133 
134 
135  void init() {
136  // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
137  for (typename std::vector<EdgeInfo*>::iterator i = myFrontierList.begin(); i != myFrontierList.end(); i++) {
138  (*i)->reset();
139  }
140  myFrontierList.clear();
141  for (typename std::vector<EdgeInfo*>::iterator i = myFound.begin(); i != myFound.end(); i++) {
142  (*i)->reset();
143  }
144  myFound.clear();
145  }
146 
147 
150  virtual void compute(const E* from, const E* to, const V* const vehicle,
151  SUMOTime msTime, std::vector<const E*>& into) {
152  assert(from != 0 && to != 0);
153  startQuery();
154  init();
155  // add begin node
156  EdgeInfo* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
157  fromInfo->effort = 0;
158  fromInfo->prev = 0;
159  fromInfo->leaveTime = STEPS2TIME(msTime);
160  myFrontierList.push_back(fromInfo);
161  // loop
162  int num_visited = 0;
163  while (!myFrontierList.empty()) {
164  num_visited += 1;
165  // use the node with the minimal length
166  EdgeInfo* const minimumInfo = myFrontierList.front();
167  const E* const minEdge = minimumInfo->edge;
168  pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
169  myFrontierList.pop_back();
170  myFound.push_back(minimumInfo);
171  // check whether the destination node was already reached
172  if (minEdge == to) {
173  buildPathFrom(minimumInfo, into);
174  endQuery(num_visited);
175  return;
176  }
177  minimumInfo->visited = true;
178  const SUMOReal effort = minimumInfo->effort + getEffort(minEdge, vehicle, minimumInfo->leaveTime);
179  const SUMOReal leaveTime = minimumInfo->leaveTime + getTravelTime(minEdge, vehicle, minimumInfo->leaveTime);
180  // check all ways from the node with the minimal length
181  unsigned int i = 0;
182  const unsigned int length_size = minEdge->getNoFollowing();
183  for (i = 0; i < length_size; i++) {
184  const E* const follower = minEdge->getFollower(i);
185  EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]);
186  // check whether it can be used
187  if (PF::operator()(follower, vehicle)) {
188  continue;
189  }
190  const SUMOReal oldEffort = followerInfo->effort;
191  if (!followerInfo->visited && effort < oldEffort) {
192  followerInfo->effort = effort;
193  followerInfo->leaveTime = leaveTime;
194  followerInfo->prev = minimumInfo;
195  if (oldEffort == std::numeric_limits<SUMOReal>::max()) {
196  myFrontierList.push_back(followerInfo);
197  push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
198  } else {
199  push_heap(myFrontierList.begin(),
200  find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
201  myComparator);
202  }
203  }
204  }
205  }
206  endQuery(num_visited);
207  myErrorMsgHandler->inform("No connection between '" + from->getID() + "' and '" + to->getID() + "' found.");
208  }
209 
210 
211  SUMOReal recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime) const {
212  SUMOReal costs = 0;
213  SUMOReal t = STEPS2TIME(msTime);
214  for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
215  if (PF::operator()(*i, v)) {
216  return -1;
217  }
218  costs += getEffort(*i, v, t);
219  t += getTravelTime(*i, v, t);
220  }
221  return costs;
222  }
223 
224 public:
226  void buildPathFrom(EdgeInfo* rbegin, std::vector<const E*>& edges) {
227  std::deque<const E*> tmp;
228  while (rbegin != 0) {
229  tmp.push_front((E*) rbegin->edge); // !!!
230  rbegin = rbegin->prev;
231  }
232  std::copy(tmp.begin(), tmp.end(), std::back_inserter(edges));
233  }
234 
235 protected:
237  std::vector<EdgeInfo> myEdgeInfos;
238 
240  std::vector<EdgeInfo*> myFrontierList;
242  std::vector<EdgeInfo*> myFound;
243 
245 
248 
249 };
250 
251 
252 template<class E, class V, class PF>
254 public:
256  typedef SUMOReal(* Operation)(const E* const, const V* const, SUMOReal);
257 
258  DijkstraRouterEffort_ByProxi(size_t noE, bool unbuildIsWarningOnly, Operation effortOperation, Operation ttOperation):
259  DijkstraRouterEffortBase<E, V, PF>(noE, unbuildIsWarningOnly),
260  myEffortOperation(effortOperation),
261  myTTOperation(ttOperation) {}
262 
263  inline SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const {
264  return (*myEffortOperation)(e, v, t);
265  }
266 
267  inline SUMOReal getTravelTime(const E* const e, const V* const v, SUMOReal t) const {
268  return (*myTTOperation)(e, v, t);
269  }
270 
271 private:
274 
277 
278 };
279 
280 
281 template<class E, class V, class PF>
283 public:
285  typedef SUMOReal(E::* Operation)(const V* const, SUMOReal) const;
286 
287  DijkstraRouterEffort_Direct(size_t noE, bool unbuildIsWarningOnly, Operation effortOperation, Operation ttOperation)
288  : DijkstraRouterEffortBase<E, V, PF>(noE, unbuildIsWarningOnly),
289  myEffortOperation(effortOperation), myTTOperation(ttOperation) {}
290 
291  inline SUMOReal getEffort(const E* const e, const V* const v, SUMOReal t) const {
292  return (e->*myEffortOperation)(v, t);
293  }
294 
295  inline SUMOReal getTravelTime(const E* const e, const V* const v, SUMOReal t) const {
296  return (e->*myTTOperation)(v, t);
297  }
298 
299 private:
302 
305 
306 
307 };
308 
309 
310 #endif
311 
312 /****************************************************************************/
313 
virtual SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const =0
Operation myEffortOperation
The object's operation to perform for obtaining the effort.
Operation myTTOperation
The object's operation to perform for obtaining the travel time.
SUMOReal(E::* Operation)(const V *const, SUMOReal) const
Type of the function that is used to retrieve the edge effort.
DijkstraRouterEffortBase(size_t noE, bool unbuildIsWarning)
Constructor.
virtual void 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...
virtual ~DijkstraRouterEffortBase()
Destructor.
EdgeInfoByEffortComparator myComparator
#define max(a, b)
Definition: polyfonts.c:65
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
SUMOReal getTravelTime(const E *const e, const V *const v, SUMOReal t) const
EdgeInfo * prev
The previous edge.
#define STEPS2TIME(x)
Definition: SUMOTime.h:65
DijkstraRouterEffort_ByProxi(size_t noE, bool unbuildIsWarningOnly, Operation effortOperation, Operation ttOperation)
MsgHandler *const myErrorMsgHandler
the handler for routing errors
virtual SUMOReal getTravelTime(const E *const e, const V *const v, SUMOReal t) const =0
SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const
bool operator()(EdgeInfo *nod1, EdgeInfo *nod2) const
Comparing method.
SUMOReal(* Operation)(const E *const, const V *const, SUMOReal)
Type of the function that is used to retrieve the edge effort.
SUMOReal getTravelTime(const E *const e, const V *const v, SUMOReal t) const
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:89
Operation myTTOperation
The object's operation to perform for obtaining the travel time.
SUMOReal recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime) const
Operation myEffortOperation
The object's operation to perform for obtaining the effort.
#define SUMOReal
Definition: config.h:215
std::vector< EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
void endQuery(int visits)
void buildPathFrom(EdgeInfo *rbegin, std::vector< const E * > &edges)
Builds the path from marked edges.
DijkstraRouterEffort_Direct(size_t noE, bool unbuildIsWarningOnly, Operation effortOperation, Operation ttOperation)
const E * edge
The current edge.
SUMOReal leaveTime
The time the vehicle leaves the edge.
SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const
SUMOReal effort
Effort to reach the edge.
std::vector< EdgeInfo * > myFound
list of visited Edges (for resetting)