1 #include "extractor/extractor.hpp"
2
3 #include "extractor/compressed_edge_container.hpp"
4 #include "extractor/compressed_node_based_graph_edge.hpp"
5 #include "extractor/edge_based_edge.hpp"
6 #include "extractor/extraction_containers.hpp"
7 #include "extractor/extraction_node.hpp"
8 #include "extractor/extraction_relation.hpp"
9 #include "extractor/extraction_way.hpp"
10 #include "extractor/extractor_callbacks.hpp"
11 #include "extractor/files.hpp"
12 #include "extractor/maneuver_override_relation_parser.hpp"
13 #include "extractor/name_table.hpp"
14 #include "extractor/node_based_graph_factory.hpp"
15 #include "extractor/node_restriction_map.hpp"
16 #include "extractor/restriction_filter.hpp"
17 #include "extractor/restriction_graph.hpp"
18 #include "extractor/restriction_parser.hpp"
19 #include "extractor/scripting_environment.hpp"
20 #include "extractor/tarjan_scc.hpp"
21 #include "extractor/way_restriction_map.hpp"
22
23 #include "guidance/files.hpp"
24 #include "guidance/guidance_processing.hpp"
25 #include "guidance/segregated_intersection_classification.hpp"
26 #include "guidance/turn_data_container.hpp"
27
28 #include "util/exception.hpp"
29 #include "util/exception_utils.hpp"
30 #include "util/integer_range.hpp"
31 #include "util/log.hpp"
32 #include "util/static_graph.hpp"
33 #include "util/static_rtree.hpp"
34 #include "util/timing_util.hpp"
35
36 // Keep debug include to make sure the debug header is in sync with types.
37 #include "util/debug.hpp"
38
39 #include <boost/assert.hpp>
40
41 #include <osmium/handler/node_locations_for_ways.hpp>
42 #include <osmium/index/map/flex_mem.hpp>
43 #include <osmium/io/any_input.hpp>
44 #include <osmium/thread/pool.hpp>
45 #include <osmium/visitor.hpp>
46
47 #if TBB_VERSION_MAJOR == 2020
48 #include <tbb/global_control.h>
49 #else
50 #include <tbb/task_scheduler_init.h>
51 #endif
52 #include <tbb/pipeline.h>
53
54 #include <algorithm>
55 #include <atomic>
56 #include <bitset>
57 #include <chrono>
58 #include <iostream>
59 #include <memory>
60 #include <thread>
61 #include <tuple>
62 #include <type_traits>
63 #include <unordered_map>
64 #include <vector>
65
66 namespace osrm
67 {
68 namespace extractor
69 {
70
71 namespace
72 {
73 // Converts the class name map into a fixed mapping of index to name
SetClassNames(const std::vector<std::string> & class_names,ExtractorCallbacks::ClassesMap & classes_map,ProfileProperties & profile_properties)74 void SetClassNames(const std::vector<std::string> &class_names,
75 ExtractorCallbacks::ClassesMap &classes_map,
76 ProfileProperties &profile_properties)
77 {
78 // if we get a list of class names we can validate if we set invalid classes
79 // and add classes that were never reference
80 if (!class_names.empty())
81 {
82 // add class names that were never used explicitly on a way
83 // this makes sure we can correctly validate unkown class names later
84 for (const auto &name : class_names)
85 {
86 if (!isValidClassName(name))
87 {
88 throw util::exception("Invalid class name " + name + " only [a-Z0-9] allowed.");
89 }
90
91 auto iter = classes_map.find(name);
92 if (iter == classes_map.end())
93 {
94 auto index = classes_map.size();
95 if (index > MAX_CLASS_INDEX)
96 {
97 throw util::exception("Maximum number of classes is " +
98 std::to_string(MAX_CLASS_INDEX + 1));
99 }
100
101 classes_map[name] = getClassData(index);
102 }
103 }
104
105 // check if class names are only from the list supplied by the user
106 for (const auto &pair : classes_map)
107 {
108 auto iter = std::find(class_names.begin(), class_names.end(), pair.first);
109 if (iter == class_names.end())
110 {
111 throw util::exception("Profile used unknown class name: " + pair.first);
112 }
113 }
114 }
115
116 for (const auto &pair : classes_map)
117 {
118 auto range = getClassIndexes(pair.second);
119 BOOST_ASSERT(range.size() == 1);
120 profile_properties.SetClassName(range.front(), pair.first);
121 }
122 }
123
124 // Converts the class name list to a mask list
SetExcludableClasses(const ExtractorCallbacks::ClassesMap & classes_map,const std::vector<std::vector<std::string>> & excludable_classes,ProfileProperties & profile_properties)125 void SetExcludableClasses(const ExtractorCallbacks::ClassesMap &classes_map,
126 const std::vector<std::vector<std::string>> &excludable_classes,
127 ProfileProperties &profile_properties)
128 {
129 if (excludable_classes.size() > MAX_EXCLUDABLE_CLASSES)
130 {
131 throw util::exception("Only " + std::to_string(MAX_EXCLUDABLE_CLASSES) +
132 " excludable combinations allowed.");
133 }
134
135 // The exclude index 0 is reserve for not excludeing anything
136 profile_properties.SetExcludableClasses(0, 0);
137
138 std::size_t combination_index = 1;
139 for (const auto &combination : excludable_classes)
140 {
141 ClassData mask = 0;
142 for (const auto &name : combination)
143 {
144 auto iter = classes_map.find(name);
145 if (iter == classes_map.end())
146 {
147 util::Log(logWARNING)
148 << "Unknown class name " + name + " in excludable combination. Ignoring.";
149 }
150 else
151 {
152 mask |= iter->second;
153 }
154 }
155
156 if (mask > 0)
157 {
158 profile_properties.SetExcludableClasses(combination_index++, mask);
159 }
160 }
161 }
162
toEdgeList(const util::NodeBasedDynamicGraph & graph)163 std::vector<CompressedNodeBasedGraphEdge> toEdgeList(const util::NodeBasedDynamicGraph &graph)
164 {
165 std::vector<CompressedNodeBasedGraphEdge> edges;
166 edges.reserve(graph.GetNumberOfEdges());
167
168 // For all nodes iterate over its edges and dump (from, to) pairs
169 for (const NodeID from_node : util::irange(0u, graph.GetNumberOfNodes()))
170 {
171 for (const EdgeID edge : graph.GetAdjacentEdgeRange(from_node))
172 {
173 const auto to_node = graph.GetTarget(edge);
174
175 edges.push_back({from_node, to_node});
176 }
177 }
178
179 return edges;
180 }
181 } // namespace
182
183 /**
184 * TODO: Refactor this function into smaller functions for better readability.
185 *
186 * This function is the entry point for the whole extraction process. The goal of the extraction
187 * step is to filter and convert the OSM geometry to something more fitting for routing.
188 * That includes:
189 * - extracting turn restrictions
190 * - splitting ways into (directional!) edge segments
191 * - checking if nodes are barriers or traffic signal
192 * - discarding all tag information: All relevant type information for nodes/ways
193 * is extracted at this point.
194 *
195 * The result of this process are the following files:
196 * .names : Names of all streets, stored as long consecutive string with prefix sum based index
197 * .osrm : Nodes and edges in a intermediate format that easy to digest for osrm-contract
198 * .restrictions : Turn restrictions that are used by osrm-contract to construct the edge-expanded
199 * graph
200 *
201 */
run(ScriptingEnvironment & scripting_environment)202 int Extractor::run(ScriptingEnvironment &scripting_environment)
203 {
204 util::LogPolicy::GetInstance().Unmute();
205
206 const unsigned recommended_num_threads = std::thread::hardware_concurrency();
207 const auto number_of_threads = std::min(recommended_num_threads, config.requested_num_threads);
208
209 #if TBB_VERSION_MAJOR == 2020
210 tbb::global_control gc(tbb::global_control::max_allowed_parallelism,
211 config.requested_num_threads);
212 #else
213 tbb::task_scheduler_init init(config.requested_num_threads);
214 BOOST_ASSERT(init.is_active());
215 #endif
216
217 LaneDescriptionMap turn_lane_map;
218 std::vector<TurnRestriction> turn_restrictions;
219 std::vector<UnresolvedManeuverOverride> unresolved_maneuver_overrides;
220 std::tie(turn_lane_map, turn_restrictions, unresolved_maneuver_overrides) =
221 ParseOSMData(scripting_environment, number_of_threads);
222
223 // Transform the node-based graph that OSM is based on into an edge-based graph
224 // that is better for routing. Every edge becomes a node, and every valid
225 // movement (e.g. turn from A->B, and B->A) becomes an edge
226 util::Log() << "Generating edge-expanded graph representation";
227
228 TIMER_START(expansion);
229
230 EdgeBasedNodeDataContainer edge_based_nodes_container;
231 std::vector<EdgeBasedNodeSegment> edge_based_node_segments;
232 util::DeallocatingVector<EdgeBasedEdge> edge_based_edge_list;
233 std::vector<EdgeWeight> edge_based_node_weights;
234 std::vector<EdgeDuration> edge_based_node_durations;
235 std::vector<EdgeDistance> edge_based_node_distances;
236 std::uint32_t ebg_connectivity_checksum = 0;
237
238 // Create a node-based graph from the OSRM file
239 NodeBasedGraphFactory node_based_graph_factory(config.GetPath(".osrm"),
240 scripting_environment,
241 turn_restrictions,
242 unresolved_maneuver_overrides);
243
244 NameTable name_table;
245 files::readNames(config.GetPath(".osrm.names"), name_table);
246
247 util::Log() << "Find segregated edges in node-based graph ..." << std::flush;
248 TIMER_START(segregated);
249
250 auto segregated_edges = guidance::findSegregatedNodes(node_based_graph_factory, name_table);
251
252 TIMER_STOP(segregated);
253 util::Log() << "ok, after " << TIMER_SEC(segregated) << "s";
254 util::Log() << "Segregated edges count = " << segregated_edges.size();
255
256 util::Log() << "Writing nodes for nodes-based and edges-based graphs ...";
257 auto const &coordinates = node_based_graph_factory.GetCoordinates();
258 files::writeNodes(
259 config.GetPath(".osrm.nbg_nodes"), coordinates, node_based_graph_factory.GetOsmNodes());
260 node_based_graph_factory.ReleaseOsmNodes();
261
262 auto const &node_based_graph = node_based_graph_factory.GetGraph();
263
264 // The osrm-partition tool requires the compressed node based graph with an embedding.
265 //
266 // The `Run` function above re-numbers non-reverse compressed node based graph edges
267 // to a continuous range so that the nodes in the edge based graph are continuous.
268 //
269 // Luckily node based node ids still coincide with the coordinate array.
270 // That's the reason we can only here write out the final compressed node based graph.
271 files::writeCompressedNodeBasedGraph(config.GetPath(".osrm.cnbg").string(),
272 toEdgeList(node_based_graph));
273
274 node_based_graph_factory.GetCompressedEdges().PrintStatistics();
275
276 const auto &barrier_nodes = node_based_graph_factory.GetBarriers();
277 const auto &traffic_signals = node_based_graph_factory.GetTrafficSignals();
278 // stealing the annotation data from the node-based graph
279 edge_based_nodes_container =
280 EdgeBasedNodeDataContainer({}, std::move(node_based_graph_factory.GetAnnotationData()));
281
282 turn_restrictions = removeInvalidRestrictions(std::move(turn_restrictions), node_based_graph);
283 auto restriction_graph = constructRestrictionGraph(turn_restrictions);
284
285 const auto number_of_node_based_nodes = node_based_graph.GetNumberOfNodes();
286
287 const auto number_of_edge_based_nodes =
288 BuildEdgeExpandedGraph(node_based_graph,
289 coordinates,
290 node_based_graph_factory.GetCompressedEdges(),
291 barrier_nodes,
292 traffic_signals,
293 restriction_graph,
294 segregated_edges,
295 name_table,
296 unresolved_maneuver_overrides,
297 turn_lane_map,
298 scripting_environment,
299 edge_based_nodes_container,
300 edge_based_node_segments,
301 edge_based_node_weights,
302 edge_based_node_durations,
303 edge_based_node_distances,
304 edge_based_edge_list,
305 ebg_connectivity_checksum);
306
307 ProcessGuidanceTurns(node_based_graph,
308 edge_based_nodes_container,
309 coordinates,
310 node_based_graph_factory.GetCompressedEdges(),
311 barrier_nodes,
312 restriction_graph,
313 name_table,
314 std::move(turn_lane_map),
315 scripting_environment);
316
317 TIMER_STOP(expansion);
318
319 // output the geometry of the node-based graph, needs to be done after the last usage, since it
320 // destroys internal containers
321 files::writeSegmentData(config.GetPath(".osrm.geometry"),
322 *node_based_graph_factory.GetCompressedEdges().ToSegmentData());
323
324 util::Log() << "Saving edge-based node weights to file.";
325 TIMER_START(timer_write_node_weights);
326 extractor::files::writeEdgeBasedNodeWeightsDurationsDistances(config.GetPath(".osrm.enw"),
327 edge_based_node_weights,
328 edge_based_node_durations,
329 edge_based_node_distances);
330 TIMER_STOP(timer_write_node_weights);
331 util::Log() << "Done writing. (" << TIMER_SEC(timer_write_node_weights) << ")";
332
333 util::Log() << "Computing strictly connected components ...";
334 FindComponents(number_of_edge_based_nodes,
335 edge_based_edge_list,
336 edge_based_node_segments,
337 edge_based_nodes_container);
338
339 util::Log() << "Building r-tree ...";
340 TIMER_START(rtree);
341 BuildRTree(std::move(edge_based_node_segments), coordinates);
342
343 TIMER_STOP(rtree);
344
345 files::writeNodeData(config.GetPath(".osrm.ebg_nodes"), edge_based_nodes_container);
346
347 util::Log() << "Writing edge-based-graph edges ... " << std::flush;
348 TIMER_START(write_edges);
349 files::writeEdgeBasedGraph(config.GetPath(".osrm.ebg"),
350 number_of_edge_based_nodes,
351 edge_based_edge_list,
352 ebg_connectivity_checksum);
353 TIMER_STOP(write_edges);
354 util::Log() << "ok, after " << TIMER_SEC(write_edges) << "s";
355
356 util::Log() << "Processed " << edge_based_edge_list.size() << " edges";
357
358 const auto nodes_per_second =
359 static_cast<std::uint64_t>(number_of_node_based_nodes / TIMER_SEC(expansion));
360 const auto edges_per_second =
361 static_cast<std::uint64_t>((number_of_edge_based_nodes) / TIMER_SEC(expansion));
362
363 util::Log() << "Expansion: " << nodes_per_second << " nodes/sec and " << edges_per_second
364 << " edges/sec";
365 util::Log() << "To prepare the data for routing, run: "
366 << "./osrm-contract " << config.GetPath(".osrm");
367
368 return 0;
369 }
370
371 std::
372 tuple<LaneDescriptionMap, std::vector<TurnRestriction>, std::vector<UnresolvedManeuverOverride>>
ParseOSMData(ScriptingEnvironment & scripting_environment,const unsigned number_of_threads)373 Extractor::ParseOSMData(ScriptingEnvironment &scripting_environment,
374 const unsigned number_of_threads)
375 {
376 TIMER_START(extracting);
377
378 util::Log() << "Input file: " << config.input_path.filename().string();
379 if (!config.profile_path.empty())
380 {
381 util::Log() << "Profile: " << config.profile_path.filename().string();
382 }
383 util::Log() << "Threads: " << number_of_threads;
384
385 const osmium::io::File input_file(config.input_path.string());
386 osmium::thread::Pool pool(number_of_threads);
387
388 util::Log() << "Parsing in progress..";
389 TIMER_START(parsing);
390
391 { // Parse OSM header
392 osmium::io::Reader reader(input_file, pool, osmium::osm_entity_bits::nothing);
393 osmium::io::Header header = reader.header();
394
395 std::string generator = header.get("generator");
396 if (generator.empty())
397 {
398 generator = "unknown tool";
399 }
400 util::Log() << "input file generated by " << generator;
401
402 // write .timestamp data file
403 std::string timestamp = header.get("osmosis_replication_timestamp");
404 if (config.data_version == "osmosis")
405 {
406 files::writeTimestamp(config.GetPath(".osrm.timestamp").string(), timestamp);
407 }
408 else
409 {
410 files::writeTimestamp(config.GetPath(".osrm.timestamp").string(), config.data_version);
411 }
412 if (timestamp.empty())
413 {
414 timestamp = "n/a";
415 }
416 util::Log() << "timestamp: " << timestamp;
417 }
418
419 // Extraction containers and restriction parser
420 ExtractionContainers extraction_containers;
421 ExtractorCallbacks::ClassesMap classes_map;
422 LaneDescriptionMap turn_lane_map;
423 auto extractor_callbacks =
424 std::make_unique<ExtractorCallbacks>(extraction_containers,
425 classes_map,
426 turn_lane_map,
427 scripting_environment.GetProfileProperties());
428
429 // get list of supported relation types
430 auto relation_types = scripting_environment.GetRelations();
431 std::sort(relation_types.begin(), relation_types.end());
432
433 std::vector<std::string> restrictions = scripting_environment.GetRestrictions();
434 // setup restriction parser
435 const RestrictionParser restriction_parser(
436 scripting_environment.GetProfileProperties().use_turn_restrictions,
437 config.parse_conditionals,
438 restrictions);
439
440 const ManeuverOverrideRelationParser maneuver_override_parser;
441
442 // OSM data reader
443 using SharedBuffer = std::shared_ptr<osmium::memory::Buffer>;
444 struct ParsedBuffer
445 {
446 SharedBuffer buffer;
447 std::vector<std::pair<const osmium::Node &, ExtractionNode>> resulting_nodes;
448 std::vector<std::pair<const osmium::Way &, ExtractionWay>> resulting_ways;
449 std::vector<std::pair<const osmium::Relation &, ExtractionRelation>> resulting_relations;
450 std::vector<InputTurnRestriction> resulting_restrictions;
451 std::vector<InputManeuverOverride> resulting_maneuver_overrides;
452 };
453
454 ExtractionRelationContainer relations;
455
456 const auto buffer_reader = [](osmium::io::Reader &reader) {
457 return tbb::filter_t<void, SharedBuffer>(
458 tbb::filter::serial_in_order, [&reader](tbb::flow_control &fc) {
459 if (auto buffer = reader.read())
460 {
461 return std::make_shared<osmium::memory::Buffer>(std::move(buffer));
462 }
463 else
464 {
465 fc.stop();
466 return SharedBuffer{};
467 }
468 });
469 };
470
471 // Node locations cache (assumes nodes are placed before ways)
472 using osmium_index_type =
473 osmium::index::map::FlexMem<osmium::unsigned_object_id_type, osmium::Location>;
474 using osmium_location_handler_type = osmium::handler::NodeLocationsForWays<osmium_index_type>;
475
476 osmium_index_type location_cache;
477 osmium_location_handler_type location_handler(location_cache);
478
479 tbb::filter_t<SharedBuffer, SharedBuffer> location_cacher(
480 tbb::filter::serial_in_order, [&location_handler](SharedBuffer buffer) {
481 osmium::apply(buffer->begin(), buffer->end(), location_handler);
482 return buffer;
483 });
484
485 // OSM elements Lua parser
486 tbb::filter_t<SharedBuffer, ParsedBuffer> buffer_transformer(
487 tbb::filter::parallel, [&](const SharedBuffer buffer) {
488 ParsedBuffer parsed_buffer;
489 parsed_buffer.buffer = buffer;
490 scripting_environment.ProcessElements(*buffer,
491 restriction_parser,
492 maneuver_override_parser,
493 relations,
494 parsed_buffer.resulting_nodes,
495 parsed_buffer.resulting_ways,
496 parsed_buffer.resulting_restrictions,
497 parsed_buffer.resulting_maneuver_overrides);
498 return parsed_buffer;
499 });
500
501 // Parsed nodes and ways handler
502 unsigned number_of_nodes = 0;
503 unsigned number_of_ways = 0;
504 unsigned number_of_restrictions = 0;
505 unsigned number_of_maneuver_overrides = 0;
506 tbb::filter_t<ParsedBuffer, void> buffer_storage(
507 tbb::filter::serial_in_order, [&](const ParsedBuffer &parsed_buffer) {
508 number_of_nodes += parsed_buffer.resulting_nodes.size();
509 // put parsed objects thru extractor callbacks
510 for (const auto &result : parsed_buffer.resulting_nodes)
511 {
512 extractor_callbacks->ProcessNode(result.first, result.second);
513 }
514 number_of_ways += parsed_buffer.resulting_ways.size();
515 for (const auto &result : parsed_buffer.resulting_ways)
516 {
517 extractor_callbacks->ProcessWay(result.first, result.second);
518 }
519
520 number_of_restrictions += parsed_buffer.resulting_restrictions.size();
521 for (const auto &result : parsed_buffer.resulting_restrictions)
522 {
523 extractor_callbacks->ProcessRestriction(result);
524 }
525
526 number_of_maneuver_overrides = parsed_buffer.resulting_maneuver_overrides.size();
527 for (const auto &result : parsed_buffer.resulting_maneuver_overrides)
528 {
529 extractor_callbacks->ProcessManeuverOverride(result);
530 }
531 });
532
533 tbb::filter_t<SharedBuffer, std::shared_ptr<ExtractionRelationContainer>> buffer_relation_cache(
534 tbb::filter::parallel, [&](const SharedBuffer buffer) {
535 if (!buffer)
536 return std::shared_ptr<ExtractionRelationContainer>{};
537
538 auto relations = std::make_shared<ExtractionRelationContainer>();
539 for (auto entity = buffer->cbegin(), end = buffer->cend(); entity != end; ++entity)
540 {
541 if (entity->type() != osmium::item_type::relation)
542 continue;
543
544 const auto &rel = static_cast<const osmium::Relation &>(*entity);
545
546 const char *rel_type = rel.get_value_by_key("type");
547 if (!rel_type || !std::binary_search(relation_types.begin(),
548 relation_types.end(),
549 std::string(rel_type)))
550 continue;
551
552 ExtractionRelation extracted_rel({rel.id(), osmium::item_type::relation});
553 for (auto const &t : rel.tags())
554 extracted_rel.attributes.emplace_back(std::make_pair(t.key(), t.value()));
555
556 for (auto const &m : rel.members())
557 {
558 ExtractionRelation::OsmIDTyped const mid(m.ref(), m.type());
559 extracted_rel.AddMember(mid, m.role());
560 relations->AddRelationMember(extracted_rel.id, mid);
561 }
562
563 relations->AddRelation(std::move(extracted_rel));
564 };
565 return relations;
566 });
567
568 unsigned number_of_relations = 0;
569 tbb::filter_t<std::shared_ptr<ExtractionRelationContainer>, void> buffer_storage_relation(
570 tbb::filter::serial_in_order,
571 [&](const std::shared_ptr<ExtractionRelationContainer> parsed_relations) {
572 number_of_relations += parsed_relations->GetRelationsNum();
573 relations.Merge(std::move(*parsed_relations));
574 });
575
576 // Parse OSM elements with parallel transformer
577 // Number of pipeline tokens that yielded the best speedup was about 1.5 * num_cores
578 const auto num_threads = std::thread::hardware_concurrency() * 1.5;
579 const auto read_meta =
580 config.use_metadata ? osmium::io::read_meta::yes : osmium::io::read_meta::no;
581
582 { // Relations reading pipeline
583 util::Log() << "Parse relations ...";
584 osmium::io::Reader reader(input_file, pool, osmium::osm_entity_bits::relation, read_meta);
585 tbb::parallel_pipeline(
586 num_threads, buffer_reader(reader) & buffer_relation_cache & buffer_storage_relation);
587 }
588
589 { // Nodes and ways reading pipeline
590 util::Log() << "Parse ways and nodes ...";
591 osmium::io::Reader reader(input_file,
592 pool,
593 osmium::osm_entity_bits::node | osmium::osm_entity_bits::way |
594 osmium::osm_entity_bits::relation,
595 read_meta);
596
597 const auto pipeline =
598 scripting_environment.HasLocationDependentData() && config.use_locations_cache
599 ? buffer_reader(reader) & location_cacher & buffer_transformer & buffer_storage
600 : buffer_reader(reader) & buffer_transformer & buffer_storage;
601 tbb::parallel_pipeline(num_threads, pipeline);
602 }
603
604 TIMER_STOP(parsing);
605 util::Log() << "Parsing finished after " << TIMER_SEC(parsing) << " seconds";
606
607 util::Log() << "Raw input contains " << number_of_nodes << " nodes, " << number_of_ways
608 << " ways, and " << number_of_relations << " relations, " << number_of_restrictions
609 << " restrictions";
610
611 extractor_callbacks.reset();
612
613 if (extraction_containers.all_edges_list.empty())
614 {
615 throw util::exception(std::string("There are no edges remaining after parsing.") +
616 SOURCE_REF);
617 }
618
619 extraction_containers.PrepareData(scripting_environment,
620 config.GetPath(".osrm").string(),
621 config.GetPath(".osrm.names").string());
622
623 auto profile_properties = scripting_environment.GetProfileProperties();
624 SetClassNames(scripting_environment.GetClassNames(), classes_map, profile_properties);
625 auto excludable_classes = scripting_environment.GetExcludableClasses();
626 SetExcludableClasses(classes_map, excludable_classes, profile_properties);
627 files::writeProfileProperties(config.GetPath(".osrm.properties").string(), profile_properties);
628
629 TIMER_STOP(extracting);
630 util::Log() << "extraction finished after " << TIMER_SEC(extracting) << "s";
631
632 return std::make_tuple(std::move(turn_lane_map),
633 std::move(extraction_containers.turn_restrictions),
634 std::move(extraction_containers.internal_maneuver_overrides));
635 }
636
FindComponents(unsigned number_of_edge_based_nodes,const util::DeallocatingVector<EdgeBasedEdge> & input_edge_list,const std::vector<EdgeBasedNodeSegment> & input_node_segments,EdgeBasedNodeDataContainer & nodes_container) const637 void Extractor::FindComponents(unsigned number_of_edge_based_nodes,
638 const util::DeallocatingVector<EdgeBasedEdge> &input_edge_list,
639 const std::vector<EdgeBasedNodeSegment> &input_node_segments,
640 EdgeBasedNodeDataContainer &nodes_container) const
641 {
642 using InputEdge = util::static_graph_details::SortableEdgeWithData<void>;
643 using UncontractedGraph = util::StaticGraph<void>;
644 std::vector<InputEdge> edges;
645 edges.reserve(input_edge_list.size() * 2);
646
647 for (const auto &edge : input_edge_list)
648 {
649 BOOST_ASSERT_MSG(static_cast<unsigned int>(std::max(edge.data.weight, 1)) > 0,
650 "edge distance < 1");
651 BOOST_ASSERT(edge.source < number_of_edge_based_nodes);
652 BOOST_ASSERT(edge.target < number_of_edge_based_nodes);
653 if (edge.data.forward)
654 {
655 edges.push_back({edge.source, edge.target});
656 }
657
658 if (edge.data.backward)
659 {
660 edges.push_back({edge.target, edge.source});
661 }
662 }
663
664 // Connect forward and backward nodes of each edge to enforce
665 // forward and backward edge-based nodes be in one strongly-connected component
666 for (const auto &segment : input_node_segments)
667 {
668 if (segment.reverse_segment_id.enabled)
669 {
670 BOOST_ASSERT(segment.forward_segment_id.id < number_of_edge_based_nodes);
671 BOOST_ASSERT(segment.reverse_segment_id.id < number_of_edge_based_nodes);
672 edges.push_back({segment.forward_segment_id.id, segment.reverse_segment_id.id});
673 edges.push_back({segment.reverse_segment_id.id, segment.forward_segment_id.id});
674 }
675 }
676
677 tbb::parallel_sort(edges.begin(), edges.end());
678 edges.erase(std::unique(edges.begin(), edges.end()), edges.end());
679
680 auto uncontracted_graph = UncontractedGraph(number_of_edge_based_nodes, edges);
681
682 TarjanSCC<UncontractedGraph> component_search(uncontracted_graph);
683 component_search.Run();
684
685 for (NodeID node_id = 0; node_id < number_of_edge_based_nodes; ++node_id)
686 {
687 const auto forward_component = component_search.GetComponentID(node_id);
688 const auto component_size = component_search.GetComponentSize(forward_component);
689 const auto is_tiny = component_size < config.small_component_size;
690 BOOST_ASSERT(node_id < nodes_container.NumberOfNodes());
691 nodes_container.nodes[node_id].component_id = {1 + forward_component, is_tiny};
692 }
693 }
694
695 /**
696 \brief Building an edge-expanded graph from node-based input and turn restrictions
697 */
698
BuildEdgeExpandedGraph(const util::NodeBasedDynamicGraph & node_based_graph,const std::vector<util::Coordinate> & coordinates,const CompressedEdgeContainer & compressed_edge_container,const std::unordered_set<NodeID> & barrier_nodes,const std::unordered_set<NodeID> & traffic_signals,const RestrictionGraph & restriction_graph,const std::unordered_set<EdgeID> & segregated_edges,const NameTable & name_table,const std::vector<UnresolvedManeuverOverride> & maneuver_overrides,const LaneDescriptionMap & turn_lane_map,ScriptingEnvironment & scripting_environment,EdgeBasedNodeDataContainer & edge_based_nodes_container,std::vector<EdgeBasedNodeSegment> & edge_based_node_segments,std::vector<EdgeWeight> & edge_based_node_weights,std::vector<EdgeDuration> & edge_based_node_durations,std::vector<EdgeDistance> & edge_based_node_distances,util::DeallocatingVector<EdgeBasedEdge> & edge_based_edge_list,std::uint32_t & connectivity_checksum)699 EdgeID Extractor::BuildEdgeExpandedGraph(
700 // input data
701 const util::NodeBasedDynamicGraph &node_based_graph,
702 const std::vector<util::Coordinate> &coordinates,
703 const CompressedEdgeContainer &compressed_edge_container,
704 const std::unordered_set<NodeID> &barrier_nodes,
705 const std::unordered_set<NodeID> &traffic_signals,
706 const RestrictionGraph &restriction_graph,
707 const std::unordered_set<EdgeID> &segregated_edges,
708 const NameTable &name_table,
709 const std::vector<UnresolvedManeuverOverride> &maneuver_overrides,
710 const LaneDescriptionMap &turn_lane_map,
711 // for calculating turn penalties
712 ScriptingEnvironment &scripting_environment,
713 // output data
714 EdgeBasedNodeDataContainer &edge_based_nodes_container,
715 std::vector<EdgeBasedNodeSegment> &edge_based_node_segments,
716 std::vector<EdgeWeight> &edge_based_node_weights,
717 std::vector<EdgeDuration> &edge_based_node_durations,
718 std::vector<EdgeDistance> &edge_based_node_distances,
719 util::DeallocatingVector<EdgeBasedEdge> &edge_based_edge_list,
720 std::uint32_t &connectivity_checksum)
721 {
722 EdgeBasedGraphFactory edge_based_graph_factory(node_based_graph,
723 edge_based_nodes_container,
724 compressed_edge_container,
725 barrier_nodes,
726 traffic_signals,
727 coordinates,
728 name_table,
729 segregated_edges,
730 turn_lane_map);
731
732 const auto create_edge_based_edges = [&]() {
733 // scoped to release intermediate data structures right after the call
734 RestrictionMap unconditional_node_restriction_map(restriction_graph);
735 ConditionalRestrictionMap conditional_node_restriction_map(restriction_graph);
736 WayRestrictionMap via_way_restriction_map(restriction_graph);
737 edge_based_graph_factory.Run(scripting_environment,
738 config.GetPath(".osrm.turn_weight_penalties").string(),
739 config.GetPath(".osrm.turn_duration_penalties").string(),
740 config.GetPath(".osrm.turn_penalties_index").string(),
741 config.GetPath(".osrm.cnbg_to_ebg").string(),
742 config.GetPath(".osrm.restrictions").string(),
743 config.GetPath(".osrm.maneuver_overrides").string(),
744 unconditional_node_restriction_map,
745 conditional_node_restriction_map,
746 via_way_restriction_map,
747 maneuver_overrides);
748 return edge_based_graph_factory.GetNumberOfEdgeBasedNodes();
749 };
750
751 const auto number_of_edge_based_nodes = create_edge_based_edges();
752
753 edge_based_graph_factory.GetEdgeBasedEdges(edge_based_edge_list);
754 edge_based_graph_factory.GetEdgeBasedNodeSegments(edge_based_node_segments);
755 edge_based_graph_factory.GetEdgeBasedNodeWeights(edge_based_node_weights);
756 edge_based_graph_factory.GetEdgeBasedNodeDurations(edge_based_node_durations);
757 edge_based_graph_factory.GetEdgeBasedNodeDistances(edge_based_node_distances);
758 connectivity_checksum = edge_based_graph_factory.GetConnectivityChecksum();
759
760 return number_of_edge_based_nodes;
761 }
762
763 /**
764 \brief Building rtree-based nearest-neighbor data structure
765
766 Saves tree into '.ramIndex' and leaves into '.fileIndex'.
767 */
BuildRTree(std::vector<EdgeBasedNodeSegment> edge_based_node_segments,const std::vector<util::Coordinate> & coordinates)768 void Extractor::BuildRTree(std::vector<EdgeBasedNodeSegment> edge_based_node_segments,
769 const std::vector<util::Coordinate> &coordinates)
770 {
771 util::Log() << "Constructing r-tree of " << edge_based_node_segments.size()
772 << " segments build on-top of " << coordinates.size() << " coordinates";
773
774 // Filter node based edges based on startpoint
775 auto start_point_count = std::accumulate(edge_based_node_segments.begin(),
776 edge_based_node_segments.end(),
777 0,
778 [](const size_t so_far, const auto &segment) {
779 return so_far + (segment.is_startpoint ? 1 : 0);
780 });
781 if (start_point_count == 0)
782 {
783 throw util::exception("There are no snappable edges left after processing. Are you "
784 "setting travel modes correctly in the profile? Cannot continue." +
785 SOURCE_REF);
786 }
787
788 TIMER_START(construction);
789 util::StaticRTree<EdgeBasedNodeSegment> rtree(
790 edge_based_node_segments, coordinates, config.GetPath(".osrm.fileIndex"));
791
792 files::writeRamIndex(config.GetPath(".osrm.ramIndex"), rtree);
793
794 TIMER_STOP(construction);
795 util::Log() << "finished r-tree construction in " << TIMER_SEC(construction) << " seconds";
796 }
797
convertIDMapToVector(const Map & map)798 template <typename Map> auto convertIDMapToVector(const Map &map)
799 {
800 std::vector<typename Map::key_type> result(map.size());
801 for (const auto &pair : map)
802 {
803 BOOST_ASSERT(pair.second < map.size());
804 result[pair.second] = pair.first;
805 }
806 return result;
807 }
808
ProcessGuidanceTurns(const util::NodeBasedDynamicGraph & node_based_graph,const extractor::EdgeBasedNodeDataContainer & edge_based_node_container,const std::vector<util::Coordinate> & node_coordinates,const CompressedEdgeContainer & compressed_edge_container,const std::unordered_set<NodeID> & barrier_nodes,const RestrictionGraph & restriction_graph,const NameTable & name_table,LaneDescriptionMap lane_description_map,ScriptingEnvironment & scripting_environment)809 void Extractor::ProcessGuidanceTurns(
810 const util::NodeBasedDynamicGraph &node_based_graph,
811 const extractor::EdgeBasedNodeDataContainer &edge_based_node_container,
812 const std::vector<util::Coordinate> &node_coordinates,
813 const CompressedEdgeContainer &compressed_edge_container,
814 const std::unordered_set<NodeID> &barrier_nodes,
815 const RestrictionGraph &restriction_graph,
816 const NameTable &name_table,
817 LaneDescriptionMap lane_description_map,
818 ScriptingEnvironment &scripting_environment)
819 {
820 // Output data
821 osrm::guidance::TurnDataExternalContainer turn_data_container;
822 util::guidance::LaneDataIdMap lane_data_map;
823 osrm::guidance::BearingClassesVector bearing_class_by_node_based_node;
824 osrm::guidance::BearingClassesMap bearing_class_hash;
825 osrm::guidance::EntryClassesMap entry_class_hash;
826 std::uint32_t connectivity_checksum = 0;
827
828 TIMER_START(turn_annotations);
829
830 {
831 SuffixTable street_name_suffix_table(scripting_environment);
832 const auto &turn_lanes_data = transformTurnLaneMapIntoArrays(lane_description_map);
833
834 RestrictionMap unconditional_node_restriction_map(restriction_graph);
835 WayRestrictionMap way_restriction_map(restriction_graph);
836
837 osrm::guidance::annotateTurns(node_based_graph,
838 edge_based_node_container,
839 node_coordinates,
840 compressed_edge_container,
841 barrier_nodes,
842 unconditional_node_restriction_map,
843 way_restriction_map,
844 name_table,
845 street_name_suffix_table,
846 turn_lanes_data,
847 lane_description_map,
848 lane_data_map,
849 turn_data_container,
850 bearing_class_by_node_based_node,
851 bearing_class_hash,
852 entry_class_hash,
853 connectivity_checksum);
854 }
855
856 TIMER_STOP(turn_annotations);
857 util::Log() << "Guidance turn annotations took " << TIMER_SEC(turn_annotations) << "s";
858
859 util::Log() << "Writing Intersection Classification Data";
860 TIMER_START(write_intersections);
861 files::writeIntersections(
862 config.GetPath(".osrm.icd").string(),
863 IntersectionBearingsContainer{bearing_class_by_node_based_node,
864 convertIDMapToVector(bearing_class_hash.data)},
865 convertIDMapToVector(entry_class_hash.data));
866 TIMER_STOP(write_intersections);
867 util::Log() << "ok, after " << TIMER_SEC(write_intersections) << "s";
868
869 util::Log() << "Writing Turns and Lane Data...";
870 TIMER_START(write_guidance_data);
871
872 {
873 auto turn_lane_data = convertIDMapToVector(lane_data_map.data);
874 files::writeTurnLaneData(config.GetPath(".osrm.tld"), turn_lane_data);
875 }
876
877 { // Turn lanes handler modifies lane_description_map, so another transformation is needed
878 std::vector<std::uint32_t> turn_lane_offsets;
879 std::vector<TurnLaneType::Mask> turn_lane_masks;
880 std::tie(turn_lane_offsets, turn_lane_masks) =
881 transformTurnLaneMapIntoArrays(lane_description_map);
882 files::writeTurnLaneDescriptions(
883 config.GetPath(".osrm.tls"), turn_lane_offsets, turn_lane_masks);
884 }
885
886 osrm::guidance::files::writeTurnData(
887 config.GetPath(".osrm.edges").string(), turn_data_container, connectivity_checksum);
888 TIMER_STOP(write_guidance_data);
889 util::Log() << "ok, after " << TIMER_SEC(write_guidance_data) << "s";
890 }
891
892 } // namespace extractor
893 } // namespace osrm
894