SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
SPTree.h
Go to the documentation of this file.
1 /****************************************************************************/
8 // Shortest Path tree of limited depth using Dijkstras algorithm
9 /****************************************************************************/
10 // SUMO, Simulation of Urban MObility; see http://sumo.dlr.de/
11 // Copyright (C) 2001-2016 DLR (http://www.dlr.de/) and contributors
12 /****************************************************************************/
13 //
14 // This file is part of SUMO.
15 // SUMO is free software: you can redistribute it and/or modify
16 // it under the terms of the GNU General Public License as published by
17 // the Free Software Foundation, either version 3 of the License, or
18 // (at your option) any later version.
19 //
20 /****************************************************************************/
21 #ifndef SPTree_h
22 #define SPTree_h
23 
24 
25 // ===========================================================================
26 // included modules
27 // ===========================================================================
28 #ifdef _MSC_VER
29 #include <windows_config.h>
30 #else
31 #include <config.h>
32 #endif
33 
34 #include <string>
35 #include <functional>
36 #include <vector>
37 #include <set>
38 #include <limits>
39 #include <algorithm>
40 #include <iterator>
42 #include <utils/common/StdDefs.h>
43 
44 
45 template<class E, class C>
46 class SPTree {
47 
48 public:
49  typedef std::vector<C> CHConnections;
50  typedef std::pair<const C*, const C*> CHConnectionPair;
51  typedef std::vector<CHConnectionPair> CHConnectionPairs;
52 
58  public:
60  bool operator()(const E* a, const E* b) const {
61  if (a->traveltime == b->traveltime) {
62  return a->edge->getNumericalID() > b->edge->getNumericalID();
63  }
64  return a->traveltime > b->traveltime;
65  }
66  };
67 
68 
72  SPTree(int maxDepth, bool validatePermissions) :
73  myMaxDepth(maxDepth),
74  myValidatePermissions(validatePermissions) {
75  }
76 
77 
78  void init() {
79  // all EdgeInfos touched in the previous query are either in myFrontier or myFound: clean those up
80  for (typename std::vector<E*>::iterator i = myFrontier.begin(); i != myFrontier.end(); i++) {
81  (*i)->reset();
82  }
83  myFrontier.clear();
84  for (typename std::vector<E*>::iterator i = myFound.begin(); i != myFound.end(); i++) {
85  (*i)->reset();
86  }
87  myFound.clear();
88  }
89 
90 
95  void rebuildFrom(E* start, const E* excluded) {
96  init();
97  start->traveltime = 0;
98  start->depth = 0;
99  start->permissions = start->edge->getPermissions();
100  myFrontier.push_back(start);
101  // build SPT
102  while (!myFrontier.empty()) {
103  E* min = myFrontier.front();
104  pop_heap(myFrontier.begin(), myFrontier.end(), myCmp);
105  myFrontier.pop_back();
106  myFound.push_back(min);
107  min->visited = true;
108  if (min->depth < myMaxDepth) {
109  for (typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
110  C& con = *it;
111  E* follower = con.target;
112  if (follower == excluded) {
113  continue;
114  }
115  const SUMOReal traveltime = min->traveltime + con.cost;
116  const SUMOReal oldTraveltime = follower->traveltime;
117  if (!follower->visited && traveltime < oldTraveltime) {
118  follower->traveltime = traveltime;
119  follower->depth = min->depth + 1;
120  follower->permissions = (min->permissions & con.permissions);
121  if (oldTraveltime == std::numeric_limits<SUMOReal>::max()) {
122  myFrontier.push_back(follower);
123  push_heap(myFrontier.begin(), myFrontier.end(), myCmp);
124  } else {
125  push_heap(myFrontier.begin(),
126  find(myFrontier.begin(), myFrontier.end(), follower) + 1,
127  myCmp);
128  }
129  }
130  }
131  }
132  }
133  }
134 
135 
137  inline bool validatePermissions() {
138  return myValidatePermissions;
139  }
140 
142  void registerForValidation(const C* aInfo, const C* fInfo) {
143  assert(myValidatePermissions);
144  myShortcutsToValidate.push_back(CHConnectionPair(aInfo, fInfo));
145  }
146 
147 
148  /* @brief for each path source->excluded->target try to find a witness with a witness
149  * with equal permissions */
150  const CHConnectionPairs& getNeededShortcuts(const E* excluded) {
151  assert(myValidatePermissions);
152  myNeededShortcuts.clear();
153  for (typename CHConnectionPairs::iterator it = myShortcutsToValidate.begin(); it != myShortcutsToValidate.end(); ++it) {
154  const C* const aInfo = it->first;
155  const C* const fInfo = it->second;
156  const SUMOReal bestWitness = dijkstraTT(
157  aInfo->target, fInfo->target, excluded, (aInfo->permissions & fInfo->permissions));
158  const SUMOReal viaCost = aInfo->cost + fInfo->cost;
159  if (viaCost < bestWitness) {
160  myNeededShortcuts.push_back(*it);
161  }
162  }
163  myShortcutsToValidate.clear();
164  return myNeededShortcuts;
165  }
166 
167 
168 private:
169  // perform dijkstra search under permission constraints
170  SUMOReal dijkstraTT(E* start, E* dest, const E* excluded, SVCPermissions permissions) {
171  init();
172  start->traveltime = 0;
173  start->depth = 0;
174  myFrontier.push_back(start);
175  // build SPT
176  while (!myFrontier.empty()) {
177  E* min = myFrontier.front();
178  if (min == dest) {
179  return dest->traveltime;
180  }
181  pop_heap(myFrontier.begin(), myFrontier.end(), myCmp);
182  myFrontier.pop_back();
183  myFound.push_back(min);
184  min->visited = true;
185  if (min->depth < myMaxDepth) {
186  for (typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
187  C& con = *it;
188  E* follower = con.target;
189  if (follower == excluded) {
190  continue;
191  }
192  if ((con.permissions & permissions) != permissions) {
193  continue;
194  }
195  const SUMOReal traveltime = min->traveltime + con.cost;
196  const SUMOReal oldTraveltime = follower->traveltime;
197  if (!follower->visited && traveltime < oldTraveltime) {
198  follower->traveltime = traveltime;
199  follower->depth = min->depth + 1;
200  follower->permissions = (min->permissions & con.permissions);
201  if (oldTraveltime == std::numeric_limits<SUMOReal>::max()) {
202  myFrontier.push_back(follower);
203  push_heap(myFrontier.begin(), myFrontier.end(), myCmp);
204  } else {
205  push_heap(myFrontier.begin(),
206  find(myFrontier.begin(), myFrontier.end(), follower) + 1,
207  myCmp);
208  }
209  }
210  }
211  }
212  }
213  return dest->traveltime;
214  }
215 
216 
217  // helper method for debugging
218  void debugPrintVector(std::vector<E*>& vec, E* start, const E* excluded) {
219  std::cout << "computed SPT from '" << start->edge->getID() << "' (excluding " << excluded->edge->getID() << ") with " << myFound.size() << " edges\n";
220  for (typename std::vector<E*>::iterator it = vec.begin(); it != vec.end(); it++) {
221  E* e = *it;
222  std::cout << "(" << e->edge->getID() << "," << e->traveltime << ") ";
223  }
224  std::cout << "\n";
225  }
226 
228  std::vector<E*> myFrontier;
230  std::vector<E*> myFound;
231 
233  EdgeByTTComparator myCmp;
234 
237 
240 
242  CHConnectionPairs myShortcutsToValidate;
244  CHConnectionPairs myNeededShortcuts;
245 };
246 
247 #endif
248 
249 /****************************************************************************/
250 
SUMOReal dijkstraTT(E *start, E *dest, const E *excluded, SVCPermissions permissions)
Definition: SPTree.h:170
#define min(a, b)
Definition: polyfonts.c:66
SPTree(int maxDepth, bool validatePermissions)
Constructor.
Definition: SPTree.h:72
int SVCPermissions
void debugPrintVector(std::vector< E * > &vec, E *start, const E *excluded)
Definition: SPTree.h:218
EdgeByTTComparator myCmp
comparator for search queue
Definition: SPTree.h:233
CHConnectionPairs myNeededShortcuts
vector of needed shortcuts after validation
Definition: SPTree.h:244
std::vector< CHConnectionPair > CHConnectionPairs
Definition: SPTree.h:51
bool operator()(const E *a, const E *b) const
Comparing method.
Definition: SPTree.h:60
void registerForValidation(const C *aInfo, const C *fInfo)
save source/target pair for later validation
Definition: SPTree.h:142
#define max(a, b)
Definition: polyfonts.c:65
std::vector< E * > myFound
the list of visited edges (used when resetting)
Definition: SPTree.h:230
const CHConnectionPairs & getNeededShortcuts(const E *excluded)
Definition: SPTree.h:150
std::pair< const C *, const C * > CHConnectionPair
Definition: SPTree.h:50
std::vector< E * > myFrontier
the min edge heap
Definition: SPTree.h:228
bool myValidatePermissions
whether permissions should be validated
Definition: SPTree.h:239
Definition: SPTree.h:46
std::vector< C > CHConnections
Definition: SPTree.h:49
void init()
Definition: SPTree.h:78
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:95
#define SUMOReal
Definition: config.h:214
CHConnectionPairs myShortcutsToValidate
vector of needed shortcuts after validation
Definition: SPTree.h:242
bool validatePermissions()
whether permissions should be validated;
Definition: SPTree.h:137
int myMaxDepth
maximum search depth
Definition: SPTree.h:236