API tools faq
paste
Advertisement
oster_man

transport_router.h

oster_man
Dec 25th, 2023
142
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 13.74 KB | Source Code | 0 0
raw download clone embed print report
  1. #pragma once
  2. #include "domain.h"
  3. #include "graph.h"
  4. #include "router.h"
  5. #include "transport_catalogue.h"
  6. #include <cmath>
  7. #include <memory>
  8. #include <set>
  9. #include <list>
  10. #include <map>
  11. #include <variant>
  12.  
  13. constexpr size_t begin_pseudo_vertex = -1;
  14.  
  15. template<typename KEY,typename VALUE>
  16. const std::map<VALUE,KEY> InvertMap(std::map<KEY,VALUE>& dictionary){
  17.     std::map<VALUE,KEY> result;
  18.     for (auto& [key,value]:dictionary)
  19.         result[value]=key;
  20.     return std::move(result);
  21. }
  22.  
  23. using namespace std::string_view_literals;
  24.  
  25. namespace Catalogue{
  26.     namespace Routering{
  27.  
  28.         using Minutes = double;
  29.         struct Settings{
  30.             double bus_wait_time=0;
  31.             double bus_velocity=0;
  32.         };
  33.  
  34.         using StopName = std::string_view;
  35.         using BusName = std::string_view;
  36.  
  37.         class RouterManager{
  38.             using Graph = graph::DirectedWeightedGraph<Minutes>;
  39.            
  40.             struct WaitCommand{
  41.                 StopName stop_name_;
  42.                 Minutes time_;
  43.  
  44.                 WaitCommand& SetTimeWaiting(Minutes time){
  45.                     time_=time;
  46.                     return *this;
  47.                 }
  48.  
  49.                 WaitCommand& SetStopName(StopName name){
  50.                     stop_name_=name;
  51.                     return *this;
  52.                 }
  53.             };
  54.  
  55.             struct BusProceedCommand{
  56.                 BusName bus_name_;
  57.                 int span_count_;
  58.                 Minutes time_;
  59.  
  60.                 BusProceedCommand& SetTime(Minutes time){
  61.                     time_=time;
  62.                     return *this;
  63.                 }
  64.  
  65.                 BusProceedCommand& SetSpanCount(size_t span_count){
  66.                     span_count_=span_count;
  67.                     return *this;
  68.                 }
  69.  
  70.                 BusProceedCommand& SetBusName(BusName name){
  71.                     bus_name_=name;
  72.                     return *this;
  73.                 }
  74.             };
  75.             public:
  76.             struct Command: private std::variant<nullptr_t,WaitCommand, BusProceedCommand>{
  77.                 using variant::variant;
  78.                
  79.                  bool IsWaitCommand() const{
  80.                     if(std::holds_alternative<WaitCommand>(*this))
  81.                         return true;
  82.                     else return false;
  83.                 }
  84.  
  85.                 bool IsBusCommand() const{
  86.                     if(std::holds_alternative<BusProceedCommand>(*this))
  87.                         return true;
  88.                     else return false;
  89.                 }
  90.  
  91.                 BusProceedCommand& AsBusCommand(){
  92.                     return std::get<BusProceedCommand>(*this);
  93.                 }
  94.  
  95.                 WaitCommand& AsWaitCommand(){
  96.                     return std::get<WaitCommand>(*this);
  97.                 }
  98.  
  99.                 std::string_view GetBusName(){
  100.                     if(IsBusCommand())
  101.                         return AsBusCommand().bus_name_;
  102.                     else
  103.                         throw std::logic_error("Not bus command");
  104.                 }
  105.  
  106.                 std::string_view GetStopName(){
  107.                     if(IsWaitCommand())
  108.                         return AsWaitCommand().stop_name_;
  109.                     else
  110.                         throw std::logic_error("Not wait command");
  111.                 }
  112.  
  113.                 int GetSpanCount(){
  114.                     if (IsBusCommand())
  115.                         return AsBusCommand().span_count_;
  116.                     else
  117.                         throw std::logic_error("Not bus command");
  118.                 }
  119.  
  120.                 WaitCommand& SetTimeWaiting(Minutes time){
  121.                     return AsWaitCommand().SetTimeWaiting(time);
  122.                 }
  123.  
  124.                 WaitCommand& SetStopName(StopName name){
  125.                     return AsWaitCommand().SetStopName(name);
  126.                 }
  127.  
  128.                 BusProceedCommand& SetBusName(BusName name){
  129.                     return AsBusCommand().SetBusName(name);
  130.                 }
  131.             };
  132.             struct ResultRouteOptimization{
  133.                 Minutes summary_time;
  134.                 std::optional<std::vector<Command>> commands;
  135.             };
  136.  
  137.             RouterManager(std::shared_ptr<Transport> catalogue):catalogue_(catalogue){
  138.             }
  139.  
  140.             ResultRouteOptimization SearchOptimalRoute(StopName from, StopName to) const{
  141.                 if(vertex_ids_by_wait_stops.count(from)&&vertex_ids_by_wait_stops.count(to)){
  142.                     if(from!=to){
  143.                         std::optional<graph::Router<Catalogue::Routering::Minutes>::RouteInfo> result = router_->BuildRoute(vertex_ids_by_wait_stops.at(from),vertex_ids_by_wait_stops.at(to));
  144.                         return {result->weight,Reinterpreter(result)};
  145.                     }
  146.                     else return {0.,std::vector<Command>()};
  147.                 }
  148.                 else
  149.                     return {};
  150.             }
  151.  
  152.             ResultRouteOptimization SearchOptimalRoute(const Stop& from, const Stop& to) const{
  153.                 return std::move(SearchOptimalRoute(from.name_,to.name_));
  154.             }
  155.  
  156.             RouterManager& SetRouterSettings(Settings settings){
  157.                 this->sets_ = settings;
  158.                 return *this;
  159.             }
  160.  
  161.             void InitRouter(){
  162.                 int number_vertexes=0;
  163.                 for(auto& [bus_name, bus_item]:catalogue_->GetBusData())
  164.                     number_vertexes+=bus_item.unique_stops_+(bus_item.stops_.size()-bus_item.unique_stops_)*2;
  165.  
  166.                 graph_=std::make_unique<Graph>(catalogue_->GetStopData().size()*3);
  167.                 InitEdgesWaitStops();
  168.                 InitVertexIdAndTimesBuses();
  169.                 router_=std::make_unique<graph::Router<Minutes>>(*graph_);
  170.             }
  171.  
  172.             private:
  173.  
  174.             std::optional<std::vector<Command>> Reinterpreter(std::optional<graph::Router<Catalogue::Routering::Minutes>::RouteInfo> data) const{
  175.                 std::vector<Command> commands;
  176.                 if(data.has_value()){
  177.                     commands.reserve(data->edges.size()+1);
  178.  
  179.                     std::vector<graph::Edge<Minutes>> edges;
  180.                     edges.reserve(data->edges.size());
  181.                     for(auto& edge:data->edges)
  182.                         edges.push_back(graph_->GetEdge(edge));
  183.  
  184.                     for(auto& edge:edges){
  185.                         if(IsWaiting(edge)){
  186.                            commands.push_back({WaitCommand().SetStopName(stops_by_vertex_ids.at(edge.to)).
  187.                                                 SetTimeWaiting(sets_.bus_wait_time)});
  188.                         }
  189.                         else if(IsBusProceed(edge)){
  190.                             commands.push_back({BusProceedCommand().SetBusName(buses_by_vertex_ids.at(edge.from).at(edge.to)).
  191.                                             SetTime(edge.weight).SetSpanCount(span_count.at(edge.from).at(edge.to))});
  192.                         }                            
  193.                         else
  194.                             throw std::logic_error("Error action defining by router");
  195.                     }
  196.                     if(!commands.empty()){
  197.                         assert(commands.front().IsWaitCommand());
  198.                         assert(commands.back().IsBusCommand());
  199.                     }
  200.                     return commands;
  201.                 }
  202.                 return std::nullopt;
  203.             }
  204.  
  205.             bool IsWaiting(graph::Edge<Minutes> edge) const{
  206.                 if(stops_by_vertex_ids.count(edge.from) && stops_by_vertex_ids.count(edge.to)){
  207.                     StopName from_name = stops_by_vertex_ids.at(edge.from);
  208.                     StopName to_name = stops_by_vertex_ids.at(edge.to);
  209.                     if(vertex_ids_by_wait_stops.at(from_name)==edge.from && vertex_ids_by_bus_stops.at(to_name)==edge.to)
  210.                         return true;
  211.                     else return false;
  212.                 }
  213.                 else return false;
  214.             }
  215.  
  216.             bool IsBusProceed(graph::Edge<Minutes> edge) const{
  217.                 if(stops_by_vertex_ids.count(edge.from) && stops_by_vertex_ids.count(edge.to)){
  218.                     StopName from_name = stops_by_vertex_ids.at(edge.from);
  219.                     StopName to_name = stops_by_vertex_ids.at(edge.to);
  220.                     if(vertex_ids_by_bus_stops.at(from_name)==edge.from && vertex_ids_by_wait_stops.at(to_name)==edge.to)
  221.                         return true;
  222.                     else return false;
  223.                 }
  224.                 else return false;
  225.             }
  226.  
  227.             void InitVertexIdAndTimesBuses(){ //инициализация псевдовершин (вспомогательные вершины, разделяющие ожидание и время в пути)
  228.                 const auto& buses = catalogue_->GetBusData();
  229.                 for (auto& [bus_name,bus_object]:buses){
  230.                     for (auto stop_ptr1=bus_object.stops_.begin();stop_ptr1!=bus_object.stops_.end()-1;++stop_ptr1){
  231.                         for (auto stop_ptr2=stop_ptr1+1;stop_ptr2!=bus_object.stops_.end();++stop_ptr2){
  232.                             Minutes time_direct = 0;
  233.                             Minutes time_reverse = 0;
  234.                             if((*stop_ptr1)->name_=="Biryusinka" && (*stop_ptr2)->name_=="TETs 26"){
  235.                                     int i=0;
  236.                                     i=i;
  237.                                 }
  238.                             for (auto route_iter = stop_ptr1;route_iter<stop_ptr2;++route_iter){
  239.                                 time_direct += ComputeTime((*route_iter)->name_,(*(route_iter+1))->name_);
  240.                                 time_reverse+=ComputeTime((*(route_iter+1))->name_,(*route_iter)->name_);
  241.                             }
  242.                             span_count[vertex_ids_by_bus_stops.at((*stop_ptr1)->name_)]
  243.                                 [vertex_ids_by_wait_stops.at((*stop_ptr2)->name_)]=std::abs(stop_ptr2-stop_ptr1);
  244.                            
  245.                             graph_->AddEdge({vertex_ids_by_bus_stops.at((*stop_ptr1)->name_),
  246.                                             vertex_ids_by_wait_stops.at((*stop_ptr2)->name_),
  247.                                             time_direct});
  248.                                 AddBusByVertexesDefinition((*stop_ptr1)->name_,
  249.                                                            (*stop_ptr2)->name_,
  250.                                                            bus_name);
  251.                             if(!bus_object.IsRoundTrip()){
  252.                                 graph_->AddEdge({vertex_ids_by_bus_stops.at((*stop_ptr2)->name_),
  253.                                                 vertex_ids_by_wait_stops.at((*stop_ptr1)->name_),
  254.                                                 time_reverse});
  255.                                 AddBusByVertexesDefinition((*stop_ptr2)->name_,
  256.                                                            (*stop_ptr1)->name_,
  257.                                                            bus_name);
  258.                                 span_count[vertex_ids_by_bus_stops.at((*stop_ptr2)->name_)]
  259.                                 [vertex_ids_by_wait_stops.at((*stop_ptr1)->name_)]=std::abs(stop_ptr2-stop_ptr1);
  260.                                 if(time_direct==0){
  261.                                     int i=0;
  262.                                     i=i;
  263.                                 }
  264.                             }
  265.                         }
  266.                     }
  267.                 }
  268.             }
  269.  
  270.             void InitEdgesWaitStops(){ //инициализация "супер-вершин" (управляющие вершины - фактические вершины, относительно которых будут делаться расчёты)
  271.                 graph::VertexId vertex_id=0;
  272.                 auto& stops = catalogue_->GetStopData();
  273.                 for(const auto& [stop_name,stop_info]:stops){
  274.                     AddWaitVertexId(stop_name,vertex_id);
  275.                     AddBusVertexId(stop_name,vertex_id+1);
  276.                     graph_->AddEdge({
  277.                         vertex_id,
  278.                         ++vertex_id,
  279.                         static_cast<double>(sets_.bus_wait_time)
  280.                         });
  281.                     ++vertex_id;
  282.                 }
  283.             }
  284.  
  285.             Minutes ComputeTime(StopName from, StopName to) const{
  286.                 Minutes dist = static_cast<double>(catalogue_->GetDistance(from,to))/sets_.bus_velocity/100.*6.;
  287.                 return dist;
  288.             }
  289.  
  290.             graph::VertexId AddWaitVertexId(StopName stop_name,graph::VertexId id){
  291.                 stops_by_vertex_ids[id]=stop_name;
  292.                 return vertex_ids_by_wait_stops[stop_name]=id;
  293.             }
  294.  
  295.             graph::VertexId AddBusVertexId(StopName stop_name, graph::VertexId id){
  296.                 stops_by_vertex_ids[id]=stop_name;
  297.                 return vertex_ids_by_bus_stops[stop_name]=id;
  298.             }
  299.  
  300.             void AddBusByVertexesDefinition(StopName from, StopName to, BusName bus_name){
  301.                 buses_by_vertex_ids[vertex_ids_by_bus_stops.at(from)][vertex_ids_by_wait_stops.at(to)]=bus_name;
  302.             }
  303.  
  304.             Settings sets_;
  305.             std::shared_ptr<Transport> catalogue_;
  306.             std::unique_ptr<Graph> graph_;
  307.             std::unique_ptr<graph::Router<Minutes>> router_;
  308.             std::map<StopName,graph::VertexId> vertex_ids_by_wait_stops;
  309.             std::map<StopName,graph::VertexId> vertex_ids_by_bus_stops;
  310.             std::map<graph::VertexId,StopName> stops_by_vertex_ids;
  311.             std::map<graph::VertexId,std::map<graph::VertexId,size_t>> span_count;
  312.             std::map<graph::VertexId,std::map<graph::VertexId,BusName>> buses_by_vertex_ids;
  313.         };
  314.     }
  315. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!