Starting from:
$30
CSCI311-Project 5 Dijkstra’s and Kruskal’s Algorithms Solved
In this project you will implement the Dijkstra’s algorithm and the Kruskal’s algorithm.
Download Project5.tar and untar it: tar -xvf Project5.tar
Use code for Project 4 and for Project 3. You will need to use classes Item, TimeStamp, Ugraph, and PriorityQueue.
Step 1. Update code for PriorityQueue class:
1. In function pop(), before removing min-Priority Item, set it’s keys[aheap[0].key] = -1. In this case if keys[v] is -1, then we will know that vertex v is not in the priority queue anymore.
2. Write the member function bool isKey(int v) that returns true if v is in the priority queue (i.e. if keys[v] is not -1), and returns false otherwise.
Step 2. Update struct edge:
struct edge{
int source;//edge is from this node to neighbor int neighbor; // adjacent node int w; //keeps auxiliary information
edge(){ source = 0; neighbor = 0; w = 0;
};
edge(int i, int j){ source = 0;//dummy value
neighbor = i; w = j;
};
edge(int from, int to, int aweight){ source = from;//edge is from this node neighbor = to;//edge is to this node
w = aweight;//weight of this edge
};
//overloaded *less than* operator will allow to compare edges bool operator<(edge y){ return (this-w < y.w) ? true : false; }; };
Step 3. Update code for Ugraph class:
1. Write overloaded member function void addEdge(int u, int v, int aweight) that takes three parameters, integers u, v and weight, and adds an edge (u, v) in Adj[u] whose weight w is set to the third parameter aweight; and adds an edge (v, u) in Adj[v] with w set to aweight.
2. Write a new member function void dijkstra(int s) that takes an integer s as a parameter and finds all shortest paths from s to all vertices (nodes) of the graph.
a. Use the vectors parents and distance to store the results (these vectors already exist in Ugraph). Inside this function, first, for all vertices v, initialize parent[v] to v and distance[v] to INT_MAX.
b. Then set distance of s to 0.
c. Then instantiate an object of PriorityQueue class using the constructor that takes a pointer to an array of Items and it’s length. You need to create an array in the Heap (using new) of Items, such that each Item has each vertex v as it’s key and has distance[v] as it’s priority. The size of this array is equal to the total number of vertices in the graph (use size of Ugraph). Simply scan array distance from left to right and for each i, initialize array at i to Item(i, distance[i]). Then you will pass this array to the constructor of PriorityQueue.
d. Then continue writing the code of the Dijkstra’s algorithm. To check if a vertex v is in the priority queue, use the member function isKey(v) of PriorityQueue.
e. When updating priority of a node v with smaller distance, update distance[v] too.
3. Write a new member function void printDistance() that prints distance of each node v, and put a space after each node and endl at the end.
4. Write a new member function void printParents() that prints parent of each node v, and put a space after each node and endl at the end.
5. Write a new recursive member function void printPath(int u, int v) that prints path by backtracking parents array starting with the second parameter v until the first parameter u is found on the path. Path is printed in the format: <vertex<space…<vertex<space. The first vertex on the path is u and the last is v. (Note: there is NO endl at the end of output).
6. Write a new member function int lenghtShortestW(int u, int v) that finds the shortest path from u to v using the Dijkstra’s algorithm, then prints this path and returns the length of the path:
a. Inside this function, call dikstra(u) that will find the shortest paths from u to all vertices;
b. Then call printPath(u, v) that will print path from u to v using parents vector; since printPath does not print endl, print endl after calling printPath.
c. Finally, return the length of the shortest path stored at distance[v].
7. Add a new private data member to Ugraph that holds the minimum spanning tree of the graph. Add vector<vector< edge mst. Inside the constructor, resize mst to size.
8. Write a new member function void kruskal() that will calculate the minimum spanning tree for the graph (and will store it in the data member mst).
a. Use parents vector to store parents (representatives of connected components) of the vertices and use distance vector to store ranks of the vertices.
b. Check if mst is not empty (size is greater than 0), clear it and resize to 0: mst.clear(), and mst.resize(0).
c. Write a new recursive member function int findSet(int v) that returns the representative of v’s connected component and sets parents of all the vertices on the path from v to the root (representative) of the connected component to the root.
d. Write a new member function void combine(int x, int y) that uses rank-by-union heuristic to combine two connected components whose representatives are x and y.
e. First, inside kruskal(), initialize parents[v] = v and distance[v] = 0 (rank of each node is zero).
f. Run while (or for) loop until (size - 1) edges have been added to MST. Continue implementing the Kruskal’s algorithm according to pseudocode in lecture slides. When adding an edge (u, v, w) (from u to v with weight w) to the minimum spanning tree, you need to add this edge to mst[u] and mst[v] (since mst is an undirected graph, an edge appears in the adjacency lists of mst twice).
g. To sort edges:
i. Comment out “bool operator….” line in struct “edge”.
ii. Put this function (not a member function) into ugraph.cpp
bool lessThan(const edge &x, const edge &y){ return (x.w < y.w) ? true : false; }
iii. Put all the edges into a temporary vector (declared inside kruskal function) of edges, vector<edge edgesAll. You will need to scan Adj to do this. Note that each edge (u, v) occurs in Adj twice: once in Adj[u] and the other time in Adj[v]; so when you consider an edge (u, v), check if u < v, then put this edge into edgesAll, and do not put edge if u v; in this case you will put the same edge only once. Use the edge’s constructor that takes three parameters: edge(u, v, weight).
iv. After this, you may use sort of the standard library (include <algorithm):
sort(edgesAll.begin(), edgesAll.end(), lessThan);
9. Write a new member function void printMST() that scans mst and prints out all vertices in mst[0], then all vertices in mst[1], and so on. Format of output: print a space after each vertex and print endl after each adjacency list of mst (e.g. print endl after all vertices of mst[0] have been printed, and so on).
Example: mst of the given graph in Figure to the left is shown in blue, and this mst will be printed like this:
4
3
3
1 4 2
Explanation: each line corresponds to adjacency list of mst[i]. The
last line corresponds to vertices at mst[3] (4 comes before 2, because edge (3,4) has less weight than edge (2, 3), so it will be pushed back to mst[3] before the edge (2, 3) ).
10. Write a new member function int weightMST() that scans mst and returns total weight of all the edges in the minimum spanning tree. Please note that each edge is repeated twice in MST, so to return the correct number, you may add up all the weights, and then divide the sum by 2.
Download Project5.tar and untar it: tar -xvf Project5.tar
Use code for Project 4 and for Project 3. You will need to use classes Item, TimeStamp, Ugraph, and PriorityQueue.
Step 1. Update code for PriorityQueue class:
1. In function pop(), before removing min-Priority Item, set it’s keys[aheap[0].key] = -1. In this case if keys[v] is -1, then we will know that vertex v is not in the priority queue anymore.
2. Write the member function bool isKey(int v) that returns true if v is in the priority queue (i.e. if keys[v] is not -1), and returns false otherwise.
Step 2. Update struct edge:
struct edge{
int source;//edge is from this node to neighbor int neighbor; // adjacent node int w; //keeps auxiliary information
edge(){ source = 0; neighbor = 0; w = 0;
};
edge(int i, int j){ source = 0;//dummy value
neighbor = i; w = j;
};
edge(int from, int to, int aweight){ source = from;//edge is from this node neighbor = to;//edge is to this node
w = aweight;//weight of this edge
};
//overloaded *less than* operator will allow to compare edges bool operator<(edge y){ return (this-w < y.w) ? true : false; }; };
Step 3. Update code for Ugraph class:
1. Write overloaded member function void addEdge(int u, int v, int aweight) that takes three parameters, integers u, v and weight, and adds an edge (u, v) in Adj[u] whose weight w is set to the third parameter aweight; and adds an edge (v, u) in Adj[v] with w set to aweight.
2. Write a new member function void dijkstra(int s) that takes an integer s as a parameter and finds all shortest paths from s to all vertices (nodes) of the graph.
a. Use the vectors parents and distance to store the results (these vectors already exist in Ugraph). Inside this function, first, for all vertices v, initialize parent[v] to v and distance[v] to INT_MAX.
b. Then set distance of s to 0.
c. Then instantiate an object of PriorityQueue class using the constructor that takes a pointer to an array of Items and it’s length. You need to create an array in the Heap (using new) of Items, such that each Item has each vertex v as it’s key and has distance[v] as it’s priority. The size of this array is equal to the total number of vertices in the graph (use size of Ugraph). Simply scan array distance from left to right and for each i, initialize array at i to Item(i, distance[i]). Then you will pass this array to the constructor of PriorityQueue.
d. Then continue writing the code of the Dijkstra’s algorithm. To check if a vertex v is in the priority queue, use the member function isKey(v) of PriorityQueue.
e. When updating priority of a node v with smaller distance, update distance[v] too.
3. Write a new member function void printDistance() that prints distance of each node v, and put a space after each node and endl at the end.
4. Write a new member function void printParents() that prints parent of each node v, and put a space after each node and endl at the end.
5. Write a new recursive member function void printPath(int u, int v) that prints path by backtracking parents array starting with the second parameter v until the first parameter u is found on the path. Path is printed in the format: <vertex<space…<vertex<space. The first vertex on the path is u and the last is v. (Note: there is NO endl at the end of output).
6. Write a new member function int lenghtShortestW(int u, int v) that finds the shortest path from u to v using the Dijkstra’s algorithm, then prints this path and returns the length of the path:
a. Inside this function, call dikstra(u) that will find the shortest paths from u to all vertices;
b. Then call printPath(u, v) that will print path from u to v using parents vector; since printPath does not print endl, print endl after calling printPath.
c. Finally, return the length of the shortest path stored at distance[v].
7. Add a new private data member to Ugraph that holds the minimum spanning tree of the graph. Add vector<vector< edge mst. Inside the constructor, resize mst to size.
8. Write a new member function void kruskal() that will calculate the minimum spanning tree for the graph (and will store it in the data member mst).
a. Use parents vector to store parents (representatives of connected components) of the vertices and use distance vector to store ranks of the vertices.
b. Check if mst is not empty (size is greater than 0), clear it and resize to 0: mst.clear(), and mst.resize(0).
c. Write a new recursive member function int findSet(int v) that returns the representative of v’s connected component and sets parents of all the vertices on the path from v to the root (representative) of the connected component to the root.
d. Write a new member function void combine(int x, int y) that uses rank-by-union heuristic to combine two connected components whose representatives are x and y.
e. First, inside kruskal(), initialize parents[v] = v and distance[v] = 0 (rank of each node is zero).
f. Run while (or for) loop until (size - 1) edges have been added to MST. Continue implementing the Kruskal’s algorithm according to pseudocode in lecture slides. When adding an edge (u, v, w) (from u to v with weight w) to the minimum spanning tree, you need to add this edge to mst[u] and mst[v] (since mst is an undirected graph, an edge appears in the adjacency lists of mst twice).
g. To sort edges:
i. Comment out “bool operator….” line in struct “edge”.
ii. Put this function (not a member function) into ugraph.cpp
bool lessThan(const edge &x, const edge &y){ return (x.w < y.w) ? true : false; }
iii. Put all the edges into a temporary vector (declared inside kruskal function) of edges, vector<edge edgesAll. You will need to scan Adj to do this. Note that each edge (u, v) occurs in Adj twice: once in Adj[u] and the other time in Adj[v]; so when you consider an edge (u, v), check if u < v, then put this edge into edgesAll, and do not put edge if u v; in this case you will put the same edge only once. Use the edge’s constructor that takes three parameters: edge(u, v, weight).
iv. After this, you may use sort of the standard library (include <algorithm):
sort(edgesAll.begin(), edgesAll.end(), lessThan);
9. Write a new member function void printMST() that scans mst and prints out all vertices in mst[0], then all vertices in mst[1], and so on. Format of output: print a space after each vertex and print endl after each adjacency list of mst (e.g. print endl after all vertices of mst[0] have been printed, and so on).
Example: mst of the given graph in Figure to the left is shown in blue, and this mst will be printed like this:
4
3
3
1 4 2
Explanation: each line corresponds to adjacency list of mst[i]. The
last line corresponds to vertices at mst[3] (4 comes before 2, because edge (3,4) has less weight than edge (2, 3), so it will be pushed back to mst[3] before the edge (2, 3) ).
10. Write a new member function int weightMST() that scans mst and returns total weight of all the edges in the minimum spanning tree. Please note that each edge is repeated twice in MST, so to return the correct number, you may add up all the weights, and then divide the sum by 2.
1 file (331.1KB)
