SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
TraCIDijkstraRouter.h
Go to the documentation of this file.
1 /****************************************************************************/
10 /****************************************************************************/
11 // SUMO, Simulation of Urban MObility; see http://sumo.sourceforge.net/
12 // Copyright (C) 2001-2012 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 TRACIDIJKSTRAROUTER_H
23 #define TRACIDIJKSTRAROUTER_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 #ifndef NO_TRACI
36 
38 #include <microsim/MSLane.h>
40 
41 
42 // ===========================================================================
43 // class definitions
44 // ===========================================================================
61 template<class E>
62 class TraCIDijkstraRouter : public SUMOAbstractRouter<E, MSVehicle> {
63 public:
65  TraCIDijkstraRouter(size_t noE/*, bool unbuildIsWarningOnly*/) :
66  SUMOAbstractRouter<E, MSVehicle>("TraciDijkstraRouter"),
68 
70  virtual ~TraCIDijkstraRouter() { }
71 
77  class EdgeInfo {
78  public:
81  : edge(0), effort(0), prev(0) {}
82 
83 
85  EdgeInfo(const E* edgeArg, SUMOReal effortArg, EdgeInfo* prevArg)
86  : edge(edgeArg), effort(effortArg), prev(prevArg) {}
87 
89  EdgeInfo(const E* edgeArg, SUMOReal effortArg, EdgeInfo* prevArg, SUMOReal distArg)
90  : edge(edgeArg), effort(effortArg), prev(prevArg), dist(distArg) {}
91 
93  const E* edge;
94 
97 
100 
103 
104  };
105 
111  public:
114 
117 
119  bool operator()(EdgeInfo* nod1, EdgeInfo* nod2) const {
120  return nod1->effort > nod2->effort;
121  }
122  };
123 
124  virtual SUMOReal getEffort(const E* const e, SUMOReal t) const {
125  SUMOReal value;
126  if (MSNet::getInstance()->getWeightsStorage().retrieveExistingEffort(e, 0, t, value)) {
127  return value;
128  }
129  const MSLane* const l = e->getLanes()[0];
130  return l->getLength() / l->getMaxSpeed();
131  }
132 
133 
136  virtual void compute(const E* from, const E* to, const MSVehicle* const vehicle,
137  SUMOTime msTime, std::vector<const E*> &into) {
138  UNUSED_PARAMETER(vehicle);
139  const SUMOReal time = STEPS2TIME(msTime);
140  // get structures to reuse
141  std::vector<bool> *visited = myReusableEdgeLists.getFreeInstance();
142  if (visited == 0) {
143  visited = new std::vector<bool>(myNoE, false);
144  } else {
145  for (size_t i = 0; i < myNoE; i++) {
146  (*visited)[i] = false; // too slow? !!!
147  }
148  }
150  if (storage == 0) {
151  storage = new EdgeInfoCont(myNoE);
152  }
153  storage->reset();
154 
155  // check the nodes
156  if (from == 0 || to == 0) {
157  throw std::exception();
158  }
159 
160  // begin computation
161  std::priority_queue < EdgeInfo*,
162  std::vector<EdgeInfo*>,
163  EdgeInfoByEffortComperator > frontierList;
164  // add begin node
165  const E* actualKnot = from;
166  if (from != 0) {
167  EdgeInfo* ei = storage->add(actualKnot, 0, 0);
168  frontierList.push(ei);
169  }
170  bool isFirstIteration = true;
171 
172  // loop
173  while (!frontierList.empty()) {
174  // use the node with the minimal length
175  EdgeInfo* minimumKnot = frontierList.top();
176  const E* minEdge = minimumKnot->edge;
177  frontierList.pop();
178  // check whether the destination node was already reached
179  if ((minEdge == to) && (!isFirstIteration)) {
180  buildPathFrom(minimumKnot, into);
181  clearTemporaryStorages(visited, storage);
182  return;
183  }
184  (*visited)[minEdge->getNumericalID()] = true;
185  const SUMOReal effort = (SUMOReal)(minimumKnot->effort + getEffort(minEdge, time + minimumKnot->effort));
186  // check all ways from the node with the minimal length
187  unsigned int i = 0;
188  const unsigned int length_size = minEdge->getNoFollowing();
189  for (i = 0; i < length_size; i++) {
190  const E* help = minEdge->getFollower(i);
191 
192  if ((!(*visited)[help->getNumericalID()] && effort < storage->getEffort(help))
193  || (help == to)) {
194 // if (help!=from) {
195  frontierList.push(storage->add(help, effort, minimumKnot));
196 // }
197  }
198  }
199 
200  isFirstIteration = false;
201  }
202  clearTemporaryStorages(visited, storage);
203  }
204 
205 
206  SUMOReal recomputeCosts(const std::vector<const E*> &edges, const MSVehicle* const v, SUMOTime msTime) const {
207  UNUSED_PARAMETER(v);
208  const SUMOReal time = STEPS2TIME(msTime);
209  SUMOReal costs = 0;
210  for (typename std::vector<const E*>::const_iterator i = edges.begin(); i != edges.end(); i++) {
211  costs += getEffort(*i, time + costs);
212  }
213  return costs;
214  }
215 
216 public:
218  void buildPathFrom(EdgeInfo* rbegin, std::vector<const E*> &edges) {
219  std::deque<const E*> tmp;
220  EdgeInfo* last = rbegin;
221  while (rbegin != 0) {
222  tmp.push_front((E*) rbegin->edge); // !!!
223  rbegin = rbegin->prev;
224  if (rbegin == last) {
225  tmp.push_front((E*) rbegin->edge);
226  break;
227  }
228  }
229  std::copy(tmp.begin(), tmp.end(), std::back_inserter(edges));
230  }
231 
232 public:
240  class EdgeInfoCont {
241  public:
243  EdgeInfoCont(size_t toAlloc)
244  : myEdgeInfos(toAlloc + 1, EdgeInfo()) { }
245 
248 
250  EdgeInfo* add(const E* edgeArg, SUMOReal effortArg, EdgeInfo* prevArg) {
251  EdgeInfo* ret = &(myEdgeInfos[edgeArg->getNumericalID()]);
252  ret->edge = edgeArg; // !!! may be set within the constructor
253  ret->effort = effortArg;
254  ret->prev = prevArg;
255  ret->dist = 0;
256  return ret;
257  }
258 
260  EdgeInfo* add(const E* edgeArg, SUMOReal effortArg, EdgeInfo* prevArg,
261  SUMOReal distArg) {
262  EdgeInfo* ret = &(myEdgeInfos[edgeArg->getNumericalID()]);
263  ret->edge = edgeArg; // !!! may be set within the constructor
264  ret->effort = effortArg;
265  ret->prev = prevArg;
266  ret->dist = distArg;
267  return ret;
268  }
269 
271  void reset() {
272  for (typename std::vector<EdgeInfo>::iterator i = myEdgeInfos.begin(); i != myEdgeInfos.end(); i++) {
273  (*i).effort = std::numeric_limits<SUMOReal>::max();
274  }
275  }
276 
277 
280  SUMOReal getEffort(const E* to) const {
281  return myEdgeInfos[to->getNumericalID()].effort;
282  }
283 
284  private:
286  std::vector<EdgeInfo> myEdgeInfos;
287 
288  };
289 
290 protected:
292  void clearTemporaryStorages(std::vector<bool> *edgeList,
293  EdgeInfoCont* consecutionList) {
295  myReusableEdgeInfoLists.addFreeInstance(consecutionList);
296  }
297 
298 
299 protected:
301  size_t myNoE;
302 
305 
308 };
309 
310 #endif
311 
312 #endif
313