SHARE
TWEET

Untitled

a guest Dec 11th, 2018 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * @file graph_tools.cpp
  3.  * This is where you will implement several functions that operate on graphs.
  4.  * Be sure to thoroughly read the comments above each function, as they give
  5.  *  hints and instructions on how to solve the problems.
  6.  */
  7.  
  8. #include "graph_tools.h"
  9.  
  10. /**
  11.  * Finds the minimum edge weight in the Graph graph.
  12.  * THIS FUNCTION IS GRADED.
  13.  *
  14.  * @param graph - the graph to search
  15.  * @return the minimum weighted edge
  16.  *
  17.  * @todo Label the minimum edge as "MIN". It will appear blue when
  18.  *  graph.savePNG() is called in minweight_test.
  19.  *
  20.  * @note You must do a traversal.
  21.  * @note You may use the STL stack and queue.
  22.  * @note You may assume the graph is connected.
  23.  *
  24.  * @hint Initially label vertices and edges as unvisited.
  25.  */
  26. int GraphTools::findMinWeight(Graph& graph)
  27. {
  28.     /* Your code here! */
  29.     std::vector<Vertex> v=graph.getVertices();
  30.     std::vector<Edge> e=graph.getEdges();
  31.     for(unsigned int i=0;i<v.size();i++)
  32.       graph.setVertexLabel(v[i],"UNEXPLORED");
  33.     for(unsigned int i=0;i<e.size();i++)
  34.       graph.setEdgeLabel(e[i].source,e[i].dest,"UNEXPLORED");
  35.     queue<Vertex> bfs;
  36.     bfs.push(v[0]);
  37.     graph.setVertexLabel(v[0],"DONE");
  38.     Vertex st =graph.getAdjacent(v[v.size()-1])[0];
  39.     int w = graph.getEdgeWeight(v[v.size()-1],st);
  40.     Vertex s= v[v.size()-1];
  41.     Vertex d = st;
  42.     while(bfs.empty()==false)
  43.     {
  44.       Vertex cur = bfs.front();
  45.       std::vector<Vertex> cu=graph.getAdjacent(cur);
  46.       for(unsigned int i=0;i<cu.size();i++)
  47.       {
  48.  
  49.         if(graph.getVertexLabel(cu[i])=="UNEXPLORED")
  50.         {
  51.               bfs.push(cu[i]);
  52.               graph.setVertexLabel(cu[i],"DONE");
  53.               graph.setEdgeLabel(cur,cu[i],"FOUND");
  54.          }
  55.          else if(graph.getEdgeLabel(cur,cu[i])=="UNEXPLORED")
  56.          {
  57.               graph.setEdgeLabel(cur,cu[i],"CROSSED");
  58.          }
  59.          if(graph.getEdgeWeight(cur,cu[i])<w)
  60.          {
  61.            w=graph.getEdgeWeight(cur,cu[i]);
  62.            s=cur;
  63.            d=cu[i];
  64.          }
  65.       }
  66.       bfs.pop();
  67.     }
  68.     graph.setEdgeLabel(s,d,"MIN");
  69.     return w;
  70. }
  71.  
  72. /**
  73.  * Returns the shortest distance (in edges) between the Vertices
  74.  *  start and end.
  75.  * THIS FUNCTION IS GRADED.
  76.  *
  77.  * @param graph - the graph to search
  78.  * @param start - the vertex to start the search from
  79.  * @param end - the vertex to find a path to
  80.  * @return the minimum number of edges between start and end
  81.  *
  82.  * @todo Label each edge "MINPATH" if it is part of the minimum path
  83.  *
  84.  * @note Remember this is the shortest path in terms of edges,
  85.  *  not edge weights.
  86.  * @note Again, you may use the STL stack and queue.
  87.  * @note You may also use the STL's unordered_map, but it is possible
  88.  *  to solve this problem without it.
  89.  *
  90.  * @hint In order to draw (and correctly count) the edges between two
  91.  *  vertices, you'll have to remember each vertex's parent somehow.
  92.  */
  93. int GraphTools::findShortestPath(Graph& graph, Vertex start, Vertex end)
  94. {
  95.     /* Your code here! */
  96.     std::vector<Vertex> v=graph.getVertices();
  97.     std::vector<Edge> e=graph.getEdges();
  98.     for(unsigned int i=0;i<v.size();i++)
  99.       graph.setVertexLabel(v[i],"UNEXPLORED");
  100.     for(unsigned int i=0;i<e.size();i++)
  101.       graph.setEdgeLabel(e[i].source,e[i].dest,"UNEXPLORED");
  102.     queue<Vertex> bfs;
  103.     bfs.push(start);
  104.     graph.setVertexLabel(start,"DONE");
  105.     unordered_map<Vertex,Vertex> map;
  106.     while(bfs.empty()==false)
  107.     {
  108.       Vertex cur = bfs.front();
  109.       std::vector<Vertex> cu=graph.getAdjacent(cur);
  110.       for(unsigned int i=0;i<cu.size();i++)
  111.       {
  112.         if(graph.getVertexLabel(cu[i])=="UNEXPLORED")
  113.         {
  114.           bfs.push(cu[i]);
  115.           graph.setVertexLabel(cu[i],"DONE");
  116.           graph.setEdgeLabel(cur,cu[i],"FOUND");
  117.           pair<Vertex,Vertex> p (cu[i],cur);
  118.           map.insert(p);
  119.  
  120.         }
  121.         else if(graph.getEdgeLabel(cur,cu[i])=="UNEXPLORED")
  122.           graph.setEdgeLabel(cur,cu[i],"CROSSED");
  123.       }
  124.       bfs.pop();
  125.     }
  126.     int ret=0;
  127.     while(end!=start)
  128.     {
  129.       graph.setEdgeLabel(end,map[end],"MINPATH");
  130.       end=map[end];
  131.       ret=ret+1;
  132.     }
  133.     return ret;
  134. }
  135.  
  136. /**
  137.  * Finds a minimal spanning tree on a graph.
  138.  * THIS FUNCTION IS GRADED.
  139.  *
  140.  * @param graph - the graph to find the MST of
  141.  *
  142.  * @todo Label the edges of a minimal spanning tree as "MST"
  143.  *  in the graph. They will appear blue when graph.savePNG() is called.
  144.  *
  145.  * @note Use your disjoint sets class from MP 7.1 to help you with
  146.  *  Kruskal's algorithm. Copy the files into the libdsets folder.
  147.  * @note You may call std::sort instead of creating a priority queue.
  148.  */
  149. void GraphTools::findMST(Graph& graph)
  150. {
  151.     /* Your code here! */
  152.     std::vector<Vertex> v=graph.getVertices();
  153.     DisjointSets ds;
  154.     ds.addelements(v.size());
  155.     std::vector<Edge> e=graph.getEdges();
  156.     std::sort(e.begin(),e.end(),so);
  157.     unsigned int j=0;
  158.     for(unsigned int i=0;i<e.size();i++)
  159.     {
  160.       if(!(j<(v.size()-1)))
  161.         break;
  162.       if(ds.find(e[i].source)!=ds.find(e[i].dest))
  163.       {
  164.         ds.setunion(e[i].source,e[i].dest);
  165.         graph.setEdgeLabel(e[i].source,e[i].dest,"MST");
  166.         j++;
  167.       }
  168.     }
  169. }
  170. bool GraphTools::so(Edge a, Edge b)
  171. {
  172.   return(a.weight<b.weight);
  173. }
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