SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules 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.dlr.de/
12 // Copyright (C) 2001-2015 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 SUMOReal(* Operation)(const E* const, const V* const, SUMOReal);
71  DijkstraRouterEffort(size_t noE, bool unbuildIsWarning, Operation effortOperation, Operation ttOperation) :
72  SUMOAbstractRouter<E, V>(effortOperation, "DijkstraRouterEffort"), myTTOperation(ttOperation),
73  myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()) {
74  for (size_t i = 0; i < noE; i++) {
75  myEdgeInfos.push_back(EdgeInfo(i));
76  }
77  }
78 
80  virtual ~DijkstraRouterEffort() { }
81 
82  virtual SUMOAbstractRouter<E, V>* clone() const {
84  }
85 
91  class EdgeInfo {
92  public:
94  EdgeInfo(size_t id)
95  : edge(E::dictionary(id)), effort(std::numeric_limits<SUMOReal>::max()), leaveTime(0), prev(0), visited(false) {}
96 
98  const E* edge;
99 
102 
105 
108 
110  bool visited;
111 
112  inline void reset() {
114  visited = false;
115  }
116  };
117 
123  public:
125  bool operator()(EdgeInfo* nod1, EdgeInfo* nod2) const {
126  if (nod1->effort == nod2->effort) {
127  return nod1->edge->getNumericalID() > nod2->edge->getNumericalID();
128  }
129  return nod1->effort > nod2->effort;
130  }
131  };
132 
133  inline SUMOReal getTravelTime(const E* const e, const V* const v, SUMOReal t) const {
134  return (*myTTOperation)(e, v, t);
135  }
136 
137  void init() {
138  // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
139  for (typename std::vector<EdgeInfo*>::iterator i = myFrontierList.begin(); i != myFrontierList.end(); i++) {
140  (*i)->reset();
141  }
142  myFrontierList.clear();
143  for (typename std::vector<EdgeInfo*>::iterator i = myFound.begin(); i != myFound.end(); i++) {
144  (*i)->reset();
145  }
146  myFound.clear();
147  }
148 
149 
152  virtual void compute(const E* from, const E* to, const V* const vehicle,
153  SUMOTime msTime, std::vector<const E*>& into) {
154  assert(from != 0 && to != 0);
155  this->startQuery();
156  const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
157  init();
158  // add begin node
159  EdgeInfo* const fromInfo = &(myEdgeInfos[from->getNumericalID()]);
160  fromInfo->effort = 0;
161  fromInfo->prev = 0;
162  fromInfo->leaveTime = STEPS2TIME(msTime);
163  myFrontierList.push_back(fromInfo);
164  // loop
165  int num_visited = 0;
166  while (!myFrontierList.empty()) {
167  num_visited += 1;
168  // use the node with the minimal length
169  EdgeInfo* const minimumInfo = myFrontierList.front();
170  const E* const minEdge = minimumInfo->edge;
171  pop_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
172  myFrontierList.pop_back();
173  myFound.push_back(minimumInfo);
174  // check whether the destination node was already reached
175  if (minEdge == to) {
176  buildPathFrom(minimumInfo, into);
177  this->endQuery(num_visited);
178  return;
179  }
180  minimumInfo->visited = true;
181  const SUMOReal effort = minimumInfo->effort + this->getEffort(minEdge, vehicle, minimumInfo->leaveTime);
182  const SUMOReal leaveTime = minimumInfo->leaveTime + getTravelTime(minEdge, vehicle, minimumInfo->leaveTime);
183  // check all ways from the node with the minimal length
184  const std::vector<E*>& successors = minEdge->getSuccessors(vClass);
185  for (typename std::vector<E*>::const_iterator it = successors.begin(); it != successors.end(); ++it) {
186  const E* const follower = *it;
187  EdgeInfo* const followerInfo = &(myEdgeInfos[follower->getNumericalID()]);
188  // check whether it can be used
189  if (PF::operator()(follower, vehicle)) {
190  continue;
191  }
192  const SUMOReal oldEffort = followerInfo->effort;
193  if (!followerInfo->visited && effort < oldEffort) {
194  followerInfo->effort = effort;
195  followerInfo->leaveTime = leaveTime;
196  followerInfo->prev = minimumInfo;
197  if (oldEffort == std::numeric_limits<SUMOReal>::max()) {
198  myFrontierList.push_back(followerInfo);
199  push_heap(myFrontierList.begin(), myFrontierList.end(), myComparator);
200  } else {
201  push_heap(myFrontierList.begin(),
202  find(myFrontierList.begin(), myFrontierList.end(), followerInfo) + 1,
203  myComparator);
204  }
205  }
206  }
207  }
208  this->endQuery(num_visited);
209  myErrorMsgHandler->inform("No connection between '" + from->getID() + "' and '" + to->getID() + "' found.");
210  }
211 
212 
213  SUMOReal recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime) const {
214  SUMOReal costs = 0;
215  SUMOReal t = STEPS2TIME(msTime);
216  for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); ++i) {
217  if (PF::operator()(*i, v)) {
218  return -1;
219  }
220  costs += this->getEffort(*i, v, t);
221  t += getTravelTime(*i, v, t);
222  }
223  return costs;
224  }
225 
226 public:
228  void buildPathFrom(EdgeInfo* rbegin, std::vector<const E*>& edges) {
229  std::deque<const E*> tmp;
230  while (rbegin != 0) {
231  tmp.push_front((E*) rbegin->edge); // !!!
232  rbegin = rbegin->prev;
233  }
234  std::copy(tmp.begin(), tmp.end(), std::back_inserter(edges));
235  }
236 
237 private:
240 
242  std::vector<EdgeInfo> myEdgeInfos;
243 
245  std::vector<EdgeInfo*> myFrontierList;
247  std::vector<EdgeInfo*> myFound;
248 
250 
253 
254 };
255 
256 
257 #endif
258 
259 /****************************************************************************/
260 
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:71
Computes the shortest path through a network using the Dijkstra algorithm.
SUMOReal getTravelTime(const E *const e, const V *const v, SUMOReal t) const
SUMOVehicleClass
Definition of vehicle classes to differ between different lane usage and authority types...
void buildPathFrom(EdgeInfo *rbegin, std::vector< const E * > &edges)
Builds the path from marked edges.
bool operator()(EdgeInfo *nod1, EdgeInfo *nod2) const
Comparing method.
SUMOReal recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime) const
std::vector< EdgeInfo > myEdgeInfos
The container of edge information.
MsgHandler *const myErrorMsgHandler
the handler for routing errors
EdgeInfo(size_t id)
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...
#define max(a, b)
Definition: polyfonts.c:65
DijkstraRouterEffort(size_t noE, bool unbuildIsWarning, Operation effortOperation, Operation ttOperation)
Constructor.
const E * edge
The current edge.
SUMOReal(* Operation)(const E *const, const V *const, SUMOReal)
std::vector< EdgeInfo * > myFound
list of visited Edges (for resetting)
#define STEPS2TIME(x)
Definition: SUMOTime.h:65
SUMOReal leaveTime
The time the vehicle leaves the edge.
EdgeInfoByEffortComparator myComparator
Operation myOperation
The object's operation to perform.
SUMOReal effort
Effort to reach the edge.
void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:89
int SUMOTime
Definition: SUMOTime.h:43
#define SUMOReal
Definition: config.h:218
void endQuery(int visits)
Operation myTTOperation
The object's operation to perform for travel times.
std::vector< EdgeInfo * > myFrontierList
A container for reusage of the min edge heap.
virtual ~DijkstraRouterEffort()
Destructor.
SUMOReal getEffort(const E *const e, const V *const v, SUMOReal t) const
EdgeInfo * prev
The previous edge.
virtual SUMOAbstractRouter< E, V > * clone() const
vehicles ignoring classes