Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2012-2025 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 AFCentralizedSPTree.h
15 : /// @author Ruediger Ebendt
16 : /// @date 01.12.2023
17 : ///
18 : // Class for a label-correcting algorithm calculating multiple shortest path
19 : // trees at once (centralized shortest path tree, cf. Hilger et al.)
20 : // Used for setting the arc flags for the arc flag router
21 : // @note Intended use is on a backward graph with flipped edges
22 : /****************************************************************************/
23 : #pragma once
24 : #include <config.h>
25 :
26 : #include <cassert>
27 : #include <string>
28 : #include <functional>
29 : #include <vector>
30 : #include <set>
31 : #include <limits>
32 : #include <algorithm>
33 : #include <iterator>
34 : #include <map>
35 : #include <iostream>
36 : #include <memory>
37 : #include <stdexcept>
38 : #include <cstddef>
39 : #include <utils/common/MsgHandler.h>
40 : #include <utils/common/StringTokenizer.h>
41 : #include <utils/common/StringUtils.h>
42 : #include <utils/common/StdDefs.h>
43 : #include <utils/common/ToString.h>
44 : #include <utils/iodevices/OutputDevice.h>
45 : #include <utils/common/SUMOTime.h>
46 : #include "SUMOAbstractRouter.h"
47 : #include "KDTreePartition.h"
48 : #include "AFInfo.h"
49 :
50 : //#define CSPT_WRITE_QGIS_FILTERS
51 : //#define CSPT_DEBUG_LEVEL_0
52 :
53 : template<class E, class N, class V>
54 : class AFCentralizedSPTree {
55 : public:
56 : typedef typename KDTreePartition<E, N, V>::Cell Cell;
57 : typedef typename AFInfo<E>::ArcInfo ArcInfo;
58 :
59 : class EdgeInfoComparator {
60 : public:
61 : /** @brief Constructor
62 : * @param[in] arcInfos The arc informations
63 : */
64 0 : EdgeInfoComparator(std::vector<ArcInfo*>& arcInfos) : myArcInfos(arcInfos) {
65 : }
66 :
67 : /** @brief Comparing method
68 : * @param[in] edgeInfo1 The first edge information
69 : * @param[in] edgeInfo2 The second edge information
70 : * @return true iff arc info key of the first edge is greater than that of the second
71 : * @note In case of ties: returns true iff the numerical id of the first edge is greater that that of the second
72 : */
73 : bool operator()(const typename SUMOAbstractRouter<E, V>::EdgeInfo* edgeInfo1,
74 : const typename SUMOAbstractRouter<E, V>::EdgeInfo* edgeInfo2) const {
75 0 : int index1 = edgeInfo1->edge->getNumericalID();
76 0 : int index2 = edgeInfo2->edge->getNumericalID();
77 0 : ArcInfo* arcInfo1 = myArcInfos[index1];
78 0 : ArcInfo* arcInfo2 = myArcInfos[index2];
79 0 : double key1 = arcInfo1->key;
80 0 : double key2 = arcInfo2->key;
81 :
82 0 : if (key1 == key2) { // tie
83 0 : return index1 > index2;
84 : }
85 0 : return key1 > key2;
86 : }
87 : private:
88 : std::vector<ArcInfo*>& myArcInfos;
89 : };
90 :
91 : /** @brief Constructor
92 : * @param[in] edges The edges
93 : * @param[in] arcInfos The arc informations (for arc flag routing)
94 : * @param[in] unbuildIsWarning The flag indicating whether network unbuilds should issue warnings or errors
95 : * @param[in] effortProvider The effort provider
96 : * @param[in] havePermissions The boolean flag indicating whether edge permissions need to be considered or not
97 : * @param[in] haveRestrictions The boolean flag indicating whether edge restrictions need to be considered or not
98 : */
99 0 : AFCentralizedSPTree(const std::vector<E*>& edges, std::vector<ArcInfo*>& arcInfos, bool unbuildIsWarning,
100 : SUMOAbstractRouter<E, V>* effortProvider,
101 : const bool havePermissions = false, const bool haveRestrictions = false) :
102 0 : myArcInfos(arcInfos),
103 0 : myHavePermissions(havePermissions),
104 0 : myHaveRestrictions(haveRestrictions),
105 0 : myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
106 0 : myEffortProvider(effortProvider),
107 0 : myMaxSpeed(NUMERICAL_EPS) {
108 0 : for (const E* const edge : edges) {
109 0 : myEdgeInfos.push_back(typename SUMOAbstractRouter<E, V>::EdgeInfo(edge));
110 0 : myMaxSpeed = MAX2(myMaxSpeed, edge->getSpeedLimit() * MAX2(1.0, edge->getLengthGeometryFactor()));
111 : }
112 0 : myComparator = new EdgeInfoComparator(myArcInfos);
113 0 : }
114 :
115 : /// @brief Destructor
116 0 : ~AFCentralizedSPTree() {
117 0 : delete myComparator;
118 0 : }
119 :
120 : /** @brief Returns true iff driving the given vehicle on the given edge is prohibited
121 : * @param[in] edge The edge
122 : * @param[in] vehicle The vehicle
123 : * @return true iff driving the given vehicle on the given edge is prohibited
124 : */
125 0 : bool isProhibited(const E* const edge, const V* const vehicle) const {
126 0 : return (myHavePermissions && edge->prohibits(vehicle)) || (myHaveRestrictions && edge->restricts(vehicle));
127 : }
128 :
129 : /** @brief Computes a shortest path tree for each boundary edge of the given cell, returns true iff this was successful
130 : * @note This is done for all such shortest path trees at once (i.e., a centralized shortest path tree is computed, see Hilger et al.)
131 : * @param[in] msTime The start time of the paths/routes in milliseconds
132 : * @param[in] cell The cell as a part of a k-d tree partition of the network
133 : * @param[in] vehicle The vehicle
134 : * @param[in] incomingEdgesOfOutgoingBoundaryEdges Maps each outgoing boundary edge to its incoming edges
135 : * @param[in] silent The boolean flag indicating whether the method stays silent or puts out messages
136 : * @return true iff the centralized shortest path tree could successfully be calculated
137 : */
138 0 : bool computeCentralizedSPTree(SUMOTime msTime, const Cell* cell, const V* const vehicle,
139 : const std::map<const E*, std::vector<const E*>>& incomingEdgesOfOutgoingBoundaryEdges,
140 : bool silent = false) {
141 : assert(cell != nullptr);
142 : const std::unordered_set<const E*>& fromEdges = cell->getOutgoingBoundaryEdges();
143 0 : if (fromEdges.empty()) { // nothing to do here
144 : return false;
145 : }
146 0 : double length = 0.; // dummy for the via edge cost update
147 0 : const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
148 0 : std::vector<const E*> fromEdgesAsVector(fromEdges.begin(), fromEdges.end());
149 0 : init(fromEdgesAsVector, vehicle, msTime);
150 : size_t numberOfVisitedFromEdges = 0;
151 : bool minIsFromEdge = false;
152 : #ifdef CSPT_DEBUG_LEVEL_0
153 : size_t numberOfTouchedSupercellEdges = 0;
154 : int num_visited = 0;
155 : #endif
156 : #ifdef _DEBUG
157 : const Cell* supercell = cell->getSupercell();
158 : #endif
159 : const bool mayRevisit = true;
160 :
161 0 : while (!myFrontierList.empty()) {
162 : #ifdef CSPT_DEBUG_LEVEL_0
163 : num_visited += 1;
164 : #endif
165 : // use the edge with the minimal length
166 0 : typename SUMOAbstractRouter<E, V>::EdgeInfo* minimumInfo = myFrontierList.front();
167 0 : const E* const minEdge = minimumInfo->edge;
168 : assert(!minEdge->isInternal());
169 0 : ArcInfo* minimumArcInfo = myArcInfos[minEdge->getNumericalID()];
170 0 : if (minimumInfo->visited || numberOfVisitedFromEdges < fromEdges.size()) {
171 : minIsFromEdge = incomingEdgesOfOutgoingBoundaryEdges.find(minEdge) != incomingEdgesOfOutgoingBoundaryEdges.end();
172 : } else {
173 : minIsFromEdge = false;
174 : }
175 0 : if (minIsFromEdge) {
176 0 : if (numberOfVisitedFromEdges < fromEdges.size()) {
177 0 : numberOfVisitedFromEdges++;
178 : }
179 : }
180 : assert(incomingEdgesOfOutgoingBoundaryEdges.size() == fromEdges.size());
181 : assert(minimumArcInfo->key != std::numeric_limits<double>::max() && minimumArcInfo->key != UNREACHABLE);
182 : size_t index;
183 : #ifdef CSPT_DEBUG_LEVEL_0
184 : if (supercell->contains(minEdge->getToJunction())) {
185 : // minEdge is a supercell edge (we check for the to-node since we work on a backward graph)
186 : if (!minimumArcInfo->touched) {
187 : numberOfTouchedSupercellEdges++;
188 : minimumArcInfo->touched = true;
189 : }
190 : }
191 : #endif
192 : #ifdef CSPT_DEBUG_LEVEL_0
193 : if (num_visited % 500 == 0) {
194 : std::cout << "num_visited: " << num_visited << ", numberOfTouchedSupercellEdges: " << numberOfTouchedSupercellEdges
195 : << ", minimumArcInfo->key: " << minimumArcInfo->key << std::endl;
196 : }
197 : #endif
198 0 : std::pop_heap(myFrontierList.begin(), myFrontierList.end(), *myComparator);
199 : myFrontierList.pop_back();
200 0 : myFound.push_back(minimumInfo);
201 0 : minimumInfo->visited = true;
202 0 : const double effortDelta = myEffortProvider->getEffort(minEdge, vehicle, minimumInfo->leaveTime);
203 0 : const double leaveTime = minimumInfo->leaveTime + myEffortProvider->getTravelTime(minEdge, vehicle, minimumInfo->leaveTime, effortDelta);
204 :
205 : // check all ways from the edge with the minimal length
206 0 : for (const std::pair<const E*, const E*>& follower : minEdge->getViaSuccessors(vClass)) {
207 : assert(!follower.first->isInternal());
208 : bool wasPushedToHeap = false;
209 0 : auto& followerInfo = myEdgeInfos[follower.first->getNumericalID()];
210 0 : ArcInfo* followerArcInfo = myArcInfos[follower.first->getNumericalID()];
211 : // check whether it can be used
212 0 : if (followerInfo.prohibited || isProhibited(follower.first, vehicle)) {
213 0 : if (!silent) {
214 0 : myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on source edge '" + followerInfo.edge->getID() + "'.");
215 : }
216 0 : continue;
217 : }
218 :
219 0 : if (followerArcInfo->effortsToBoundaryNodes.empty()) { // non-initialized non-supercell edge
220 : assert(!supercell->contains(follower.first->getToJunction()));
221 0 : std::fill_n(std::back_inserter(followerArcInfo->effortsToBoundaryNodes),
222 : minimumArcInfo->effortsToBoundaryNodes.size(), std::numeric_limits<double>::max());
223 : }
224 :
225 : double key = std::numeric_limits<double>::max();
226 : assert(followerArcInfo->effortsToBoundaryNodes.size() == minimumArcInfo->effortsToBoundaryNodes.size());
227 : bool hasImproved = false;
228 : // loop over all boundary nodes
229 0 : for (index = 0; index < followerArcInfo->effortsToBoundaryNodes.size(); index++) {
230 : // is minEdge a from-edge (i.e., an outgoing boundary edge of the passed cell),
231 : // and 'index' not the index of its from-node (i.e., not of the 'own' boundary node)?
232 0 : if (minIsFromEdge && (incomingEdgesOfOutgoingBoundaryEdges.at(minEdge))[index]) {
233 : // if yes, assign the successor edges of the incoming edge of minEdge on the shortest route from
234 : // the boundary node with the index 'index' to followersOfIncomingEdge
235 : assert((incomingEdgesOfOutgoingBoundaryEdges.at(minEdge)).size()
236 : == followerArcInfo->effortsToBoundaryNodes.size());
237 : const std::vector<std::pair<const E*, const E*>>& followersOfIncomingEdge
238 0 : = ((incomingEdgesOfOutgoingBoundaryEdges.at(minEdge))[index])->getViaSuccessors(vClass);
239 : // is the current follower among said successor edges?
240 : bool turningAllowed = false;
241 0 : for (std::pair<const E*, const E*> followerOfIncomingEdge : followersOfIncomingEdge) {
242 0 : if (follower.first == followerOfIncomingEdge.first) {
243 : turningAllowed = true;
244 : break;
245 : }
246 : }
247 : // if not, then turning from said incoming edge to the current follower is not allowed
248 : // and we mustn't propagate the distance to said boundary node
249 : // instead simply skip this follower
250 0 : if (!turningAllowed) {
251 0 : continue;
252 : }
253 : }
254 : // propagate distances to other boundary nodes
255 0 : double effortToFollower = minimumArcInfo->effortsToBoundaryNodes[index] == UNREACHABLE ?
256 : UNREACHABLE : minimumArcInfo->effortsToBoundaryNodes[index] + effortDelta;
257 0 : if (effortToFollower == UNREACHABLE) {
258 0 : continue; // no need to consider this follower
259 : }
260 0 : double time = leaveTime;
261 0 : myEffortProvider->updateViaEdgeCost(follower.second, vehicle, time, effortToFollower, length);
262 0 : if (effortToFollower < key) {
263 : key = effortToFollower;
264 : }
265 0 : const double oldEffort = followerArcInfo->effortsToBoundaryNodes[index];
266 0 : if (oldEffort != std::numeric_limits<double>::max()) {
267 : wasPushedToHeap = true; // must have been pushed to heap during an earlier visit
268 : }
269 :
270 0 : if ((!followerInfo.visited || mayRevisit)
271 : && effortToFollower < oldEffort) {
272 : hasImproved = true;
273 0 : followerArcInfo->effortsToBoundaryNodes[index] = effortToFollower;
274 : }
275 : } // end index loop
276 :
277 0 : if (!hasImproved) {
278 0 : continue; // no need to re-enque this follower, continue w/ next one
279 : }
280 0 : followerArcInfo->key = key;
281 0 : if (!wasPushedToHeap) {
282 0 : myFrontierList.push_back(&followerInfo);
283 0 : std::push_heap(myFrontierList.begin(), myFrontierList.end(), *myComparator);
284 : } else {
285 0 : auto fi = std::find(myFrontierList.begin(), myFrontierList.end(), &followerInfo);
286 0 : if (fi == myFrontierList.end()) { // has already been expanded, reinsert into frontier
287 : assert(mayRevisit);
288 0 : myFrontierList.push_back(&followerInfo);
289 0 : std::push_heap(myFrontierList.begin(), myFrontierList.end(), *myComparator);
290 : } else {
291 0 : std::push_heap(myFrontierList.begin(), fi + 1, *myComparator);
292 : }
293 : }
294 : } // end follower loop
295 : } // end while (!myFrontierList.empty())
296 :
297 : #ifdef CSPT_DEBUG_LEVEL_0
298 : std::cout << "centralizedSPTree finished (queue empty)." << std::endl;
299 : #endif
300 : return true;
301 0 : }
302 :
303 : protected:
304 : /** @brief Initialize the arc flag router
305 : * @param[in] fromEdges The container of from-/head/source edges
306 : * @param[in] vehicle The vehicle
307 : * @param[in] msTime The start time of the paths/routes in milliseconds
308 : */
309 : void init(std::vector<const E*> fromEdges, const V* const vehicle, SUMOTime msTime);
310 : /// @brief The min edge heap
311 : /// @note A container for reusage of the min edge heap
312 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFrontierList;
313 : /// @brief The list of visited edges (for resetting)
314 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo*> myFound;
315 : /// The container of edge information
316 : std::vector<typename SUMOAbstractRouter<E, V>::EdgeInfo> myEdgeInfos;
317 : /// @brief The edge informations specific to arc flag routing
318 : /// @note As opposed to the standard informations in SUMOAbstractRouter<E, V>::EdgeInfo
319 : std::vector<ArcInfo*>& myArcInfos;
320 : /// @brief The boolean flag indicating whether edge permissions need to be considered or not
321 : const bool myHavePermissions;
322 : /// @brief The boolean flag indicating whether edge restrictions need to be considered or not
323 : const bool myHaveRestrictions;
324 : /// @brief The handler for routing errors
325 : MsgHandler* const myErrorMsgHandler;
326 : /// @brief The object's operation to perform
327 : SUMOAbstractRouter<E, V>* myEffortProvider;
328 : /// @brief The comparator
329 : EdgeInfoComparator* myComparator;
330 : /// @brief The maximum speed in the network
331 : double myMaxSpeed;
332 : };
333 :
334 : // ===========================================================================
335 : // method definitions
336 : // ===========================================================================
337 :
338 : template<class E, class N, class V>
339 0 : void AFCentralizedSPTree<E, N, V>::init(std::vector<const E*> fromEdges, const V* const vehicle, SUMOTime msTime) {
340 : // all EdgeInfos touched in the previous query are either in myFrontierList or myFound: clean those up
341 0 : for (auto& edgeInfo : myFrontierList) {
342 0 : edgeInfo->reset();
343 : }
344 : myFrontierList.clear();
345 0 : for (auto& edgeInfo : myFound) {
346 0 : edgeInfo->reset();
347 : }
348 0 : for (auto& arcInfo : myArcInfos) {
349 0 : arcInfo->reset(); // does not reset effortsToBoundaryNodes
350 : }
351 : myFound.clear();
352 0 : for (const E* from : fromEdges) {
353 0 : if (from->isInternal()) {
354 0 : continue;
355 : }
356 : int edgeID = from->getNumericalID();
357 0 : auto& fromInfo = myEdgeInfos[edgeID];
358 0 : if (fromInfo.prohibited || isProhibited(from, vehicle)) {
359 0 : continue;
360 : }
361 0 : fromInfo.heuristicEffort = 0.;
362 0 : fromInfo.prev = nullptr;
363 0 : fromInfo.leaveTime = STEPS2TIME(msTime);
364 0 : myFrontierList.push_back(&fromInfo);
365 0 : ArcInfo* fromArcInfo = myArcInfos[edgeID];
366 0 : fromArcInfo->key = 0;
367 : }
368 0 : }
|
