daily pastebin goal
52%
SHARE
TWEET

Untitled

a guest Dec 12th, 2018 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <queue>
  2. #include <algorithm>
  3. #include <string>
  4. #include <list>
  5.  
  6. /**
  7.  * Returns an std::list of vertex keys that creates some shortest path between `start` and `end`.
  8.  *
  9.  * This list MUST include the key of the `start` vertex as the first vertex in the list, the key of
  10.  * the `end` vertex as the last element in the list, and an ordered list of all vertexMap that must
  11.  * be traveled along the shortest path.
  12.  *
  13.  * For example, the path a -> c -> e returns a list with three elements: "a", "c", "e".
  14.  *
  15.  * @param start The key for the starting vertex.
  16.  * @param end   The key for the ending vertex.
  17.  */
  18. template <class V, class E>
  19. std::list<std::string> Graph<V,E>::shortestPath(const std::string start, const std::string end) {
  20.   struct Vertex {
  21.     std::string key;
  22.     int length;
  23.  
  24.     Vertex() {
  25.       key = "";
  26.       length = 0;
  27.     }
  28.  
  29.     Vertex(std::string theKey, int theLength) {
  30.       key = theKey;
  31.       length = theLength;
  32.     }
  33.   };
  34.  
  35.  
  36.   std::list<std::string> path;
  37.   std::queue<string> q;
  38.   q.push(start);
  39.  
  40.   std::unordered_map<std::string, Vertex> vertexMap;
  41.   vertexMap.insert(make_pair(start, Vertex()));
  42.  
  43.   while (!q.empty()) {
  44.     std::string & key = q.front();
  45.     q.pop();
  46.  
  47.     Vertex vertex = vertexMap.at(key);
  48.     std::list<reference_wrapper<E>> edges = incidentEdges(key);
  49.  
  50.     for (typename std::list<reference_wrapper<E>>::iterator it = edges.begin(); it != edges.end(); it++) {
  51.       Edge edge = (*it).get();
  52.       std::string edgeKey;
  53.  
  54.       if (edge.dest().key() != key) {
  55.         edgeKey = edge.dest().key();
  56.       } else {
  57.         edgeKey = edge.source().key();
  58.       }
  59.  
  60.       bool shouldClear = false;
  61.  
  62.       if (vertexMap.find(edgeKey) == vertexMap.end()) {
  63.         q.push(edgeKey);
  64.         vertexMap.insert(make_pair(edgeKey, Vertex(key, 1 + vertex.length)));
  65.  
  66.         shouldClear = true;
  67.       }
  68.  
  69.       if (shouldClear && end == edgeKey) {
  70.         while (!q.empty()) {
  71.           q.pop();
  72.         }
  73.  
  74.         break;
  75.       }
  76.     }
  77.   }
  78.  
  79.   std::string current = end;
  80.  
  81.   while (current.length() != 0) {
  82.     path.push_front(current);
  83.     current = vertexMap.at(current).key;
  84.   }
  85.  
  86.   return path;
  87. }
RAW Paste Data
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
 
Top