1 #ifndef OSRM_EXTRACTOR_NODE_BASED_GRAPH_FACTORY_HPP_ 2 #define OSRM_EXTRACTOR_NODE_BASED_GRAPH_FACTORY_HPP_ 3 4 #include "extractor/compressed_edge_container.hpp" 5 #include "extractor/maneuver_override.hpp" 6 #include "extractor/node_based_edge.hpp" 7 #include "extractor/node_data_container.hpp" 8 #include "extractor/packed_osm_ids.hpp" 9 #include "extractor/scripting_environment.hpp" 10 11 #include "util/coordinate.hpp" 12 #include "util/node_based_graph.hpp" 13 14 #include <boost/filesystem/path.hpp> 15 16 #include <memory> 17 #include <string> 18 #include <unordered_set> 19 #include <vector> 20 21 namespace osrm 22 { 23 namespace extractor 24 { 25 26 // Turn the output of the extraction process into a graph that represents junctions as nodes and 27 // ways as edges between these nodes. The graph forms the further input for OSRMs creation of the 28 // edge-based graph and is also the basic concept for annotating paths. All information from ways 29 // that is transferred into the API response is connected to the edges of the node-based graph. 30 // 31 // The input to the graph creation is the set of edges, traffic signals, barriers, meta-data,... 32 // which is generated during extraction and stored within the extraction containers. 33 class NodeBasedGraphFactory 34 { 35 public: 36 // The node-based graph factory loads the *.osrm file and transforms the data within into the 37 // node-based graph to represent the OSM network. This includes geometry compression, annotation 38 // data optimisation and many other aspects. After this step, the edge-based graph factory can 39 // turn the graph into the routing graph to be used with the navigation algorithms. 40 NodeBasedGraphFactory(const boost::filesystem::path &input_file, 41 ScriptingEnvironment &scripting_environment, 42 std::vector<TurnRestriction> &turn_restrictions, 43 std::vector<UnresolvedManeuverOverride> &maneuver_overrides); 44 GetGraph() const45 auto const &GetGraph() const { return compressed_output_graph; } GetBarriers() const46 auto const &GetBarriers() const { return barriers; } GetTrafficSignals() const47 auto const &GetTrafficSignals() const { return traffic_signals; } GetCompressedEdges() const48 auto const &GetCompressedEdges() const { return compressed_edge_container; } GetCoordinates() const49 auto const &GetCoordinates() const { return coordinates; } GetAnnotationData() const50 auto const &GetAnnotationData() const { return annotation_data; } GetOsmNodes() const51 auto const &GetOsmNodes() const { return osm_node_ids; } GetCompressedEdges()52 auto &GetCompressedEdges() { return compressed_edge_container; } GetCoordinates()53 auto &GetCoordinates() { return coordinates; } GetAnnotationData()54 auto &GetAnnotationData() { return annotation_data; } GetOsmNodes()55 auto &GetOsmNodes() { return osm_node_ids; } 56 57 // to reduce the memory footprint, the node-based graph factory allows releasing memory after it 58 // might have been used for the last time: 59 void ReleaseOsmNodes(); 60 61 private: 62 // Get the information from the *.osrm file (direct product of the extractor callback/extraction 63 // containers) and prepare the graph creation process 64 void LoadDataFromFile(const boost::filesystem::path &input_file); 65 66 // Compress the node-based graph into a compact representation of itself. This removes storing a 67 // single edge for every part of the geometry and might also combine meta-data for multiple 68 // edges into a single representative form 69 void Compress(ScriptingEnvironment &scripting_environment, 70 std::vector<TurnRestriction> &turn_restrictions, 71 std::vector<UnresolvedManeuverOverride> &maneuver_overrides); 72 73 // Most ways are bidirectional, making the geometry in forward and backward direction the same, 74 // except for reversal. We make use of this fact by keeping only one representation of the 75 // geometry around 76 void CompressGeometry(); 77 78 // After graph compression, some of the annotation entries might not be referenced anymore. We 79 // compress the annotation data by relabeling the node-based graph references and removing all 80 // unreferenced entries 81 void CompressAnnotationData(); 82 83 // After produce, this will contain a compressed version of the node-based graph 84 util::NodeBasedDynamicGraph compressed_output_graph; 85 // To store the meta-data for the graph that is purely annotative / not used for the navigation 86 // itself. Since the edges of a node-based graph form the nodes of the edge based graphs, we 87 // transform this data into the EdgeBasedNodeDataContainer as output storage. 88 std::vector<NodeBasedEdgeAnnotation> annotation_data; 89 90 // General Information about the graph, not used outside of extractor 91 std::unordered_set<NodeID> barriers; 92 std::unordered_set<NodeID> traffic_signals; 93 94 std::vector<util::Coordinate> coordinates; 95 96 // data to keep in sync with the node-based graph 97 extractor::PackedOSMIDs osm_node_ids; 98 99 // for the compressed geometry 100 extractor::CompressedEdgeContainer compressed_edge_container; 101 }; 102 103 } // namespace extractor 104 } // namespace osrm 105 106 #endif // OSRM_EXTRACTOR_NODE_BASED_GRAPH_FACTORY_HPP_ 107