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