Line data    Source code

       1              : #ifndef ROUTING_KIT_CUSTOMIZABLE_CONSTRACTION_HIERARCHY_H
       2              : #define ROUTING_KIT_CUSTOMIZABLE_CONSTRACTION_HIERARCHY_H
       3              : 
       4              : #include <routingkit/constants.h>
       5              : #include <routingkit/id_set_queue.h>
       6              : #include <routingkit/bit_vector.h>
       7              : #include <routingkit/id_mapper.h>
       8              : 
       9              : #include <vector>
      10              : #include <string>
      11              : #include <functional>
      12              : 
      13              : namespace RoutingKit{
      14              : 
      15              : class ContractionHierarchy;
      16              : 
      17              : struct CustomizableContractionHierarchy{
      18          849 :         CustomizableContractionHierarchy(){}
      19              : 
      20              :         CustomizableContractionHierarchy(std::vector<unsigned>order, std::vector<unsigned>tail, std::vector<unsigned>head, std::function<void(const std::string&)>log_message = [](const std::string&){}, bool filter_always_inf_arcs = false);
      21              : 
      22              :         unsigned node_count()const{
      23        92247 :                 return rank.size();
      24              :         }
      25              : 
      26              :         unsigned input_arc_count() const {
      27              :                 return input_arc_to_cch_arc.size();
      28              :         }
      29              : 
      30              :         unsigned cch_arc_count() const {
      31      2220542 :                 return up_head.size();
      32              :         }
      33              : 
      34              : // private:
      35              :         std::vector<unsigned>order;
      36              :         std::vector<unsigned>rank;
      37              :         
      38              :         std::vector<unsigned>elimination_tree_parent;
      39              :         
      40              :         std::vector<unsigned>up_first_out;
      41              :         std::vector<unsigned>up_head;
      42              :         std::vector<unsigned>up_tail;
      43              :         
      44              :         std::vector<unsigned>down_first_out;
      45              :         std::vector<unsigned>down_head;
      46              :         std::vector<unsigned>down_to_up;
      47              :         
      48              :         std::vector<unsigned>input_arc_to_cch_arc;
      49              :         BitVector is_input_arc_upward;
      50              : 
      51              :         BitVector does_cch_arc_have_input_arc;
      52              :         LocalIDMapper does_cch_arc_have_input_arc_mapper;
      53              : 
      54              :         std::vector<unsigned>forward_input_arc_of_cch;
      55              :         std::vector<unsigned>backward_input_arc_of_cch;
      56              : 
      57              :         BitVector does_cch_arc_have_extra_input_arc;
      58              :         LocalIDMapper does_cch_arc_have_extra_input_arc_mapper;
      59              : 
      60              :         std::vector<unsigned>first_extra_forward_input_arc_of_cch;
      61              :         std::vector<unsigned>first_extra_backward_input_arc_of_cch;
      62              :         
      63              :         std::vector<unsigned>extra_forward_input_arc_of_cch;
      64              :         std::vector<unsigned>extra_backward_input_arc_of_cch;
      65              : };
      66              : 
      67         2882 : struct CustomizableContractionHierarchyMetric{
      68              :         CustomizableContractionHierarchyMetric(){}
      69              :         CustomizableContractionHierarchyMetric(const CustomizableContractionHierarchy&cch, const unsigned*input_weight);
      70              :         CustomizableContractionHierarchyMetric(const CustomizableContractionHierarchy&cch, const std::vector<unsigned>&input_weight);
      71              : 
      72              :         CustomizableContractionHierarchyMetric& reset(const CustomizableContractionHierarchy&cch, const unsigned*input_weight);
      73              :         CustomizableContractionHierarchyMetric& reset(const CustomizableContractionHierarchy&cch, const std::vector<unsigned>&input_weight);
      74              : 
      75              :         CustomizableContractionHierarchyMetric& reset(const unsigned*input_weight);
      76              :         CustomizableContractionHierarchyMetric& reset(const std::vector<unsigned>&input_weight);
      77              : 
      78              :         CustomizableContractionHierarchyMetric& customize();
      79              : 
      80              :         ContractionHierarchy build_contraction_hierarchy_using_perfect_witness_search();
      81              : 
      82              : // private:
      83              :         std::vector<unsigned>forward;
      84              :         std::vector<unsigned>backward;
      85              :         const CustomizableContractionHierarchy*cch;
      86              :         const unsigned*input_weight;
      87              : 
      88              : };
      89              : 
      90              : struct CustomizableContractionHierarchyParallelization{
      91              :         CustomizableContractionHierarchyParallelization(){}
      92              :         explicit CustomizableContractionHierarchyParallelization(const CustomizableContractionHierarchy&cch);
      93              : 
      94              :         CustomizableContractionHierarchyParallelization& reset(const CustomizableContractionHierarchy&cch){
      95              :                 *this = CustomizableContractionHierarchyParallelization(cch);
      96              :                 return *this;
      97              :         }
      98              : 
      99              : 
     100              :         CustomizableContractionHierarchyParallelization& customize(CustomizableContractionHierarchyMetric&metric);
     101              :         CustomizableContractionHierarchyParallelization& customize(CustomizableContractionHierarchyMetric&metric, unsigned thread_count);
     102              : 
     103              : // private:
     104              :         std::vector<unsigned>first_arc_of_level;
     105              :         std::vector<unsigned>arcs_ordered_by_level;
     106              :         const CustomizableContractionHierarchy*cch;
     107              : 
     108              : };
     109              : 
     110         1449 : struct CustomizableContractionHierarchyPartialCustomization{
     111              :         CustomizableContractionHierarchyPartialCustomization(){}
     112              :         explicit CustomizableContractionHierarchyPartialCustomization(const CustomizableContractionHierarchy&cch);
     113              : 
     114              :         CustomizableContractionHierarchyPartialCustomization&reset();
     115              :         CustomizableContractionHierarchyPartialCustomization&reset(const CustomizableContractionHierarchy&cch);
     116              : 
     117              :         CustomizableContractionHierarchyPartialCustomization&update_arc(unsigned xy);
     118              :         CustomizableContractionHierarchyPartialCustomization&customize(CustomizableContractionHierarchyMetric&metric);
     119              : 
     120              : // private:
     121              :         IDSetMinQueue q;
     122              :         const CustomizableContractionHierarchy*cch;
     123              : };
     124              : 
     125              : struct CustomizableContractionHierarchyQuery{
     126          902 :         CustomizableContractionHierarchyQuery(){}
     127              :         explicit CustomizableContractionHierarchyQuery(const CustomizableContractionHierarchyMetric&metric);
     128              : 
     129              :         CustomizableContractionHierarchyQuery&reset();
     130              :         CustomizableContractionHierarchyQuery&reset(const CustomizableContractionHierarchyMetric&metric);
     131              : 
     132              :         CustomizableContractionHierarchyQuery&add_source(unsigned s, unsigned dist_to_s = 0);
     133              :         CustomizableContractionHierarchyQuery&add_target(unsigned t, unsigned dist_to_t = 0);
     134              : 
     135              :         CustomizableContractionHierarchyQuery&run();
     136              : 
     137              :         unsigned get_used_source();
     138              :         unsigned get_used_target();
     139              : 
     140              :         unsigned get_distance();
     141              :         std::vector<unsigned> get_node_path();
     142              :         std::vector<unsigned> get_arc_path();
     143              : 
     144              :         // One-To-Many
     145              :         CustomizableContractionHierarchyQuery& reset_source();
     146              :         CustomizableContractionHierarchyQuery& pin_targets(const std::vector<unsigned>&);
     147              :         CustomizableContractionHierarchyQuery& run_to_pinned_targets();
     148              : 
     149              :         CustomizableContractionHierarchyQuery& get_distances_to_targets(unsigned*dist);
     150              :         std::vector<unsigned> get_distances_to_targets();
     151              : 
     152              :         // Many-To-One
     153              :         CustomizableContractionHierarchyQuery& reset_target();
     154              :         CustomizableContractionHierarchyQuery& pin_sources(const std::vector<unsigned>&);
     155              :         CustomizableContractionHierarchyQuery& run_to_pinned_sources();
     156              : 
     157              :         CustomizableContractionHierarchyQuery& get_distances_to_sources(unsigned*dist);
     158              :         std::vector<unsigned> get_distances_to_sources();
     159              : 
     160              : // private:
     161              :         std::vector<unsigned>forward_tentative_distance, backward_tentative_distance;
     162              :         std::vector<unsigned>source_node;
     163              :         std::vector<unsigned>source_elimination_tree_end;
     164              :         std::vector<unsigned>target_node;
     165              :         std::vector<unsigned>target_elimination_tree_end;
     166              : 
     167              :         std::vector<unsigned>forward_predecessor_node, backward_predecessor_node;
     168              : 
     169              :         std::vector<bool>in_forward_search_space, in_backward_search_space;
     170              :         
     171              :         unsigned shortest_path_meeting_node;
     172              : 
     173              :         const CustomizableContractionHierarchy*cch;
     174              :         const CustomizableContractionHierarchyMetric*metric;
     175              :         unsigned state;
     176              : };
     177              : 
     178              : } // namespace RoutingKit
     179              : 
     180              : #endif