Line data    Source code

       1              : #ifndef ROUTING_KIT_NESTED_DISSECTION_H
       2              : #define ROUTING_KIT_NESTED_DISSECTION_H
       3              : 
       4              : #include <routingkit/bit_vector.h>
       5              : #include <routingkit/constants.h>
       6              : 
       7              : #include <vector>
       8              : #include <stdexcept>
       9              : #include <functional>
      10              : #include <string>
      11              : 
      12              : namespace RoutingKit{
      13              : 
      14              : struct GraphFragment{
      15              :         std::vector<unsigned>global_node_id;
      16              :         std::vector<unsigned>first_out;
      17              :         std::vector<unsigned>tail;
      18              :         std::vector<unsigned>head;
      19              :         std::vector<unsigned>back_arc;
      20              : 
      21              :         unsigned node_count()const{
      22      1935654 :                 return global_node_id.size();
      23              :         }
      24              : 
      25              :         unsigned arc_count()const{
      26       194122 :                 return tail.size();
      27              :         }
      28              : };
      29              : 
      30              : GraphFragment make_graph_fragment(unsigned node_count, const std::vector<unsigned>&tail, const std::vector<unsigned>&head);
      31              : 
      32              : std::vector<GraphFragment>decompose_graph_fragment_into_connected_components(GraphFragment fragment);
      33              : 
      34        37240 : struct CutSide{
      35              :         unsigned node_on_side_count;
      36              :         unsigned cut_size;
      37              :         BitVector is_node_on_side;
      38              : };
      39              : 
      40              : void pick_smaller_side(CutSide&cut);
      41              : 
      42              : class BlockingFlow{
      43              : private:
      44              :         const GraphFragment*fragment;
      45              :         BitVector is_source;
      46              :         BitVector is_target;
      47              : 
      48              :         unsigned flow_intensity;
      49              :         
      50              :         BitVector is_arc_saturated;
      51              :         BitVector is_arc_blocked;
      52              : 
      53              :         bool is_finished_flag;
      54              : public:
      55              :         BlockingFlow(){}
      56              :         BlockingFlow(const GraphFragment&, BitVector is_source, BitVector is_target);
      57              : 
      58              :         CutSide get_source_cut();
      59              :         CutSide get_target_cut();
      60              :         CutSide get_balanced_cut();
      61              : 
      62              :         void advance();
      63              : 
      64              :         unsigned get_current_flow_intensity()const{
      65        89244 :                 return flow_intensity;
      66              :         }
      67              : 
      68              :         bool is_finished()const{
      69        89244 :                 return is_finished_flag;
      70              :         }
      71              : };
      72              : 
      73              : CutSide inertial_flow(
      74              :         const GraphFragment&fragment,
      75              :         unsigned min_balance,
      76              :         const std::vector<float>&latitude, const std::vector<float>&longitude,
      77              :         const std::function<void(const std::string&)>&log_message = [](const std::string&){}
      78              : );
      79              : 
      80              : CutSide inertial_flow(
      81              :         const GraphFragment&fragment,
      82              :         const std::vector<float>&latitude, const std::vector<float>&longitude,
      83              :         const std::function<void(const std::string&)>&log_message = [](const std::string&){}
      84              : );
      85              : 
      86              : BitVector derive_separator_from_cut(const GraphFragment&fragment, const BitVector&cut);
      87              : 
      88         5504 : struct SeparatorDecomposition{
      89              :   struct Node{
      90              :     unsigned left_child;
      91              :     unsigned right_sibling;
      92              :     unsigned first_separator_vertex;
      93              :     unsigned last_separator_vertex;
      94              :   };
      95              : 
      96              :   std::vector<Node>tree;
      97              :   std::vector<unsigned>order;
      98              : };
      99              : 
     100              : SeparatorDecomposition compute_separator_decomposition(
     101              :         GraphFragment fragment,
     102              :         const std::function<BitVector(const GraphFragment&)>&compute_separator,
     103              :         const std::function<void(const std::string&)>&log_message = [](const std::string&){}
     104              : );
     105              : 
     106              : std::vector<unsigned>compute_nested_node_dissection_order(
     107              :         GraphFragment fragment,
     108              :         const std::function<BitVector(const GraphFragment&)>&compute_separator,
     109              :         const std::function<void(const std::string&)>&log_message = [](const std::string&){}
     110              : );
     111              : 
     112              : std::vector<unsigned>compute_nested_node_dissection_order_using_inertial_flow(
     113              :         unsigned node_count,
     114              :         const std::vector<unsigned>&tail, const std::vector<unsigned>&head,
     115              :         const std::vector<float>&latitude, const std::vector<float>&longitude,
     116              :         const std::function<void(const std::string&)>&log_message = [](const std::string&){}
     117              : );
     118              : 
     119              : } // RoutingKit
     120              : 
     121              : #endif
     122              :