1 #include "extractor/node_based_graph_factory.hpp"
2 #include "extractor/files.hpp"
3 #include "extractor/graph_compressor.hpp"
4 #include "storage/io.hpp"
5
6 #include "util/log.hpp"
7 #include "util/timing_util.hpp"
8
9 #include <boost/assert.hpp>
10
11 #include <set>
12
13 namespace osrm
14 {
15 namespace extractor
16 {
17
NodeBasedGraphFactory(const boost::filesystem::path & input_file,ScriptingEnvironment & scripting_environment,std::vector<TurnRestriction> & turn_restrictions,std::vector<UnresolvedManeuverOverride> & maneuver_overrides)18 NodeBasedGraphFactory::NodeBasedGraphFactory(
19 const boost::filesystem::path &input_file,
20 ScriptingEnvironment &scripting_environment,
21 std::vector<TurnRestriction> &turn_restrictions,
22 std::vector<UnresolvedManeuverOverride> &maneuver_overrides)
23 {
24 LoadDataFromFile(input_file);
25 Compress(scripting_environment, turn_restrictions, maneuver_overrides);
26 CompressGeometry();
27 CompressAnnotationData();
28 }
29
30 // load the data serialised during the extraction run
LoadDataFromFile(const boost::filesystem::path & input_file)31 void NodeBasedGraphFactory::LoadDataFromFile(const boost::filesystem::path &input_file)
32 {
33 auto barriers_iter = inserter(barriers, end(barriers));
34 auto traffic_signals_iter = inserter(traffic_signals, end(traffic_signals));
35 std::vector<NodeBasedEdge> edge_list;
36
37 files::readRawNBGraph(input_file,
38 barriers_iter,
39 traffic_signals_iter,
40 coordinates,
41 osm_node_ids,
42 edge_list,
43 annotation_data);
44
45 const auto number_of_node_based_nodes = coordinates.size();
46 if (edge_list.empty())
47 {
48 throw util::exception("Node-based-graph (" + input_file.string() + ") contains no edges." +
49 SOURCE_REF);
50 }
51
52 // at this point, the data isn't compressed, but since we update the graph in-place, we assign
53 // it here.
54 compressed_output_graph =
55 util::NodeBasedDynamicGraphFromEdges(number_of_node_based_nodes, edge_list);
56
57 // check whether the graph is sane
58 BOOST_ASSERT([this]() {
59 for (const auto nbg_node_u : util::irange(0u, compressed_output_graph.GetNumberOfNodes()))
60 {
61 for (EdgeID nbg_edge_id : compressed_output_graph.GetAdjacentEdgeRange(nbg_node_u))
62 {
63 // we cannot have invalid edge-ids in the graph
64 if (nbg_edge_id == SPECIAL_EDGEID)
65 return false;
66
67 const auto nbg_node_v = compressed_output_graph.GetTarget(nbg_edge_id);
68
69 auto reverse = compressed_output_graph.FindEdge(nbg_node_v, nbg_node_u);
70
71 // found an edge that is reversed in both directions, should be two distinct edges
72 if (compressed_output_graph.GetEdgeData(nbg_edge_id).reversed &&
73 compressed_output_graph.GetEdgeData(reverse).reversed)
74 return false;
75 }
76 }
77 return true;
78 }());
79 }
80
Compress(ScriptingEnvironment & scripting_environment,std::vector<TurnRestriction> & turn_restrictions,std::vector<UnresolvedManeuverOverride> & maneuver_overrides)81 void NodeBasedGraphFactory::Compress(ScriptingEnvironment &scripting_environment,
82 std::vector<TurnRestriction> &turn_restrictions,
83 std::vector<UnresolvedManeuverOverride> &maneuver_overrides)
84 {
85 GraphCompressor graph_compressor;
86 graph_compressor.Compress(barriers,
87 traffic_signals,
88 scripting_environment,
89 turn_restrictions,
90 maneuver_overrides,
91 compressed_output_graph,
92 annotation_data,
93 compressed_edge_container);
94 }
95
CompressGeometry()96 void NodeBasedGraphFactory::CompressGeometry()
97 {
98 for (const auto nbg_node_u : util::irange(0u, compressed_output_graph.GetNumberOfNodes()))
99 {
100 for (EdgeID nbg_edge_id : compressed_output_graph.GetAdjacentEdgeRange(nbg_node_u))
101 {
102 BOOST_ASSERT(nbg_edge_id != SPECIAL_EDGEID);
103
104 const auto &nbg_edge_data = compressed_output_graph.GetEdgeData(nbg_edge_id);
105 const auto nbg_node_v = compressed_output_graph.GetTarget(nbg_edge_id);
106 BOOST_ASSERT(nbg_node_v != SPECIAL_NODEID);
107 BOOST_ASSERT(nbg_node_u != nbg_node_v);
108
109 // pick only every other edge, since we have every edge as an outgoing
110 // and incoming egde
111 if (nbg_node_u >= nbg_node_v)
112 {
113 continue;
114 }
115
116 auto from = nbg_node_u, to = nbg_node_v;
117 // if we found a non-forward edge reverse and try again
118 if (nbg_edge_data.reversed)
119 std::swap(from, to);
120
121 // find forward edge id and
122 const EdgeID edge_id_1 = compressed_output_graph.FindEdge(from, to);
123 BOOST_ASSERT(edge_id_1 != SPECIAL_EDGEID);
124
125 // find reverse edge id and
126 const EdgeID edge_id_2 = compressed_output_graph.FindEdge(to, from);
127 BOOST_ASSERT(edge_id_2 != SPECIAL_EDGEID);
128
129 auto packed_geometry_id = compressed_edge_container.ZipEdges(edge_id_1, edge_id_2);
130
131 // remember the geometry ID for both edges in the node-based graph
132 compressed_output_graph.GetEdgeData(edge_id_1).geometry_id = {packed_geometry_id, true};
133 compressed_output_graph.GetEdgeData(edge_id_2).geometry_id = {packed_geometry_id,
134 false};
135 }
136 }
137 }
138
CompressAnnotationData()139 void NodeBasedGraphFactory::CompressAnnotationData()
140 {
141 TIMER_START(compress_annotation);
142 /** Main idea, that we need to remove duplicated and unreferenced data
143 * For that:
144 * 1. We create set, that contains indecies of unique data items. Just create
145 * comparator, that compare data from annotation_data vector by passed index.
146 * 2. Create cached id's unordered_map, where key - stored id in set,
147 * value - index of item in a set from begin. We need that map, because
148 * std::distance(set.begin(), it) is too slow O(N). So any words in that step we reorder
149 * annotation data to the order it stored in a set. Apply new id's to edge data.
150 * 3. Remove unused anootation_data items.
151 * 4. At final step just need to sort result annotation_data in the same order as set.
152 * That makes id's stored in edge data valid.
153 */
154 struct IndexComparator
155 {
156 IndexComparator(const std::vector<NodeBasedEdgeAnnotation> &annotation_data_)
157 : annotation_data(annotation_data_)
158 {
159 }
160
161 bool operator()(AnnotationID a, AnnotationID b) const
162 {
163 return annotation_data[a] < annotation_data[b];
164 }
165
166 private:
167 const std::vector<NodeBasedEdgeAnnotation> &annotation_data;
168 };
169
170 /** 1 */
171 IndexComparator comparator(annotation_data);
172 std::set<AnnotationID, IndexComparator> unique_annotations(comparator);
173
174 // first we mark entries, by setting their mapping to 0
175 for (const auto nbg_node_u : util::irange(0u, compressed_output_graph.GetNumberOfNodes()))
176 {
177 BOOST_ASSERT(nbg_node_u != SPECIAL_NODEID);
178 for (EdgeID nbg_edge_id : compressed_output_graph.GetAdjacentEdgeRange(nbg_node_u))
179 {
180 auto const &edge = compressed_output_graph.GetEdgeData(nbg_edge_id);
181 unique_annotations.insert(edge.annotation_data);
182 }
183 }
184
185 // make additional map, because std::distance of std::set seems is O(N)
186 // that very slow
187 /** 2 */
188 AnnotationID new_id = 0;
189 std::unordered_map<AnnotationID, AnnotationID> cached_ids;
190 for (auto id : unique_annotations)
191 cached_ids[id] = new_id++;
192
193 // apply the mapping
194 for (const auto nbg_node_u : util::irange(0u, compressed_output_graph.GetNumberOfNodes()))
195 {
196 BOOST_ASSERT(nbg_node_u != SPECIAL_NODEID);
197 for (EdgeID nbg_edge_id : compressed_output_graph.GetAdjacentEdgeRange(nbg_node_u))
198 {
199 auto &edge = compressed_output_graph.GetEdgeData(nbg_edge_id);
200 auto const it = unique_annotations.find(edge.annotation_data);
201 BOOST_ASSERT(it != unique_annotations.end());
202 auto const it2 = cached_ids.find(*it);
203 BOOST_ASSERT(it2 != cached_ids.end());
204
205 edge.annotation_data = it2->second;
206 }
207 }
208
209 /** 3 */
210 // mark unused references for remove
211 for (AnnotationID id = 0; id < annotation_data.size(); ++id)
212 {
213 auto const it = unique_annotations.find(id);
214 if (it == unique_annotations.end() || *it != id)
215 annotation_data[id].name_id = INVALID_NAMEID;
216 }
217
218 // remove unreferenced entries, shifting other entries to the front
219 const auto new_end =
220 std::remove_if(annotation_data.begin(), annotation_data.end(), [&](auto const &data) {
221 // both elements are considered equal (to remove the second
222 // one) if the annotation mapping of the second one is
223 // invalid
224 return data.name_id == INVALID_NAMEID;
225 });
226
227 const auto old_size = annotation_data.size();
228 // remove all remaining elements
229 annotation_data.erase(new_end, annotation_data.end());
230
231 // reorder data in the same order
232 /** 4 */
233 std::sort(annotation_data.begin(), annotation_data.end());
234
235 TIMER_STOP(compress_annotation);
236 util::Log() << " graph compression removed " << (old_size - annotation_data.size())
237 << " annotations of " << old_size << " in " << TIMER_SEC(compress_annotation)
238 << " seconds";
239 }
240
ReleaseOsmNodes()241 void NodeBasedGraphFactory::ReleaseOsmNodes()
242 {
243 // replace with a new vector to release old memory
244 extractor::PackedOSMIDs().swap(osm_node_ids);
245 }
246
247 } // namespace extractor
248 } // namespace osrm
249