Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2026 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 68115328 : if (a->traveltime == b->traveltime) {
52 836526 : return a->edge->getNumericalID() > b->edge->getNumericalID();
53 : }
54 67278802 : return a->traveltime > b->traveltime;
55 : }
56 : };
57 :
58 :
59 : /**
60 : * @brief Constructor
61 : */
62 666 : SPTree(int maxDepth, bool validatePermissions) :
63 666 : myMaxDepth(maxDepth),
64 666 : myValidatePermissions(validatePermissions) {
65 : }
66 :
67 :
68 169477 : void init() {
69 : // all EdgeInfos touched in the previous query are either in myFrontier or myFound: clean those up
70 169477 : for (typename std::vector<E*>::iterator i = myFrontier.begin(); i != myFrontier.end(); i++) {
71 0 : (*i)->reset();
72 : }
73 : myFrontier.clear();
74 11638232 : for (typename std::vector<E*>::iterator i = myFound.begin(); i != myFound.end(); i++) {
75 11468755 : (*i)->reset();
76 : }
77 : myFound.clear();
78 169477 : }
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 169463 : void rebuildFrom(E* start, const E* excluded) {
86 169463 : init();
87 169463 : start->traveltime = 0;
88 169463 : start->depth = 0;
89 169463 : start->permissions = start->edge->getPermissions();
90 169463 : myFrontier.push_back(start);
91 : // build SPT
92 11638823 : while (!myFrontier.empty()) {
93 11469360 : E* min = myFrontier.front();
94 11469360 : std::pop_heap(myFrontier.begin(), myFrontier.end(), myCmp);
95 : myFrontier.pop_back();
96 11469360 : myFound.push_back(min);
97 11469360 : min->visited = true;
98 11469360 : if (min->depth < myMaxDepth) {
99 67010513 : for (typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
100 : C& con = *it;
101 60013401 : E* follower = con.target;
102 60013401 : if (follower == excluded) {
103 1181237 : continue;
104 : }
105 58832164 : const double traveltime = min->traveltime + con.cost;
106 58832164 : const double oldTraveltime = follower->traveltime;
107 58832164 : if (!follower->visited && traveltime < oldTraveltime) {
108 14417136 : follower->traveltime = traveltime;
109 14417136 : follower->depth = min->depth + 1;
110 14417136 : follower->permissions = (min->permissions & con.permissions);
111 14417136 : if (oldTraveltime == std::numeric_limits<double>::max()) {
112 11299897 : myFrontier.push_back(follower);
113 : std::push_heap(myFrontier.begin(), myFrontier.end(), myCmp);
114 : } else {
115 : std::push_heap(myFrontier.begin(),
116 3117239 : std::find(myFrontier.begin(), myFrontier.end(), follower) + 1,
117 : myCmp);
118 : }
119 : }
120 : }
121 : }
122 : }
123 169463 : }
124 :
125 :
126 : /// @brief whether permissions should be validated;
127 : inline bool validatePermissions() {
128 130292 : 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 14 : myShortcutsToValidate.push_back(CHConnectionPair(aInfo, fInfo));
135 14 : }
136 :
137 :
138 : /* @brief for each path source->excluded->target try to find a witness with a witness
139 : * with equal permissions */
140 140 : const CHConnectionPairs& getNeededShortcuts(const E* excluded) {
141 : assert(myValidatePermissions);
142 : myNeededShortcuts.clear();
143 154 : for (typename CHConnectionPairs::iterator it = myShortcutsToValidate.begin(); it != myShortcutsToValidate.end(); ++it) {
144 14 : const C* const aInfo = it->first;
145 14 : const C* const fInfo = it->second;
146 14 : const double bestWitness = dijkstraTT(
147 14 : aInfo->target, fInfo->target, excluded, (aInfo->permissions & fInfo->permissions));
148 14 : const double viaCost = aInfo->cost + fInfo->cost;
149 14 : if (viaCost < bestWitness) {
150 14 : myNeededShortcuts.push_back(*it);
151 : }
152 : }
153 : myShortcutsToValidate.clear();
154 140 : return myNeededShortcuts;
155 : }
156 :
157 :
158 : private:
159 : // perform dijkstra search under permission constraints
160 14 : double dijkstraTT(E* start, E* dest, const E* excluded, SVCPermissions permissions) {
161 14 : init();
162 14 : start->traveltime = 0;
163 14 : start->depth = 0;
164 14 : myFrontier.push_back(start);
165 : // build SPT
166 28 : while (!myFrontier.empty()) {
167 14 : E* min = myFrontier.front();
168 14 : if (min == dest) {
169 0 : return dest->traveltime;
170 : }
171 14 : std::pop_heap(myFrontier.begin(), myFrontier.end(), myCmp);
172 : myFrontier.pop_back();
173 14 : myFound.push_back(min);
174 14 : min->visited = true;
175 14 : if (min->depth < myMaxDepth) {
176 42 : for (typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
177 : C& con = *it;
178 28 : E* follower = con.target;
179 28 : if (follower == excluded) {
180 28 : continue;
181 : }
182 14 : if ((con.permissions & permissions) != permissions) {
183 14 : 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 14 : 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 : };
|
