1 #include "extractor/compressed_edge_container.hpp"
2 #include "util/log.hpp"
3
4 #include <boost/assert.hpp>
5 #include <boost/filesystem.hpp>
6 #include <boost/filesystem/fstream.hpp>
7 #include <boost/numeric/conversion/cast.hpp>
8
9 #include <limits>
10 #include <string>
11
12 #include <iostream>
13
14 namespace osrm
15 {
16 namespace extractor
17 {
18
CompressedEdgeContainer()19 CompressedEdgeContainer::CompressedEdgeContainer()
20 {
21 m_free_list.reserve(100);
22 IncreaseFreeList();
23 }
24
IncreaseFreeList()25 void CompressedEdgeContainer::IncreaseFreeList()
26 {
27 m_compressed_oneway_geometries.resize(m_compressed_oneway_geometries.size() + 100);
28 for (unsigned i = 100; i > 0; --i)
29 {
30 m_free_list.emplace_back(free_list_maximum);
31 ++free_list_maximum;
32 }
33 }
34
HasEntryForID(const EdgeID edge_id) const35 bool CompressedEdgeContainer::HasEntryForID(const EdgeID edge_id) const
36 {
37 auto iter = m_edge_id_to_list_index_map.find(edge_id);
38 return iter != m_edge_id_to_list_index_map.end();
39 }
40
HasZippedEntryForForwardID(const EdgeID edge_id) const41 bool CompressedEdgeContainer::HasZippedEntryForForwardID(const EdgeID edge_id) const
42 {
43 auto iter = m_forward_edge_id_to_zipped_index_map.find(edge_id);
44 return iter != m_forward_edge_id_to_zipped_index_map.end();
45 }
46
HasZippedEntryForReverseID(const EdgeID edge_id) const47 bool CompressedEdgeContainer::HasZippedEntryForReverseID(const EdgeID edge_id) const
48 {
49 auto iter = m_reverse_edge_id_to_zipped_index_map.find(edge_id);
50 return iter != m_reverse_edge_id_to_zipped_index_map.end();
51 }
52
GetPositionForID(const EdgeID edge_id) const53 unsigned CompressedEdgeContainer::GetPositionForID(const EdgeID edge_id) const
54 {
55 auto map_iterator = m_edge_id_to_list_index_map.find(edge_id);
56 BOOST_ASSERT(map_iterator != m_edge_id_to_list_index_map.end());
57 BOOST_ASSERT(map_iterator->second < m_compressed_oneway_geometries.size());
58 return map_iterator->second;
59 }
60
GetZippedPositionForForwardID(const EdgeID edge_id) const61 unsigned CompressedEdgeContainer::GetZippedPositionForForwardID(const EdgeID edge_id) const
62 {
63 auto map_iterator = m_forward_edge_id_to_zipped_index_map.find(edge_id);
64 BOOST_ASSERT(map_iterator != m_forward_edge_id_to_zipped_index_map.end());
65 BOOST_ASSERT(map_iterator->second < segment_data->nodes.size());
66 return map_iterator->second;
67 }
68
GetZippedPositionForReverseID(const EdgeID edge_id) const69 unsigned CompressedEdgeContainer::GetZippedPositionForReverseID(const EdgeID edge_id) const
70 {
71 auto map_iterator = m_reverse_edge_id_to_zipped_index_map.find(edge_id);
72 BOOST_ASSERT(map_iterator != m_reverse_edge_id_to_zipped_index_map.end());
73 BOOST_ASSERT(map_iterator->second < segment_data->nodes.size());
74 return map_iterator->second;
75 }
76
ClipWeight(const SegmentWeight weight)77 SegmentWeight CompressedEdgeContainer::ClipWeight(const SegmentWeight weight)
78 {
79 if (weight >= INVALID_SEGMENT_WEIGHT)
80 {
81 clipped_weights++;
82 return MAX_SEGMENT_WEIGHT;
83 }
84 return weight;
85 }
86
ClipDuration(const SegmentDuration duration)87 SegmentDuration CompressedEdgeContainer::ClipDuration(const SegmentDuration duration)
88 {
89 if (duration >= INVALID_SEGMENT_DURATION)
90 {
91 clipped_weights++;
92 return MAX_SEGMENT_DURATION;
93 }
94 return duration;
95 }
96
97 // Adds info for a compressed edge to the container. edge_id_2
98 // has been removed from the graph, so we have to save These edges/nodes
99 // have already been trimmed from the graph, this function just stores
100 // the original data for unpacking later.
101 //
102 // edge_id_1 edge_id_2
103 // ----------> via_node_id -----------> target_node_id
104 // weight_1 weight_2
105 // duration_1 duration_2
CompressEdge(const EdgeID edge_id_1,const EdgeID edge_id_2,const NodeID via_node_id,const NodeID target_node_id,const EdgeWeight weight1,const EdgeWeight weight2,const EdgeDuration duration1,const EdgeDuration duration2,const EdgeWeight node_weight_penalty,const EdgeDuration node_duration_penalty)106 void CompressedEdgeContainer::CompressEdge(const EdgeID edge_id_1,
107 const EdgeID edge_id_2,
108 const NodeID via_node_id,
109 const NodeID target_node_id,
110 const EdgeWeight weight1,
111 const EdgeWeight weight2,
112 const EdgeDuration duration1,
113 const EdgeDuration duration2,
114 const EdgeWeight node_weight_penalty,
115 const EdgeDuration node_duration_penalty)
116 {
117 // remove super-trivial geometries
118 BOOST_ASSERT(SPECIAL_EDGEID != edge_id_1);
119 BOOST_ASSERT(SPECIAL_EDGEID != edge_id_2);
120 BOOST_ASSERT(SPECIAL_NODEID != via_node_id);
121 BOOST_ASSERT(SPECIAL_NODEID != target_node_id);
122 BOOST_ASSERT(INVALID_SEGMENT_WEIGHT != weight1);
123 BOOST_ASSERT(INVALID_SEGMENT_WEIGHT != weight2);
124
125 // append list of removed edge_id plus via node to surviving edge id:
126 // <surv_1, .. , surv_n, via_node_id, rem_1, .. rem_n
127 //
128 // General scheme:
129 // 1. append via node id to list of edge_id_1
130 // 2. find list for edge_id_2, if yes add all elements and delete it
131
132 // Add via node id. List is created if it does not exist
133 if (!HasEntryForID(edge_id_1))
134 {
135 // create a new entry in the map
136 if (0 == m_free_list.size())
137 {
138 // make sure there is a place to put the entries
139 IncreaseFreeList();
140 }
141 BOOST_ASSERT(!m_free_list.empty());
142 m_edge_id_to_list_index_map[edge_id_1] = m_free_list.back();
143 m_free_list.pop_back();
144 }
145
146 // find bucket index
147 const auto iter = m_edge_id_to_list_index_map.find(edge_id_1);
148 BOOST_ASSERT(iter != m_edge_id_to_list_index_map.end());
149 const unsigned edge_bucket_id1 = iter->second;
150 BOOST_ASSERT(edge_bucket_id1 == GetPositionForID(edge_id_1));
151 BOOST_ASSERT(edge_bucket_id1 < m_compressed_oneway_geometries.size());
152
153 std::vector<OnewayCompressedEdge> &edge_bucket_list1 =
154 m_compressed_oneway_geometries[edge_bucket_id1];
155
156 bool was_empty = edge_bucket_list1.empty();
157
158 // note we don't save the start coordinate: it is implicitly given by edge 1
159 // weight1 is the distance to the (currently) last coordinate in the bucket
160 if (was_empty)
161 {
162 edge_bucket_list1.emplace_back(
163 OnewayCompressedEdge{via_node_id, ClipWeight(weight1), ClipDuration(duration1)});
164 }
165
166 BOOST_ASSERT(0 < edge_bucket_list1.size());
167 BOOST_ASSERT(!edge_bucket_list1.empty());
168
169 // if the via-node offers a penalty, we add the weight of the penalty as an artificial
170 // segment that references SPECIAL_NODEID
171 if (node_weight_penalty != INVALID_EDGE_WEIGHT &&
172 node_duration_penalty != MAXIMAL_EDGE_DURATION)
173 {
174 edge_bucket_list1.emplace_back(OnewayCompressedEdge{
175 via_node_id, ClipWeight(node_weight_penalty), ClipDuration(node_duration_penalty)});
176 }
177
178 if (HasEntryForID(edge_id_2))
179 {
180 // second edge is not atomic anymore
181 const unsigned list_to_remove_index = GetPositionForID(edge_id_2);
182 BOOST_ASSERT(list_to_remove_index < m_compressed_oneway_geometries.size());
183
184 std::vector<OnewayCompressedEdge> &edge_bucket_list2 =
185 m_compressed_oneway_geometries[list_to_remove_index];
186
187 // found an existing list, append it to the list of edge_id_1
188 edge_bucket_list1.insert(
189 edge_bucket_list1.end(), edge_bucket_list2.begin(), edge_bucket_list2.end());
190
191 // remove the list of edge_id_2
192 m_edge_id_to_list_index_map.erase(edge_id_2);
193 BOOST_ASSERT(m_edge_id_to_list_index_map.end() ==
194 m_edge_id_to_list_index_map.find(edge_id_2));
195 edge_bucket_list2.clear();
196 BOOST_ASSERT(0 == edge_bucket_list2.size());
197 m_free_list.emplace_back(list_to_remove_index);
198 BOOST_ASSERT(list_to_remove_index == m_free_list.back());
199 }
200 else
201 {
202 // we are certain that the second edge is atomic.
203 edge_bucket_list1.emplace_back(
204 OnewayCompressedEdge{target_node_id, ClipWeight(weight2), ClipDuration(duration2)});
205 }
206 }
207
AddUncompressedEdge(const EdgeID edge_id,const NodeID target_node_id,const SegmentWeight weight,const SegmentDuration duration)208 void CompressedEdgeContainer::AddUncompressedEdge(const EdgeID edge_id,
209 const NodeID target_node_id,
210 const SegmentWeight weight,
211 const SegmentDuration duration)
212 {
213 // remove super-trivial geometries
214 BOOST_ASSERT(SPECIAL_EDGEID != edge_id);
215 BOOST_ASSERT(SPECIAL_NODEID != target_node_id);
216 BOOST_ASSERT(INVALID_EDGE_WEIGHT != weight);
217
218 // Add via node id. List is created if it does not exist
219 if (!HasEntryForID(edge_id))
220 {
221 // create a new entry in the map
222 if (0 == m_free_list.size())
223 {
224 // make sure there is a place to put the entries
225 IncreaseFreeList();
226 }
227 BOOST_ASSERT(!m_free_list.empty());
228 m_edge_id_to_list_index_map[edge_id] = m_free_list.back();
229 m_free_list.pop_back();
230 }
231
232 // find bucket index
233 const auto iter = m_edge_id_to_list_index_map.find(edge_id);
234 BOOST_ASSERT(iter != m_edge_id_to_list_index_map.end());
235 const unsigned edge_bucket_id = iter->second;
236 BOOST_ASSERT(edge_bucket_id == GetPositionForID(edge_id));
237 BOOST_ASSERT(edge_bucket_id < m_compressed_oneway_geometries.size());
238
239 std::vector<OnewayCompressedEdge> &edge_bucket_list =
240 m_compressed_oneway_geometries[edge_bucket_id];
241
242 // note we don't save the start coordinate: it is implicitly given by edge_id
243 // weight is the distance to the (currently) last coordinate in the bucket
244 // Don't re-add this if it's already in there.
245 if (edge_bucket_list.empty())
246 {
247 edge_bucket_list.emplace_back(
248 OnewayCompressedEdge{target_node_id, ClipWeight(weight), ClipDuration(duration)});
249 }
250 }
251
InitializeBothwayVector()252 void CompressedEdgeContainer::InitializeBothwayVector()
253 {
254 segment_data = std::make_unique<SegmentDataContainer>();
255 segment_data->index.reserve(m_compressed_oneway_geometries.size());
256 segment_data->nodes.reserve(m_compressed_oneway_geometries.size());
257 segment_data->fwd_weights.reserve(m_compressed_oneway_geometries.size());
258 segment_data->rev_weights.reserve(m_compressed_oneway_geometries.size());
259 segment_data->fwd_durations.reserve(m_compressed_oneway_geometries.size());
260 segment_data->rev_durations.reserve(m_compressed_oneway_geometries.size());
261 segment_data->fwd_datasources.reserve(m_compressed_oneway_geometries.size());
262 segment_data->rev_datasources.reserve(m_compressed_oneway_geometries.size());
263 }
264
ZipEdges(const EdgeID f_edge_id,const EdgeID r_edge_id)265 unsigned CompressedEdgeContainer::ZipEdges(const EdgeID f_edge_id, const EdgeID r_edge_id)
266 {
267 if (!segment_data)
268 InitializeBothwayVector();
269
270 const auto &forward_bucket = GetBucketReference(f_edge_id);
271 const auto &reverse_bucket = GetBucketReference(r_edge_id);
272
273 BOOST_ASSERT(forward_bucket.size() == reverse_bucket.size());
274
275 const unsigned zipped_geometry_id = segment_data->index.size();
276 m_forward_edge_id_to_zipped_index_map[f_edge_id] = zipped_geometry_id;
277 m_reverse_edge_id_to_zipped_index_map[r_edge_id] = zipped_geometry_id;
278
279 segment_data->index.emplace_back(segment_data->nodes.size());
280
281 const auto &first_node = reverse_bucket.back();
282
283 constexpr DatasourceID LUA_SOURCE = 0;
284
285 segment_data->nodes.emplace_back(first_node.node_id);
286 segment_data->fwd_weights.emplace_back(INVALID_SEGMENT_WEIGHT);
287 segment_data->rev_weights.emplace_back(first_node.weight);
288 segment_data->fwd_durations.emplace_back(INVALID_SEGMENT_DURATION);
289 segment_data->rev_durations.emplace_back(first_node.duration);
290 segment_data->fwd_datasources.emplace_back(LUA_SOURCE);
291 segment_data->rev_datasources.emplace_back(LUA_SOURCE);
292
293 for (std::size_t i = 0; i < forward_bucket.size() - 1; ++i)
294 {
295 const auto &fwd_node = forward_bucket.at(i);
296 const auto &rev_node = reverse_bucket.at(reverse_bucket.size() - 2 - i);
297
298 BOOST_ASSERT(fwd_node.node_id == rev_node.node_id);
299
300 segment_data->nodes.emplace_back(fwd_node.node_id);
301 segment_data->fwd_weights.emplace_back(fwd_node.weight);
302 segment_data->rev_weights.emplace_back(rev_node.weight);
303 segment_data->fwd_durations.emplace_back(fwd_node.duration);
304 segment_data->rev_durations.emplace_back(rev_node.duration);
305 segment_data->fwd_datasources.emplace_back(LUA_SOURCE);
306 segment_data->rev_datasources.emplace_back(LUA_SOURCE);
307 }
308
309 const auto &last_node = forward_bucket.back();
310
311 segment_data->nodes.emplace_back(last_node.node_id);
312 segment_data->fwd_weights.emplace_back(last_node.weight);
313 segment_data->rev_weights.emplace_back(INVALID_SEGMENT_WEIGHT);
314 segment_data->fwd_durations.emplace_back(last_node.duration);
315 segment_data->rev_durations.emplace_back(INVALID_SEGMENT_DURATION);
316 segment_data->fwd_datasources.emplace_back(LUA_SOURCE);
317 segment_data->rev_datasources.emplace_back(LUA_SOURCE);
318
319 return zipped_geometry_id;
320 }
321
PrintStatistics() const322 void CompressedEdgeContainer::PrintStatistics() const
323 {
324 const uint64_t compressed_edges = m_compressed_oneway_geometries.size();
325 BOOST_ASSERT(0 == compressed_edges % 2);
326 BOOST_ASSERT(m_compressed_oneway_geometries.size() + m_free_list.size() > 0);
327
328 uint64_t compressed_geometries = 0;
329 uint64_t longest_chain_length = 0;
330 for (const std::vector<OnewayCompressedEdge> ¤t_vector : m_compressed_oneway_geometries)
331 {
332 compressed_geometries += current_vector.size();
333 longest_chain_length = std::max(longest_chain_length, (uint64_t)current_vector.size());
334 }
335
336 if (clipped_weights > 0)
337 {
338 util::Log(logWARNING) << "Clipped " << clipped_weights << " segment weights to "
339 << (INVALID_SEGMENT_WEIGHT - 1);
340 }
341 if (clipped_durations > 0)
342 {
343 util::Log(logWARNING) << "Clipped " << clipped_durations << " segment durations to "
344 << (INVALID_SEGMENT_DURATION - 1);
345 }
346
347 util::Log() << "Geometry successfully removed:"
348 "\n compressed edges: "
349 << compressed_edges << "\n compressed geometries: " << compressed_geometries
350 << "\n longest chain length: " << longest_chain_length << "\n cmpr ratio: "
351 << ((float)compressed_edges / std::max(compressed_geometries, (uint64_t)1))
352 << "\n avg chain length: "
353 << (float)compressed_geometries / std::max((uint64_t)1, compressed_edges);
354 }
355
356 const CompressedEdgeContainer::OnewayEdgeBucket &
GetBucketReference(const EdgeID edge_id) const357 CompressedEdgeContainer::GetBucketReference(const EdgeID edge_id) const
358 {
359 const unsigned index = m_edge_id_to_list_index_map.at(edge_id);
360 return m_compressed_oneway_geometries.at(index);
361 }
362
363 // Since all edges are technically in the compressed geometry container,
364 // regardless of whether a compressed edge actually contains multiple
365 // original segments, we use 'Trivial' here to describe compressed edges
366 // that only contain one original segment
IsTrivial(const EdgeID edge_id) const367 bool CompressedEdgeContainer::IsTrivial(const EdgeID edge_id) const
368 {
369 const auto &bucket = GetBucketReference(edge_id);
370 return bucket.size() == 1;
371 }
372
GetFirstEdgeTargetID(const EdgeID edge_id) const373 NodeID CompressedEdgeContainer::GetFirstEdgeTargetID(const EdgeID edge_id) const
374 {
375 const auto &bucket = GetBucketReference(edge_id);
376 BOOST_ASSERT(bucket.size() >= 1);
377 return bucket.front().node_id;
378 }
GetLastEdgeTargetID(const EdgeID edge_id) const379 NodeID CompressedEdgeContainer::GetLastEdgeTargetID(const EdgeID edge_id) const
380 {
381 const auto &bucket = GetBucketReference(edge_id);
382 BOOST_ASSERT(bucket.size() >= 1);
383 return bucket.back().node_id;
384 }
GetLastEdgeSourceID(const EdgeID edge_id) const385 NodeID CompressedEdgeContainer::GetLastEdgeSourceID(const EdgeID edge_id) const
386 {
387 const auto &bucket = GetBucketReference(edge_id);
388 BOOST_ASSERT(bucket.size() >= 2);
389 return bucket[bucket.size() - 2].node_id;
390 }
391
ToSegmentData()392 std::unique_ptr<SegmentDataContainer> CompressedEdgeContainer::ToSegmentData()
393 {
394 // Finalize the index
395 segment_data->index.push_back(segment_data->nodes.size());
396
397 return std::move(segment_data);
398 }
399 } // namespace extractor
400 } // namespace osrm
401