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-2018 German Aerospace Center (DLR) and others.
4 // This program and the accompanying materials
5 // are made available under the terms of the Eclipse Public License v2.0
6 // which accompanies this distribution, and is available at
7 // http://www.eclipse.org/legal/epl-v20.html
8 // SPDX-License-Identifier: EPL-2.0
9 /****************************************************************************/
16 // Shortest Path tree of limited depth using Dijkstras algorithm
17 /****************************************************************************/
18 #ifndef SPTree_h
19 #define SPTree_h
20 
21 
22 // ===========================================================================
23 // included modules
24 // ===========================================================================
25 #include <config.h>
26 
27 #include <string>
28 #include <functional>
29 #include <vector>
30 #include <set>
31 #include <limits>
32 #include <algorithm>
33 #include <iterator>
35 #include <utils/common/StdDefs.h>
36 
37 
38 template<class E, class C>
39 class SPTree {
40 
41 public:
42  typedef std::vector<C> CHConnections;
43  typedef std::pair<const C*, const C*> CHConnectionPair;
44  typedef std::vector<CHConnectionPair> CHConnectionPairs;
45 
51  public:
53  bool operator()(const E* a, const E* b) const {
54  if (a->traveltime == b->traveltime) {
55  return a->edge->getNumericalID() > b->edge->getNumericalID();
56  }
57  return a->traveltime > b->traveltime;
58  }
59  };
60 
61 
65  SPTree(int maxDepth, bool validatePermissions) :
66  myMaxDepth(maxDepth),
67  myValidatePermissions(validatePermissions) {
68  }
69 
70 
71  void init() {
72  // all EdgeInfos touched in the previous query are either in myFrontier or myFound: clean those up
73  for (typename std::vector<E*>::iterator i = myFrontier.begin(); i != myFrontier.end(); i++) {
74  (*i)->reset();
75  }
76  myFrontier.clear();
77  for (typename std::vector<E*>::iterator i = myFound.begin(); i != myFound.end(); i++) {
78  (*i)->reset();
79  }
80  myFound.clear();
81  }
82 
83 
88  void rebuildFrom(E* start, const E* excluded) {
89  init();
90  start->traveltime = 0;
91  start->depth = 0;
92  start->permissions = start->edge->getPermissions();
93  myFrontier.push_back(start);
94  // build SPT
95  while (!myFrontier.empty()) {
96  E* min = myFrontier.front();
97  pop_heap(myFrontier.begin(), myFrontier.end(), myCmp);
98  myFrontier.pop_back();
99  myFound.push_back(min);
100  min->visited = true;
101  if (min->depth < myMaxDepth) {
102  for (typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
103  C& con = *it;
104  E* follower = con.target;
105  if (follower == excluded) {
106  continue;
107  }
108  const double traveltime = min->traveltime + con.cost;
109  const double oldTraveltime = follower->traveltime;
110  if (!follower->visited && traveltime < oldTraveltime) {
111  follower->traveltime = traveltime;
112  follower->depth = min->depth + 1;
113  follower->permissions = (min->permissions & con.permissions);
114  if (oldTraveltime == std::numeric_limits<double>::max()) {
115  myFrontier.push_back(follower);
116  push_heap(myFrontier.begin(), myFrontier.end(), myCmp);
117  } else {
118  push_heap(myFrontier.begin(),
119  find(myFrontier.begin(), myFrontier.end(), follower) + 1,
120  myCmp);
121  }
122  }
123  }
124  }
125  }
126  }
127 
128 
130  inline bool validatePermissions() {
131  return myValidatePermissions;
132  }
133 
135  void registerForValidation(const C* aInfo, const C* fInfo) {
136  assert(myValidatePermissions);
137  myShortcutsToValidate.push_back(CHConnectionPair(aInfo, fInfo));
138  }
139 
140 
141  /* @brief for each path source->excluded->target try to find a witness with a witness
142  * with equal permissions */
143  const CHConnectionPairs& getNeededShortcuts(const E* excluded) {
144  assert(myValidatePermissions);
145  myNeededShortcuts.clear();
146  for (typename CHConnectionPairs::iterator it = myShortcutsToValidate.begin(); it != myShortcutsToValidate.end(); ++it) {
147  const C* const aInfo = it->first;
148  const C* const fInfo = it->second;
149  const double bestWitness = dijkstraTT(
150  aInfo->target, fInfo->target, excluded, (aInfo->permissions & fInfo->permissions));
151  const double viaCost = aInfo->cost + fInfo->cost;
152  if (viaCost < bestWitness) {
153  myNeededShortcuts.push_back(*it);
154  }
155  }
156  myShortcutsToValidate.clear();
157  return myNeededShortcuts;
158  }
159 
160 
161 private:
162  // perform dijkstra search under permission constraints
163  double dijkstraTT(E* start, E* dest, const E* excluded, SVCPermissions permissions) {
164  init();
165  start->traveltime = 0;
166  start->depth = 0;
167  myFrontier.push_back(start);
168  // build SPT
169  while (!myFrontier.empty()) {
170  E* min = myFrontier.front();
171  if (min == dest) {
172  return dest->traveltime;
173  }
174  pop_heap(myFrontier.begin(), myFrontier.end(), myCmp);
175  myFrontier.pop_back();
176  myFound.push_back(min);
177  min->visited = true;
178  if (min->depth < myMaxDepth) {
179  for (typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
180  C& con = *it;
181  E* follower = con.target;
182  if (follower == excluded) {
183  continue;
184  }
185  if ((con.permissions & permissions) != permissions) {
186  continue;
187  }
188  const double traveltime = min->traveltime + con.cost;
189  const double oldTraveltime = follower->traveltime;
190  if (!follower->visited && traveltime < oldTraveltime) {
191  follower->traveltime = traveltime;
192  follower->depth = min->depth + 1;
193  follower->permissions = (min->permissions & con.permissions);
194  if (oldTraveltime == std::numeric_limits<double>::max()) {
195  myFrontier.push_back(follower);
196  push_heap(myFrontier.begin(), myFrontier.end(), myCmp);
197  } else {
198  push_heap(myFrontier.begin(),
199  find(myFrontier.begin(), myFrontier.end(), follower) + 1,
200  myCmp);
201  }
202  }
203  }
204  }
205  }
206  return dest->traveltime;
207  }
208 
209 
210  // helper method for debugging
211  void debugPrintVector(std::vector<E*>& vec, E* start, const E* excluded) {
212  std::cout << "computed SPT from '" << start->edge->getID() << "' (excluding " << excluded->edge->getID() << ") with " << myFound.size() << " edges\n";
213  for (typename std::vector<E*>::iterator it = vec.begin(); it != vec.end(); it++) {
214  E* e = *it;
215  std::cout << "(" << e->edge->getID() << "," << e->traveltime << ") ";
216  }
217  std::cout << "\n";
218  }
219 
221  std::vector<E*> myFrontier;
223  std::vector<E*> myFound;
224 
226  EdgeByTTComparator myCmp;
227 
230 
233 
235  CHConnectionPairs myShortcutsToValidate;
237  CHConnectionPairs myNeededShortcuts;
238 };
239 
240 #endif
241 
242 /****************************************************************************/
243 
double dijkstraTT(E *start, E *dest, const E *excluded, SVCPermissions permissions)
Definition: SPTree.h:163
SPTree(int maxDepth, bool validatePermissions)
Constructor.
Definition: SPTree.h:65
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:226
CHConnectionPairs myNeededShortcuts
vector of needed shortcuts after validation
Definition: SPTree.h:237
std::vector< CHConnectionPair > CHConnectionPairs
Definition: SPTree.h:44
void registerForValidation(const C *aInfo, const C *fInfo)
save source/target pair for later validation
Definition: SPTree.h:135
std::vector< E * > myFound
the list of visited edges (used when resetting)
Definition: SPTree.h:223
const CHConnectionPairs & getNeededShortcuts(const E *excluded)
Definition: SPTree.h:143
std::pair< const C *, const C * > CHConnectionPair
Definition: SPTree.h:43
std::vector< E * > myFrontier
the min edge heap
Definition: SPTree.h:221
void debugPrintVector(std::vector< E *> &vec, E *start, const E *excluded)
Definition: SPTree.h:211
bool myValidatePermissions
whether permissions should be validated
Definition: SPTree.h:232
Definition: SPTree.h:39
std::vector< C > CHConnections
Definition: SPTree.h:42
void init()
Definition: SPTree.h:71
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:88
CHConnectionPairs myShortcutsToValidate
vector of needed shortcuts after validation
Definition: SPTree.h:235
bool validatePermissions()
whether permissions should be validated;
Definition: SPTree.h:130
bool operator()(const E *a, const E *b) const
Comparing method.
Definition: SPTree.h:53
int myMaxDepth
maximum search depth
Definition: SPTree.h:229