1 #include "extractor/edge_based_graph_factory.hpp"
2 #include "extractor/conditional_turn_penalty.hpp"
3 #include "extractor/edge_based_edge.hpp"
4 #include "extractor/files.hpp"
5 #include "extractor/intersection/intersection_analysis.hpp"
6 #include "extractor/scripting_environment.hpp"
7 #include "extractor/serialization.hpp"
8 #include "extractor/suffix_table.hpp"
9
10 #include "storage/io.hpp"
11
12 #include "util/assert.hpp"
13 #include "util/bearing.hpp"
14 #include "util/connectivity_checksum.hpp"
15 #include "util/coordinate.hpp"
16 #include "util/coordinate_calculation.hpp"
17 #include "util/exception.hpp"
18 #include "util/integer_range.hpp"
19 #include "util/log.hpp"
20 #include "util/percent.hpp"
21 #include "util/timing_util.hpp"
22
23 #include <boost/assert.hpp>
24 #include <boost/crc.hpp>
25 #include <boost/functional/hash.hpp>
26 #include <boost/numeric/conversion/cast.hpp>
27
28 #include <algorithm>
29 #include <cmath>
30 #include <iomanip>
31 #include <limits>
32 #include <sstream>
33 #include <string>
34 #include <thread>
35 #include <tuple>
36 #include <unordered_map>
37
38 #include <tbb/blocked_range.h>
39 #include <tbb/parallel_for.h>
40 #include <tbb/pipeline.h>
41
42 namespace std
43 {
44 template <> struct hash<std::pair<NodeID, NodeID>>
45 {
operator ()std::hash46 std::size_t operator()(const std::pair<NodeID, NodeID> &mk) const noexcept
47 {
48 std::size_t seed = 0;
49 boost::hash_combine(seed, mk.first);
50 boost::hash_combine(seed, mk.second);
51 return seed;
52 }
53 };
54 } // namespace std
55
56 namespace osrm
57 {
58 namespace extractor
59 {
60
61 // Configuration to find representative candidate for turn angle calculations
EdgeBasedGraphFactory(const util::NodeBasedDynamicGraph & node_based_graph,EdgeBasedNodeDataContainer & node_data_container,const CompressedEdgeContainer & compressed_edge_container,const std::unordered_set<NodeID> & barrier_nodes,const std::unordered_set<NodeID> & traffic_lights,const std::vector<util::Coordinate> & coordinates,const NameTable & name_table,const std::unordered_set<EdgeID> & segregated_edges,const extractor::LaneDescriptionMap & lane_description_map)62 EdgeBasedGraphFactory::EdgeBasedGraphFactory(
63 const util::NodeBasedDynamicGraph &node_based_graph,
64 EdgeBasedNodeDataContainer &node_data_container,
65 const CompressedEdgeContainer &compressed_edge_container,
66 const std::unordered_set<NodeID> &barrier_nodes,
67 const std::unordered_set<NodeID> &traffic_lights,
68 const std::vector<util::Coordinate> &coordinates,
69 const NameTable &name_table,
70 const std::unordered_set<EdgeID> &segregated_edges,
71 const extractor::LaneDescriptionMap &lane_description_map)
72 : m_edge_based_node_container(node_data_container), m_connectivity_checksum(0),
73 m_number_of_edge_based_nodes(0), m_coordinates(coordinates),
74 m_node_based_graph(std::move(node_based_graph)), m_barrier_nodes(barrier_nodes),
75 m_traffic_lights(traffic_lights), m_compressed_edge_container(compressed_edge_container),
76 name_table(name_table), segregated_edges(segregated_edges),
77 lane_description_map(lane_description_map)
78 {
79 }
80
GetEdgeBasedEdges(util::DeallocatingVector<EdgeBasedEdge> & output_edge_list)81 void EdgeBasedGraphFactory::GetEdgeBasedEdges(
82 util::DeallocatingVector<EdgeBasedEdge> &output_edge_list)
83 {
84 BOOST_ASSERT_MSG(0 == output_edge_list.size(), "Vector is not empty");
85 using std::swap; // Koenig swap
86 swap(m_edge_based_edge_list, output_edge_list);
87 }
88
GetEdgeBasedNodeSegments(std::vector<EdgeBasedNodeSegment> & nodes)89 void EdgeBasedGraphFactory::GetEdgeBasedNodeSegments(std::vector<EdgeBasedNodeSegment> &nodes)
90 {
91 using std::swap; // Koenig swap
92 swap(nodes, m_edge_based_node_segments);
93 }
94
GetEdgeBasedNodeWeights(std::vector<EdgeWeight> & output_node_weights)95 void EdgeBasedGraphFactory::GetEdgeBasedNodeWeights(std::vector<EdgeWeight> &output_node_weights)
96 {
97 using std::swap; // Koenig swap
98 swap(m_edge_based_node_weights, output_node_weights);
99 }
100
GetEdgeBasedNodeDurations(std::vector<EdgeWeight> & output_node_durations)101 void EdgeBasedGraphFactory::GetEdgeBasedNodeDurations(
102 std::vector<EdgeWeight> &output_node_durations)
103 {
104 using std::swap; // Koenig swap
105 swap(m_edge_based_node_durations, output_node_durations);
106 }
107
GetEdgeBasedNodeDistances(std::vector<EdgeDistance> & output_node_distances)108 void EdgeBasedGraphFactory::GetEdgeBasedNodeDistances(
109 std::vector<EdgeDistance> &output_node_distances)
110 {
111 using std::swap; // Koenig swap
112 swap(m_edge_based_node_distances, output_node_distances);
113 }
114
GetConnectivityChecksum() const115 std::uint32_t EdgeBasedGraphFactory::GetConnectivityChecksum() const
116 {
117 return m_connectivity_checksum;
118 }
119
GetNumberOfEdgeBasedNodes() const120 std::uint64_t EdgeBasedGraphFactory::GetNumberOfEdgeBasedNodes() const
121 {
122 return m_number_of_edge_based_nodes;
123 }
124
InsertEdgeBasedNode(const NodeID node_u,const NodeID node_v)125 NBGToEBG EdgeBasedGraphFactory::InsertEdgeBasedNode(const NodeID node_u, const NodeID node_v)
126 {
127 // merge edges together into one EdgeBasedNode
128 BOOST_ASSERT(node_u != SPECIAL_NODEID);
129 BOOST_ASSERT(node_v != SPECIAL_NODEID);
130
131 // find forward edge id and
132 const EdgeID edge_id_1 = m_node_based_graph.FindEdge(node_u, node_v);
133 BOOST_ASSERT(edge_id_1 != SPECIAL_EDGEID);
134
135 const EdgeData &forward_data = m_node_based_graph.GetEdgeData(edge_id_1);
136
137 // find reverse edge id and
138 const EdgeID edge_id_2 = m_node_based_graph.FindEdge(node_v, node_u);
139 BOOST_ASSERT(edge_id_2 != SPECIAL_EDGEID);
140
141 const EdgeData &reverse_data = m_node_based_graph.GetEdgeData(edge_id_2);
142
143 BOOST_ASSERT(nbe_to_ebn_mapping[edge_id_1] != SPECIAL_NODEID ||
144 nbe_to_ebn_mapping[edge_id_2] != SPECIAL_NODEID);
145
146 // ⚠ Use the sign bit of node weights to distinguish oneway streets:
147 // * MSB is set - a node corresponds to a one-way street
148 // * MSB is clear - a node corresponds to a bidirectional street
149 // Before using node weights data values must be adjusted:
150 // * in contraction if MSB is set the node weight is INVALID_EDGE_WEIGHT.
151 // This adjustment is needed to enforce loop creation for oneways.
152 // * in other cases node weights must be masked with 0x7fffffff to clear MSB
153 if (nbe_to_ebn_mapping[edge_id_1] != SPECIAL_NODEID &&
154 nbe_to_ebn_mapping[edge_id_2] == SPECIAL_NODEID)
155 m_edge_based_node_weights[nbe_to_ebn_mapping[edge_id_1]] |= 0x80000000;
156
157 BOOST_ASSERT(m_compressed_edge_container.HasEntryForID(edge_id_1) ==
158 m_compressed_edge_container.HasEntryForID(edge_id_2));
159 BOOST_ASSERT(m_compressed_edge_container.HasEntryForID(edge_id_1));
160 BOOST_ASSERT(m_compressed_edge_container.HasEntryForID(edge_id_2));
161 const auto &forward_geometry = m_compressed_edge_container.GetBucketReference(edge_id_1);
162 BOOST_ASSERT(forward_geometry.size() ==
163 m_compressed_edge_container.GetBucketReference(edge_id_2).size());
164 const auto segment_count = forward_geometry.size();
165
166 // There should always be some geometry
167 BOOST_ASSERT(0 != segment_count);
168
169 // const unsigned packed_geometry_id = m_compressed_edge_container.ZipEdges(edge_id_1,
170 // edge_id_2);
171
172 NodeID current_edge_source_coordinate_id = node_u;
173
174 const auto edge_id_to_segment_id = [](const NodeID edge_based_node_id) {
175 if (edge_based_node_id == SPECIAL_NODEID)
176 {
177 return SegmentID{SPECIAL_SEGMENTID, false};
178 }
179
180 return SegmentID{edge_based_node_id, true};
181 };
182
183 // Add edge-based node data for forward and reverse nodes indexed by edge_id
184 BOOST_ASSERT(nbe_to_ebn_mapping[edge_id_1] != SPECIAL_EDGEID);
185 m_edge_based_node_container.nodes[nbe_to_ebn_mapping[edge_id_1]].geometry_id =
186 forward_data.geometry_id;
187 m_edge_based_node_container.nodes[nbe_to_ebn_mapping[edge_id_1]].annotation_id =
188 forward_data.annotation_data;
189 m_edge_based_node_container.nodes[nbe_to_ebn_mapping[edge_id_1]].segregated =
190 segregated_edges.count(edge_id_1) > 0;
191
192 if (nbe_to_ebn_mapping[edge_id_2] != SPECIAL_EDGEID)
193 {
194 m_edge_based_node_container.nodes[nbe_to_ebn_mapping[edge_id_2]].geometry_id =
195 reverse_data.geometry_id;
196 m_edge_based_node_container.nodes[nbe_to_ebn_mapping[edge_id_2]].annotation_id =
197 reverse_data.annotation_data;
198 m_edge_based_node_container.nodes[nbe_to_ebn_mapping[edge_id_2]].segregated =
199 segregated_edges.count(edge_id_2) > 0;
200 }
201
202 // Add segments of edge-based nodes
203 for (const auto i : util::irange(std::size_t{0}, segment_count))
204 {
205 BOOST_ASSERT(
206 current_edge_source_coordinate_id ==
207 m_compressed_edge_container.GetBucketReference(edge_id_2)[segment_count - 1 - i]
208 .node_id);
209 const NodeID current_edge_target_coordinate_id = forward_geometry[i].node_id;
210
211 // don't add node-segments for penalties
212 if (current_edge_target_coordinate_id == current_edge_source_coordinate_id)
213 continue;
214
215 BOOST_ASSERT(current_edge_target_coordinate_id != current_edge_source_coordinate_id);
216
217 // build edges
218 m_edge_based_node_segments.emplace_back(
219 edge_id_to_segment_id(nbe_to_ebn_mapping[edge_id_1]),
220 edge_id_to_segment_id(nbe_to_ebn_mapping[edge_id_2]),
221 current_edge_source_coordinate_id,
222 current_edge_target_coordinate_id,
223 i,
224 forward_data.flags.startpoint || reverse_data.flags.startpoint);
225
226 current_edge_source_coordinate_id = current_edge_target_coordinate_id;
227 }
228
229 BOOST_ASSERT(current_edge_source_coordinate_id == node_v);
230
231 return NBGToEBG{node_u, node_v, nbe_to_ebn_mapping[edge_id_1], nbe_to_ebn_mapping[edge_id_2]};
232 }
233
Run(ScriptingEnvironment & scripting_environment,const std::string & turn_weight_penalties_filename,const std::string & turn_duration_penalties_filename,const std::string & turn_penalties_index_filename,const std::string & cnbg_ebg_mapping_path,const std::string & conditional_penalties_filename,const std::string & maneuver_overrides_filename,const RestrictionMap & unconditional_node_restriction_map,const ConditionalRestrictionMap & conditional_node_restriction_map,const WayRestrictionMap & way_restriction_map,const std::vector<UnresolvedManeuverOverride> & unresolved_maneuver_overrides)234 void EdgeBasedGraphFactory::Run(
235 ScriptingEnvironment &scripting_environment,
236 const std::string &turn_weight_penalties_filename,
237 const std::string &turn_duration_penalties_filename,
238 const std::string &turn_penalties_index_filename,
239 const std::string &cnbg_ebg_mapping_path,
240 const std::string &conditional_penalties_filename,
241 const std::string &maneuver_overrides_filename,
242 const RestrictionMap &unconditional_node_restriction_map,
243 const ConditionalRestrictionMap &conditional_node_restriction_map,
244 const WayRestrictionMap &way_restriction_map,
245 const std::vector<UnresolvedManeuverOverride> &unresolved_maneuver_overrides)
246 {
247 TIMER_START(renumber);
248 m_number_of_edge_based_nodes =
249 LabelEdgeBasedNodes() + way_restriction_map.NumberOfDuplicatedNodes();
250 TIMER_STOP(renumber);
251
252 // Allocate memory for edge-based nodes
253 // In addition to the normal edges, allocate enough space for copied edges from
254 // via-way-restrictions, see calculation above
255 m_edge_based_node_container.nodes.resize(m_number_of_edge_based_nodes);
256
257 TIMER_START(generate_nodes);
258 {
259 auto mapping = GenerateEdgeExpandedNodes(way_restriction_map);
260 files::writeNBGMapping(cnbg_ebg_mapping_path, mapping);
261 }
262 TIMER_STOP(generate_nodes);
263
264 TIMER_START(generate_edges);
265 GenerateEdgeExpandedEdges(scripting_environment,
266 turn_weight_penalties_filename,
267 turn_duration_penalties_filename,
268 turn_penalties_index_filename,
269 conditional_penalties_filename,
270 maneuver_overrides_filename,
271 unconditional_node_restriction_map,
272 conditional_node_restriction_map,
273 way_restriction_map,
274 unresolved_maneuver_overrides);
275
276 TIMER_STOP(generate_edges);
277
278 util::Log() << "Timing statistics for edge-expanded graph:";
279 util::Log() << "Renumbering edges: " << TIMER_SEC(renumber) << "s";
280 util::Log() << "Generating nodes: " << TIMER_SEC(generate_nodes) << "s";
281 util::Log() << "Generating edges: " << TIMER_SEC(generate_edges) << "s";
282 }
283
284 /// Renumbers all _forward_ edges and sets the edge_id.
285 /// A specific numbering is not important. Any unique ID will do.
286 /// Returns the number of edge-based nodes.
LabelEdgeBasedNodes()287 unsigned EdgeBasedGraphFactory::LabelEdgeBasedNodes()
288 {
289 // heuristic: node-based graph node is a simple intersection with four edges
290 // (edge-based nodes)
291 constexpr std::size_t ESTIMATED_EDGE_COUNT = 4;
292 m_edge_based_node_weights.reserve(ESTIMATED_EDGE_COUNT * m_node_based_graph.GetNumberOfNodes());
293 m_edge_based_node_durations.reserve(ESTIMATED_EDGE_COUNT *
294 m_node_based_graph.GetNumberOfNodes());
295 m_edge_based_node_distances.reserve(ESTIMATED_EDGE_COUNT *
296 m_node_based_graph.GetNumberOfNodes());
297 nbe_to_ebn_mapping.resize(m_node_based_graph.GetEdgeCapacity(), SPECIAL_NODEID);
298
299 // renumber edge based node of outgoing edges
300 unsigned numbered_edges_count = 0;
301 for (const auto current_node : util::irange(0u, m_node_based_graph.GetNumberOfNodes()))
302 {
303 for (const auto current_edge : m_node_based_graph.GetAdjacentEdgeRange(current_node))
304 {
305 const EdgeData &edge_data = m_node_based_graph.GetEdgeData(current_edge);
306 // only number incoming edges
307 if (edge_data.reversed)
308 {
309 continue;
310 }
311
312 m_edge_based_node_weights.push_back(edge_data.weight);
313 m_edge_based_node_durations.push_back(edge_data.duration);
314 m_edge_based_node_distances.push_back(edge_data.distance);
315
316 BOOST_ASSERT(numbered_edges_count < m_node_based_graph.GetNumberOfEdges());
317 nbe_to_ebn_mapping[current_edge] = numbered_edges_count;
318 ++numbered_edges_count;
319 }
320 }
321
322 return numbered_edges_count;
323 }
324
325 // Creates the nodes in the edge expanded graph from edges in the node-based graph.
326 std::vector<NBGToEBG>
GenerateEdgeExpandedNodes(const WayRestrictionMap & way_restriction_map)327 EdgeBasedGraphFactory::GenerateEdgeExpandedNodes(const WayRestrictionMap &way_restriction_map)
328 {
329 std::vector<NBGToEBG> mapping;
330
331 util::Log() << "Generating edge expanded nodes ... ";
332 // indicating a normal node within the edge-based graph. This node represents an edge in the
333 // node-based graph
334 {
335 util::UnbufferedLog log;
336 util::Percent progress(log, m_node_based_graph.GetNumberOfNodes());
337
338 // m_compressed_edge_container.InitializeBothwayVector();
339
340 // loop over all edges and generate new set of nodes
341 for (const auto nbg_node_u : util::irange(0u, m_node_based_graph.GetNumberOfNodes()))
342 {
343 BOOST_ASSERT(nbg_node_u != SPECIAL_NODEID);
344 progress.PrintStatus(nbg_node_u);
345 for (EdgeID nbg_edge_id : m_node_based_graph.GetAdjacentEdgeRange(nbg_node_u))
346 {
347 BOOST_ASSERT(nbg_edge_id != SPECIAL_EDGEID);
348
349 const NodeID nbg_node_v = m_node_based_graph.GetTarget(nbg_edge_id);
350 BOOST_ASSERT(nbg_node_v != SPECIAL_NODEID);
351 BOOST_ASSERT(nbg_node_u != nbg_node_v);
352
353 // pick only every other edge, since we have every edge as an outgoing and incoming
354 // egde
355 if (nbg_node_u >= nbg_node_v)
356 {
357 continue;
358 }
359
360 // if we found a non-forward edge reverse and try again
361 if (nbe_to_ebn_mapping[nbg_edge_id] == SPECIAL_NODEID)
362 {
363 mapping.push_back(InsertEdgeBasedNode(nbg_node_v, nbg_node_u));
364 }
365 else
366 {
367 mapping.push_back(InsertEdgeBasedNode(nbg_node_u, nbg_node_v));
368 }
369 }
370 }
371 }
372
373 util::Log() << "Expanding via-way turn restrictions ... ";
374 // Add copies of the nodes
375 {
376 util::UnbufferedLog log;
377 const auto via_edges = way_restriction_map.DuplicatedViaEdges();
378 util::Percent progress(log, via_edges.size());
379
380 NodeID edge_based_node_id =
381 NodeID(m_number_of_edge_based_nodes - way_restriction_map.NumberOfDuplicatedNodes());
382 std::size_t progress_counter = 0;
383 // allocate enough space for the mapping
384 for (const auto edge : via_edges)
385 {
386 const auto node_u = edge.from;
387 const auto node_v = edge.to;
388 // we know that the edge exists as non-reversed edge
389 const auto eid = m_node_based_graph.FindEdge(node_u, node_v);
390
391 BOOST_ASSERT(nbe_to_ebn_mapping[eid] != SPECIAL_NODEID);
392
393 // merge edges together into one EdgeBasedNode
394 BOOST_ASSERT(node_u != SPECIAL_NODEID);
395 BOOST_ASSERT(node_v != SPECIAL_NODEID);
396
397 // find node in the edge based graph, we only require one id:
398 const EdgeData &edge_data = m_node_based_graph.GetEdgeData(eid);
399 // BOOST_ASSERT(edge_data.edge_id < m_edge_based_node_container.Size());
400 m_edge_based_node_container.nodes[edge_based_node_id].geometry_id =
401 edge_data.geometry_id;
402 m_edge_based_node_container.nodes[edge_based_node_id].annotation_id =
403 edge_data.annotation_data;
404 m_edge_based_node_container.nodes[edge_based_node_id].segregated =
405 segregated_edges.count(eid) > 0;
406
407 const auto ebn_weight = m_edge_based_node_weights[nbe_to_ebn_mapping[eid]];
408 BOOST_ASSERT((ebn_weight & 0x7fffffff) == edge_data.weight);
409 m_edge_based_node_weights.push_back(ebn_weight);
410 m_edge_based_node_durations.push_back(
411 m_edge_based_node_durations[nbe_to_ebn_mapping[eid]]);
412 m_edge_based_node_distances.push_back(
413 m_edge_based_node_distances[nbe_to_ebn_mapping[eid]]);
414
415 // Include duplicate nodes in cnbg to ebg mapping. This means a
416 // compressed node pair (u,v) can appear multiple times in this list.
417 // This is needed by the MLD partition step to ensure duplicate nodes
418 // are also assigned to partitions (the MLD partitioner is currently
419 // the only consumer of this mapping).
420 mapping.push_back(NBGToEBG{node_u, node_v, edge_based_node_id, SPECIAL_NODEID});
421
422 edge_based_node_id++;
423 progress.PrintStatus(progress_counter++);
424 }
425 }
426
427 BOOST_ASSERT(m_number_of_edge_based_nodes == m_edge_based_node_weights.size());
428 BOOST_ASSERT(m_number_of_edge_based_nodes == m_edge_based_node_durations.size());
429 BOOST_ASSERT(m_number_of_edge_based_nodes == m_edge_based_node_distances.size());
430
431 util::Log() << "Generated " << m_number_of_edge_based_nodes << " nodes ("
432 << way_restriction_map.NumberOfDuplicatedNodes()
433 << " of which are duplicates) and " << m_edge_based_node_segments.size()
434 << " segments in edge-expanded graph";
435
436 return mapping;
437 }
438
439 /// Actually it also generates turn data and serializes them...
GenerateEdgeExpandedEdges(ScriptingEnvironment & scripting_environment,const std::string & turn_weight_penalties_filename,const std::string & turn_duration_penalties_filename,const std::string & turn_penalties_index_filename,const std::string & conditional_penalties_filename,const std::string & maneuver_overrides_filename,const RestrictionMap & unconditional_node_restriction_map,const ConditionalRestrictionMap & conditional_node_restriction_map,const WayRestrictionMap & way_restriction_map,const std::vector<UnresolvedManeuverOverride> & unresolved_maneuver_overrides)440 void EdgeBasedGraphFactory::GenerateEdgeExpandedEdges(
441 ScriptingEnvironment &scripting_environment,
442 const std::string &turn_weight_penalties_filename,
443 const std::string &turn_duration_penalties_filename,
444 const std::string &turn_penalties_index_filename,
445 const std::string &conditional_penalties_filename,
446 const std::string &maneuver_overrides_filename,
447 const RestrictionMap &unconditional_node_restriction_map,
448 const ConditionalRestrictionMap &conditional_node_restriction_map,
449 const WayRestrictionMap &way_restriction_map,
450 const std::vector<UnresolvedManeuverOverride> &unresolved_maneuver_overrides)
451 {
452 util::Log() << "Generating edge-expanded edges ";
453
454 std::size_t node_based_edge_counter = 0;
455
456 SuffixTable street_name_suffix_table(scripting_environment);
457 const auto &turn_lanes_data = transformTurnLaneMapIntoArrays(lane_description_map);
458 intersection::MergableRoadDetector mergable_road_detector(m_node_based_graph,
459 m_edge_based_node_container,
460 m_coordinates,
461 m_compressed_edge_container,
462 unconditional_node_restriction_map,
463 m_barrier_nodes,
464 turn_lanes_data,
465 name_table,
466 street_name_suffix_table);
467
468 // FIXME these need to be tuned in pre-allocated size
469 std::vector<TurnPenalty> turn_weight_penalties;
470 std::vector<TurnPenalty> turn_duration_penalties;
471 std::vector<lookup::TurnIndexBlock> turn_penalties_index;
472
473 // Now, renumber all our maneuver overrides to use edge-based-nodes
474 std::vector<StorageManeuverOverride> storage_maneuver_overrides;
475 std::vector<NodeID> maneuver_override_sequences;
476
477 const auto weight_multiplier =
478 scripting_environment.GetProfileProperties().GetWeightMultiplier();
479
480 // filled in during next stage, kept alive through following scope
481 std::vector<Conditional> conditionals;
482 // The following block generates the edge-based-edges using a parallel processing pipeline.
483 // Sets of intersection IDs are batched in groups of GRAINSIZE (100) `generator_stage`, then
484 // those groups are processed in parallel `processor_stage`. Finally, results are appended to
485 // the various buffer vectors by the `output_stage` in the same order that the `generator_stage`
486 // created them in (tbb::filter::serial_in_order creates this guarantee). The order needs to be
487 // maintained because we depend on it later in the processing pipeline.
488 {
489 const NodeID node_count = m_node_based_graph.GetNumberOfNodes();
490
491 // This struct is the buffered output of the `processor_stage`. This data is
492 // appended to the various output arrays/files by the `output_stage`.
493 // same as IntersectionData, but grouped with edge to allow sorting after creating.
494 struct EdgeWithData
495 {
496 EdgeBasedEdge edge;
497 lookup::TurnIndexBlock turn_index;
498 TurnPenalty turn_weight_penalty;
499 TurnPenalty turn_duration_penalty;
500 };
501
502 auto const transfer_data = [&](const EdgeWithData &edge_with_data) {
503 m_edge_based_edge_list.push_back(edge_with_data.edge);
504 turn_weight_penalties.push_back(edge_with_data.turn_weight_penalty);
505 turn_duration_penalties.push_back(edge_with_data.turn_duration_penalty);
506 turn_penalties_index.push_back(edge_with_data.turn_index);
507 };
508
509 struct EdgesPipelineBuffer
510 {
511 std::size_t nodes_processed = 0;
512
513 std::vector<EdgeWithData> continuous_data; // may need this
514 std::vector<EdgeWithData> delayed_data; // may need this
515 std::vector<Conditional> conditionals;
516
517 std::unordered_map<NodeBasedTurn, std::pair<NodeID, NodeID>> turn_to_ebn_map;
518
519 util::ConnectivityChecksum checksum;
520 };
521 using EdgesPipelineBufferPtr = std::shared_ptr<EdgesPipelineBuffer>;
522
523 m_connectivity_checksum = 0;
524
525 std::unordered_map<NodeBasedTurn, std::pair<NodeID, NodeID>> global_turn_to_ebn_map;
526
527 // going over all nodes (which form the center of an intersection), we compute all possible
528 // turns along these intersections.
529 NodeID current_node = 0;
530
531 // Handle intersections in sets of 100. The pipeline below has a serial bottleneck during
532 // the writing phase, so we want to make the parallel workers do more work to give the
533 // serial final stage time to complete its tasks.
534 const constexpr unsigned GRAINSIZE = 100;
535
536 // First part of the pipeline generates iterator ranges of IDs in sets of GRAINSIZE
537 tbb::filter_t<void, tbb::blocked_range<NodeID>> generator_stage(
538 tbb::filter::serial_in_order, [&](tbb::flow_control &fc) {
539 if (current_node < node_count)
540 {
541 auto next_node = std::min(current_node + GRAINSIZE, node_count);
542 auto result = tbb::blocked_range<NodeID>(current_node, next_node);
543 current_node = next_node;
544 return result;
545 }
546 else
547 {
548 fc.stop();
549 return tbb::blocked_range<NodeID>(node_count, node_count);
550 }
551 });
552
553 // Generate edges for either artificial nodes or the main graph
554 const auto generate_edge = [this, &scripting_environment, weight_multiplier](
555 // what nodes will be used? In most cases this will be the id
556 // stored in the edge_data. In case of duplicated nodes (e.g.
557 // due to via-way restrictions), one/both of these might
558 // refer to a newly added edge based node
559 const auto edge_based_node_from,
560 const auto edge_based_node_to,
561 // the situation of the turn
562 const auto node_along_road_entering,
563 const auto node_based_edge_from,
564 const auto intersection_node,
565 const auto node_based_edge_to,
566 const auto &turn_angle,
567 const auto &road_legs_on_the_right,
568 const auto &road_legs_on_the_left,
569 const auto &edge_geometries) {
570 const auto &edge_data1 = m_node_based_graph.GetEdgeData(node_based_edge_from);
571 const auto &edge_data2 = m_node_based_graph.GetEdgeData(node_based_edge_to);
572
573 BOOST_ASSERT(nbe_to_ebn_mapping[node_based_edge_from] !=
574 nbe_to_ebn_mapping[node_based_edge_to]);
575 BOOST_ASSERT(!edge_data1.reversed);
576 BOOST_ASSERT(!edge_data2.reversed);
577
578 // compute weight and duration penalties
579 const auto is_traffic_light = m_traffic_lights.count(intersection_node);
580 const auto is_uturn =
581 guidance::getTurnDirection(turn_angle) == guidance::DirectionModifier::UTurn;
582
583 ExtractionTurn extracted_turn(
584 // general info
585 turn_angle,
586 road_legs_on_the_right.size() + road_legs_on_the_left.size() + 2 - is_uturn,
587 is_uturn,
588 is_traffic_light,
589 m_edge_based_node_container.GetAnnotation(edge_data1.annotation_data)
590 .is_left_hand_driving,
591 // source info
592 edge_data1.flags.restricted,
593 m_edge_based_node_container.GetAnnotation(edge_data1.annotation_data).travel_mode,
594 edge_data1.flags.road_classification.IsMotorwayClass(),
595 edge_data1.flags.road_classification.IsLinkClass(),
596 edge_data1.flags.road_classification.GetNumberOfLanes(),
597 edge_data1.flags.highway_turn_classification,
598 edge_data1.flags.access_turn_classification,
599 ((double)intersection::findEdgeLength(edge_geometries, node_based_edge_from) /
600 edge_data1.duration) *
601 36,
602 edge_data1.flags.road_classification.GetPriority(),
603 // target info
604 edge_data2.flags.restricted,
605 m_edge_based_node_container.GetAnnotation(edge_data2.annotation_data).travel_mode,
606 edge_data2.flags.road_classification.IsMotorwayClass(),
607 edge_data2.flags.road_classification.IsLinkClass(),
608 edge_data2.flags.road_classification.GetNumberOfLanes(),
609 edge_data2.flags.highway_turn_classification,
610 edge_data2.flags.access_turn_classification,
611 ((double)intersection::findEdgeLength(edge_geometries, node_based_edge_to) /
612 edge_data2.duration) *
613 36,
614 edge_data2.flags.road_classification.GetPriority(),
615 // connected roads
616 road_legs_on_the_right,
617 road_legs_on_the_left);
618
619 scripting_environment.ProcessTurn(extracted_turn);
620
621 // turn penalties are limited to [-2^15, 2^15) which roughly translates to 54 minutes
622 // and fits signed 16bit deci-seconds
623 auto weight_penalty =
624 boost::numeric_cast<TurnPenalty>(extracted_turn.weight * weight_multiplier);
625 auto duration_penalty = boost::numeric_cast<TurnPenalty>(extracted_turn.duration * 10.);
626
627 BOOST_ASSERT(SPECIAL_NODEID != nbe_to_ebn_mapping[node_based_edge_from]);
628 BOOST_ASSERT(SPECIAL_NODEID != nbe_to_ebn_mapping[node_based_edge_to]);
629
630 // auto turn_id = m_edge_based_edge_list.size();
631 auto weight = boost::numeric_cast<EdgeWeight>(edge_data1.weight + weight_penalty);
632 auto duration = boost::numeric_cast<EdgeWeight>(edge_data1.duration + duration_penalty);
633 auto distance = boost::numeric_cast<EdgeDistance>(edge_data1.distance);
634
635 EdgeBasedEdge edge_based_edge = {edge_based_node_from,
636 edge_based_node_to,
637 SPECIAL_NODEID, // This will be updated once the main
638 // loop completes!
639 weight,
640 duration,
641 distance,
642 true,
643 false};
644
645 // We write out the mapping between the edge-expanded edges and the original nodes.
646 // Since each edge represents a possible maneuver, external programs can use this to
647 // quickly perform updates to edge weights in order to penalize certain turns.
648
649 // If this edge is 'trivial' -- where the compressed edge corresponds exactly to an
650 // original OSM segment -- we can pull the turn's preceding node ID directly with
651 // `node_along_road_entering`;
652 // otherwise, we need to look up the node immediately preceding the turn from the
653 // compressed edge container.
654 const bool isTrivial = m_compressed_edge_container.IsTrivial(node_based_edge_from);
655
656 const auto &from_node =
657 isTrivial ? node_along_road_entering
658 : m_compressed_edge_container.GetLastEdgeSourceID(node_based_edge_from);
659 const auto &to_node =
660 m_compressed_edge_container.GetFirstEdgeTargetID(node_based_edge_to);
661
662 lookup::TurnIndexBlock turn_index_block = {from_node, intersection_node, to_node};
663
664 // insert data into the designated buffer
665 return EdgeWithData{
666 edge_based_edge, turn_index_block, weight_penalty, duration_penalty};
667 };
668
669 //
670 // Edge-based-graph stage
671 //
672 tbb::filter_t<tbb::blocked_range<NodeID>, EdgesPipelineBufferPtr> processor_stage(
673 tbb::filter::parallel, [&](const tbb::blocked_range<NodeID> &intersection_node_range) {
674 auto buffer = std::make_shared<EdgesPipelineBuffer>();
675 buffer->nodes_processed = intersection_node_range.size();
676
677 for (auto intersection_node = intersection_node_range.begin(),
678 end = intersection_node_range.end();
679 intersection_node < end;
680 ++intersection_node)
681 {
682 // We capture the thread-local work in these objects, then flush them in a
683 // controlled manner at the end of the parallel range
684 const auto &incoming_edges =
685 intersection::getIncomingEdges(m_node_based_graph, intersection_node);
686 const auto &outgoing_edges =
687 intersection::getOutgoingEdges(m_node_based_graph, intersection_node);
688
689 intersection::IntersectionEdgeGeometries edge_geometries;
690 std::unordered_set<EdgeID> merged_edge_ids;
691 std::tie(edge_geometries, merged_edge_ids) =
692 intersection::getIntersectionGeometries(m_node_based_graph,
693 m_compressed_edge_container,
694 m_coordinates,
695 mergable_road_detector,
696 intersection_node);
697
698 buffer->checksum.process_byte(incoming_edges.size());
699 buffer->checksum.process_byte(outgoing_edges.size());
700
701 // all nodes in the graph are connected in both directions. We check all
702 // outgoing nodes to find the incoming edge. This is a larger search overhead,
703 // but the cost we need to pay to generate edges here is worth the additional
704 // search overhead.
705 //
706 // a -> b <-> c
707 // |
708 // v
709 // d
710 //
711 // will have:
712 // a: b,rev=0
713 // b: a,rev=1 c,rev=0 d,rev=0
714 // c: b,rev=0
715 //
716 // From the flags alone, we cannot determine which nodes are connected to `b` by
717 // an outgoing edge. Therefore, we have to search all connected edges for edges
718 // entering `b`
719
720 for (const auto &incoming_edge : incoming_edges)
721 {
722 ++node_based_edge_counter;
723
724 const auto connected_roads =
725 extractor::intersection::getConnectedRoadsForEdgeGeometries(
726 m_node_based_graph,
727 m_edge_based_node_container,
728 unconditional_node_restriction_map,
729 m_barrier_nodes,
730 turn_lanes_data,
731 incoming_edge,
732 edge_geometries,
733 merged_edge_ids);
734
735 // check if this edge is part of a restriction via-way
736 const auto is_restriction_via_edge =
737 way_restriction_map.IsViaWayEdge(incoming_edge.node, intersection_node);
738
739 for (const auto &outgoing_edge : outgoing_edges)
740 {
741 auto is_turn_allowed =
742 intersection::isTurnAllowed(m_node_based_graph,
743 m_edge_based_node_container,
744 unconditional_node_restriction_map,
745 m_barrier_nodes,
746 edge_geometries,
747 turn_lanes_data,
748 incoming_edge,
749 outgoing_edge);
750 buffer->checksum.process_bit(is_turn_allowed);
751
752 if (!is_turn_allowed)
753 continue;
754
755 const auto turn =
756 std::find_if(connected_roads.begin(),
757 connected_roads.end(),
758 [edge = outgoing_edge.edge](const auto &road) {
759 return road.eid == edge;
760 });
761 OSRM_ASSERT(turn != connected_roads.end(),
762 m_coordinates[intersection_node]);
763
764 std::vector<ExtractionTurnLeg> road_legs_on_the_right;
765 std::vector<ExtractionTurnLeg> road_legs_on_the_left;
766
767 auto get_connected_road_info = [&](const auto &connected_edge) {
768 const auto &edge_data =
769 m_node_based_graph.GetEdgeData(connected_edge.eid);
770
771 bool is_incoming, is_outgoing;
772 if (edge_data.reversed)
773 {
774 // If getConnectedRoads adds reversed edge it means
775 // this edge is incoming-only
776 is_incoming = true;
777 is_outgoing = false;
778 }
779 else
780 {
781 // It does not add incoming edge if there is outgoing so we
782 // should find it ourselves
783 is_incoming = false;
784 auto reversed_edge = m_node_based_graph.FindEdge(
785 m_node_based_graph.GetTarget(connected_edge.eid),
786 intersection_node);
787 if (reversed_edge != SPECIAL_EDGEID)
788 {
789 const auto &reversed_edge_data =
790 m_node_based_graph.GetEdgeData(reversed_edge);
791
792 if (!reversed_edge_data.reversed)
793 {
794 is_incoming = true;
795 }
796 }
797
798 is_outgoing = true;
799 }
800
801 return ExtractionTurnLeg(
802 edge_data.flags.restricted,
803 edge_data.flags.road_classification.IsMotorwayClass(),
804 edge_data.flags.road_classification.IsLinkClass(),
805 edge_data.flags.road_classification.GetNumberOfLanes(),
806 edge_data.flags.highway_turn_classification,
807 edge_data.flags.access_turn_classification,
808 ((double)intersection::findEdgeLength(edge_geometries,
809 connected_edge.eid) /
810 edge_data.duration) *
811 36,
812 edge_data.flags.road_classification.GetPriority(),
813 is_incoming,
814 is_outgoing);
815 };
816
817 // all connected roads on the right of a u turn
818 const auto is_uturn = guidance::getTurnDirection(turn->angle) ==
819 guidance::DirectionModifier::UTurn;
820 if (is_uturn)
821 {
822 if (turn != connected_roads.begin())
823 {
824 std::transform(connected_roads.begin() + 1,
825 turn,
826 std::back_inserter(road_legs_on_the_right),
827 get_connected_road_info);
828 }
829
830 std::transform(turn + 1,
831 connected_roads.end(),
832 std::back_inserter(road_legs_on_the_right),
833 get_connected_road_info);
834 }
835 else
836 {
837 if (connected_roads.begin() != turn)
838 {
839 std::transform(connected_roads.begin() + 1,
840 turn,
841 std::back_inserter(road_legs_on_the_right),
842 get_connected_road_info);
843 }
844 std::transform(turn + 1,
845 connected_roads.end(),
846 std::back_inserter(road_legs_on_the_left),
847 get_connected_road_info);
848 }
849
850 if (is_uturn && turn != connected_roads.begin())
851 {
852 util::Log(logWARNING)
853 << "Turn is a u turn but not turning to the first connected "
854 "edge of the intersection. Node ID: "
855 << intersection_node << ", OSM link: "
856 << toOSMLink(m_coordinates[intersection_node]);
857 }
858 else if (turn == connected_roads.begin() && !is_uturn)
859 {
860 util::Log(logWARNING)
861 << "Turn is a u turn but not classified as a u turn. Node ID: "
862 << intersection_node << ", OSM link: "
863 << toOSMLink(m_coordinates[intersection_node]);
864 }
865
866 // In case a way restriction starts at a given location, add a turn onto
867 // every artificial node emanating here.
868 //
869 // e - f
870 // |
871 // a - b
872 // |
873 // c - d
874 //
875 // ab via bc to cd
876 // ab via be to ef
877 //
878 // has two artificial nodes (be/bc) with restrictions starting at `ab`.
879 // Since every restriction group (abc | abe) refers to the same
880 // artificial node, we simply have to find a single representative for
881 // the turn. Here we check whether the turn in question is the start of
882 // a via way restriction. If that should be the case, we switch the id
883 // of the edge-based-node for the target to the ID of the duplicated
884 // node associated with the turn. (e.g. ab via bc switches bc to bc_dup)
885 auto const target_id = way_restriction_map.RemapIfRestrictionStart(
886 nbe_to_ebn_mapping[outgoing_edge.edge],
887 incoming_edge.node,
888 outgoing_edge.node,
889 m_node_based_graph.GetTarget(outgoing_edge.edge),
890 m_number_of_edge_based_nodes);
891
892 /***************************/
893
894 const auto outgoing_edge_target =
895 m_node_based_graph.GetTarget(outgoing_edge.edge);
896
897 // TODO: this loop is not optimized - once we have a few
898 // overrides available, we should index this for faster
899 // lookups
900 for (auto &override : unresolved_maneuver_overrides)
901 {
902 for (auto &turn : override.turn_sequence)
903 {
904 if (turn.from == incoming_edge.node &&
905 turn.via == intersection_node &&
906 turn.to == outgoing_edge_target)
907 {
908 const auto &ebn_from =
909 nbe_to_ebn_mapping[incoming_edge.edge];
910 const auto &ebn_to = target_id;
911 buffer->turn_to_ebn_map[turn] =
912 std::make_pair(ebn_from, ebn_to);
913 }
914 }
915 }
916
917 { // scope to forget edge_with_data after
918 const auto edge_with_data =
919 generate_edge(nbe_to_ebn_mapping[incoming_edge.edge],
920 target_id,
921 incoming_edge.node,
922 incoming_edge.edge,
923 outgoing_edge.node,
924 outgoing_edge.edge,
925 turn->angle,
926 road_legs_on_the_right,
927 road_legs_on_the_left,
928 edge_geometries);
929
930 buffer->continuous_data.push_back(edge_with_data);
931
932 // get conditional restrictions that apply to this turn
933 const auto &restrictions =
934 conditional_node_restriction_map.Restrictions(
935 incoming_edge.node,
936 outgoing_edge.node,
937 outgoing_edge_target);
938 for (const auto &restriction : restrictions)
939 {
940 buffer->conditionals.push_back(
941 {nbe_to_ebn_mapping[incoming_edge.edge],
942 target_id,
943 {static_cast<std::uint64_t>(-1),
944 m_coordinates[intersection_node],
945 restriction->condition}});
946 }
947 }
948
949 // When on the edge of a via-way turn restriction, we need to not only
950 // handle the normal edges for the way, but also add turns for every
951 // duplicated node. This process is integrated here to avoid doing the
952 // turn analysis multiple times.
953 if (is_restriction_via_edge)
954 {
955 const auto duplicated_nodes = way_restriction_map.DuplicatedNodeIDs(
956 incoming_edge.node, intersection_node);
957
958 // next to the normal restrictions tracked in `entry_allowed`, via
959 // ways might introduce additional restrictions. These are handled
960 // here when turning off a via-way
961 for (auto duplicated_node_id : duplicated_nodes)
962 {
963 const auto from_id =
964 NodeID(m_number_of_edge_based_nodes -
965 way_restriction_map.NumberOfDuplicatedNodes() +
966 duplicated_node_id);
967
968 auto const node_at_end_of_turn =
969 m_node_based_graph.GetTarget(outgoing_edge.edge);
970
971 const auto is_restricted = way_restriction_map.IsRestricted(
972 duplicated_node_id, node_at_end_of_turn);
973
974 if (is_restricted)
975 {
976 auto const &restrictions =
977 way_restriction_map.GetRestrictions(
978 duplicated_node_id, node_at_end_of_turn);
979
980 auto const has_unconditional =
981 std::any_of(restrictions.begin(),
982 restrictions.end(),
983 [](const auto &restriction) {
984 return restriction->IsUnconditional();
985 });
986 if (has_unconditional)
987 continue;
988
989 // From this via way, the outgoing edge will either:
990 // a) take a conditional turn transferring to a via
991 // path of an overlapping restriction.
992 // b) take a conditional turn to exit the restriction.
993 // If a) is applicable here, we change the target to be
994 // the duplicate restriction node.
995 auto const via_target_id =
996 way_restriction_map.RemapIfRestrictionVia(
997 nbe_to_ebn_mapping[outgoing_edge.edge],
998 from_id,
999 m_node_based_graph.GetTarget(outgoing_edge.edge),
1000 m_number_of_edge_based_nodes);
1001
1002 // add into delayed data
1003 auto edge_with_data = generate_edge(from_id,
1004 via_target_id,
1005 incoming_edge.node,
1006 incoming_edge.edge,
1007 outgoing_edge.node,
1008 outgoing_edge.edge,
1009 turn->angle,
1010 road_legs_on_the_right,
1011 road_legs_on_the_left,
1012 edge_geometries);
1013
1014 buffer->delayed_data.push_back(edge_with_data);
1015
1016 // also add the conditions for the way
1017 for (const auto &restriction : restrictions)
1018 {
1019 // add a new conditional for the edge we just
1020 // created
1021 buffer->conditionals.push_back(
1022 {from_id,
1023 via_target_id,
1024 {static_cast<std::uint64_t>(-1),
1025 m_coordinates[intersection_node],
1026 restriction->condition}});
1027 }
1028 }
1029 else
1030 {
1031 // From this via way, the outgoing edge will either:
1032 // a) continue along the current via path
1033 // b) transfer to a via path of an overlapping restriction.
1034 // c) exit the restriction
1035 // If a) or b) are applicable here, we change the target to
1036 // be the duplicate restriction node.
1037 auto const via_target_id =
1038 way_restriction_map.RemapIfRestrictionVia(
1039 nbe_to_ebn_mapping[outgoing_edge.edge],
1040 from_id,
1041 m_node_based_graph.GetTarget(outgoing_edge.edge),
1042 m_number_of_edge_based_nodes);
1043
1044 auto edge_with_data = generate_edge(from_id,
1045 via_target_id,
1046 incoming_edge.node,
1047 incoming_edge.edge,
1048 outgoing_edge.node,
1049 outgoing_edge.edge,
1050 turn->angle,
1051 road_legs_on_the_right,
1052 road_legs_on_the_left,
1053 edge_geometries);
1054
1055 buffer->delayed_data.push_back(edge_with_data);
1056 }
1057 }
1058 }
1059 }
1060 }
1061 }
1062
1063 return buffer;
1064 });
1065
1066 // Last part of the pipeline puts all the calculated data into the serial buffers
1067 util::UnbufferedLog log;
1068 util::Percent routing_progress(log, node_count);
1069 std::vector<EdgeWithData> delayed_data;
1070 tbb::filter_t<EdgesPipelineBufferPtr, void> output_stage(
1071 tbb::filter::serial_in_order, [&](auto buffer) {
1072 routing_progress.PrintAddition(buffer->nodes_processed);
1073
1074 m_connectivity_checksum = buffer->checksum.update_checksum(m_connectivity_checksum);
1075
1076 // Copy data from local buffers into global EBG data
1077 std::for_each(
1078 buffer->continuous_data.begin(), buffer->continuous_data.end(), transfer_data);
1079 conditionals.insert(
1080 conditionals.end(), buffer->conditionals.begin(), buffer->conditionals.end());
1081
1082 // NOTE: potential overflow here if we hit 2^32 routable edges
1083 BOOST_ASSERT(m_edge_based_edge_list.size() <= std::numeric_limits<NodeID>::max());
1084
1085 // Copy via-way restrictions delayed data
1086 delayed_data.insert(
1087 delayed_data.end(), buffer->delayed_data.begin(), buffer->delayed_data.end());
1088
1089 std::for_each(buffer->turn_to_ebn_map.begin(),
1090 buffer->turn_to_ebn_map.end(),
1091 [&global_turn_to_ebn_map](const auto &p) {
1092 // TODO: log conflicts here
1093 global_turn_to_ebn_map.insert(p);
1094 });
1095 });
1096
1097 // Now, execute the pipeline. The value of "5" here was chosen by experimentation
1098 // on a 16-CPU machine and seemed to give the best performance. This value needs
1099 // to be balanced with the GRAINSIZE above - ideally, the pipeline puts as much work
1100 // as possible in the `intersection_handler` step so that those parallel workers don't
1101 // get blocked too much by the slower (io-performing) `buffer_storage`
1102 tbb::parallel_pipeline(std::thread::hardware_concurrency() * 5,
1103 generator_stage & processor_stage & output_stage);
1104
1105 // NOTE: buffer.delayed_data and buffer.delayed_turn_data have the same index
1106 std::for_each(delayed_data.begin(), delayed_data.end(), transfer_data);
1107
1108 // Now, replace node-based-node ID values in the `node_sequence` with
1109 // the edge-based-node values we found and stored in the `turn_to_ebn_map`
1110 for (auto &unresolved_override : unresolved_maneuver_overrides)
1111 {
1112 StorageManeuverOverride storage_override;
1113 storage_override.instruction_node = unresolved_override.instruction_node;
1114 storage_override.override_type = unresolved_override.override_type;
1115 storage_override.direction = unresolved_override.direction;
1116
1117 std::vector<NodeID> node_sequence(unresolved_override.turn_sequence.size() + 1,
1118 SPECIAL_NODEID);
1119
1120 for (std::int64_t i = unresolved_override.turn_sequence.size() - 1; i >= 0; --i)
1121 {
1122 const auto v = global_turn_to_ebn_map.find(unresolved_override.turn_sequence[i]);
1123 if (v != global_turn_to_ebn_map.end())
1124 {
1125 node_sequence[i] = v->second.first;
1126 node_sequence[i + 1] = v->second.second;
1127 }
1128 }
1129 storage_override.node_sequence_offset_begin = maneuver_override_sequences.size();
1130 storage_override.node_sequence_offset_end =
1131 maneuver_override_sequences.size() + node_sequence.size();
1132
1133 storage_override.start_node = node_sequence.front();
1134
1135 maneuver_override_sequences.insert(
1136 maneuver_override_sequences.end(), node_sequence.begin(), node_sequence.end());
1137
1138 storage_maneuver_overrides.push_back(storage_override);
1139 }
1140 }
1141 {
1142 util::Log() << "Sorting and writing " << storage_maneuver_overrides.size()
1143 << " maneuver overrides...";
1144
1145 // Sort by `from_node`, so that later lookups can be done with a binary search.
1146 std::sort(storage_maneuver_overrides.begin(),
1147 storage_maneuver_overrides.end(),
1148 [](const auto &a, const auto &b) { return a.start_node < b.start_node; });
1149
1150 files::writeManeuverOverrides(
1151 maneuver_overrides_filename, storage_maneuver_overrides, maneuver_override_sequences);
1152 }
1153
1154 util::Log() << "done.";
1155 util::Log() << "Renumbering turns";
1156 // Now, update the turn_id property on every EdgeBasedEdge - it will equal the position in the
1157 // m_edge_based_edge_list array for each object.
1158 tbb::parallel_for(tbb::blocked_range<NodeID>(0, m_edge_based_edge_list.size()),
1159 [this](const tbb::blocked_range<NodeID> &range) {
1160 for (auto x = range.begin(), end = range.end(); x != end; ++x)
1161 {
1162 m_edge_based_edge_list[x].data.turn_id = x;
1163 }
1164 });
1165
1166 // re-hash conditionals to connect to their respective edge-based edges. Due to the ordering, we
1167 // do not really have a choice but to index the conditional penalties and walk over all
1168 // edge-based-edges to find the ID of the edge
1169 auto const indexed_conditionals = IndexConditionals(std::move(conditionals));
1170 util::Log() << "Writing " << indexed_conditionals.size() << " conditional turn penalties...";
1171 extractor::files::writeConditionalRestrictions(conditional_penalties_filename,
1172 indexed_conditionals);
1173
1174 // write weight penalties per turn
1175 BOOST_ASSERT(turn_weight_penalties.size() == turn_duration_penalties.size() &&
1176 turn_weight_penalties.size() == turn_penalties_index.size());
1177 files::writeTurnWeightPenalty(turn_weight_penalties_filename, turn_weight_penalties);
1178 files::writeTurnDurationPenalty(turn_duration_penalties_filename, turn_duration_penalties);
1179 files::writeTurnPenaltiesIndex(turn_penalties_index_filename, turn_penalties_index);
1180
1181 util::Log() << "Generated " << m_edge_based_node_segments.size() << " edge based node segments";
1182 util::Log() << "Node-based graph contains " << node_based_edge_counter << " edges";
1183 util::Log() << "Edge-expanded graph ...";
1184 util::Log() << " contains " << m_edge_based_edge_list.size() << " edges";
1185 }
1186
1187 std::vector<ConditionalTurnPenalty>
IndexConditionals(std::vector<Conditional> && conditionals) const1188 EdgeBasedGraphFactory::IndexConditionals(std::vector<Conditional> &&conditionals) const
1189 {
1190 boost::unordered_multimap<std::pair<NodeID, NodeID>, ConditionalTurnPenalty *> index;
1191
1192 // build and index of all conditional restrictions
1193 for (auto &conditional : conditionals)
1194 index.insert(std::make_pair(std::make_pair(conditional.from_node, conditional.to_node),
1195 &conditional.penalty));
1196
1197 std::vector<ConditionalTurnPenalty> indexed_restrictions;
1198
1199 for (auto const &edge : m_edge_based_edge_list)
1200 {
1201 auto const range = index.equal_range(std::make_pair(edge.source, edge.target));
1202 for (auto itr = range.first; itr != range.second; ++itr)
1203 {
1204 itr->second->turn_offset = edge.data.turn_id;
1205 indexed_restrictions.push_back(*itr->second);
1206 }
1207 }
1208
1209 return indexed_restrictions;
1210 }
1211
1212 } // namespace extractor
1213 } // namespace osrm
1214