Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifndef DIJKSTRA_HPP_
- #define DIJKSTRA_HPP_
- #include <string>
- #include <iostream>
- #include <fstream>
- #include <sstream>
- #include <limits> //Biggest int: std::numeric_limits<int>::max()
- #include "array_queue.hpp"
- #include "array_stack.hpp"
- #include "heap_adjustable_hash_priority_queue.hpp"
- #include "hash_graph.hpp"
- namespace ics {
- class Info {
- public:
- Info() { }
- Info(std::string a_node) : node(a_node) { }
- bool operator==(const Info &rhs) const { return node == rhs.node && cost == rhs.cost && from == rhs.from; }
- bool operator!=(const Info &rhs) const { return !(*this == rhs); }
- friend std::ostream &operator<<(std::ostream &outs, const Info &i) {
- outs << "Info[" << i.node << "," << i.cost << "," << i.from << "]";
- return outs;
- }
- //Public instance variable definitions
- std::string node = "?";
- int cost = std::numeric_limits<int>::max();
- std::string from = "?";
- };
- bool gt_info(const Info &a, const Info &b) { return a.cost < b.cost; }
- int hash_info(const Info &a){return (a.cost == std::numeric_limits<int>::max()) ? a.cost : 0;}
- //Put needed hashing functions here
- typedef ics::HashGraph<int> DistGraph;
- typedef ics::HeapAdjustableHashPriorityQueue<Info, gt_info,hash_info> CostPQ;
- typedef ics::HashOpenMap<std::string, Info, DistGraph::hash_str> CostMap;
- typedef ics::pair<std::string, Info> CostMapEntry;
- //Return the final_map as specified in the lecture-note description of
- // extended Dijkstra algorithm
- CostMap extended_dijkstra(const DistGraph &g, std::string start_node) {
- CostMap answer_map;
- CostMap info_map;
- for(auto i: g.all_nodes()) {
- info_map[i.first] = Info();
- }
- info_map[start_node].cost = 0;
- CostPQ info_pq;
- for(auto i:info_map){
- info_pq.enqueue(i.second);
- }
- while(!info_map.empty()){
- Info current = info_pq.dequeue();
- if(current.cost == std::numeric_limits<int>::max()){
- break;
- }
- std::string min_node = current.node;
- int min_cost = current.cost;
- info_map.erase(min_node);
- answer_map.put(min_node,current);
- for(const auto& d: g.out_nodes(min_node)){
- if(!answer_map.has_key(d)){
- Info old = info_map[d];
- if( info_map[d].cost == std::numeric_limits<int>::max() || info_map[d].cost < (min_cost + g.edge_value(min_node,d))){
- info_map[min_node].cost = info_map[d].cost;
- info_map[d].from = min_node;
- info_pq.update(old,info_map[d]);
- }
- }
- }
- }
- return answer_map;
- }
- //Return a queue whose front is the start node (implicit in answer_map) and whose
- // rear is the end node
- ArrayQueue <std::string> recover_path(const CostMap &answer_map, std::string end_node) {
- CostMap temp = answer_map;
- ArrayStack <std::string>tempStack;
- std::string counter = end_node;
- while(temp[counter].from != "?"){
- tempStack.push(counter);
- counter = temp[counter].from;
- }
- tempStack.push(counter);
- ArrayQueue <std::string> minPath;
- while(!tempStack.empty()){
- minPath.enqueue(tempStack.pop());
- }
- return minPath;
- }
- }
- #endif /* DIJKSTRA_HPP_ */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement