• API
• FAQ
• Tools
• Archive
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");
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();
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();
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.  *
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;
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.

Top