1 #include "extractor/graph_compressor.hpp"
2
3 #include "extractor/compressed_edge_container.hpp"
4 #include "extractor/extraction_turn.hpp"
5 #include "extractor/restriction.hpp"
6 #include "extractor/restriction_compressor.hpp"
7 #include "guidance/intersection.hpp"
8
9 #include "util/dynamic_graph.hpp"
10 #include "util/node_based_graph.hpp"
11 #include "util/percent.hpp"
12
13 #include "util/log.hpp"
14
15 #include <boost/assert.hpp>
16 #include <unordered_set>
17
18 namespace osrm
19 {
20 namespace extractor
21 {
22
Compress(const std::unordered_set<NodeID> & barrier_nodes,const std::unordered_set<NodeID> & traffic_signals,ScriptingEnvironment & scripting_environment,std::vector<TurnRestriction> & turn_restrictions,std::vector<UnresolvedManeuverOverride> & maneuver_overrides,util::NodeBasedDynamicGraph & graph,const std::vector<NodeBasedEdgeAnnotation> & node_data_container,CompressedEdgeContainer & geometry_compressor)23 void GraphCompressor::Compress(const std::unordered_set<NodeID> &barrier_nodes,
24 const std::unordered_set<NodeID> &traffic_signals,
25 ScriptingEnvironment &scripting_environment,
26 std::vector<TurnRestriction> &turn_restrictions,
27 std::vector<UnresolvedManeuverOverride> &maneuver_overrides,
28 util::NodeBasedDynamicGraph &graph,
29 const std::vector<NodeBasedEdgeAnnotation> &node_data_container,
30 CompressedEdgeContainer &geometry_compressor)
31 {
32 const unsigned original_number_of_nodes = graph.GetNumberOfNodes();
33 const unsigned original_number_of_edges = graph.GetNumberOfEdges();
34
35 RestrictionCompressor restriction_compressor(turn_restrictions, maneuver_overrides);
36
37 // Some degree two nodes are not compressed if they act as entry/exit points into a
38 // restriction path.
39 std::unordered_set<NodeID> restriction_via_nodes;
40
41 const auto remember_via_nodes = [&](const auto &restriction) {
42 if (restriction.Type() == RestrictionType::NODE_RESTRICTION)
43 {
44 restriction_via_nodes.insert(restriction.AsNodeRestriction().via);
45 }
46 else
47 {
48 BOOST_ASSERT(restriction.Type() == RestrictionType::WAY_RESTRICTION);
49 const auto &way_restriction = restriction.AsWayRestriction();
50 // We do not compress the first and last via nodes so that we know how to enter/exit
51 // a restriction path and apply the restrictions correctly.
52 restriction_via_nodes.insert(way_restriction.via.front());
53 restriction_via_nodes.insert(way_restriction.via.back());
54 }
55 };
56 std::for_each(turn_restrictions.begin(), turn_restrictions.end(), remember_via_nodes);
57 {
58 const auto weight_multiplier =
59 scripting_environment.GetProfileProperties().GetWeightMultiplier();
60 util::UnbufferedLog log;
61 util::Percent progress(log, original_number_of_nodes);
62
63 for (const NodeID node_v : util::irange(0u, original_number_of_nodes))
64 {
65 progress.PrintStatus(node_v);
66
67 // only contract degree 2 vertices
68 if (2 != graph.GetOutDegree(node_v))
69 {
70 continue;
71 }
72
73 // don't contract barrier node
74 if (barrier_nodes.end() != barrier_nodes.find(node_v))
75 {
76 continue;
77 }
78
79 // check if v is an entry/exit via node for a turn restriction
80 if (restriction_via_nodes.count(node_v) > 0)
81 {
82 continue;
83 }
84
85 // reverse_e2 forward_e2
86 // u <---------- v -----------> w
87 // ----------> <-----------
88 // forward_e1 reverse_e1
89 //
90 // Will be compressed to:
91 //
92 // reverse_e1
93 // u <---------- w
94 // ---------->
95 // forward_e1
96 //
97 // If the edges are compatible.
98 const bool reverse_edge_order = graph.GetEdgeData(graph.BeginEdges(node_v)).reversed;
99 const EdgeID forward_e2 = graph.BeginEdges(node_v) + reverse_edge_order;
100 BOOST_ASSERT(SPECIAL_EDGEID != forward_e2);
101 BOOST_ASSERT(forward_e2 >= graph.BeginEdges(node_v) &&
102 forward_e2 < graph.EndEdges(node_v));
103 const EdgeID reverse_e2 = graph.BeginEdges(node_v) + 1 - reverse_edge_order;
104
105 BOOST_ASSERT(SPECIAL_EDGEID != reverse_e2);
106 BOOST_ASSERT(reverse_e2 >= graph.BeginEdges(node_v) &&
107 reverse_e2 < graph.EndEdges(node_v));
108
109 const EdgeData &fwd_edge_data2 = graph.GetEdgeData(forward_e2);
110 const EdgeData &rev_edge_data2 = graph.GetEdgeData(reverse_e2);
111
112 const NodeID node_w = graph.GetTarget(forward_e2);
113 BOOST_ASSERT(SPECIAL_NODEID != node_w);
114 BOOST_ASSERT(node_v != node_w);
115 const NodeID node_u = graph.GetTarget(reverse_e2);
116 BOOST_ASSERT(SPECIAL_NODEID != node_u);
117 BOOST_ASSERT(node_u != node_v);
118
119 const EdgeID forward_e1 = graph.FindEdge(node_u, node_v);
120 BOOST_ASSERT(SPECIAL_EDGEID != forward_e1);
121 BOOST_ASSERT(node_v == graph.GetTarget(forward_e1));
122 const EdgeID reverse_e1 = graph.FindEdge(node_w, node_v);
123 BOOST_ASSERT(SPECIAL_EDGEID != reverse_e1);
124 BOOST_ASSERT(node_v == graph.GetTarget(reverse_e1));
125
126 const EdgeData &fwd_edge_data1 = graph.GetEdgeData(forward_e1);
127 const EdgeData &rev_edge_data1 = graph.GetEdgeData(reverse_e1);
128 const auto fwd_annotation_data1 = node_data_container[fwd_edge_data1.annotation_data];
129 const auto fwd_annotation_data2 = node_data_container[fwd_edge_data2.annotation_data];
130 const auto rev_annotation_data1 = node_data_container[rev_edge_data1.annotation_data];
131 const auto rev_annotation_data2 = node_data_container[rev_edge_data2.annotation_data];
132
133 if (graph.FindEdgeInEitherDirection(node_u, node_w) != SPECIAL_EDGEID)
134 {
135 continue;
136 }
137
138 // this case can happen if two ways with different names overlap
139 if ((fwd_annotation_data1.name_id != rev_annotation_data1.name_id) ||
140 (fwd_annotation_data2.name_id != rev_annotation_data2.name_id))
141 {
142 continue;
143 }
144
145 if ((fwd_edge_data1.flags == fwd_edge_data2.flags) &&
146 (rev_edge_data1.flags == rev_edge_data2.flags) &&
147 (fwd_edge_data1.reversed == fwd_edge_data2.reversed) &&
148 (rev_edge_data1.reversed == rev_edge_data2.reversed) &&
149 // annotations need to match, except for the lane-id which can differ
150 fwd_annotation_data1.CanCombineWith(fwd_annotation_data2) &&
151 rev_annotation_data1.CanCombineWith(rev_annotation_data2))
152 {
153 BOOST_ASSERT(!(graph.GetEdgeData(forward_e1).reversed &&
154 graph.GetEdgeData(reverse_e1).reversed));
155 /*
156 * Remember Lane Data for compressed parts. This handles scenarios where lane-data
157 * is
158 * only kept up until a traffic light.
159 *
160 * | |
161 * ---------------- |
162 * -^ | |
163 * ----------- |
164 * -v | |
165 * --------------- |
166 * | |
167 *
168 * u ------- v ---- w
169 *
170 * Since the edge is compressable, we can transfer:
171 * "left|right" (uv) and "" (uw) into a string with "left|right" (uw) for the
172 * compressed
173 * edge.
174 * Doing so, we might mess up the point from where the lanes are shown. It should be
175 * reasonable, since the announcements have to come early anyhow. So there is a
176 * potential danger in here, but it saves us from adding a lot of additional edges
177 * for
178 * turn-lanes. Without this, we would have to treat any turn-lane beginning/ending
179 * just
180 * like a barrier.
181 */
182 const auto selectAnnotation =
183 [&node_data_container](const AnnotationID front_annotation,
184 const AnnotationID back_annotation) {
185 // A lane has tags: u - (front) - v - (back) - w
186 // During contraction, we keep only one of the tags. Usually the one closer
187 // to the intersection is preferred. If its empty, however, we keep the
188 // non-empty one
189 if (node_data_container[back_annotation].lane_description_id ==
190 INVALID_LANE_DESCRIPTIONID)
191 return front_annotation;
192 return back_annotation;
193 };
194
195 graph.GetEdgeData(forward_e1).annotation_data = selectAnnotation(
196 fwd_edge_data1.annotation_data, fwd_edge_data2.annotation_data);
197 graph.GetEdgeData(reverse_e1).annotation_data = selectAnnotation(
198 rev_edge_data1.annotation_data, rev_edge_data2.annotation_data);
199 graph.GetEdgeData(forward_e2).annotation_data = selectAnnotation(
200 fwd_edge_data2.annotation_data, fwd_edge_data1.annotation_data);
201 graph.GetEdgeData(reverse_e2).annotation_data = selectAnnotation(
202 rev_edge_data2.annotation_data, rev_edge_data1.annotation_data);
203
204 // Add node penalty when compress edge crosses a traffic signal
205 const bool has_node_penalty = traffic_signals.find(node_v) != traffic_signals.end();
206 EdgeDuration node_duration_penalty = MAXIMAL_EDGE_DURATION;
207 EdgeWeight node_weight_penalty = INVALID_EDGE_WEIGHT;
208 if (has_node_penalty)
209 {
210 // we cannot handle this as node penalty, if it depends on turn direction
211 if (fwd_edge_data1.flags.restricted != fwd_edge_data2.flags.restricted)
212 continue;
213
214 // generate an artifical turn for the turn penalty generation
215 std::vector<ExtractionTurnLeg> roads_on_the_right;
216 std::vector<ExtractionTurnLeg> roads_on_the_left;
217 ExtractionTurn extraction_turn(0,
218 2,
219 false,
220 true,
221 false,
222 false,
223 TRAVEL_MODE_DRIVING,
224 false,
225 false,
226 1,
227 0,
228 0,
229 0,
230 0,
231 false,
232 TRAVEL_MODE_DRIVING,
233 false,
234 false,
235 1,
236 0,
237 0,
238 0,
239 0,
240 roads_on_the_right,
241 roads_on_the_left);
242 scripting_environment.ProcessTurn(extraction_turn);
243 node_duration_penalty = extraction_turn.duration * 10;
244 node_weight_penalty = extraction_turn.weight * weight_multiplier;
245 }
246
247 // Get weights before graph is modified
248 const auto forward_weight1 = fwd_edge_data1.weight;
249 const auto forward_weight2 = fwd_edge_data2.weight;
250 const auto forward_duration1 = fwd_edge_data1.duration;
251 const auto forward_duration2 = fwd_edge_data2.duration;
252 const auto forward_distance2 = fwd_edge_data2.distance;
253
254 BOOST_ASSERT(0 != forward_weight1);
255 BOOST_ASSERT(0 != forward_weight2);
256
257 const auto reverse_weight1 = rev_edge_data1.weight;
258 const auto reverse_weight2 = rev_edge_data2.weight;
259 const auto reverse_duration1 = rev_edge_data1.duration;
260 const auto reverse_duration2 = rev_edge_data2.duration;
261 const auto reverse_distance2 = rev_edge_data2.distance;
262
263 #ifndef NDEBUG
264 // Because distances are symmetrical, we only need one
265 // per edge - here we double-check that they match
266 // their mirrors.
267 const auto reverse_distance1 = rev_edge_data1.distance;
268 const auto forward_distance1 = fwd_edge_data1.distance;
269 BOOST_ASSERT(forward_distance1 == reverse_distance2);
270 BOOST_ASSERT(forward_distance2 == reverse_distance1);
271 #endif
272
273 BOOST_ASSERT(0 != reverse_weight1);
274 BOOST_ASSERT(0 != reverse_weight2);
275
276 // add weight of e2's to e1
277 graph.GetEdgeData(forward_e1).weight += forward_weight2;
278 graph.GetEdgeData(reverse_e1).weight += reverse_weight2;
279
280 // add duration of e2's to e1
281 graph.GetEdgeData(forward_e1).duration += forward_duration2;
282 graph.GetEdgeData(reverse_e1).duration += reverse_duration2;
283
284 // add distance of e2's to e1
285 graph.GetEdgeData(forward_e1).distance += forward_distance2;
286 graph.GetEdgeData(reverse_e1).distance += reverse_distance2;
287
288 if (node_weight_penalty != INVALID_EDGE_WEIGHT &&
289 node_duration_penalty != MAXIMAL_EDGE_DURATION)
290 {
291 graph.GetEdgeData(forward_e1).weight += node_weight_penalty;
292 graph.GetEdgeData(reverse_e1).weight += node_weight_penalty;
293 graph.GetEdgeData(forward_e1).duration += node_duration_penalty;
294 graph.GetEdgeData(reverse_e1).duration += node_duration_penalty;
295 // Note: no penalties for distances
296 }
297
298 // extend e1's to targets of e2's
299 graph.SetTarget(forward_e1, node_w);
300 graph.SetTarget(reverse_e1, node_u);
301
302 // remove e2's (if bidir, otherwise only one)
303 graph.DeleteEdge(node_v, forward_e2);
304 graph.DeleteEdge(node_v, reverse_e2);
305
306 // update any involved turn restrictions
307 restriction_compressor.Compress(node_u, node_v, node_w);
308
309 // store compressed geometry in container
310 geometry_compressor.CompressEdge(forward_e1,
311 forward_e2,
312 node_v,
313 node_w,
314 forward_weight1,
315 forward_weight2,
316 forward_duration1,
317 forward_duration2,
318 node_weight_penalty,
319 node_duration_penalty);
320 geometry_compressor.CompressEdge(reverse_e1,
321 reverse_e2,
322 node_v,
323 node_u,
324 reverse_weight1,
325 reverse_weight2,
326 reverse_duration1,
327 reverse_duration2,
328 node_weight_penalty,
329 node_duration_penalty);
330 }
331 }
332 }
333
334 PrintStatistics(original_number_of_nodes, original_number_of_edges, graph);
335
336 // Repeate the loop, but now add all edges as uncompressed values.
337 // The function AddUncompressedEdge does nothing if the edge is already
338 // in the CompressedEdgeContainer.
339 for (const NodeID node_u : util::irange(0u, original_number_of_nodes))
340 {
341 for (const auto edge_id : util::irange(graph.BeginEdges(node_u), graph.EndEdges(node_u)))
342 {
343 const EdgeData &data = graph.GetEdgeData(edge_id);
344 const NodeID target = graph.GetTarget(edge_id);
345 geometry_compressor.AddUncompressedEdge(edge_id, target, data.weight, data.duration);
346 }
347 }
348 }
349
PrintStatistics(unsigned original_number_of_nodes,unsigned original_number_of_edges,const util::NodeBasedDynamicGraph & graph) const350 void GraphCompressor::PrintStatistics(unsigned original_number_of_nodes,
351 unsigned original_number_of_edges,
352 const util::NodeBasedDynamicGraph &graph) const
353 {
354
355 unsigned new_node_count = 0;
356 unsigned new_edge_count = 0;
357
358 for (const auto i : util::irange(0u, graph.GetNumberOfNodes()))
359 {
360 if (graph.GetOutDegree(i) > 0)
361 {
362 ++new_node_count;
363 new_edge_count += (graph.EndEdges(i) - graph.BeginEdges(i));
364 }
365 }
366 util::Log() << "Node compression ratio: " << new_node_count / (double)original_number_of_nodes;
367 util::Log() << "Edge compression ratio: " << new_edge_count / (double)original_number_of_edges;
368 }
369 } // namespace extractor
370 } // namespace osrm
371