Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2024 German Aerospace Center (DLR) and others.
4 : // This program and the accompanying materials are made available under the
5 : // terms of the Eclipse Public License 2.0 which is available at
6 : // https://www.eclipse.org/legal/epl-2.0/
7 : // This Source Code may also be made available under the following Secondary
8 : // Licenses when the conditions for such availability set forth in the Eclipse
9 : // Public License 2.0 are satisfied: GNU General Public License, version 2
10 : // or later which is available at
11 : // https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12 : // SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13 : /****************************************************************************/
14 : /// @file SPTree.h
15 : /// @author Laura Bieker
16 : /// @author Michael Behrisch
17 : /// @date February 2012
18 : ///
19 : // Shortest Path tree of limited depth using Dijkstras algorithm
20 : /****************************************************************************/
21 : #pragma once
22 : #include <config.h>
23 :
24 : #include <string>
25 : #include <functional>
26 : #include <vector>
27 : #include <set>
28 : #include <limits>
29 : #include <algorithm>
30 : #include <iterator>
31 : #include <utils/common/MsgHandler.h>
32 : #include <utils/common/StdDefs.h>
33 :
34 :
35 : template<class E, class C>
36 : class SPTree {
37 :
38 : public:
39 : typedef std::vector<C> CHConnections;
40 : typedef std::pair<const C*, const C*> CHConnectionPair;
41 : typedef std::vector<CHConnectionPair> CHConnectionPairs;
42 :
43 : /**
44 : * @class EdgeInfoByEffortComparator
45 : * Class to compare (and so sort) nodes by their effort
46 : */
47 : class EdgeByTTComparator {
48 : public:
49 : /// Comparing method
50 : bool operator()(const E* a, const E* b) const {
51 50634869 : if (a->traveltime == b->traveltime) {
52 3666387 : return a->edge->getNumericalID() > b->edge->getNumericalID();
53 : }
54 46968482 : return a->traveltime > b->traveltime;
55 : }
56 : };
57 :
58 :
59 : /**
60 : * @brief Constructor
61 : */
62 574 : SPTree(int maxDepth, bool validatePermissions) :
63 574 : myMaxDepth(maxDepth),
64 574 : myValidatePermissions(validatePermissions) {
65 : }
66 :
67 :
68 128375 : void init() {
69 : // all EdgeInfos touched in the previous query are either in myFrontier or myFound: clean those up
70 128375 : for (typename std::vector<E*>::iterator i = myFrontier.begin(); i != myFrontier.end(); i++) {
71 0 : (*i)->reset();
72 : }
73 : myFrontier.clear();
74 8756310 : for (typename std::vector<E*>::iterator i = myFound.begin(); i != myFound.end(); i++) {
75 8627935 : (*i)->reset();
76 : }
77 : myFound.clear();
78 128375 : }
79 :
80 :
81 : /**
82 : * @brief build a shortest path tree from start to a depth of myMaxdepth. The given
83 : * edge is excluded from this tree
84 : */
85 128355 : void rebuildFrom(E* start, const E* excluded) {
86 128355 : init();
87 128355 : start->traveltime = 0;
88 128355 : start->depth = 0;
89 128355 : start->permissions = start->edge->getPermissions();
90 128355 : myFrontier.push_back(start);
91 : // build SPT
92 8756803 : while (!myFrontier.empty()) {
93 8628448 : E* min = myFrontier.front();
94 8628448 : std::pop_heap(myFrontier.begin(), myFrontier.end(), myCmp);
95 : myFrontier.pop_back();
96 8628448 : myFound.push_back(min);
97 8628448 : min->visited = true;
98 8628448 : if (min->depth < myMaxDepth) {
99 48943291 : for (typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
100 : C& con = *it;
101 43674651 : E* follower = con.target;
102 43674651 : if (follower == excluded) {
103 865718 : continue;
104 : }
105 42808933 : const double traveltime = min->traveltime + con.cost;
106 42808933 : const double oldTraveltime = follower->traveltime;
107 42808933 : if (!follower->visited && traveltime < oldTraveltime) {
108 10616122 : follower->traveltime = traveltime;
109 10616122 : follower->depth = min->depth + 1;
110 10616122 : follower->permissions = (min->permissions & con.permissions);
111 10616122 : if (oldTraveltime == std::numeric_limits<double>::max()) {
112 8500093 : myFrontier.push_back(follower);
113 : std::push_heap(myFrontier.begin(), myFrontier.end(), myCmp);
114 : } else {
115 : std::push_heap(myFrontier.begin(),
116 2116029 : std::find(myFrontier.begin(), myFrontier.end(), follower) + 1,
117 : myCmp);
118 : }
119 : }
120 : }
121 : }
122 : }
123 128355 : }
124 :
125 :
126 : /// @brief whether permissions should be validated;
127 : inline bool validatePermissions() {
128 105236 : return myValidatePermissions;
129 : }
130 :
131 : /// @brief save source/target pair for later validation
132 : void registerForValidation(const C* aInfo, const C* fInfo) {
133 : assert(myValidatePermissions);
134 20 : myShortcutsToValidate.push_back(CHConnectionPair(aInfo, fInfo));
135 20 : }
136 :
137 :
138 : /* @brief for each path source->excluded->target try to find a witness with a witness
139 : * with equal permissions */
140 200 : const CHConnectionPairs& getNeededShortcuts(const E* excluded) {
141 : assert(myValidatePermissions);
142 : myNeededShortcuts.clear();
143 220 : for (typename CHConnectionPairs::iterator it = myShortcutsToValidate.begin(); it != myShortcutsToValidate.end(); ++it) {
144 20 : const C* const aInfo = it->first;
145 20 : const C* const fInfo = it->second;
146 20 : const double bestWitness = dijkstraTT(
147 20 : aInfo->target, fInfo->target, excluded, (aInfo->permissions & fInfo->permissions));
148 20 : const double viaCost = aInfo->cost + fInfo->cost;
149 20 : if (viaCost < bestWitness) {
150 20 : myNeededShortcuts.push_back(*it);
151 : }
152 : }
153 : myShortcutsToValidate.clear();
154 200 : return myNeededShortcuts;
155 : }
156 :
157 :
158 : private:
159 : // perform dijkstra search under permission constraints
160 20 : double dijkstraTT(E* start, E* dest, const E* excluded, SVCPermissions permissions) {
161 20 : init();
162 20 : start->traveltime = 0;
163 20 : start->depth = 0;
164 20 : myFrontier.push_back(start);
165 : // build SPT
166 40 : while (!myFrontier.empty()) {
167 20 : E* min = myFrontier.front();
168 20 : if (min == dest) {
169 0 : return dest->traveltime;
170 : }
171 20 : std::pop_heap(myFrontier.begin(), myFrontier.end(), myCmp);
172 : myFrontier.pop_back();
173 20 : myFound.push_back(min);
174 20 : min->visited = true;
175 20 : if (min->depth < myMaxDepth) {
176 60 : for (typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
177 : C& con = *it;
178 40 : E* follower = con.target;
179 40 : if (follower == excluded) {
180 40 : continue;
181 : }
182 20 : if ((con.permissions & permissions) != permissions) {
183 20 : continue;
184 : }
185 0 : const double traveltime = min->traveltime + con.cost;
186 0 : const double oldTraveltime = follower->traveltime;
187 0 : if (!follower->visited && traveltime < oldTraveltime) {
188 0 : follower->traveltime = traveltime;
189 0 : follower->depth = min->depth + 1;
190 0 : follower->permissions = (min->permissions & con.permissions);
191 0 : if (oldTraveltime == std::numeric_limits<double>::max()) {
192 0 : myFrontier.push_back(follower);
193 : std::push_heap(myFrontier.begin(), myFrontier.end(), myCmp);
194 : } else {
195 : std::push_heap(myFrontier.begin(),
196 0 : std::find(myFrontier.begin(), myFrontier.end(), follower) + 1,
197 : myCmp);
198 : }
199 : }
200 : }
201 : }
202 : }
203 20 : return dest->traveltime;
204 : }
205 :
206 :
207 : // helper method for debugging
208 : void debugPrintVector(std::vector<E*>& vec, E* start, const E* excluded) {
209 : std::cout << "computed SPT from '" << start->edge->getID() << "' (excluding " << excluded->edge->getID() << ") with " << myFound.size() << " edges\n";
210 : for (typename std::vector<E*>::iterator it = vec.begin(); it != vec.end(); it++) {
211 : E* e = *it;
212 : std::cout << "(" << e->edge->getID() << "," << e->traveltime << ") ";
213 : }
214 : std::cout << "\n";
215 : }
216 :
217 : /// @brief the min edge heap
218 : std::vector<E*> myFrontier;
219 : /// @brief the list of visited edges (used when resetting)
220 : std::vector<E*> myFound;
221 :
222 : /// @brief comparator for search queue
223 : EdgeByTTComparator myCmp;
224 :
225 : /// @brief maximum search depth
226 : int myMaxDepth;
227 :
228 : /// @brief whether permissions should be validated
229 : bool myValidatePermissions;
230 :
231 : /// @brief vector of needed shortcuts after validation
232 : CHConnectionPairs myShortcutsToValidate;
233 : /// @brief vector of needed shortcuts after validation
234 : CHConnectionPairs myNeededShortcuts;
235 : };
|
