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 AFBuilder.h
15 : /// @author Ruediger Ebendt
16 : /// @date 01.11.2023
17 : ///
18 : // Arc flags builder for the arc flag router
19 : /****************************************************************************/
20 : #pragma once
21 : #include <config.h>
22 : #include <vector>
23 : // uncomment to disable assert()
24 : // #define NDEBUG
25 : #include <cassert>
26 :
27 : #include "AFBuild.h"
28 : #include "FlippedEdge.h"
29 :
30 : //#define AFBL_DEBUG_LEVEL_0
31 : //#define AFBL_DEBUG_LEVEL_1
32 : //#define AFBL_DEBUG_LEVEL_2
33 :
34 : #ifdef AFBL_DEBUG_LEVEL_2
35 : #define AFBL_DEBUG_LEVEL_1
36 : #endif
37 :
38 : #ifdef AFBL_DEBUG_LEVEL_1
39 : #define AFBL_DEBUG_LEVEL_0
40 : #endif
41 :
42 : // ===========================================================================
43 : // class definitions
44 : // ===========================================================================
45 : /**
46 : * @class AFBuilder
47 : * @brief Builds arc flags for shortest path search with the arc flag router
48 : */
49 :
50 : template<class E, class N, class V, class M>
51 : class AFBuilder {
52 : public:
53 : typedef typename AFInfo<E>::FlagInfo FlagInfo;
54 : typedef AbstractLookupTable<FlippedEdge<E, N, V>, V> FlippedLookupTable;
55 :
56 : /** @brief Constructor
57 : * @param[in] numberOfLevels The number of levels
58 : * @param[in] edges The container with all edges of the network
59 : * @param[in] unbuildIsWarning The flag indicating whether network unbuilds should issue warnings or errors
60 : * @param[in] flippedOperation The operation for a backward graph with flipped edges
61 : * @param[in] flippedLookup The lookup table for a backward graph with flipped edges
62 : * @param[in] havePermissions The flag indicating whether edges have permissions which must be respected
63 : * @param[in] haveRestrictions The flag indicating whether edges have restrictions which must be respected
64 : * @param[in] toProhibit The list of explicitly prohibited edges
65 : */
66 0 : AFBuilder(int numberOfLevels, const std::vector<E*>& edges, bool unbuildIsWarning,
67 : typename SUMOAbstractRouter<FlippedEdge<E, N, V>, V>::Operation flippedOperation,
68 : const std::shared_ptr<const FlippedLookupTable> flippedLookup = nullptr,
69 : const bool havePermissions = false, const bool haveRestrictions = false,
70 : const std::map<const FlippedEdge<E, N, V>*, double>* toProhibit = nullptr) :
71 0 : myEdges(edges),
72 0 : myNumberOfLevels(numberOfLevels),
73 0 : myNumberOfArcFlags(2 * (myNumberOfLevels - 1)),
74 : #ifdef AFBL_DEBUG_LEVEL_0
75 : myArcFlagsFileName("arcflags.csv"),
76 : #endif
77 0 : myAmClean(true) {
78 0 : for (const E* const edge : edges) {
79 0 : myFlagInfos.push_back(new FlagInfo(edge));
80 : }
81 : // build the backward graph with flipped edges / nodes in advance
82 : #ifdef AFBL_DEBUG_LEVEL_0
83 : std::cout << "Building flipped edges (" << edges.size() << " edges) / nodes..." << std::endl;
84 : #endif
85 0 : for (const E* const edge : edges) {
86 0 : myFlippedEdges.push_back(edge->getFlippedRoutingEdge());
87 : }
88 0 : for (FlippedEdge<E, N, V>* flippedEdge : myFlippedEdges) {
89 0 : flippedEdge->init();
90 : }
91 : #ifdef AFBL_DEBUG_LEVEL_0
92 : std::cout << "Flipped edges / nodes are ready." << std::endl;
93 : #endif
94 0 : myFlippedPartition = new KDTreePartition<FlippedEdge<E, N, V>, FlippedNode<E, N, V>, V>(myNumberOfLevels,
95 0 : myFlippedEdges, havePermissions, haveRestrictions);
96 : #ifdef AFBL_DEBUG_LEVEL_0
97 : std::cout << "Instantiating arc flag build..." << std::endl;
98 : #endif
99 0 : myArcFlagBuild = new AFBuild<E, N, V, M>(myFlippedEdges, myFlippedPartition, numberOfLevels, unbuildIsWarning,
100 : flippedOperation, flippedLookup, havePermissions, haveRestrictions, toProhibit);
101 :
102 : #ifdef AFBL_DEBUG_LEVEL_0
103 : std::cout << "Arc flag build is instantiated (but still uninitialized)." << std::endl;
104 : #endif
105 0 : } // end of constructor
106 :
107 : /// @brief Destructor
108 : ~AFBuilder();
109 :
110 : /// @brief Returns the arc flag build
111 : AFBuild<E, N, V, M>* getArcFlagBuild() {
112 0 : return myArcFlagBuild;
113 : }
114 : /// @brief Returns the edges
115 : const std::vector<E*>& getEdges() {
116 0 : return myEdges;
117 : }
118 : /// @brief Resets the builder
119 : void reset();
120 : /** @brief Build the arc flag information for the arc flag router
121 : * @param[in] msTime The start time of the routes in milliseconds
122 : * @param[in] The vehicle
123 : * @return The vector with the arc flag information
124 : */
125 : std::vector<FlagInfo*>& build(SUMOTime msTime, const V* const vehicle);
126 : /** @brief Converts a SHARC level number to a partition level number
127 : * @param[in] sHARCLevel The SHARC level
128 : * @return The partition level number
129 : */
130 : int sHARCLevel2PartitionLevel(int sHARCLevel) {
131 : return AFRouter<E, N, V, M>::sHARCLevel2PartitionLevel(sHARCLevel, myNumberOfLevels);
132 : }
133 :
134 : protected:
135 : #ifdef AFBL_DEBUG_LEVEL_0
136 : /** @brief Loads already precomputed arc flags from a CSV file (for testing purposes)
137 : * @param[in] fileName The name of the CSV file
138 : */
139 : void loadFlagsFromCsv(const std::string fileName);
140 : /** @brief Saves computed arc flags to a CSV file (for testing purposes)
141 : * @param[in] fileName The name of the CSV file
142 : */
143 : void saveFlagsToCsv(const std::string fileName);
144 : /** @brief Returns true iff a file with the given name exists
145 : * @param[in] name The name of the file to test for existence
146 : * @return true iff a file with the given name exists
147 : */
148 : bool fileExists(const std::string& name) {
149 : std::ifstream f(name.c_str());
150 : return f.good();
151 : }
152 : #endif
153 : /// @brief The edges
154 : const std::vector<E*>& myEdges;
155 : /// @brief The flipped (backward) edges
156 : std::vector<FlippedEdge<E, N, V>*> myFlippedEdges;
157 : /// @brief The k-d tree partition of the backward graph with flipped edges
158 : KDTreePartition<FlippedEdge<E, N, V>, FlippedNode<E, N, V>, V>* myFlippedPartition;
159 : /// @brief The flag informations
160 : std::vector<FlagInfo*> myFlagInfos;
161 : /// @brief The arc flag build
162 : AFBuild<E, N, V, M>* myArcFlagBuild;
163 : /// @brief The number of levels of the k-d tree partition of the network
164 : int myNumberOfLevels;
165 : /// @brief The number of arc flags per each edge
166 : int myNumberOfArcFlags;
167 : #ifdef AFBL_DEBUG_LEVEL_0
168 : /// @brief The name of the arc flags file.
169 : // @note This is a CSV file for convenience/testing purposes
170 : const std::string myArcFlagsFileName;
171 : #endif
172 : bool myAmClean;
173 : };
174 :
175 : // ===========================================================================
176 : // method definitions
177 : // ===========================================================================
178 :
179 : template<class E, class N, class V, class M>
180 0 : AFBuilder<E, N, V, M>::~AFBuilder() {
181 0 : delete myArcFlagBuild;
182 0 : delete myFlippedPartition;
183 0 : for (FlagInfo* flagInfo : myFlagInfos) {
184 0 : delete flagInfo;
185 : }
186 0 : }
187 :
188 : template<class E, class N, class V, class M>
189 : void AFBuilder<E, N, V, M>::reset() {
190 0 : for (FlagInfo* flagInfo : myFlagInfos) {
191 0 : flagInfo->reset();
192 : }
193 0 : myAmClean = true;
194 0 : }
195 :
196 : template<class E, class N, class V, class M>
197 0 : std::vector<typename AFInfo<E>::FlagInfo*>& AFBuilder<E, N, V, M>::build(SUMOTime msTime, const V* const vehicle) {
198 0 : if (!myAmClean) {
199 : reset();
200 : }
201 : assert(myFlippedPartition);
202 0 : if (myFlippedPartition->isClean()) {
203 0 : myFlippedPartition->init(vehicle);
204 0 : myArcFlagBuild->setFlippedPartition(myFlippedPartition);
205 : } else {
206 0 : myFlippedPartition->reset(vehicle);
207 : }
208 : assert(myArcFlagBuild);
209 : #ifdef AFBL_DEBUG_LEVEL_0
210 : bool fileExists = this->fileExists(myArcFlagsFileName);
211 : if (fileExists && myAmClean) {
212 : std::cout << "Loading arc flags from file " << myArcFlagsFileName << std::endl;
213 : loadFlagsFromCsv(myArcFlagsFileName);
214 : std::cout << "Arc flags loaded." << std::endl;
215 : } else {
216 : #endif
217 0 : myArcFlagBuild->init(msTime, vehicle, myFlagInfos);
218 : #ifdef AFBL_DEBUG_LEVEL_0
219 : }
220 : #endif
221 0 : delete myFlippedPartition;
222 0 : myFlippedPartition = nullptr;
223 :
224 : #ifdef AFBL_DEBUG_LEVEL_0
225 : if (!fileExists) {
226 : std::cout << "Saving arc flags..." << std::endl;
227 : // save flag vectors in a CSV file (one column, flag vectors in the order of edges)
228 : saveFlagsToCsv(myArcFlagsFileName);
229 : std::cout << "Arc flags have been saved." << std::endl;
230 : }
231 : #endif
232 0 : myAmClean = false;
233 0 : return myFlagInfos;
234 : }
235 :
236 : #ifdef AFBL_DEBUG_LEVEL_0
237 : template<class E, class N, class V, class M>
238 : void AFBuilder<E, N, V, M>::saveFlagsToCsv(const std::string fileName) {
239 : std::ofstream csvFile(fileName);
240 : for (FlagInfo* flagInfo : myFlagInfos) {
241 : if ((flagInfo->arcFlags).empty()) {
242 : // default flag is false / zero
243 : std::fill_n(std::back_inserter(flagInfo->arcFlags),
244 : myNumberOfArcFlags, false);
245 : }
246 : for (bool flag : flagInfo->arcFlags) {
247 : csvFile << flag;
248 : }
249 : csvFile << std::endl;
250 : }
251 : csvFile.close();
252 : }
253 :
254 : template<class E, class N, class V, class M>
255 : void AFBuilder<E, N, V, M>::loadFlagsFromCsv(const std::string fileName) {
256 : assert(myAmClean);
257 : std::string fileNameCopy = fileName;
258 : std::ifstream csvFile(fileNameCopy);
259 : std::string result;
260 : if (!csvFile.is_open()) {
261 : result = fileNameCopy.insert(0, "Could not open CSV file ");
262 : throw std::runtime_error(result);
263 : }
264 : for (FlagInfo* flagInfo : myFlagInfos) {
265 : (flagInfo->arcFlags).clear();
266 : std::fill_n(std::back_inserter(flagInfo->arcFlags),
267 : myNumberOfArcFlags, false);
268 : std::string line;
269 : if (std::getline(csvFile, line)) {
270 : if (line.empty()) {
271 : continue;
272 : }
273 : std::stringstream stringStream(line);
274 : std::string flagAsString(1, '\0');
275 : int pos = 0;
276 : while (stringStream.read(&flagAsString[0], 1)) {
277 : (flagInfo->arcFlags)[pos++] = (!flagAsString.compare("0") ? 0 : 1);
278 : }
279 : } else {
280 : result = fileNameCopy.insert(0, "CSV file ");
281 : throw std::runtime_error(result.append(" has not enough lines - wrong or corrupted file?"));
282 : }
283 : }
284 : myAmClean = false;
285 : csvFile.close();
286 : }
287 : #endif
|
