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 /****************************************************************************/
10 /// @file    SPTree.h
11 /// @author  Laura Bieker
12 /// @author  Michael Behrisch
13 /// @date    February 2012
14 /// @version $Id$
15 ///
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>
34 #include <utils/common/MsgHandler.h>
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 
46     /**
47      * @class EdgeInfoByEffortComparator
48      * Class to compare (and so sort) nodes by their effort
49      */
50     class EdgeByTTComparator {
51     public:
52         /// Comparing method
operator()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 
62     /**
63      * @brief Constructor
64      */
SPTree(int maxDepth,bool validatePermissions)65     SPTree(int maxDepth, bool validatePermissions) :
66         myMaxDepth(maxDepth),
67         myValidatePermissions(validatePermissions) {
68     }
69 
70 
init()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 
84     /**
85      * @brief build a shortest path tree from start to a depth of myMaxdepth. The given
86      * edge is excluded from this tree
87      */
rebuildFrom(E * start,const E * excluded)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             std::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                             std::push_heap(myFrontier.begin(), myFrontier.end(), myCmp);
117                         } else {
118                             std::push_heap(myFrontier.begin(),
119                                            std::find(myFrontier.begin(), myFrontier.end(), follower) + 1,
120                                            myCmp);
121                         }
122                     }
123                 }
124             }
125         }
126     }
127 
128 
129     /// @brief whether permissions should be validated;
validatePermissions()130     inline bool validatePermissions() {
131         return myValidatePermissions;
132     }
133 
134     /// @brief save source/target pair for later validation
registerForValidation(const C * aInfo,const C * fInfo)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 */
getNeededShortcuts(const E * excluded)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
dijkstraTT(E * start,E * dest,const E * excluded,SVCPermissions permissions)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             std::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                             std::push_heap(myFrontier.begin(), myFrontier.end(), myCmp);
197                         } else {
198                             std::push_heap(myFrontier.begin(),
199                                            std::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
debugPrintVector(std::vector<E * > & vec,E * start,const E * excluded)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 
220     /// @brief the min edge heap
221     std::vector<E*> myFrontier;
222     /// @brief the list of visited edges (used when resetting)
223     std::vector<E*> myFound;
224 
225     /// @brief comparator for search queue
226     EdgeByTTComparator myCmp;
227 
228     /// @brief maximum search depth
229     int myMaxDepth;
230 
231     /// @brief whether permissions should be validated
232     bool myValidatePermissions;
233 
234     /// @brief vector of needed shortcuts after validation
235     CHConnectionPairs myShortcutsToValidate;
236     /// @brief vector of needed shortcuts after validation
237     CHConnectionPairs myNeededShortcuts;
238 };
239 
240 #endif
241 
242 /****************************************************************************/
243 
244