Eclipse SUMO - Simulation of Urban MObility
Loading...
Searching...
No Matches
SPTree.h
Go to the documentation of this file.
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/****************************************************************************/
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>
33
34
35template<class E, class C>
36class SPTree {
37
38public:
39 typedef std::vector<C> CHConnections;
40 typedef std::pair<const C*, const C*> CHConnectionPair;
41 typedef std::vector<CHConnectionPair> CHConnectionPairs;
42
48 public:
50 bool operator()(const E* a, const E* b) const {
51 if (a->traveltime == b->traveltime) {
52 return a->edge->getNumericalID() > b->edge->getNumericalID();
53 }
54 return a->traveltime > b->traveltime;
55 }
56 };
57
58
62 SPTree(int maxDepth, bool validatePermissions) :
63 myMaxDepth(maxDepth),
65 }
66
67
68 void init() {
69 // all EdgeInfos touched in the previous query are either in myFrontier or myFound: clean those up
70 for (typename std::vector<E*>::iterator i = myFrontier.begin(); i != myFrontier.end(); i++) {
71 (*i)->reset();
72 }
73 myFrontier.clear();
74 for (typename std::vector<E*>::iterator i = myFound.begin(); i != myFound.end(); i++) {
75 (*i)->reset();
76 }
77 myFound.clear();
78 }
79
80
85 void rebuildFrom(E* start, const E* excluded) {
86 init();
87 start->traveltime = 0;
88 start->depth = 0;
89 start->permissions = start->edge->getPermissions();
90 myFrontier.push_back(start);
91 // build SPT
92 while (!myFrontier.empty()) {
93 E* min = myFrontier.front();
94 std::pop_heap(myFrontier.begin(), myFrontier.end(), myCmp);
95 myFrontier.pop_back();
96 myFound.push_back(min);
97 min->visited = true;
98 if (min->depth < myMaxDepth) {
99 for (typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
100 C& con = *it;
101 E* follower = con.target;
102 if (follower == excluded) {
103 continue;
104 }
105 const double traveltime = min->traveltime + con.cost;
106 const double oldTraveltime = follower->traveltime;
107 if (!follower->visited && traveltime < oldTraveltime) {
108 follower->traveltime = traveltime;
109 follower->depth = min->depth + 1;
110 follower->permissions = (min->permissions & con.permissions);
111 if (oldTraveltime == std::numeric_limits<double>::max()) {
112 myFrontier.push_back(follower);
113 std::push_heap(myFrontier.begin(), myFrontier.end(), myCmp);
114 } else {
115 std::push_heap(myFrontier.begin(),
116 std::find(myFrontier.begin(), myFrontier.end(), follower) + 1,
117 myCmp);
118 }
119 }
120 }
121 }
122 }
123 }
124
125
127 inline bool validatePermissions() {
129 }
130
132 void registerForValidation(const C* aInfo, const C* fInfo) {
133 assert(myValidatePermissions);
134 myShortcutsToValidate.push_back(CHConnectionPair(aInfo, fInfo));
135 }
136
137
138 /* @brief for each path source->excluded->target try to find a witness with a witness
139 * with equal permissions */
140 const CHConnectionPairs& getNeededShortcuts(const E* excluded) {
141 assert(myValidatePermissions);
142 myNeededShortcuts.clear();
143 for (typename CHConnectionPairs::iterator it = myShortcutsToValidate.begin(); it != myShortcutsToValidate.end(); ++it) {
144 const C* const aInfo = it->first;
145 const C* const fInfo = it->second;
146 const double bestWitness = dijkstraTT(
147 aInfo->target, fInfo->target, excluded, (aInfo->permissions & fInfo->permissions));
148 const double viaCost = aInfo->cost + fInfo->cost;
149 if (viaCost < bestWitness) {
150 myNeededShortcuts.push_back(*it);
151 }
152 }
153 myShortcutsToValidate.clear();
154 return myNeededShortcuts;
155 }
156
157
158private:
159 // perform dijkstra search under permission constraints
160 double dijkstraTT(E* start, E* dest, const E* excluded, SVCPermissions permissions) {
161 init();
162 start->traveltime = 0;
163 start->depth = 0;
164 myFrontier.push_back(start);
165 // build SPT
166 while (!myFrontier.empty()) {
167 E* min = myFrontier.front();
168 if (min == dest) {
169 return dest->traveltime;
170 }
171 std::pop_heap(myFrontier.begin(), myFrontier.end(), myCmp);
172 myFrontier.pop_back();
173 myFound.push_back(min);
174 min->visited = true;
175 if (min->depth < myMaxDepth) {
176 for (typename CHConnections::iterator it = min->followers.begin(); it != min->followers.end(); it++) {
177 C& con = *it;
178 E* follower = con.target;
179 if (follower == excluded) {
180 continue;
181 }
182 if ((con.permissions & permissions) != permissions) {
183 continue;
184 }
185 const double traveltime = min->traveltime + con.cost;
186 const double oldTraveltime = follower->traveltime;
187 if (!follower->visited && traveltime < oldTraveltime) {
188 follower->traveltime = traveltime;
189 follower->depth = min->depth + 1;
190 follower->permissions = (min->permissions & con.permissions);
191 if (oldTraveltime == std::numeric_limits<double>::max()) {
192 myFrontier.push_back(follower);
193 std::push_heap(myFrontier.begin(), myFrontier.end(), myCmp);
194 } else {
195 std::push_heap(myFrontier.begin(),
196 std::find(myFrontier.begin(), myFrontier.end(), follower) + 1,
197 myCmp);
198 }
199 }
200 }
201 }
202 }
203 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
218 std::vector<E*> myFrontier;
220 std::vector<E*> myFound;
221
224
227
230
235};
long long int SVCPermissions
bitset where each bit declares whether a certain SVC may use this edge/lane
bool operator()(const E *a, const E *b) const
Comparing method.
Definition SPTree.h:50
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:85
void debugPrintVector(std::vector< E * > &vec, E *start, const E *excluded)
Definition SPTree.h:208
std::vector< E * > myFrontier
the min edge heap
Definition SPTree.h:218
std::pair< const C *, const C * > CHConnectionPair
Definition SPTree.h:40
CHConnectionPairs myNeededShortcuts
vector of needed shortcuts after validation
Definition SPTree.h:234
std::vector< C > CHConnections
Definition SPTree.h:39
void init()
Definition SPTree.h:68
std::vector< CHConnectionPair > CHConnectionPairs
Definition SPTree.h:41
std::vector< E * > myFound
the list of visited edges (used when resetting)
Definition SPTree.h:220
bool myValidatePermissions
whether permissions should be validated
Definition SPTree.h:229
CHConnectionPairs myShortcutsToValidate
vector of needed shortcuts after validation
Definition SPTree.h:232
bool validatePermissions()
whether permissions should be validated;
Definition SPTree.h:127
const CHConnectionPairs & getNeededShortcuts(const E *excluded)
Definition SPTree.h:140
SPTree(int maxDepth, bool validatePermissions)
Constructor.
Definition SPTree.h:62
void registerForValidation(const C *aInfo, const C *fInfo)
save source/target pair for later validation
Definition SPTree.h:132
int myMaxDepth
maximum search depth
Definition SPTree.h:226
EdgeByTTComparator myCmp
comparator for search queue
Definition SPTree.h:223
double dijkstraTT(E *start, E *dest, const E *excluded, SVCPermissions permissions)
Definition SPTree.h:160