Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-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 AFBuild.h
15 : /// @author Ruediger Ebendt
16 : /// @date 01.12.2023
17 : ///
18 : // Class for building the arc flags for (multi-level) arc flag routing
19 : /****************************************************************************/
20 : #pragma once
21 : #include <config.h>
22 : #include <memory>
23 : #include <vector>
24 : #include <unordered_set>
25 : #include <math.h>
26 : #include <cmath>
27 : #include <limits>
28 : #include <stdexcept>
29 : #include <string>
30 : #include <cinttypes>
31 : #include <utility>
32 : #include <utils/common/SUMOTime.h>
33 : #include <utils/common/SUMOVehicleClass.h>
34 : #include "KDTreePartition.h"
35 : #include "Node2EdgeRouter.h"
36 : #include "FlippedEdge.h"
37 : #include "AFCentralizedSPTree.h"
38 :
39 : //#define AFBU_WRITE_QGIS_FILTERS
40 : #ifdef AFBU_WRITE_QGIS_FILTERS
41 : #include <fstream>
42 : #include <sstream>
43 : #endif
44 :
45 : //#define AFBU_DEBUG_LEVEL_0
46 : //#define AFBU_DEBUG_LEVEL_1
47 : //#define AFBU_DEBUG_LEVEL_2
48 :
49 : #ifdef AFBU_DEBUG_LEVEL_2
50 : #define AFBU_DEBUG_LEVEL_1
51 : #endif
52 :
53 : #ifdef AFBU_DEBUG_LEVEL_1
54 : #define AFBU_DEBUG_LEVEL_0
55 : #endif
56 :
57 : // uncomment to disable assert()
58 : // #define NDEBUG
59 : #include <cassert>
60 :
61 : // ===========================================================================
62 : // class declarations
63 : // ===========================================================================
64 : template<class E, class N, class V, class M>
65 : class AFRouter;
66 :
67 : // ===========================================================================
68 : // class definitions
69 : // ===========================================================================
70 :
71 : /**
72 : * @class AFBuild
73 : * @brief Builds the flags for (multi-level) arc flag routing (Hilger et al.) in its multi-level variant
74 : * (also called "stripped SHARC" by Delling et al.)
75 : *
76 : * The template parameters are:
77 : * @param E The edge class to use (MSEdge/ROEdge )
78 : * @param N The node class to use (MSJunction/RONode)
79 : * @param V The vehicle class to use (MSVehicle/ROVehicle)
80 : */
81 : template<class E, class N, class V, class M>
82 : class AFBuild {
83 : public:
84 : /// @brief Maximum difference of two path lengths considered to be equal
85 : const double EPS = 0.009;
86 : typedef typename KDTreePartition<FlippedEdge<E, N, V>, FlippedNode<E, N, V>, V>::Cell Cell;
87 : typedef typename AFInfo<FlippedEdge<E, N, V>>::ArcInfo ArcInfo;
88 : typedef typename AFInfo<E>::FlagInfo FlagInfo;
89 : typedef AbstractLookupTable<FlippedEdge<E, N, V>, V> FlippedLookupTable;
90 :
91 : /** @brief Constructor
92 : * @param[in] flippedEdges The flipped (aka reversed / backward) edges
93 : * @param[in] flippedPartition The k-d tree partition of the backward graph with flipped edges
94 : * @param[in] numberOfLevels The number of levels
95 : * @param[in] unbuildIsWarning The flag indicating whether network unbuilds should issue warnings or errors
96 : * @param[in] flippedOperation The operation for a backward graph with flipped edges
97 : * @param[in] flippedLookup The lookup table for a backward graph with flipped edges
98 : * @param[in] havePermissions The boolean flag indicating whether edge permissions need to be considered or not
99 : * @param[in] haveRestrictions The boolean flag indicating whether edge restrictions need to be considered or not
100 : * @param[in] toProhibit The list of explicitly prohibited edges
101 : */
102 0 : AFBuild(
103 : const std::vector<FlippedEdge<E, N, V>*>& flippedEdges,
104 : const KDTreePartition<FlippedEdge<E, N, V>, FlippedNode<E, N, V>, V>* const flippedPartition,
105 : int numberOfLevels, bool unbuildIsWarning,
106 : typename SUMOAbstractRouter<FlippedEdge<E, N, V>, V>::Operation flippedOperation,
107 : const std::shared_ptr<const FlippedLookupTable> flippedLookup = nullptr,
108 : const bool havePermissions = false, const bool haveRestrictions = false,
109 : const std::vector<FlippedEdge<E, N, V>*>* toProhibit = nullptr) :
110 0 : myFlippedEdges(flippedEdges),
111 0 : myFlippedPartition(flippedPartition),
112 0 : myNumberOfLevels(numberOfLevels),
113 0 : myErrorMsgHandler(unbuildIsWarning ? MsgHandler::getWarningInstance() : MsgHandler::getErrorInstance()),
114 0 : myFlippedOperation(flippedOperation),
115 : myFlippedLookupTable(flippedLookup),
116 0 : myHavePermissions(havePermissions),
117 0 : myHaveRestrictions(haveRestrictions),
118 0 : myProhibited(toProhibit),
119 0 : myNode2EdgeRouter(new Node2EdgeRouter<FlippedEdge<E, N, V>, FlippedNode<E, N, V>, V, M>(myFlippedEdges,
120 0 : unbuildIsWarning, myFlippedOperation, myFlippedLookupTable, myHavePermissions, myHaveRestrictions)) {
121 0 : myCentralizedSPTree = new AFCentralizedSPTree<FlippedEdge<E, N, V>, FlippedNode<E, N, V>, V>(myFlippedEdges,
122 0 : myArcInfos, unbuildIsWarning, myNode2EdgeRouter, myHavePermissions, myHaveRestrictions);
123 0 : if (toProhibit) {
124 0 : myNode2EdgeRouter->prohibit(*toProhibit);
125 : }
126 0 : }
127 :
128 : /// @brief Destructor
129 0 : ~AFBuild() {
130 0 : delete myCentralizedSPTree;
131 0 : delete myNode2EdgeRouter;
132 0 : }
133 :
134 : /// @brief Returns the operation for a backward graph with flipped edges
135 : typename SUMOAbstractRouter<FlippedEdge<E, N, V>, V>::Operation getFlippedOperation() {
136 0 : return myFlippedOperation;
137 : }
138 : /// @brief Returns the lookup table for the backward graph with flipped edges
139 : const std::shared_ptr<const FlippedLookupTable> getFlippedLookup() {
140 : return myFlippedLookupTable;
141 : }
142 : /** @brief Initialize the arc flag build
143 : * @param[in] msTime The start time of the routes in milliseconds
144 : * @param[in] vehicle The vehicle
145 : * @param[in] flagInfos The arc flag informations
146 : */
147 : void init(SUMOTime time, const V* const vehicle, std::vector<FlagInfo*>& flagInfos);
148 : /** @brief Set the flipped partition
149 : * param[in] flippedPartition The flipped partition
150 : */
151 : void setFlippedPartition(const KDTreePartition<FlippedEdge<E, N, V>, FlippedNode<E, N, V>, V>* flippedPartition) {
152 0 : myFlippedPartition = flippedPartition;
153 0 : }
154 : /** @brief Converts a partition level number to a SHARC level number
155 : * @param[in] partitionLevel The partition level
156 : * @return The SHARC level number corresponding to the given partition level number
157 : */
158 : int partitionLevel2SHARCLevel(int partitionLevel) {
159 : return AFRouter<E, N, V, M>::partitionLevel2SHARCLevel(partitionLevel, myNumberOfLevels);
160 : }
161 : /** @brief Converts a SHARC level number to a partition level number
162 : * @param[in] sHARCLevel The SHARC level
163 : * @return The partition level number corresponding to the given SHARC level number
164 : */
165 : int sHARCLevel2PartitionLevel(int sHARCLevel) {
166 0 : return AFRouter<E, N, V, M>::sHARCLevel2PartitionLevel(sHARCLevel, myNumberOfLevels);
167 : }
168 :
169 : protected:
170 : /** @brief Computes the arc flags for all cells at a given level
171 : * @param[in] msTime The start time of the routes in milliseconds
172 : * @param[in] sHARCLevel The SHARC level
173 : * @param[in] vehicle The vehicle
174 : */
175 : void computeArcFlags(SUMOTime msTime, int sHARCLevel, const V* const vehicle);
176 : /** @brief Computes the arc flags for a given cell
177 : * @param[in] msTime The start time of the routes in milliseconds
178 : * @param sHARCLevel The SHARC level
179 : * @param[in] cell The cell
180 : * @param[in] vehicle The vehicle
181 : */
182 : void computeArcFlags(SUMOTime msTime, const int sHARCLevel, const Cell* cell, const V* const vehicle);
183 : /** @brief Computes the arc flags for a given cell (naive version)
184 : * @param[in] msTime The start time of the routes in milliseconds
185 : * @param sHARCLevel The SHARC level
186 : * @param[in] cell The cell
187 : * @param[in] vehicle The vehicle
188 : */
189 : void computeArcFlagsNaive(SUMOTime msTime, const int sHARCLevel, const Cell* cell, const V* const vehicle);
190 : /** @brief Put the arc flag of the edge in arcInfo
191 : * @note wrt the passed SHARC level, and the boolean flag indicating whether the respective cell is a left or lower one or not
192 : * @param[in] arcInfo The arc information
193 : * @param[in] sHARCLevel The SHARC level
194 : * @param[in] isLeftOrLowerCell The boolean flag indicating whether the respective cell is a left or lower one or not
195 : */
196 : void putArcFlag(ArcInfo* arcInfo, const int sHARCLevel, const bool isLeftOrLowerCell);
197 : /// @brief The flipped edges
198 : const std::vector<FlippedEdge<E, N, V>*>& myFlippedEdges;
199 : /// @brief The partition for the backward graph with flipped edges
200 : const KDTreePartition<FlippedEdge<E, N, V>, FlippedNode<E, N, V>, V>* myFlippedPartition;
201 : /// @brief The number of levels
202 : const int myNumberOfLevels;
203 : /// @brief The handler for routing errors
204 : MsgHandler* const myErrorMsgHandler;
205 : /// @brief The object's operation to perform on a backward graph with flipped edges
206 : typename SUMOAbstractRouter<FlippedEdge<E, N, V>, V>::Operation myFlippedOperation;
207 : /// @brief The lookup table for travel time heuristics
208 : const std::shared_ptr<const FlippedLookupTable> myFlippedLookupTable;
209 : /// @brief The boolean flag indicating whether edge permissions need to be considered or not
210 : const bool myHavePermissions;
211 : /// @brief The boolean flag indicating whether edge restrictions need to be considered or not
212 : const bool myHaveRestrictions;
213 : /// @brief The list of explicitly prohibited edges
214 : const std::vector<FlippedEdge<E, N, V>*>* myProhibited;
215 : /// @brief The node-to-edge router (for a backward graph with flipped edges)
216 : Node2EdgeRouter<FlippedEdge<E, N, V>, FlippedNode<E, N, V>, V, M>* myNode2EdgeRouter;
217 : /// @brief A Dijkstra based centralized label-correcting algorithm
218 : // @note Builds shortest path trees for all boundary nodes at once
219 : // @note It operates on a backward graph with flipped edges
220 : AFCentralizedSPTree<FlippedEdge<E, N, V>, FlippedNode<E, N, V>, V>* myCentralizedSPTree;
221 : /// @brief The container of arc informations (for the centralized shortest path tree)
222 : std::vector<ArcInfo*> myArcInfos;
223 :
224 : private:
225 : /** @brief Initialize the boundary edges
226 : * param[in] boundaryEdges The boundary edges
227 : */
228 : void initBoundaryEdges(const std::unordered_set<const FlippedEdge<E, N, V>*>& boundaryEdges);
229 : /** @brief Initialize the supercell edges
230 : * @param[in] supercell The supercell
231 : * @param[in] boundaryEdges The boundary edges
232 : * @param[in] numberOfBoundaryNodes The number of boundary nodes
233 : */
234 : void initSupercellEdges(const Cell* supercell,
235 : const std::unordered_set<const FlippedEdge<E, N, V>*>& boundaryEdges,
236 : size_t numberOfBoundaryNodes);
237 : /** @brief Helper method for computeArcFlags(), which computes the arc flags for a given cell
238 : * @param[in] msTime The start time of the routes in milliseconds
239 : * @param[in] sHARCLevel The SHARC level
240 : * @param[in] cell The cell
241 : * @param[in] vehicle The vehicle
242 : */
243 : void computeArcFlagsAux(SUMOTime msTime, const int sHARCLevel, const Cell* cell, const V* const vehicle);
244 : }; // end of class AFBuild declaration
245 :
246 : // ===========================================================================
247 : // method definitions
248 : // ===========================================================================
249 :
250 : template<class E, class N, class V, class M>
251 0 : void AFBuild<E, N, V, M>::init(SUMOTime msTime, const V* const vehicle, std::vector<FlagInfo*>& flagInfos) {
252 0 : if (myArcInfos.empty()) {
253 0 : for (const FlippedEdge<E, N, V>* const flippedEdge : myFlippedEdges) {
254 0 : myArcInfos.push_back(new ArcInfo(flippedEdge));
255 : }
256 : }
257 : int sHARCLevel;
258 0 : for (sHARCLevel = 0; sHARCLevel < myNumberOfLevels - 1; sHARCLevel++) {
259 : #ifdef AFBU_DEBUG_LEVEL_0
260 : std::cout << "Starting computation of flags of level " << sHARCLevel << " (levels run from 0 to "
261 : << myNumberOfLevels - 2 << ")." << std::endl;
262 : #endif
263 : #ifdef AFBU_DEBUG_LEVEL_2
264 : if (sHARCLevel != 0) {
265 : continue;
266 : }
267 : #endif
268 0 : computeArcFlags(msTime, sHARCLevel, vehicle);
269 : }
270 : #ifdef AFBU_DEBUG_LEVEL_0
271 : std::cout << "Copying arc flags from the arc infos... " << std::endl;
272 : #endif
273 : int index = 0;
274 0 : for (const ArcInfo* arcInfo : myArcInfos) {
275 0 : flagInfos[index++]->arcFlags = arcInfo->arcFlags;
276 0 : delete arcInfo;
277 : }
278 : #ifdef AFBU_DEBUG_LEVEL_0
279 : std::cout << "Arc flags copied from the arc infos. " << std::endl;
280 : #endif
281 : myArcInfos.clear();
282 0 : }
283 :
284 : template<class E, class N, class V, class M>
285 0 : void AFBuild<E, N, V, M>::computeArcFlags(SUMOTime msTime, const int sHARCLevel, const V* const vehicle) {
286 : try {
287 : assert(myFlippedPartition);
288 0 : const std::vector<const Cell*>& levelCells = myFlippedPartition->getCellsAtLevel(sHARCLevel2PartitionLevel(sHARCLevel));
289 : #ifdef AFBU_DEBUG_LEVEL_0
290 : int i = 0;
291 : #endif
292 0 : for (const Cell* cell : levelCells) {
293 : #ifdef AFBU_DEBUG_LEVEL_0
294 : std::cout << "Starting to compute core flags of the " << i++ << "th cell..." << std::endl;
295 : #endif
296 : #ifdef AFBU_DEBUG_LEVEL_2
297 : if (cell->getNumber() == 4) {
298 : #endif
299 : // kept to make comparisons possible
300 : //computeArcFlagsNaive(msTime, sHARCLevel, cell, vehicle);
301 0 : computeArcFlags(msTime, sHARCLevel, cell, vehicle);
302 : // clean up (all except the computed flags, of course)
303 : #ifdef AFBU_DEBUG_LEVEL_0
304 : std::cout << "Cleaning up after computeArcFlags..." << std::endl;
305 : #endif
306 0 : for (ArcInfo* arcInfo : myArcInfos) {
307 : arcInfo->effortsToBoundaryNodes.clear();
308 0 : arcInfo->touched = false;
309 : }
310 : #ifdef AFBU_DEBUG_LEVEL_0
311 : std::cout << "Cleaned up." << std::endl;
312 : #endif
313 : #ifdef AFBU_DEBUG_LEVEL_2
314 : }
315 : #endif
316 : }
317 0 : } catch (const std::invalid_argument& e) {
318 0 : std::cerr << "Exception: " << e.what() << std::endl;
319 0 : exit(-1);
320 : }
321 0 : }
322 :
323 : template<class E, class N, class V, class M>
324 : void AFBuild<E, N, V, M>::computeArcFlagsNaive(SUMOTime msTime, const int sHARCLevel, const Cell* cell, const V* const vehicle) {
325 : const Cell* supercell = cell->getSupercell();
326 : const std::unordered_set<const FlippedEdge<E, N, V>*>& boundaryEdges = cell->getOutgoingBoundaryEdges();
327 : const std::vector<const FlippedNode<E, N, V>*>& boundaryNodes = cell->getBoundaryFromNodes();
328 : #ifdef AFBU_DEBUG_LEVEL_1
329 : std::cout << "Number of boundary edges: " << boundaryEdges.size() << std::endl;
330 : std::cout << "Number of boundary nodes: " << boundaryNodes.size() << std::endl;
331 : std::cout << "Cell number: " << cell->getNumber() << std::endl;
332 : std::cout << "Supercell number: " << supercell->getNumber() << std::endl;
333 : #endif
334 : //
335 : // initialization of arc flag vectors
336 : initBoundaryEdges(boundaryEdges);
337 :
338 : #ifdef AFBU_DEBUG_LEVEL_0
339 : long long int startTime = SysUtils::getCurrentMillis();
340 : #endif
341 : for (const FlippedNode<E, N, V>* boundaryNode : boundaryNodes) {
342 : for (const FlippedEdge<E, N, V>* boundaryEdge : boundaryEdges) {
343 : assert(!boundaryEdge->isInternal());
344 : ArcInfo* arcInfo = myArcInfos[boundaryEdge->getNumericalID()];
345 : if (boundaryNode == boundaryEdge->getFromJunction()) {
346 : arcInfo->effortsToBoundaryNodes.push_back(0.);
347 : continue;
348 : }
349 : // compute effort
350 : std::vector<const FlippedEdge<E, N, V>*> into;
351 : #ifdef AFBU_DEBUG_LEVEL_2
352 : std::vector<const FlippedEdge<E, N, V>*> into2;
353 : #endif
354 : if (myNode2EdgeRouter->computeNode2Edge(boundaryNode, boundaryEdge, vehicle, msTime, into)) {
355 : double recomputedEffort = myNode2EdgeRouter->recomputeCostsNoLastEdge(into, vehicle, msTime);
356 : arcInfo->effortsToBoundaryNodes.push_back(recomputedEffort);
357 : #ifdef AFBU_DEBUG_LEVEL_2
358 : if (!into.empty() && myNode2EdgeRouter->compute(into[0], boundaryEdge, vehicle, msTime, into2)) {
359 : double recomputedEffort2 = myNode2EdgeRouter->recomputeCosts(into2, vehicle, msTime);
360 :
361 : std::cout << "node2Edge router succeeded, effort: " << recomputedEffort << ", effort incl. last edge: " << recomputedEffort2 << std::endl;
362 : assert(recomputedEffort <= recomputedEffort2);
363 : }
364 : #endif
365 : } else {
366 : arcInfo->effortsToBoundaryNodes.push_back(UNREACHABLE);
367 : #ifdef AFBU_DEBUG_LEVEL_2
368 : std::cout << "UNREACHABLE!" << std::endl;
369 : #endif
370 : }
371 : }
372 : }
373 : #ifdef AFBU_DEBUG_LEVEL_0
374 : long long int timeSpent = SysUtils::getCurrentMillis() - startTime;
375 : std::cout << "Initial distance computation spent " + elapsedMs2string(timeSpent) + "." << std::endl;
376 : #endif
377 :
378 : // initialize all supercell edges' labels, arc flag vectors for the centralized shortest path tree algorithm / arc flag build
379 : initSupercellEdges(supercell, boundaryEdges, boundaryNodes.size());
380 : #ifdef AFBU_DEBUG_LEVEL_0
381 : std::cout << "Initialization of all supercell edges' labels and arc flag vectors done. Starting the centralized shortest path tree algorithm..." << std::endl;
382 : #endif
383 : if (myCentralizedSPTree->computeCentralizedSPTree(msTime, cell, vehicle)) {
384 : computeArcFlagsAux(msTime, sHARCLevel, cell, vehicle);
385 : }
386 : #ifdef AFBU_DEBUG_LEVEL_0
387 : std::cout << "Centralized shortest path tree algorithm finished." << std::endl;
388 : #endif
389 : }
390 :
391 : template<class E, class N, class V, class M>
392 0 : void AFBuild<E, N, V, M>::computeArcFlags(SUMOTime msTime, const int sHARCLevel, const Cell* cell, const V* const vehicle) {
393 : const Cell* supercell = cell->getSupercell();
394 : const std::unordered_set<const FlippedEdge<E, N, V>*>& boundaryEdges = cell->getOutgoingBoundaryEdges();
395 : const std::vector<const FlippedNode<E, N, V>*>& boundaryNodes = cell->getBoundaryFromNodes();
396 : #ifdef AFBU_DEBUG_LEVEL_1
397 : std::cout << "Number of boundary edges: " << boundaryEdges.size() << std::endl;
398 : std::cout << "Number of boundary nodes: " << boundaryNodes.size() << std::endl;
399 : std::cout << "Cell number: " << cell->getNumber() << std::endl;
400 : std::cout << "Supercell number: " << supercell->getNumber() << std::endl;
401 : #endif
402 : // initialization of arc flag vectors
403 0 : initBoundaryEdges(boundaryEdges);
404 : #ifdef AFBU_DEBUG_LEVEL_1
405 : long long int startTime = SysUtils::getCurrentMillis();
406 : #endif
407 : std::map<const FlippedEdge<E, N, V>*, std::vector<const FlippedEdge<E, N, V>*>> incomingEdgesOfOutgoingBoundaryEdges;
408 : size_t numberOfBoundaryNodes = boundaryNodes.size();
409 0 : for (const FlippedEdge<E, N, V>* boundaryEdge : boundaryEdges) {
410 0 : incomingEdgesOfOutgoingBoundaryEdges[boundaryEdge] = std::vector<const FlippedEdge<E, N, V>*>(numberOfBoundaryNodes);
411 : }
412 : int index = 0; // boundary node index
413 0 : for (const FlippedNode<E, N, V>* boundaryNode : boundaryNodes) {
414 0 : myNode2EdgeRouter->reset(vehicle);
415 0 : if (myNode2EdgeRouter->computeNode2Edges(boundaryNode, boundaryEdges, vehicle, msTime)) {
416 : #ifdef AFBU_DEBUG_LEVEL_2
417 : std::cout << "Node-to-edge router succeeded." << std::endl;
418 : #endif
419 : }
420 0 : for (const FlippedEdge<E, N, V>* boundaryEdge : boundaryEdges) {
421 : assert(!boundaryEdge->isInternal());
422 0 : ArcInfo* arcInfo = myArcInfos[boundaryEdge->getNumericalID()];
423 0 : if (boundaryNode == boundaryEdge->getFromJunction()) {
424 0 : arcInfo->effortsToBoundaryNodes.push_back(0.);
425 0 : (incomingEdgesOfOutgoingBoundaryEdges[boundaryEdge])[index] = nullptr;
426 0 : continue;
427 : }
428 0 : double effort = (myNode2EdgeRouter->edgeInfo(boundaryEdge))->effort;
429 : const FlippedEdge<E, N, V>* incomingEdge
430 0 : = (myNode2EdgeRouter->edgeInfo(boundaryEdge))->prev ?
431 : (myNode2EdgeRouter->edgeInfo(boundaryEdge))->prev->edge : nullptr;
432 0 : (incomingEdgesOfOutgoingBoundaryEdges[boundaryEdge])[index] = incomingEdge;
433 0 : arcInfo->effortsToBoundaryNodes.push_back(effort == std::numeric_limits<double>::max() ? UNREACHABLE : effort);
434 : }
435 0 : index++;
436 : } // end for boundary nodes
437 : #ifdef AFBU_DEBUG_LEVEL_0
438 : long long int timeSpent = SysUtils::getCurrentMillis() - startTime;
439 : std::cout << "Initial distance computation spent " + elapsedMs2string(timeSpent) + "." << std::endl;
440 : #endif
441 : // initialize all supercell edges' labels and arc flag vectors for the centralized shortest path DAG algorithm / arc flag build
442 0 : initSupercellEdges(supercell, boundaryEdges, boundaryNodes.size());
443 : #ifdef AFBU_DEBUG_LEVEL_0
444 : std::cout << "Initialization of all supercell edges' labels and arc flag vectors done. Starting the centralized shortest path tree algorithm..." << std::endl;
445 : #endif
446 : #ifdef AFBU_DEBUG_LEVEL_0
447 : startTime = SysUtils::getCurrentMillis();
448 : #endif
449 0 : if (myCentralizedSPTree->computeCentralizedSPTree(msTime, cell, vehicle, incomingEdgesOfOutgoingBoundaryEdges)) {
450 : #ifdef AFBU_DEBUG_LEVEL_0
451 : timeSpent = SysUtils::getCurrentMillis() - startTime;
452 : std::cout << "Centralized SP tree computation spent " + elapsedMs2string(timeSpent) + "." << std::endl;
453 : #endif
454 0 : computeArcFlagsAux(msTime, sHARCLevel, cell, vehicle);
455 : }
456 : #ifdef AFBU_DEBUG_LEVEL_0
457 : std::cout << "Centralized shortest path tree algorithm finished." << std::endl;
458 : #endif
459 0 : }
460 :
461 : template<class E, class N, class V, class M>
462 0 : void AFBuild<E, N, V, M>::computeArcFlagsAux(SUMOTime msTime, const int sHARCLevel, const Cell* cell, const V* const vehicle) {
463 : const Cell* supercell = cell->getSupercell();
464 : std::pair<typename std::vector<const FlippedNode<E, N, V>*>::const_iterator,
465 : typename std::vector<const FlippedNode<E, N, V>*>::const_iterator> supercellNodeIterators = supercell->nodeIterators();
466 : typename std::vector<const FlippedNode<E, N, V>*>::const_iterator first = supercellNodeIterators.first;
467 : typename std::vector<const FlippedNode<E, N, V>*>::const_iterator last = supercellNodeIterators.second;
468 : typename std::vector<const FlippedNode<E, N, V>*>::const_iterator iter;
469 : std::unordered_set<ArcInfo*> arcInfosOnAShortestPath;
470 : #ifdef AFBU_DEBUG_LEVEL_1
471 : int numberOfSupercellEdges = 0;
472 : #endif
473 0 : for (iter = first; iter != last; iter++) {
474 0 : const std::vector<const FlippedEdge<E, N, V>*> incomingEdges = (*iter)->getIncoming();
475 0 : for (const FlippedEdge<E, N, V>* supercellEdge : incomingEdges) {
476 0 : if (supercellEdge->isInternal()) {
477 0 : continue;
478 : }
479 0 : if ((myNode2EdgeRouter->edgeInfo(supercellEdge))->prohibited
480 0 : || myNode2EdgeRouter->isProhibited(supercellEdge, vehicle)) {
481 0 : continue;
482 : }
483 : #ifdef AFBU_DEBUG_LEVEL_1
484 : numberOfSupercellEdges++;
485 : #endif
486 0 : ArcInfo* supercellArcInfo = myArcInfos[supercellEdge->getNumericalID()];
487 : // start by initializing to set of all supercell edge arc infos
488 : arcInfosOnAShortestPath.insert(supercellArcInfo);
489 : }
490 : }
491 : #ifdef AFBU_DEBUG_LEVEL_1
492 : std::cout << "Number of supercell edges: " << numberOfSupercellEdges << std::endl;
493 : #endif
494 0 : const SUMOVehicleClass vClass = vehicle == 0 ? SVC_IGNORING : vehicle->getVClass();
495 : #ifdef AFBU_DEBUG_LEVEL_1
496 : std::cout << "Identifying shortest paths..." << std::endl;
497 : #endif
498 : #ifdef AFBU_DEBUG_LEVEL_0
499 : long long int startTime = SysUtils::getCurrentMillis();
500 : #endif
501 : std::unordered_set<ArcInfo*> erasedEdges;
502 0 : for (auto iter2 = arcInfosOnAShortestPath.begin(); iter2 != arcInfosOnAShortestPath.end();) {
503 0 : const ArcInfo* arcInfo = *iter2;
504 : assert(!arcInfo->edge->isInternal());
505 : assert(myNode2EdgeRouter);
506 : assert(!(myNode2EdgeRouter->edgeInfo(arcInfo->edge))->prohibited
507 : && !myNode2EdgeRouter->isProhibited(arcInfo->edge, vehicle));
508 : size_t numberOfBoundaryNodes = arcInfo->effortsToBoundaryNodes.size();
509 : size_t index;
510 : bool onShortestPath = false;
511 : // attempt to prove that the edge is on a shortest path for at least one boundary node
512 0 : for (index = 0; index < numberOfBoundaryNodes; index++) {
513 0 : double effort1ToBoundaryNode = arcInfo->effortsToBoundaryNodes[index];
514 0 : if (effort1ToBoundaryNode == UNREACHABLE) {
515 0 : continue;
516 : }
517 0 : if (effort1ToBoundaryNode == std::numeric_limits<double>::max()) {
518 0 : continue;
519 : }
520 0 : double sTime = STEPS2TIME(msTime);
521 0 : double edgeEffort = myNode2EdgeRouter->getEffort(arcInfo->edge, vehicle, sTime);
522 0 : sTime += myNode2EdgeRouter->getTravelTime(arcInfo->edge, vehicle, sTime, edgeEffort);
523 : double oldEdgeEffort = edgeEffort;
524 : double oldSTime = sTime;
525 :
526 0 : for (const std::pair<const FlippedEdge<E, N, V>*, const FlippedEdge<E, N, V>*>& follower : arcInfo->edge->getViaSuccessors(vClass)) {
527 : assert(!follower.first->isInternal());
528 0 : ArcInfo* followerInfo = myArcInfos[follower.first->getNumericalID()];
529 :
530 : // check whether it can be used
531 0 : if ((myNode2EdgeRouter->edgeInfo(follower.first))->prohibited
532 0 : || myNode2EdgeRouter->isProhibited(follower.first, vehicle)) {
533 0 : myErrorMsgHandler->inform("Vehicle '" + Named::getIDSecure(vehicle) + "' is not allowed on source edge '" + followerInfo->edge->getID() + "'.");
534 0 : continue;
535 : }
536 0 : if (followerInfo->effortsToBoundaryNodes.empty()) {
537 0 : continue;
538 : }
539 0 : double effort2ToBoundaryNode = followerInfo->effortsToBoundaryNodes[index];
540 0 : if (effort2ToBoundaryNode == UNREACHABLE) {
541 0 : continue;
542 : }
543 0 : if (effort2ToBoundaryNode == std::numeric_limits<double>::max()) {
544 0 : continue;
545 : }
546 :
547 : // add via efforts to current follower to edge effort
548 0 : double length = 0.; // dummy length for call of updateViaEdgeCost
549 0 : myNode2EdgeRouter->updateViaEdgeCost(follower.second, vehicle,
550 : sTime /* has been updated to the time where the edge has been traversed */, edgeEffort, length);
551 : // test whether edge is on a shortest path to a boundary node
552 0 : if (effort1ToBoundaryNode + edgeEffort /* edge effort incl. via efforts to current follower of edge */
553 : <= effort2ToBoundaryNode /* efforts incl. via efforts to current follower o. e. */
554 0 : + EPS && effort1ToBoundaryNode + edgeEffort >= effort2ToBoundaryNode - EPS) {
555 : onShortestPath = true;
556 0 : break; // a shortest path to one boundary node suffices
557 : }
558 0 : edgeEffort = oldEdgeEffort;
559 0 : sTime = oldSTime;
560 : } // end of loop over outgoing edges
561 : } // loop over indexes
562 0 : if (!onShortestPath) {
563 : erasedEdges.insert(*iter2);
564 : iter2 = arcInfosOnAShortestPath.erase(iter2); // not on a shortest path, remove it
565 : } else {
566 : ++iter2;
567 : }
568 : } // loop over edge infos
569 :
570 : #ifdef AFBU_DEBUG_LEVEL_0
571 : std::cout << "Edges clearly not on a shortest path have been removed. Number of edges on a shortest path is now: "
572 : << arcInfosOnAShortestPath.size() << std::endl;
573 : #endif
574 :
575 : // set arc flags (for level sHARCLevel) for all edges completely inside the cell
576 : // (done since these edges all have a to-node inside the cell, i.e. we have to set the own-cell flag for them).
577 0 : std::unordered_set<const FlippedEdge<E, N, V>*>* pEdgesInsideCell = cell->edgeSet(vehicle);
578 : std::unordered_set<const FlippedEdge<E, N, V>*> edgesInsideCell = *pEdgesInsideCell;
579 : #ifdef AFBU_DEBUG_LEVEL_0
580 : std::cout << "Adding all edges completely inside the cell to set of edges on a shortest path, cell no:"
581 : << cell->getNumber() << std::endl;
582 : #endif
583 0 : for (const FlippedEdge<E, N, V>* edgeInsideCell : edgesInsideCell) {
584 0 : ArcInfo* arcInfo = myArcInfos[edgeInsideCell->getNumericalID()];
585 0 : if ((myNode2EdgeRouter->edgeInfo(edgeInsideCell))->prohibited
586 0 : || myNode2EdgeRouter->isProhibited(edgeInsideCell, vehicle)) {
587 0 : continue;
588 : }
589 : arcInfosOnAShortestPath.insert(arcInfo);
590 : }
591 0 : delete pEdgesInsideCell;
592 : #ifdef AFBU_DEBUG_LEVEL_0
593 : std::cout << "Edges inside cell added." << std::endl;
594 : long long int timeSpent = SysUtils::getCurrentMillis() - startTime;
595 : std::cout << "Shortest path identification spent " + elapsedMs2string(timeSpent) + "." << std::endl;
596 : #endif
597 :
598 : #ifdef AFBU_WRITE_QGIS_FILTERS
599 : std::string qgisFilterString = "id IN (";
600 : std::unordered_set<const FlippedNode<E, N, V>*> nodesOnAShortestPath;
601 : std::unordered_set<const FlippedNode<E, N, V>*> erasedNodes;
602 : for (const ArcInfo* arcInfo : arcInfosOnAShortestPath) {
603 : assert(!(myNode2EdgeRouter->edgeInfo(arcInfo->edge))->prohibited
604 : && !myNode2EdgeRouter->isProhibited(arcInfo->edge, vehicle));
605 : nodesOnAShortestPath.insert(arcInfo->edge->getFromJunction());
606 : nodesOnAShortestPath.insert(arcInfo->edge->getToJunction());
607 : }
608 : for (const ArcInfo* erasedEdgeArcInfo : erasedEdges) {
609 : erasedNodes.insert(erasedEdgeArcInfo->edge->getFromJunction());
610 : erasedNodes.insert(erasedEdgeArcInfo->edge->getToJunction());
611 : }
612 : size_t k = 0;
613 : // go through the relevant nodes of the supercell
614 : size_t numberOfNodesOnAShortestPath = nodesOnAShortestPath.size();
615 : for (const FlippedNode<E, N, V>* node : nodesOnAShortestPath) {
616 : k++;
617 : qgisFilterString += node->getID() + (k < numberOfNodesOnAShortestPath ? ", " : "");
618 : }
619 : qgisFilterString += ")";
620 : std::ostringstream pathAndFileName;
621 : pathAndFileName << "./filter_superset_nodes_cell_" << cell->getNumber() << "_supercell_" << supercell->getNumber() << ".qqf";
622 : std::ofstream file;
623 : file.open(pathAndFileName.str());
624 : std::ostringstream content;
625 : content << "<Query>" << qgisFilterString << "</Query>";
626 : file << content.str();
627 : file.close();
628 : // erased nodes
629 : k = 0;
630 : qgisFilterString.clear();
631 : qgisFilterString = "id IN (";
632 : // go through the erased nodes of the supercell
633 : size_t numberOfErasedNodes = erasedNodes.size();
634 : for (const FlippedNode<E, N, V>* node : erasedNodes) {
635 : k++;
636 : qgisFilterString += node->getID() + (k < numberOfErasedNodes ? ", " : "");
637 : }
638 : qgisFilterString += ")";
639 : pathAndFileName.str("");
640 : pathAndFileName.clear();
641 : pathAndFileName << "./filter_erased_nodes_cell_" << cell->getNumber() << "_supercell_" << supercell->getNumber() << ".qqf";
642 : file.clear();
643 : file.open(pathAndFileName.str());
644 : content.str("");
645 : content.clear();
646 : content << "<Query>" << qgisFilterString << "</Query>";
647 : file << content.str();
648 : file.close();
649 : #endif
650 : // put arc flags for level 'sHARCLevel' for all supercell edges which are on a shortest path
651 0 : for (ArcInfo* arcInfo : arcInfosOnAShortestPath) {
652 : putArcFlag(arcInfo, sHARCLevel, cell->isLeftOrLowerCell());
653 : }
654 0 : }
655 :
656 : template<class E, class N, class V, class M>
657 : void AFBuild<E, N, V, M>::putArcFlag(ArcInfo* arcInfo, const int sHARCLevel, const bool isLeftOrLowerCell) {
658 : assert(arcInfo);
659 0 : (arcInfo->arcFlags)[sHARCLevel * 2 + (isLeftOrLowerCell ? 0 : 1)] = 1;
660 : }
661 :
662 : template<class E, class N, class V, class M>
663 0 : void AFBuild<E, N, V, M>::initBoundaryEdges(const std::unordered_set<const FlippedEdge<E, N, V>*>& boundaryEdges) {
664 : // initialization of arc flag vectors
665 0 : for (const FlippedEdge<E, N, V>* boundaryEdge : boundaryEdges) {
666 : assert(!boundaryEdge->isInternal());
667 : ArcInfo* arcInfo;
668 0 : arcInfo = myArcInfos[boundaryEdge->getNumericalID()];
669 : if (arcInfo->arcFlags.empty()) {
670 0 : std::fill_n(std::back_inserter(arcInfo->arcFlags),
671 0 : myFlippedPartition->numberOfArcFlags(), false);
672 : }
673 : arcInfo->effortsToBoundaryNodes.clear();
674 : }
675 0 : }
676 :
677 : template<class E, class N, class V, class M>
678 0 : void AFBuild<E, N, V, M>::initSupercellEdges(
679 : const Cell* supercell,
680 : const std::unordered_set<const FlippedEdge<E, N, V>*>& boundaryEdges,
681 : size_t numberOfBoundaryNodes) {
682 : std::pair<typename std::vector<const FlippedNode<E, N, V>*>::const_iterator,
683 : typename std::vector<const FlippedNode<E, N, V>*>::const_iterator> supercellNodeIterators = supercell->nodeIterators();
684 : typename std::vector<const FlippedNode<E, N, V>*>::const_iterator first = supercellNodeIterators.first;
685 : typename std::vector<const FlippedNode<E, N, V>*>::const_iterator last = supercellNodeIterators.second;
686 : typename std::vector<const FlippedNode<E, N, V>*>::const_iterator iter;
687 0 : for (iter = first; iter != last; iter++) {
688 0 : const std::vector<const FlippedEdge<E, N, V>*> incomingEdges = (*iter)->getIncoming();
689 0 : for (const FlippedEdge<E, N, V>* supercellEdge : incomingEdges) {
690 0 : if (supercellEdge->isInternal()) {
691 0 : continue;
692 : }
693 0 : if (boundaryEdges.count(supercellEdge)) {
694 0 : continue;
695 : }
696 : ArcInfo* supercellArcInfo;
697 0 : supercellArcInfo = myArcInfos[supercellEdge->getNumericalID()];
698 : if (supercellArcInfo->arcFlags.empty()) {
699 0 : std::fill_n(std::back_inserter(supercellArcInfo->arcFlags),
700 0 : myFlippedPartition->numberOfArcFlags(), false);
701 : }
702 : supercellArcInfo->effortsToBoundaryNodes.clear();
703 0 : std::fill_n(std::back_inserter(supercellArcInfo->effortsToBoundaryNodes),
704 : numberOfBoundaryNodes, std::numeric_limits<double>::max());
705 : }
706 : }
707 0 : }
|
