SUMO - Simulation of Urban MObility
SPTree.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 /****************************************************************************/
18 // Shortest Path tree of limited depth using Dijkstras algorithm
19 /****************************************************************************/
20 #ifndef SPTree_h
21 #define SPTree_h
22 
23 
24 // ===========================================================================
25 // included modules
26 // ===========================================================================
27 #ifdef _MSC_VER
28 #include <windows_config.h>
29 #else
30 #include <config.h>
31 #endif
32 
33 #include <string>
34 #include <functional>
35 #include <vector>
36 #include <set>
37 #include <limits>
38 #include <algorithm>
39 #include <iterator>
41 #include <utils/common/StdDefs.h>
42 
43 
44 template<class E, class C>
45 class SPTree {
46 
47 public:
48  typedef std::vector<C> CHConnections;
49  typedef std::pair<const C*, const C*> CHConnectionPair;
50  typedef std::vector<CHConnectionPair> CHConnectionPairs;
51 
57  public:
59  bool operator()(const E* a, const E* b) const {
60  if (a->traveltime == b->traveltime) {
61  return a->edge->getNumericalID() > b->edge->getNumericalID();
62  }
63  return a->traveltime > b->traveltime;
64  }
65  };
66 
67 
71  SPTree(int maxDepth, bool validatePermissions) :
72  myMaxDepth(maxDepth),
73  myValidatePermissions(validatePermissions) {
74  }
75 
76 
77  void init() {
78  // all EdgeInfos touched in the previous query are either in myFrontier or myFound: clean those up
79  for (typename std::vector<E*>::iterator i = myFrontier.begin(); i != myFrontier.end(); i++) {
80  (*i)->reset();
81  }
82  myFrontier.clear();
83  for (typename std::vector<E*>::iterator i = myFound.begin(); i != myFound.end(); i++) {
84  (*i)->reset();
85  }
86  myFound.clear();
87  }
88 
89 
94  void rebuildFrom(E* start, const E* excluded) {
95  init();
96  start->traveltime = 0;
97  start->depth = 0;
98  start->permissions = start->edge->getPermissions();
99  myFrontier.push_back(start);
100  // build SPT
101  while (!myFrontier.empty()) {
102  E* min = myFrontier.front();
103  pop_heap(myFrontier.begin(), myFrontier.end(), myCmp);
104  myFrontier.pop_back();
105  myFound.push_back(min);
106  min->visited = true;
107  if (min->depth < myMaxDepth) {
108  for (typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
109  C& con = *it;
110  E* follower = con.target;
111  if (follower == excluded) {
112  continue;
113  }
114  const double traveltime = min->traveltime + con.cost;
115  const double oldTraveltime = follower->traveltime;
116  if (!follower->visited && traveltime < oldTraveltime) {
117  follower->traveltime = traveltime;
118  follower->depth = min->depth + 1;
119  follower->permissions = (min->permissions & con.permissions);
120  if (oldTraveltime == std::numeric_limits<double>::max()) {
121  myFrontier.push_back(follower);
122  push_heap(myFrontier.begin(), myFrontier.end(), myCmp);
123  } else {
124  push_heap(myFrontier.begin(),
125  find(myFrontier.begin(), myFrontier.end(), follower) + 1,
126  myCmp);
127  }
128  }
129  }
130  }
131  }
132  }
133 
134 
136  inline bool validatePermissions() {
137  return myValidatePermissions;
138  }
139 
141  void registerForValidation(const C* aInfo, const C* fInfo) {
142  assert(myValidatePermissions);
143  myShortcutsToValidate.push_back(CHConnectionPair(aInfo, fInfo));
144  }
145 
146 
147  /* @brief for each path source->excluded->target try to find a witness with a witness
148  * with equal permissions */
149  const CHConnectionPairs& getNeededShortcuts(const E* excluded) {
150  assert(myValidatePermissions);
151  myNeededShortcuts.clear();
152  for (typename CHConnectionPairs::iterator it = myShortcutsToValidate.begin(); it != myShortcutsToValidate.end(); ++it) {
153  const C* const aInfo = it->first;
154  const C* const fInfo = it->second;
155  const double bestWitness = dijkstraTT(
156  aInfo->target, fInfo->target, excluded, (aInfo->permissions & fInfo->permissions));
157  const double viaCost = aInfo->cost + fInfo->cost;
158  if (viaCost < bestWitness) {
159  myNeededShortcuts.push_back(*it);
160  }
161  }
162  myShortcutsToValidate.clear();
163  return myNeededShortcuts;
164  }
165 
166 
167 private:
168  // perform dijkstra search under permission constraints
169  double dijkstraTT(E* start, E* dest, const E* excluded, SVCPermissions permissions) {
170  init();
171  start->traveltime = 0;
172  start->depth = 0;
173  myFrontier.push_back(start);
174  // build SPT
175  while (!myFrontier.empty()) {
176  E* min = myFrontier.front();
177  if (min == dest) {
178  return dest->traveltime;
179  }
180  pop_heap(myFrontier.begin(), myFrontier.end(), myCmp);
181  myFrontier.pop_back();
182  myFound.push_back(min);
183  min->visited = true;
184  if (min->depth < myMaxDepth) {
185  for (typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
186  C& con = *it;
187  E* follower = con.target;
188  if (follower == excluded) {
189  continue;
190  }
191  if ((con.permissions & permissions) != permissions) {
192  continue;
193  }
194  const double traveltime = min->traveltime + con.cost;
195  const double oldTraveltime = follower->traveltime;
196  if (!follower->visited && traveltime < oldTraveltime) {
197  follower->traveltime = traveltime;
198  follower->depth = min->depth + 1;
199  follower->permissions = (min->permissions & con.permissions);
200  if (oldTraveltime == std::numeric_limits<double>::max()) {
201  myFrontier.push_back(follower);
202  push_heap(myFrontier.begin(), myFrontier.end(), myCmp);
203  } else {
204  push_heap(myFrontier.begin(),
205  find(myFrontier.begin(), myFrontier.end(), follower) + 1,
206  myCmp);
207  }
208  }
209  }
210  }
211  }
212  return dest->traveltime;
213  }
214 
215 
216  // helper method for debugging
217  void debugPrintVector(std::vector<E*>& vec, E* start, const E* excluded) {
218  std::cout << "computed SPT from '" << start->edge->getID() << "' (excluding " << excluded->edge->getID() << ") with " << myFound.size() << " edges\n";
219  for (typename std::vector<E*>::iterator it = vec.begin(); it != vec.end(); it++) {
220  E* e = *it;
221  std::cout << "(" << e->edge->getID() << "," << e->traveltime << ") ";
222  }
223  std::cout << "\n";
224  }
225 
227  std::vector<E*> myFrontier;
229  std::vector<E*> myFound;
230 
232  EdgeByTTComparator myCmp;
233 
236 
239 
241  CHConnectionPairs myShortcutsToValidate;
243  CHConnectionPairs myNeededShortcuts;
244 };
245 
246 #endif
247 
248 /****************************************************************************/
249 
double dijkstraTT(E *start, E *dest, const E *excluded, SVCPermissions permissions)
Definition: SPTree.h:169
SPTree(int maxDepth, bool validatePermissions)
Constructor.
Definition: SPTree.h:71
int SVCPermissions
bitset where each bit declares whether a certain SVC may use this edge/lane
EdgeByTTComparator myCmp
comparator for search queue
Definition: SPTree.h:232
CHConnectionPairs myNeededShortcuts
vector of needed shortcuts after validation
Definition: SPTree.h:243
std::vector< CHConnectionPair > CHConnectionPairs
Definition: SPTree.h:50
void registerForValidation(const C *aInfo, const C *fInfo)
save source/target pair for later validation
Definition: SPTree.h:141
std::vector< E * > myFound
the list of visited edges (used when resetting)
Definition: SPTree.h:229
const CHConnectionPairs & getNeededShortcuts(const E *excluded)
Definition: SPTree.h:149
std::pair< const C *, const C * > CHConnectionPair
Definition: SPTree.h:49
std::vector< E * > myFrontier
the min edge heap
Definition: SPTree.h:227
void debugPrintVector(std::vector< E *> &vec, E *start, const E *excluded)
Definition: SPTree.h:217
bool myValidatePermissions
whether permissions should be validated
Definition: SPTree.h:238
Definition: SPTree.h:45
std::vector< C > CHConnections
Definition: SPTree.h:48
void init()
Definition: SPTree.h:77
void rebuildFrom(E *start, const E *excluded)
build a shortest path tree from start to a depth of myMaxdepth. The given edge is excluded from this ...
Definition: SPTree.h:94
CHConnectionPairs myShortcutsToValidate
vector of needed shortcuts after validation
Definition: SPTree.h:241
bool validatePermissions()
whether permissions should be validated;
Definition: SPTree.h:136
bool operator()(const E *a, const E *b) const
Comparing method.
Definition: SPTree.h:59
int myMaxDepth
maximum search depth
Definition: SPTree.h:235