pompeiifreckles

Fuck C++

Oct 22nd, 2020
1,239
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<queue>
  3. #include<map>
  4. #include<set>
  5. #include<vector>
  6. #include<climits>
  7. #include<functional>
  8.  
  9. // Node and Edge Structures
  10. class Node {
  11.     private:
  12.     Node *predecessor;
  13.  
  14.     public:
  15.     const char value;
  16.     int hops;
  17.  
  18.     Node(char c)
  19.     : value(std::toupper(c)), hops(INT_MAX), predecessor(nullptr) {}
  20.  
  21.     void setPredecessor(Node& n) {
  22.         predecessor = &n;
  23.     }
  24.  
  25.     const Node * getPredecessor() {
  26.         if(predecessor != nullptr)
  27.             return predecessor;
  28.         return nullptr;
  29.     }
  30. };
  31.  
  32. class Edge {
  33.     public:
  34.     Node& from;
  35.     Node& to;
  36.     const int weight;
  37. };
  38.  
  39. // Create a graph
  40. Node source('S');                   // Create a source node
  41.  
  42. std::map<char, Node&> all_nodes = {
  43.     {'T', *(new Node('T'))},
  44.     {'Y', *(new Node('Y'))},
  45.     {'Z', *(new Node('Z'))},
  46.     {'X', *(new Node('X'))},
  47. };
  48.  
  49. std::vector<Edge> all_edges = {
  50.     {.from = source, .to = all_nodes.at('T'), .weight = 10},
  51.     {.from = source, .to = all_nodes.at('Y'), .weight = 5},
  52.     {.from = all_nodes.at('T'), .to = all_nodes.at('Y'), .weight = 2},
  53.     {.from = all_nodes.at('Y'), .to = all_nodes.at('T'), .weight = 3},
  54.     {.from = all_nodes.at('T'), .to = all_nodes.at('X'), .weight = 1},
  55.     {.from = all_nodes.at('Y'), .to = all_nodes.at('X'), .weight = 9},
  56.     {.from = all_nodes.at('Z'), .to = all_nodes.at('X'), .weight = 6},
  57.     {.from = all_nodes.at('X'), .to = all_nodes.at('Z'), .weight = 4},
  58.     {.from = all_nodes.at('Y'), .to = all_nodes.at('Z'), .weight = 2},
  59.     {.from = all_nodes.at('Z'), .to = source, .weight = 7},
  60. };
  61.  
  62.  
  63. // Supporting class and functions
  64. class queue_cmp {
  65.     public:
  66.     bool operator()(const Node& a, const Node& b) {
  67.         return a.hops>b.hops;
  68.     }
  69. };
  70.  
  71. class set_cmp {
  72.     public:
  73.     bool operator()(const Node& a, const Node& b) {
  74.         return a.hops != b.hops;
  75.     }
  76. };
  77.  
  78. // Find adjacent Edges
  79. std::vector<std::reference_wrapper<Edge>> r_vector;
  80. std::vector<std::reference_wrapper<Edge>>& adjacentEdges(const Node& n) {
  81.     std::cout<<n.value<<":"<<std::endl;
  82.     r_vector.clear();
  83.     for(auto& e: all_edges) {
  84.         if(e.from.value == n.value) {
  85.             r_vector.push_back(e);
  86.             std::cout<<e.from.value<<" -> "<<e.to.value<<"\t"<<e.weight<<std::endl;
  87.         }
  88.     }
  89.  
  90.     std::cout<<std::endl;
  91.  
  92.     return r_vector;
  93. }
  94.  
  95.  
  96.  
  97. int main() {
  98.     // Initialize source node
  99.     source.hops = 0;
  100.  
  101.     std::set<std::reference_wrapper<Node>, set_cmp> dijkstra_Set;
  102.     std::priority_queue<Node, std::vector<std::reference_wrapper<Node>>, queue_cmp> dijkstra_Queue;
  103.     dijkstra_Queue.push(source);
  104.     for(auto& v: all_nodes) {
  105.         dijkstra_Queue.push(v.second);
  106.     }
  107.  
  108.  
  109.     while(!dijkstra_Queue.empty()) {
  110.         Node& u = dijkstra_Queue.top().get();
  111.         dijkstra_Queue.pop();
  112.         dijkstra_Set.emplace(u);
  113.  
  114.         // std::cout<<u.value<<": ";        
  115.         for(Edge& e: adjacentEdges(u)) {
  116.             // std::cout<<e.to.value<<" ";
  117.             // Relax(u, v, w)
  118.             if(e.to.hops > u.hops + e.weight) {
  119.                 e.to.hops = u.hops + e.weight;
  120.                 e.to.setPredecessor(u);          
  121.  
  122.                 // std::cout<<u.value<<" -> "<<e.to.value<<std::endl;
  123.             }    
  124.         }
  125.         // std::cout<<std::endl;
  126.     }
  127.  
  128.     for(auto& v: all_nodes) {
  129.         if(v.second.getPredecessor() != nullptr)
  130.         std::cout<<v.second.getPredecessor()->value<<" -> "<<v.second.value<<std::endl;
  131.     }
  132.  
  133. }
RAW Paste Data