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