Line data Source code
1 : #ifndef ROUTING_KIT_CONTRACTION_HIERARCHY_H
2 : #define ROUTING_KIT_CONTRACTION_HIERARCHY_H
3 :
4 : #include <routingkit/id_queue.h>
5 : #include <routingkit/timestamp_flag.h>
6 : #include <routingkit/bit_vector.h>
7 : #include <routingkit/permutation.h>
8 :
9 : #include <vector>
10 : #include <string>
11 : #include <functional>
12 : #include <cassert>
13 : #include <type_traits>
14 : #include <limits.h>
15 :
16 : namespace RoutingKit{
17 :
18 : class ContractionHierarchy{
19 : public:
20 : static const unsigned default_max_pop_count = 500;
21 :
22 : static ContractionHierarchy build(
23 : unsigned node_count, std::vector<unsigned>tail, std::vector<unsigned>head, std::vector<unsigned>weight,
24 : const std::function<void(std::string)>&log_message = std::function<void(std::string)>(), unsigned max_pop_count = default_max_pop_count
25 : );
26 :
27 : static ContractionHierarchy build_given_rank(
28 : std::vector<unsigned>rank,
29 : std::vector<unsigned>tail, std::vector<unsigned>head, std::vector<unsigned>weight,
30 : const std::function<void(std::string)>&log_message = std::function<void(std::string)>(), unsigned max_pop_count = default_max_pop_count
31 : );
32 :
33 : static ContractionHierarchy build_given_order(
34 : std::vector<unsigned>order,
35 : std::vector<unsigned>tail, std::vector<unsigned>head, std::vector<unsigned>weight,
36 : const std::function<void(std::string)>&log_message = std::function<void(std::string)>(), unsigned max_pop_count = default_max_pop_count
37 : );
38 :
39 : static ContractionHierarchy read(std::function<void(char*, unsigned long long)>data_source);
40 : static ContractionHierarchy read(std::function<void(char*, unsigned long long)>data_source, unsigned long long file_size);
41 : static ContractionHierarchy read(std::istream&in);
42 : static ContractionHierarchy read(std::istream&in, unsigned long long file_size);
43 : static ContractionHierarchy load_file(const std::string&file_name);
44 :
45 : void write(std::function<void(const char*, unsigned long long)>data_sink) const;
46 : void write(std::ostream&out) const;
47 : void save_file(const std::string&file_name) const;
48 :
49 : unsigned node_count()const{
50 0 : return rank.size();
51 : }
52 :
53 : struct Side{
54 : std::vector<unsigned>first_out;
55 : std::vector<unsigned>head;
56 : std::vector<unsigned>weight;
57 :
58 : BitVector is_shortcut_an_original_arc;
59 : std::vector<unsigned>shortcut_first_arc; // contains input arc ID if not shortcut
60 : std::vector<unsigned>shortcut_second_arc;// contains input tail node ID if not shortcut
61 : };
62 :
63 : std::vector<unsigned>rank, order;
64 : Side forward, backward;
65 : };
66 :
67 : void check_contraction_hierarchy_for_errors(const ContractionHierarchy&ch);
68 :
69 : template<class Weight>
70 : struct ContractionHierarchyExtraWeight{
71 :
72 0 : ContractionHierarchyExtraWeight(){}
73 :
74 : template<class InputWeightContainer, class LinkFunction>
75 : ContractionHierarchyExtraWeight(const ContractionHierarchy&ch, const InputWeightContainer&extra_weight, const LinkFunction&link){ reset(ch, extra_weight, link); }
76 :
77 : template<class InputWeightContainer, class LinkFunction>
78 : ContractionHierarchyExtraWeight& reset(const ContractionHierarchy&ch, const InputWeightContainer&extra_weight, const LinkFunction&link);
79 :
80 : std::vector<Weight>forward_weight, backward_weight;
81 : };
82 :
83 : namespace detail{
84 : template<class T>
85 : using ReturnTypeWhenPassedIntOf = typename std::remove_const<typename std::remove_reference<decltype(std::declval<T>()(1))>::type>::type;
86 :
87 : template<class T>
88 : using ValueTypeOfContainer = typename std::remove_const<typename std::remove_reference<decltype(std::declval<T>()[1])>::type>::type;
89 :
90 : template<class T>
91 : struct GetExtraWeightTypeHelper{
92 : typedef ValueTypeOfContainer<T> type;
93 : };
94 :
95 : template<class T>
96 : struct GetExtraWeightTypeHelper<ContractionHierarchyExtraWeight<T>>{
97 : typedef T type;
98 : };
99 :
100 : template<class T>
101 : using GetExtraWeightType = typename GetExtraWeightTypeHelper<T>::type;
102 : }
103 :
104 : class ContractionHierarchyQuery{
105 : public:
106 : ContractionHierarchyQuery():ch(0){}
107 : explicit ContractionHierarchyQuery(const ContractionHierarchy&ch);
108 :
109 : ContractionHierarchyQuery&reset();
110 : ContractionHierarchyQuery&reset(const ContractionHierarchy&ch);
111 :
112 : ContractionHierarchyQuery&add_source(unsigned s, unsigned dist_to_s = 0);
113 : ContractionHierarchyQuery&add_target(unsigned t, unsigned dist_to_t = 0);
114 :
115 : ContractionHierarchyQuery&run();
116 :
117 : unsigned get_used_source();
118 : unsigned get_used_target();
119 :
120 : unsigned get_distance();
121 : std::vector<unsigned>get_node_path();
122 : std::vector<unsigned>get_arc_path();
123 :
124 : template<class ExtraWeight, class LinkFunction>
125 : detail::GetExtraWeightType<ExtraWeight> get_extra_weight_distance(const ExtraWeight&extra_weight, const LinkFunction&link);
126 :
127 : ContractionHierarchyQuery& reset_source();
128 : ContractionHierarchyQuery& pin_targets(const std::vector<unsigned>&);
129 : unsigned get_pinned_target_count();
130 : ContractionHierarchyQuery& run_to_pinned_targets();
131 :
132 : ContractionHierarchyQuery& get_distances_to_targets(unsigned*dist);
133 : std::vector<unsigned> get_distances_to_targets();
134 :
135 : ContractionHierarchyQuery& reset_target();
136 : ContractionHierarchyQuery& pin_sources(const std::vector<unsigned>&);
137 : unsigned get_pinned_source_count();
138 : ContractionHierarchyQuery& run_to_pinned_sources();
139 :
140 : ContractionHierarchyQuery& get_distances_to_sources(unsigned*dist);
141 : std::vector<unsigned> get_distances_to_sources();
142 :
143 : // TODO: Mirror these functions in CCH
144 :
145 : ContractionHierarchyQuery& get_used_sources_to_targets(unsigned*dist);
146 : std::vector<unsigned> get_used_sources_to_targets();
147 :
148 : ContractionHierarchyQuery& get_used_targets_to_sources(unsigned*dist);
149 : std::vector<unsigned> get_used_targets_to_sources();
150 :
151 : // The get_extra_weight_distances function follow a pattern.
152 : // The usage pattern is
153 : //
154 : // get_extra_weight_distances_to_[target|source](extra_weight, link, [, tmp, [dist]])
155 : //
156 : // There get_extra_weight_distances_to_target is used if targets were pinned, whereas
157 : // get_extra_weight_distances_to_source is for pinned sources.
158 : //
159 : // There are four additional parameters. Their meaning are:
160 : //
161 : // * extra_weight: The extra weight according to which the path length should be computed.
162 : // This can be a ContractionHierarchyExtraWeight<T> or a container<T>. The former is faster.
163 : // container<T> is a placeholder for anything that has an operator[] that provides read-only
164 : // access to the arc weight. For every arc a, the expression extra_weight[a] should
165 : // give the extra weight. Using ContractionHierarchyExtraWeight<T> is faster.
166 : // Typical types for container<T> are const vector<T> and const T*.
167 : //
168 : // * The extra weight does not have to be a scalar value. It can be an arbitrary structure.
169 : // However, the algorithm needs to know how to concatenate the weights of two arcs.
170 : // The link parameter is a functor that tells it how to do it.
171 : // For travel time, the link parameter is the addition. If some of your
172 : // values are inf_weight, normal addition can run into overflow problems. RoutingKit therefore
173 : // provides the SaturatedWeightAddition functor that correctly handles overflows for unsigned and int weights.
174 : //
175 : // The link function will never be provided a default constructed object, i.e.,
176 : // it does not exploit that link(T(),foo) == foo.
177 : //
178 : // * tmp is a container<T>. Its size must be at least node_count. The content of
179 : // the first node_count elements in undefined after this function is completed.
180 : // If the parameter is omitted, a temporary buffer is allocated. If the function
181 : // is called multiple times, it can be faster to only allocate one buffer.
182 : //
183 : // * dist is a container<T>. Its size is the number of pinned sources or targets.
184 : // the output is written to it. If it is omited, a vector<T> is allocated and
185 : // returned by the function.
186 : //
187 : // If the source and the target nodes are equal, the extra weight length is
188 : // default constructed T. If there is no path, the extra weight length is also
189 : // default constructed T. For integers default constructed means 0.
190 : //
191 : // If both tmp and dist are present, the function is guarenteed to not allocate or free any memory.
192 : // If tmp and dist are present, and link is guarenteed to not throw, the function is guarenteed to not throw.
193 :
194 : template<class ExtraWeight, class LinkFunction> std::vector<detail::GetExtraWeightType<ExtraWeight>> get_extra_weight_distances_to_targets(const ExtraWeight&extra_weight, const LinkFunction&link);
195 : template<class ExtraWeight, class LinkFunction, class TmpContainer> std::vector<detail::GetExtraWeightType<ExtraWeight>> get_extra_weight_distances_to_targets(const ExtraWeight&extra_weight, const LinkFunction&link, TmpContainer&tmp);
196 : template<class ExtraWeight, class LinkFunction, class TmpContainer, class DistContainer> ContractionHierarchyQuery& get_extra_weight_distances_to_targets(const ExtraWeight&extra_weight, const LinkFunction&link, TmpContainer&tmp, DistContainer&dist);
197 : template<class ExtraWeight, class LinkFunction> std::vector<detail::GetExtraWeightType<ExtraWeight>> get_extra_weight_distances_to_sources(const ExtraWeight&extra_weight, const LinkFunction&link);
198 : template<class ExtraWeight, class LinkFunction, class TmpContainer> std::vector<detail::GetExtraWeightType<ExtraWeight>> get_extra_weight_distances_to_sources(const ExtraWeight&extra_weight, const LinkFunction&link, TmpContainer&tmp);
199 : template<class ExtraWeight, class LinkFunction, class TmpContainer, class DistContainer> ContractionHierarchyQuery& get_extra_weight_distances_to_sources(const ExtraWeight&extra_weight, const LinkFunction&link, TmpContainer&tmp, DistContainer&dist);
200 :
201 : //private:
202 : const ContractionHierarchy*ch;
203 :
204 : TimestampFlags was_forward_pushed, was_backward_pushed;
205 : MinIDQueue forward_queue, backward_queue;
206 : std::vector<unsigned>forward_tentative_distance, backward_tentative_distance;
207 : std::vector<unsigned>forward_predecessor_node, backward_predecessor_node;
208 : std::vector<unsigned>forward_predecessor_arc, backward_predecessor_arc;
209 : unsigned shortest_path_meeting_node;
210 : unsigned many_to_many_source_or_target_count;
211 :
212 : enum class InternalState:unsigned{
213 : initialized,
214 : run,
215 : source_pinned,
216 : source_run,
217 : target_pinned,
218 : target_run
219 : }state;
220 : };
221 :
222 : struct SaturatedWeightAddition{
223 : unsigned operator()(unsigned l, unsigned r)const;
224 : int operator()(int l, int r)const;
225 : };
226 :
227 : // ------ Template & inline implementations; no more interface descriptions beyond this line -------
228 :
229 : inline
230 : unsigned ContractionHierarchyQuery::get_pinned_target_count(){
231 : assert(state == ContractionHierarchyQuery::InternalState::target_run || state == ContractionHierarchyQuery::InternalState::target_pinned);
232 : return many_to_many_source_or_target_count;
233 : }
234 :
235 : inline
236 : unsigned ContractionHierarchyQuery::get_pinned_source_count(){
237 : assert(state == ContractionHierarchyQuery::InternalState::source_run || state == ContractionHierarchyQuery::InternalState::source_pinned);
238 : return many_to_many_source_or_target_count;
239 : }
240 :
241 : template<class ExtraWeight, class LinkFunction>
242 : std::vector<detail::GetExtraWeightType<ExtraWeight>> ContractionHierarchyQuery::get_extra_weight_distances_to_targets(
243 : const ExtraWeight&extra_weight,
244 : const LinkFunction&link
245 : ){
246 : std::vector<detail::GetExtraWeightType<ExtraWeight>>tmp(ch->node_count()), dist(get_pinned_target_count());
247 : get_extra_weight_distances_to_targets(extra_weight, link, tmp, dist);
248 : return dist; // NVRO
249 : }
250 :
251 : template<class ExtraWeight, class LinkFunction, class TmpContainer>
252 : std::vector<detail::GetExtraWeightType<ExtraWeight>> ContractionHierarchyQuery::get_extra_weight_distances_to_targets(
253 : const ExtraWeight&extra_weight,
254 : const LinkFunction&link,
255 : TmpContainer&tmp
256 : ){
257 : std::vector<detail::GetExtraWeightType<ExtraWeight>>dist(get_pinned_target_count());
258 : get_extra_weight_distances_to_targets(extra_weight, link, tmp, dist);
259 : return dist; // NVRO
260 : }
261 :
262 :
263 : template<class ExtraWeight, class LinkFunction>
264 : std::vector<detail::GetExtraWeightType<ExtraWeight>> ContractionHierarchyQuery::get_extra_weight_distances_to_sources(
265 : const ExtraWeight&extra_weight,
266 : const LinkFunction&link
267 : ){
268 : std::vector<detail::GetExtraWeightType<ExtraWeight>>tmp(ch->node_count()), dist(get_pinned_source_count());
269 : get_extra_weight_distances_to_sources(extra_weight, link, tmp, dist);
270 : return dist; // NVRO
271 : }
272 :
273 : template<class ExtraWeight, class LinkFunction, class TmpContainer>
274 : std::vector<detail::GetExtraWeightType<ExtraWeight>> ContractionHierarchyQuery::get_extra_weight_distances_to_sources(
275 : const ExtraWeight&extra_weight,
276 : const LinkFunction&link,
277 : TmpContainer&tmp
278 : ){
279 : std::vector<detail::GetExtraWeightType<ExtraWeight>>dist(get_pinned_source_count());
280 : get_extra_weight_distances_to_sources(extra_weight, link, tmp, dist);
281 : return dist; // NVRO
282 : }
283 :
284 : inline
285 : unsigned SaturatedWeightAddition::operator()(unsigned l, unsigned r)const{
286 : assert(l <= inf_weight && "unsigned weight must not be larger than inf_weight");
287 : assert(r <= inf_weight && "unsigned weight must not be larger than inf_weight");
288 0 : if(l >= inf_weight-r)
289 : return inf_weight;
290 : else
291 0 : return l+r;
292 : }
293 :
294 : inline
295 : int SaturatedWeightAddition::operator()(int l, int r)const{
296 : static_assert(inf_weight == INT_MAX, "this function assumes that inf_weight is INT_MAX");
297 0 : if(l > 0){
298 0 : if (r > INT_MAX - l){
299 : return INT_MAX;
300 : }
301 0 : }else if(r < INT_MIN - l){
302 : return INT_MIN;
303 : }
304 :
305 0 : return l + r;
306 : }
307 :
308 : namespace detail{
309 : template<class LinkFunction>
310 : struct InverseLinkFunction{
311 : explicit InverseLinkFunction(const LinkFunction&link):link(link){}
312 :
313 : template<class L, class R>
314 : auto operator()(L&&l, R&&r)const
315 : -> decltype(std::declval<LinkFunction>()(std::forward<R>(r), std::forward<L>(l)))
316 : {
317 0 : return link(std::forward<R>(r), std::forward<L>(l));
318 : }
319 :
320 : const LinkFunction&link;
321 : };
322 :
323 : template<class LinkFunction>
324 : InverseLinkFunction<LinkFunction>inverse_link_function(const LinkFunction&link){
325 : return InverseLinkFunction<LinkFunction>(link);
326 : }
327 :
328 : template<class InputWeightContainer, class LinkFunction>
329 : struct ShortcutWeights{
330 : typedef typename std::remove_reference<decltype(std::declval<InputWeightContainer>()[0])>::type Weight;
331 :
332 : const InputWeightContainer&input_weight;
333 : const LinkFunction&link;
334 :
335 : const ContractionHierarchy&ch;
336 :
337 0 : ShortcutWeights(const InputWeightContainer&input_weight, const LinkFunction&link, const ContractionHierarchy&ch):
338 0 : input_weight(input_weight), link(link), ch(ch){}
339 :
340 0 : Weight get_forward_weight(unsigned a)const{
341 : assert(a < ch.forward.is_shortcut_an_original_arc.size());
342 0 : if(ch.forward.is_shortcut_an_original_arc.is_set(a)){
343 0 : return input_weight[ch.forward.shortcut_first_arc[a]];
344 : }else{
345 0 : return link(get_backward_weight(ch.forward.shortcut_first_arc[a]), get_forward_weight(ch.forward.shortcut_second_arc[a]));
346 : }
347 : }
348 :
349 0 : Weight get_backward_weight(unsigned a)const{
350 : assert(a < ch.backward.is_shortcut_an_original_arc.size());
351 0 : if(ch.backward.is_shortcut_an_original_arc.is_set(a)){
352 0 : return input_weight[ch.backward.shortcut_first_arc[a]];
353 : }else{
354 0 : return link(get_backward_weight(ch.backward.shortcut_first_arc[a]), get_forward_weight(ch.backward.shortcut_second_arc[a]));
355 : }
356 : }
357 : };
358 :
359 : template<class WeightT, class LinkFunction>
360 : struct ShortcutWeights<ContractionHierarchyExtraWeight<WeightT>, LinkFunction>{
361 :
362 : typedef WeightT Weight;
363 :
364 : const ContractionHierarchyExtraWeight<WeightT>&extra_weight;
365 :
366 : explicit ShortcutWeights(const ContractionHierarchyExtraWeight<WeightT>&extra_weight, const LinkFunction&, const ContractionHierarchy&):
367 : extra_weight(extra_weight){}
368 :
369 : const Weight&get_forward_weight(unsigned a)const{
370 0 : return extra_weight.forward_weight[a];
371 : }
372 :
373 : const Weight&get_backward_weight(unsigned a)const{
374 0 : return extra_weight.backward_weight[a];
375 : }
376 : };
377 :
378 : template<class ExtraWeight, class LinkFunction>
379 : ShortcutWeights<ExtraWeight, LinkFunction> make_shortcut_weights(const ExtraWeight&extra_weight, const LinkFunction&link, const ContractionHierarchy&ch){
380 : return ShortcutWeights<ExtraWeight, LinkFunction>{extra_weight, link, ch};
381 : }
382 :
383 : template<class ShortcutWeights>
384 : struct InvertShorcutWeights{
385 : typedef typename ShortcutWeights::Weight Weight;
386 :
387 : const ShortcutWeights&shortcut_weights;
388 :
389 : explicit InvertShorcutWeights(const ShortcutWeights&shortcut_weights):shortcut_weights(shortcut_weights){}
390 :
391 : auto get_forward_weight(unsigned a)const->decltype(std::declval<ShortcutWeights>().get_backward_weight(a)){
392 0 : return shortcut_weights.get_backward_weight(a);
393 : }
394 :
395 : auto get_backward_weight(unsigned a)const->decltype(std::declval<ShortcutWeights>().get_forward_weight(a)){
396 0 : return shortcut_weights.get_forward_weight(a);
397 : }
398 : };
399 :
400 : template<class ShortcutWeights>
401 : InvertShorcutWeights<ShortcutWeights>inverse_shortcut_weights(const ShortcutWeights&shortcut_weights){
402 : return InvertShorcutWeights<ShortcutWeights>(shortcut_weights);
403 : }
404 :
405 : template<class GetForwardWeight, class LinkFunction>
406 0 : ReturnTypeWhenPassedIntOf<GetForwardWeight> get_extra_weight_up_distance(
407 : unsigned shortest_path_meeting_node,
408 : const std::vector<unsigned>&forward_predecessor_node,
409 : const std::vector<unsigned>&forward_predecessor_arc,
410 : const GetForwardWeight&get_forward_extra_weight,
411 : const LinkFunction&link
412 : ){
413 : using Weight = ReturnTypeWhenPassedIntOf<GetForwardWeight>;
414 :
415 : unsigned x = shortest_path_meeting_node;
416 : assert(forward_predecessor_node[x] != invalid_id);
417 0 : Weight ret = get_forward_extra_weight(forward_predecessor_arc[x]);
418 0 : x = forward_predecessor_node[x];
419 :
420 0 : while(forward_predecessor_node[x] != invalid_id){
421 0 : ret = link(get_forward_extra_weight(forward_predecessor_arc[x]), ret);
422 0 : x = forward_predecessor_node[x];
423 : }
424 0 : return ret;
425 : }
426 :
427 :
428 : template<class ShortcutWeights, class LinkFunction>
429 0 : typename ShortcutWeights::Weight internal_get_extra_weight_distance(
430 : const ShortcutWeights&shortcut_weights,
431 : const LinkFunction&link,
432 : unsigned shortest_path_meeting_node,
433 : const std::vector<unsigned>&forward_predecessor_node,
434 : const std::vector<unsigned>&forward_predecessor_arc,
435 : const std::vector<unsigned>&backward_predecessor_node,
436 : const std::vector<unsigned>&backward_predecessor_arc
437 : ){
438 : using Weight = typename ShortcutWeights::Weight;
439 :
440 0 : if(shortest_path_meeting_node == invalid_id)
441 : return Weight{};
442 :
443 :
444 0 : auto inverted_link = detail::inverse_link_function(link);
445 :
446 0 : bool has_up_part = forward_predecessor_node[shortest_path_meeting_node] != invalid_id;
447 0 : bool has_down_part = backward_predecessor_node[shortest_path_meeting_node] != invalid_id;
448 :
449 : // This if-then-else chain avoids the need for a neutral element with respect to link
450 :
451 0 : if(!has_up_part && !has_down_part) {
452 : return Weight{};
453 0 : } else if(has_up_part && has_down_part) {
454 0 : return link(
455 : detail::get_extra_weight_up_distance(
456 : shortest_path_meeting_node,
457 : forward_predecessor_node,
458 : forward_predecessor_arc,
459 0 : [&](unsigned a)->decltype(shortcut_weights.get_forward_weight(a)){return shortcut_weights.get_forward_weight(a);},
460 : link
461 : ),
462 : detail::get_extra_weight_up_distance(
463 : shortest_path_meeting_node,
464 : backward_predecessor_node,
465 : backward_predecessor_arc,
466 0 : [&](unsigned a)->decltype(shortcut_weights.get_backward_weight(a)){return shortcut_weights.get_backward_weight(a);},
467 : inverted_link
468 : )
469 : );
470 0 : } else if(has_up_part) {
471 0 : return detail::get_extra_weight_up_distance(
472 : shortest_path_meeting_node,
473 : forward_predecessor_node,
474 : forward_predecessor_arc,
475 0 : [&](unsigned a)->decltype(shortcut_weights.get_forward_weight(a)){return shortcut_weights.get_forward_weight(a);},
476 : link
477 : );
478 : } else {
479 0 : return detail::get_extra_weight_up_distance(
480 : shortest_path_meeting_node,
481 : backward_predecessor_node,
482 : backward_predecessor_arc,
483 0 : [&](unsigned a)->decltype(shortcut_weights.get_backward_weight(a)){return shortcut_weights.get_backward_weight(a);},
484 : inverted_link
485 : );
486 : }
487 : }
488 :
489 : }
490 :
491 : template<class ExtraWeight, class LinkFunction>
492 0 : detail::GetExtraWeightType<ExtraWeight> ContractionHierarchyQuery::get_extra_weight_distance(
493 : const ExtraWeight&extra_weight,
494 : const LinkFunction&link){
495 : assert(ch && "query object must have an attached CH");
496 : assert(state == ContractionHierarchyQuery::InternalState::run);
497 :
498 0 : auto shortcut_weight = detail::make_shortcut_weights(extra_weight, link, *ch);
499 :
500 0 : return detail::internal_get_extra_weight_distance(
501 : shortcut_weight, link,
502 : shortest_path_meeting_node,
503 0 : forward_predecessor_node, forward_predecessor_arc,
504 0 : backward_predecessor_node, backward_predecessor_arc
505 0 : );
506 : }
507 :
508 : template<class Weight> template<class InputWeightContainer, class LinkFunction>
509 0 : ContractionHierarchyExtraWeight<Weight>& ContractionHierarchyExtraWeight<Weight>::reset(const ContractionHierarchy&ch, const InputWeightContainer&input_extra_weight, const LinkFunction&link){
510 : const unsigned node_count = ch.node_count();
511 :
512 0 : forward_weight.resize(ch.forward.weight.size());
513 0 : backward_weight.resize(ch.backward.weight.size());
514 :
515 0 : for(unsigned x=0; x<node_count; ++x){
516 0 : for(unsigned xy=ch.forward.first_out[x]; xy<ch.forward.first_out[x+1]; ++xy){
517 0 : if(ch.forward.is_shortcut_an_original_arc.is_set(xy)){
518 0 : forward_weight[xy] = input_extra_weight[ch.forward.shortcut_first_arc[xy]];
519 : } else {
520 0 : forward_weight[xy] = link(
521 0 : backward_weight[ch.forward.shortcut_first_arc[xy]],
522 0 : forward_weight[ch.forward.shortcut_second_arc[xy]]
523 : );
524 : }
525 : }
526 0 : for(unsigned xy=ch.backward.first_out[x]; xy<ch.backward.first_out[x+1]; ++xy){
527 0 : if(ch.backward.is_shortcut_an_original_arc.is_set(xy)){
528 0 : backward_weight[xy] = input_extra_weight[ch.backward.shortcut_first_arc[xy]];
529 : } else {
530 0 : backward_weight[xy] = link(
531 0 : backward_weight[ch.backward.shortcut_first_arc[xy]],
532 0 : forward_weight[ch.backward.shortcut_second_arc[xy]]
533 : );
534 : }
535 : }
536 : }
537 0 : return *this;
538 : }
539 :
540 :
541 : namespace detail{
542 : template<class LinkFunction, class ExtraWeight, class TmpContainer, class DistContainer>
543 0 : void extract_distances_to_targets(
544 : const std::vector<unsigned>&target_list,
545 : unsigned target_count,
546 :
547 : const TimestampFlags&has_forward_predecessor,
548 : const std::vector<unsigned>&forward_predecessor_node,
549 : const std::vector<unsigned>&predecessor_arc,
550 :
551 : const ExtraWeight&extra_weight,
552 : const std::vector<unsigned>&forward_first_out,
553 : const std::vector<unsigned>&forward_head,
554 : const std::vector<unsigned>&backward_first_out,
555 : const std::vector<unsigned>&backward_head,
556 :
557 : TmpContainer&source_to_node_distance,
558 : TimestampFlags&has_source_to_node_distance,
559 :
560 : DistContainer&output,
561 :
562 : std::vector<unsigned>&stack,
563 :
564 : const LinkFunction&link
565 : ){
566 : using Weight = typename ExtraWeight::Weight;
567 :
568 : has_source_to_node_distance.reset_all();
569 :
570 0 : unsigned nodes_on_stack_with_forward_precessor_count = 0;
571 0 : unsigned stack_size = 0;
572 :
573 0 : auto push = [&](unsigned x){
574 : assert(stack_size < stack.size());
575 0 : stack[stack_size++] = x;
576 : };
577 :
578 0 : auto pop = [&]{
579 : assert(stack_size != 0);
580 0 : return stack[--stack_size];
581 : };
582 :
583 0 : auto single_forward_step_expand_distance_to_node = [&](unsigned x){
584 : assert(!has_source_to_node_distance.is_set(x));
585 : assert(has_forward_predecessor.is_set(x));
586 : assert(forward_predecessor_node[x] != invalid_id);
587 :
588 0 : unsigned a = predecessor_arc[x];
589 0 : unsigned p = forward_predecessor_node[x];
590 :
591 0 : if(has_source_to_node_distance.is_set(p))
592 0 : source_to_node_distance[x] = link(source_to_node_distance[p], extra_weight.get_forward_weight(a));
593 : else
594 0 : source_to_node_distance[x] = extra_weight.get_forward_weight(a); // p is source
595 0 : has_source_to_node_distance.set(x);
596 : };
597 :
598 0 : auto single_backward_step_expand_distance_to_node = [&](unsigned x){
599 : assert(!has_source_to_node_distance.is_set(x));
600 : assert(!has_forward_predecessor.is_set(x));
601 :
602 0 : unsigned a = predecessor_arc[x];
603 0 : unsigned p = backward_head[a];
604 :
605 0 : if(has_source_to_node_distance.is_set(p))
606 0 : source_to_node_distance[x] = link(source_to_node_distance[p], extra_weight.get_backward_weight(a));
607 : else
608 0 : source_to_node_distance[x] = extra_weight.get_backward_weight(a); // p is source
609 :
610 0 : has_source_to_node_distance.set(x);
611 : };
612 :
613 0 : auto push_non_reached_nodes = [&](unsigned x){
614 : assert(!has_source_to_node_distance.is_set(x));
615 0 : while(!has_forward_predecessor.is_set(x)){
616 0 : push(x);
617 0 : unsigned y = backward_head[predecessor_arc[x]];
618 : assert(y > x);
619 : x = y;
620 0 : if(has_source_to_node_distance.is_set(x))
621 : return;
622 : }
623 0 : while(forward_predecessor_node[x] != invalid_id){
624 : assert(has_forward_predecessor.is_set(x));
625 0 : push(x);
626 0 : ++nodes_on_stack_with_forward_precessor_count;
627 0 : unsigned y = forward_predecessor_node[x];
628 : assert(y < x);
629 : x = y;
630 0 : if(has_source_to_node_distance.is_set(x))
631 : return;
632 : }
633 0 : source_to_node_distance[x] = Weight{}; // x is source node
634 : };
635 :
636 0 : auto expand_distances_from_source_to_node = [&](unsigned x){
637 0 : if(!has_source_to_node_distance.is_set(x)){
638 0 : push_non_reached_nodes(x);
639 0 : while(stack_size != 0){
640 0 : unsigned y = pop();
641 0 : if(nodes_on_stack_with_forward_precessor_count != 0){
642 0 : --nodes_on_stack_with_forward_precessor_count;
643 0 : single_forward_step_expand_distance_to_node(y);
644 : }else{
645 0 : single_backward_step_expand_distance_to_node(y);
646 : }
647 : }
648 : }
649 : };
650 :
651 0 : for(unsigned i=0; i<target_count; ++i){
652 0 : unsigned t = target_list[i];
653 : assert(t != invalid_id);
654 :
655 0 : if(!has_forward_predecessor.is_set(t) && predecessor_arc[t] == invalid_id){
656 0 : output[i] = Weight{}; // t is not reachable
657 : }else{
658 0 : expand_distances_from_source_to_node(t);
659 0 : output[i] = source_to_node_distance[t];
660 : }
661 : }
662 0 : }
663 : }
664 :
665 : template<class ExtraWeight, class LinkFunction, class TmpContainer, class DistContainer>
666 0 : ContractionHierarchyQuery& ContractionHierarchyQuery::get_extra_weight_distances_to_targets(
667 : const ExtraWeight&extra_weight,
668 : const LinkFunction&link,
669 : TmpContainer&tmp,
670 : DistContainer&dist
671 : ){
672 : assert(state == ContractionHierarchyQuery::InternalState::target_run);
673 :
674 0 : auto shortcut_weight = detail::make_shortcut_weights(extra_weight, link, *ch);
675 :
676 0 : detail::extract_distances_to_targets(
677 0 : backward_predecessor_node, many_to_many_source_or_target_count,
678 :
679 0 : was_forward_pushed,
680 0 : forward_predecessor_node, forward_predecessor_arc,
681 :
682 : shortcut_weight,
683 0 : ch->forward.first_out,
684 0 : ch->forward.head,
685 0 : ch->backward.first_out,
686 0 : ch->backward.head,
687 :
688 : tmp,
689 0 : was_backward_pushed,
690 :
691 : dist,
692 :
693 0 : backward_predecessor_arc,
694 :
695 : link
696 : );
697 :
698 0 : return *this;
699 : }
700 :
701 : template<class ExtraWeight, class LinkFunction, class TmpContainer, class DistContainer>
702 0 : ContractionHierarchyQuery& ContractionHierarchyQuery::get_extra_weight_distances_to_sources(
703 : const ExtraWeight&extra_weight,
704 : const LinkFunction&link,
705 : TmpContainer&tmp,
706 : DistContainer&dist
707 : ){
708 : assert(state == ContractionHierarchyQuery::InternalState::source_run);
709 :
710 0 : auto inverted_link = detail::inverse_link_function(link);
711 :
712 0 : auto shortcut_weight = detail::make_shortcut_weights(extra_weight, link, *ch);
713 0 : auto inverted_shortcut_weight = detail::inverse_shortcut_weights(shortcut_weight);
714 :
715 0 : detail::extract_distances_to_targets(
716 0 : forward_predecessor_node, many_to_many_source_or_target_count,
717 :
718 0 : was_backward_pushed,
719 0 : backward_predecessor_node, backward_predecessor_arc,
720 :
721 : inverted_shortcut_weight,
722 0 : ch->backward.first_out,
723 0 : ch->backward.head,
724 0 : ch->forward.first_out,
725 0 : ch->forward.head,
726 :
727 : tmp,
728 0 : was_forward_pushed,
729 :
730 : dist,
731 :
732 0 : forward_predecessor_arc,
733 :
734 : inverted_link
735 : );
736 :
737 0 : return *this;
738 : }
739 :
740 : extern template struct ContractionHierarchyExtraWeight<unsigned>;
741 : extern template struct ContractionHierarchyExtraWeight<int>;
742 : extern template ContractionHierarchyQuery& ContractionHierarchyQuery::get_extra_weight_distances_to_targets<std::vector<int>, SaturatedWeightAddition, std::vector<int>, std::vector<int>>(const std::vector<int>&, const SaturatedWeightAddition&, std::vector<int>&, std::vector<int>&);
743 : extern template ContractionHierarchyQuery& ContractionHierarchyQuery::get_extra_weight_distances_to_sources<std::vector<int>, SaturatedWeightAddition, std::vector<int>, std::vector<int>>(const std::vector<int>&, const SaturatedWeightAddition&, std::vector<int>&, std::vector<int>&);
744 : extern template ContractionHierarchyQuery& ContractionHierarchyQuery::get_extra_weight_distances_to_targets<std::vector<unsigned>, SaturatedWeightAddition, std::vector<unsigned>, std::vector<unsigned>>(const std::vector<unsigned>&, const SaturatedWeightAddition&, std::vector<unsigned>&, std::vector<unsigned>&);
745 : extern template ContractionHierarchyQuery& ContractionHierarchyQuery::get_extra_weight_distances_to_sources<std::vector<unsigned>, SaturatedWeightAddition, std::vector<unsigned>, std::vector<unsigned>>(const std::vector<unsigned>&, const SaturatedWeightAddition&, std::vector<unsigned>&, std::vector<unsigned>&);
746 : extern template ContractionHierarchyQuery& ContractionHierarchyQuery::get_extra_weight_distances_to_targets<ContractionHierarchyExtraWeight<int>, SaturatedWeightAddition, std::vector<int>, std::vector<int>>(const ContractionHierarchyExtraWeight<int>&, const SaturatedWeightAddition&, std::vector<int>&, std::vector<int>&);
747 : extern template ContractionHierarchyQuery& ContractionHierarchyQuery::get_extra_weight_distances_to_sources<ContractionHierarchyExtraWeight<int>, SaturatedWeightAddition, std::vector<int>, std::vector<int>>(const ContractionHierarchyExtraWeight<int>&, const SaturatedWeightAddition&, std::vector<int>&, std::vector<int>&);
748 : extern template ContractionHierarchyQuery& ContractionHierarchyQuery::get_extra_weight_distances_to_targets<ContractionHierarchyExtraWeight<unsigned>, SaturatedWeightAddition, std::vector<unsigned>, std::vector<unsigned>>(const ContractionHierarchyExtraWeight<unsigned>&, const SaturatedWeightAddition&, std::vector<unsigned>&, std::vector<unsigned>&);
749 : extern template ContractionHierarchyQuery& ContractionHierarchyQuery::get_extra_weight_distances_to_sources<ContractionHierarchyExtraWeight<unsigned>, SaturatedWeightAddition, std::vector<unsigned>, std::vector<unsigned>>(const ContractionHierarchyExtraWeight<unsigned>&, const SaturatedWeightAddition&, std::vector<unsigned>&, std::vector<unsigned>&);
750 : extern template ContractionHierarchyExtraWeight<unsigned>& ContractionHierarchyExtraWeight<unsigned>::reset<std::vector<unsigned>, SaturatedWeightAddition>(const ContractionHierarchy&ch, const std::vector<unsigned>&, const SaturatedWeightAddition&);
751 : extern template ContractionHierarchyExtraWeight<int>& ContractionHierarchyExtraWeight<int>::reset<std::vector<int>, SaturatedWeightAddition>(const ContractionHierarchy&ch, const std::vector<int>&, const SaturatedWeightAddition&);
752 : extern template unsigned ContractionHierarchyQuery::get_extra_weight_distance<std::vector<unsigned>,SaturatedWeightAddition>(const std::vector<unsigned>&, const SaturatedWeightAddition&);
753 : extern template int ContractionHierarchyQuery::get_extra_weight_distance<std::vector<int>,SaturatedWeightAddition>(const std::vector<int>&, const SaturatedWeightAddition&);
754 : extern template unsigned ContractionHierarchyQuery::get_extra_weight_distance<ContractionHierarchyExtraWeight<unsigned>,SaturatedWeightAddition>(const ContractionHierarchyExtraWeight<unsigned>&, const SaturatedWeightAddition&);
755 : extern template int ContractionHierarchyQuery::get_extra_weight_distance<ContractionHierarchyExtraWeight<int>,SaturatedWeightAddition>(const ContractionHierarchyExtraWeight<int>&, const SaturatedWeightAddition&);
756 :
757 : } // namespace RoutingKit
758 :
759 : #endif
|
