Files To be Submitted:<\/p>\n
You are required to turn in the following source file(s) in C++:<\/p>\n
Assignment8.cpp\u00a0
LinkedList.h
Graph.h
Stack.h
Makefile
README.txt<\/p>\n
You can also submit additional files.<\/p>\n
\u00a0<\/p>\n
\u00a0<\/p>\n
Objectives:<\/p>\n
This is to practice making graphs and perform some operations.<\/p>\n
\u00a0<\/p>\n
Assignment Description:<\/p>\n
This assignment is to implement a graph data structure using an adjacency list and also to find a circuit (a sequence of edges starting from one node\/vertex and ending to itself) using every edge of the graph.<\/p>\n
Assignment8.cpp file (a driver program) needs to be created to process the information from the file named \u201cgraph.txt\u201d. The file \u201cgraph.txt\u201d will have some information on an undirected graph, and its first line has the format of:<\/p>\n
n m<\/p>\n
where n is the number of nodes\/vertices and m is the number of edges in the graph. Then the nodes\/vertices of this graph are named as 1, 2, \u2026 n.\u00a0 A real example for this can be:<\/p>\n
12 35<\/p>\n
In this case, there will be 12 nodes\/vertices and 35 edges. After this line, there will be m lines containing the information of edges in the format of:<\/p>\n
s e<\/p>\n
where s and e are two nodes\/vertices of the edge. \u00a0You can assume that each edge read from the file has a weight of 1. A real example for this can be:<\/p>\n
1 2<\/p>\n
In this case, there is an edge between the vertex 1 and the vertex 2, with its weight of 1.<\/p>\n
\u00a0<\/p>\n
Here is a sample graph.txt file:<\/p>\n
graph.txt\u00a0Download graph.txt<\/p>\n
In this assignment, you need to implement an adjacency list that is an array of linked lists. First you need to create a LinkedList struct\/class whose each node containing an adjacency vertex, its weight, a variable \u201cnotUsed\u201d and variable \u201cvirtual1\u201d that will be used in the later steps of the assignment. All edges read from the file will be non-virtual edges and all edges are marked as not used at the beginning. You also need to define insertEdge( ) function in the LinkedList in order to add each edge information. You need to add each edge information in the increasing order of the adjacent vertices. In this assignment, it is possible to have more than one edge between two nodes (non-virtual and virtual), and in that case, add non-virtual vertex first, and virtual vertex later. If we have the following edges:<\/p>\n
vertex 1 to vertex 2, non-virtual, weight 1<\/p>\n
vertex 1 to vertex 2, virtual, weight 1<\/p>\n
vertex 1 to vertex 3, non-virtual, weight 1<\/p>\n
Then the linked list of the vertex 1 needs to have its adjacent vertices in the following order:<\/p>\n
head -> vertex 2, non-virtual, weight 1 -> vertex 2, virtual, weight 1 -> vertex 3, non virtual, weight 1<\/p>\n
Because this is an undirected graph, if you see the edge information 1 2, then you need to store the information of two edges, an edge from 1 to 2 with its weight 1 and also an edge from 2 to 1 with its weight 1.<\/p>\n
After creating the Linked List data structure, you need to create Graph.h and create an adjacency list that is an array of linked lists in it. The size of the array is the number of nodes\/vertices, and each slot should correspond to each vertex in their increasing order. You also need to compute and record the degree (the number of out-going edges) for each vertex. After populating the adjacency list by reading from the specified file and computing the degree for each vertex, you need to print out the vertices with an odd degree in their increasing order, using the following format:<\/p>\n
The odd-degree vertices in G: O = { 3 4 5 7 14 15 }\u00a0<\/p>\n
If the list is empty. Then you can print it as:\u00a0<\/p>\n
The odd-degree vertices in G: O = {\u00a0 }\u00a0<\/p>\n
3. If some vertices have an odd degree, we will need to go through some edges more than one for a circuit. Therefore, we will be adding some virtual edges using the following way. You are required to use (and define) the Floyd-Warshall( ) function in the Graph class, using the Floyd-Warshall algorithm to find the shortest paths for all pairs of vertices on the graph. In the Floyd-Warshall function, you need to compute the two dimensional D (distance) array and pi array.\u00a0 Then your program needs to print out its result on the graph G and also on the set of odd degree vertices O using the following format:\u00a0<\/p>\n
Results of Floyd-Warshall on G: (distance)<\/p>\n
\u00a0<\/p>\n
\u00a0<\/p>\n
\u00a0\u00a0\u00a0\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 5\u00a0\u00a0\u00a0 6\u00a0\u00a0\u00a0 7\u00a0\u00a0\u00a0 8\u00a0\u00a0\u00a0 9\u00a0\u00a0 10\u00a0\u00a0 11\u00a0\u00a0 12\u00a0\u00a0 13\u00a0\u00a0 14\u00a0\u00a0 15<\/p>\n
—\u00a0 -+-\u00a0 —\u00a0 —\u00a0 —\u00a0 —\u00a0 —\u00a0 —\u00a0 —\u00a0 —\u00a0 —\u00a0 —\u00a0 —\u00a0 —\u00a0 —\u00a0 —\u00a0 —\u00a0<\/p>\n
\u00a0 1\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 4<\/p>\n
\u00a0 2\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 4<\/p>\n
\u00a0 3\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3<\/p>\n
\u00a0 4\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 4<\/p>\n
\u00a0 5\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3<\/p>\n
\u00a0 6\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2<\/p>\n
\u00a0 7\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 1<\/p>\n
\u00a0 8\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1<\/p>\n
\u00a0 9\u00a0\u00a0 |\u00a0\u00a0 \u00a0\u00a03\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3<\/p>\n
\u00a010\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3<\/p>\n
\u00a011\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 4<\/p>\n
\u00a012\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 3 \u00a0\u00a0\u00a03\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3<\/p>\n
\u00a013\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2<\/p>\n
\u00a014\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 1<\/p>\n
\u00a015\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 0\u00a0\u00a0<\/p>\n
Results of Floyd-Warshall on O:<\/p>\n
\u00a0<\/p>\n
\u00a0\u00a0\u00a0\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 5\u00a0\u00a0\u00a0 7\u00a0\u00a0 14\u00a0\u00a0 15<\/p>\n
—\u00a0 -+-\u00a0 —\u00a0 —\u00a0 —\u00a0 —\u00a0 —\u00a0 —\u00a0<\/p>\n
\u00a0 3\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3<\/p>\n
\u00a0 4\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 4<\/p>\n
\u00a0 5\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 3<\/p>\n
\u00a0 7\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 2\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 1<\/p>\n
\u00a014\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 0\u00a0\u00a0\u00a0 1<\/p>\n
\u00a015\u00a0\u00a0 |\u00a0\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 4\u00a0\u00a0\u00a0 3\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 1\u00a0\u00a0\u00a0 0\u00a0<\/p>\n
For an undirected graph G, a matching is a subset of edges such that no two edges on the set are incident on a common vertex. A perfect matching is a matching in which every vertex is matched, i.e., every vertex in the Graph is incident to an edge in the matching (set of edges). You need to define perfectMatching( ) function in the Graph by implementing the following steps, using the greedy algorithm. We collect only the edges in the result of Floyd-Warshall on O (the set of odd degree vertices) where the starting vertex and the ending vertex are different, with their weight. Create an array of edges (with a starting vertex, an ending vertex, and its weight) and store the edges from the result of Floyd-Warshall result on O. Since they are undirected, they can appear twice, but store only once when their starting vertex is less than their ending vertex. For instance, to store the edge between 3 and 5 with the weight 1, then store the edge (3, 5) with its weight 1, and not the edge (5, 3). Then sort the array of edges by implementing one of insertion sort, merge sort, quick sort, or heap sort. You need to define sortEdges( ) function in the Graph by implementing one of them. To sort edges, you need to sort using the increasing order of their weights first, then by the increasing order of their starting vertices, then by the increasing order of their ending vertices. For instance, the following is the sorted order of the above Floyd-Warshall result on O. You need to print your sorted result using the following format:<\/p>\n
\u00a0<\/p>\n
The sorted edges of odd-degree vertices from Floyd-Warshall:<\/p>\n
(4,5) with its weight 1<\/p>\n
(7,14) with its weight 1<\/p>\n
(7,15) with its weight 1<\/p>\n
(14,15) with its weight 1<\/p>\n
(3,4) with its weight 2<\/p>\n
(3,5) with its weight 2<\/p>\n
(3,7) with its weight 2<\/p>\n
(5,7) with its weight 2<\/p>\n
(3,14) with its weight 3<\/p>\n
(3,15) with its weight 3<\/p>\n
(4,7) with its weight 3<\/p>\n
(5,14) with its weight 3<\/p>\n
(5,15) with its weight 3<\/p>\n
(4,14) with its weight 4<\/p>\n
(4,15) with its weight 4<\/p>\n
Using the sorted edges, you need to create the perfect matching M (set of edges). For this example, first you add the first edge (4,5) to M. Then you need to examine each edge in the sorted list in their sorted order to see if any of its starting vertex or ending vertex is common with any of the starting vertex and ending vertex of edges that are already in M. The edges (7,14) does not have any common vertex with (4,5) in M, and it will be added to M. (now M has { (4,5), (7,14) }. The next edge (7,15) has the vertex 7 in common with one of the edges in M, so it will not be added. The edge (14,15) will not be added because of the vertex 14 and the edge (3,4) will not be added because of the vertex 4, and so on. For this example, the result M contains { (4,5), (7,14), (3,15) }. Then your program needs to print out its result using the following format:<\/p>\n
The greedy perfect matching in O: M = { (4,5) (7,14) (3,15) }<\/p>\n
The edges need to be listed in the order inserted. If the list is empty. Then you can print it as:<\/p>\n
The greedy perfect matching in O: M = {\u00a0 }<\/p>\n
After computing the perfect matching with some edges, you need to insert these edges with their weight into the adjacency list of the original graph as virtual edges. These are undirected edges, thus need to be inserted twice in the graph for both directions. There might be more than one edge between a pair of vertices. In that case, you need to insert them in the order specified in the step 2.<\/p>\n
\u00a0<\/p>\n
6. In this step, you will compute its circuit (a sequence of edges to go through every edge of the graph, starting from one node\/vertex and ending to itself, it might go through some edges and vertices more than once). First you need to define the Stack data structure by creating a struct\/class of Edge containing two vertices and its weight and making an array of edges or a linked list of edges (either of them can represent a stack as long as we use LIFO, Last-In-First-Out order). You also need to define the push( ) function to push an edge and the pop( ) function to pop the last edge. Create two variables \u201ccircuit\u201d and \u201ctempStack\u201d of this Stack data structure, initially being empty.<\/p>\n
Then you need to define the modified DFS (Depth First Search) and DFS_VISIT in the Graph.h in order to compute its circuit. First you always need to start the search from the vertex 1. The DFS and DFS_VISIT that we saw in class was calling DFS_VISIT for the vertices with white color, but here we call it for the vertices with white or gray color. The aim is to explore every edge that is incident with each vertex. Once we explore an edge by visiting an adjacent vertex, you need to mark the edge as \u201cused\u201d (see the step 2 for this) and push the edge onto the \u201ctempStack\u201d. We mark such edge as \u201cused\u201d in the adjacency list so that we will not explore it again later on. Remember that each edge is stored twice in the adjacency list because it is an undirected edge. If a vertex does not have any more edge that is incident with it, then pop the last edge from the \u201ctempStack\u201d. If the popped edge is a non-virtual edge, say (u, v), then switch the order of its vertices to (v, u) and push\/append it to the \u201ccircuit\u201d. If the popped edge is a virtual edge, then you need to obtain a path of non-virtual edges to go from the vertex v to the vertex u from the Floyd-Warshall, the pi array, and push them onto the \u201ccircuit\u201d stack. For instance, if we take the virtual edge (15,3) with its weight 3, and switch their vertices to (3,15), the edge (3,15) was obtained from the shortest path that is the sequence of the edges (3,6), (6,7), and (7,15)\u00a0 (You can use the pi array obtained by the Floyd-Warshall to get such information). Therefore the edges (3,6), (6,7), and (7,15) are pushed onto the \u201ccircuit\u201d stack in this order. At this point, the search will need to back-track to the vertex u.<\/p>\n
For the sample example, first we select the edge (1,2). It is pushed onto the temporary Stack. Then the edge (2,3) is selected, then the edge (3,1) is selected. At this point you have:<\/p>\n
Circuit: Empty<\/p>\n
Stack:\u00a0\u00a0 (1,2) (2,3) (3,1)<\/p>\n
Once we reached the vertex 1, there is no more edge that we have not selected from the vertex 1, thus we need to back track. The edge (3,1) is popped from the temporary stack and pushed onto the circuit.<\/p>\n
Circuit: (1,3)<\/p>\n
Stack:\u00a0\u00a0 (1,2) (2,3)\u00a0<\/p>\n
\u00a0After continuing to select more edges, we have:<\/p>\n
Circuit: (1,3)<\/p>\n
Stack:\u00a0\u00a0 (1,2) (2,3) (3,6) (6,5) (5,2) (2,4) (4,5) (5,4) (4,9) (9,6) (6,7) (7,8) (8,15) (15,3)<\/p>\n
At this point, there is no more edge that we have not selected from the vertex 3, we pop the edge (15,3) from the temporary stack. Since the edge (15,3) is a virtual edge with its weight 3, and switch their vertices to (3,15), the edge (3,15) was obtained from the shortest path that is the sequence of the edges (3,6), (6,7), and (7,15). Therefore the edges (3,6), (6,7), and (7,15) are pushed on to the \u201ccircuit\u201d stack in this order.<\/p>\n
Circuit: (1,3) (3,6) (6,7) (7,15)<\/p>\n
Stack:\u00a0\u00a0 (1,2) (2,3) (3,6) (6,5) (5,2) (2,4) (4,5) (5,4) (4,9) (9,6) (6,7) (7,8) (8,15)<\/p>\n
Once the DFS is completed, your program needs to print out the edges in the circuit using the following format:<\/p>\n
\u00a0<\/p>\n
The circuit is:<\/p>\n
(1,3)<\/p>\n
(3,6)<\/p>\n
(6,7)<\/p>\n
\u2026<\/p>\n
(2,1)<\/p>\n
\u00a0<\/p>\n
Note that your program can be tested with different inputs from the above sample input, but the format will be the same.<\/p>\n
You must submit a file called \u201cMakefile\u201d that compiles your Assignment8.cpp, LinkedList.cpp, Graph.h, Stack.h files and generate an executable file called \u201cAssignment8\u201d to the gradescope. Make sure that your program is generating correct outputs when you submit your files.<\/p>\n
—————-<\/p>\n
The following is a partial Makefile.\u00a0Makefile\u00a0Download Makefile<\/p>\n
Once you create this file, then you can type “make” in a command line to compile and it should generate an executable file called “assignment8”.<\/p>\n
——————————<\/p>\n
EXEC = assignment8<\/p>\n
CPP = g++<\/p>\n
CFLAGS = -c -Wall<\/p>\n
$(EXEC)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 : Assignment8.o Graph.o<\/p>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 $(CPP) -o $(EXEC) Assignment8.o Graph.o<\/p>\n
Assignment8.o : Assignment8.cpp<\/p>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 $(CPP) $(CFLAGS) Assignment8.cpp<\/p>\n
Graph.o\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 : Graph.h Graph.cpp<\/p>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 $(CPP) $(CFLAGS) Graph.cpp<\/p>\n
clean\u00a0\u00a0 :<\/p>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 rm *.o<\/p>\n
——————————–<\/p>\n
\u00a0<\/p>\n
To compile type (in a command line such as linux, ubuntu, mac terminal):<\/p>\n
make<\/p>\n
To execute:<\/p>\n
.\/assignment8<\/p>\n
You need to have the \u201cgraph.txt\u201d file in the same folder as Makefile\/Assignment8.cpp files<\/p>\n
To store its output into a file named myout1.txt:<\/p>\n
.\/assignment8 > myout1.txt<\/p>\n
Then you can compare myout1.txt and output1.txt (its expected output given below)<\/p>\n
output1.txt\u00a0Download output1.txt<\/p>\n
\u00a0<\/p>\n
——————————–\u00a0<\/p>\n
Implementation\/Documentation Requirements:<\/p>\n
You need implement this program using C++ and it has to read from a file (graph.txt), and prints its output to a screen (the standard output).<\/p>\n
Your program needs to compile and execute in general.asu.edu.<\/p>\n
You need to define Graph class with insertEdge( ) , printGraph(), DFS( ), DFS_VISIT( ), Floyd-Warshall( ), perfectMatching( ), sortEdges( ). You can decide which parameters are needed. Additional functions can be added.<\/p>\n
You need to define LinkedList class\/struct with insertEdge( ). This is to specify an adjacent node and its weight to be added. This function should be called by insertEdge( ) in the Graph that specify two vertices, and its weight. You can decide which parameters are needed.<\/p>\n
You need to define Stack class\/struct with pop( ) and push( ) functions.<\/p>\n
Your code should be well documented and commented.<\/p>\n
You must use the provided data sets.<\/p>\n
Also you are not allowed to use any predefined data structures (such as ones in the library in C++, etc.) except arrays and strings (you can use predefined functions of the string), you need to build your own data structures and operations associated with them (such as insert or search). You are not allowed to use vectors.<\/p>\n
Copying any codes from other people’s programs or online is considered to be cheating and will lead to a report to the Dean and you will be penalized. If the code you submitted is not your original work, it can be considered as an academic integrity policy violation. Also check the rules stated in the syllabus of the course regarding the academic integrity policies.<\/p>\n
——————————–<\/p>\n
What to turn in:<\/p>\n
You must turn in C++ source code using the Gradescope.<\/p>\n
The types of files that you can submit are .cpp, or .h files. Your program needs to compile and execute correctly in the gradescope.<\/p>\n
You program should be well commented and documented, make sure the first few lines of your program contain your name, your ASU email address, and a description of each file. You should use indentation, good variable names, and clear, easy to read, and specific comments. (You will be graded on comments.)<\/p>\n
———\u00a0<\/p>\n
Input<\/p>\n
Here is a sample content of graph.txt file<\/p>\n
graph.txt\u00a0Download graph.txt<\/p>\n
Output<\/p>\n
Here is the output for the above graph.txt file<\/p>\n
output1.txt\u00a0Download output1.txt<\/p>\n
Your program will be tested with more test cases other than these test cases.<\/p>\n
————-\u00a0<\/p>\n
Error Handling<\/p>\n
Your program will be tested with other input files besides the one above, thus is expected to be robust. Your program might also be tested using test cases not given to you.<\/p>\n
Grading Criteria\u00a0<\/p>\n
____\/ 1 \u00a0 \u00a0 \u00a0Makefile is submitted and it works correctly. Your Makefile should compile your source code and should create an executable file name \u201cassignment8\u201d. If this part does not work, then you will get zero on this assignment<\/p>\n
____\/ 3 \u00a0 \u00a0 Documentation (correct and complete code description and comments, header for each function\/method, each file should have your name at its top) and good indentation and spacing (easy to read) A README file needs to be provided to describe your project, what information is in each file<\/p>\n
____\/ 1 \u00a0 \u00a0 Assignment8.cpp file is provided to handle the file read.<\/p>\n
____\/ 1 \u00a0 \u00a0 \u00a0the Graph data structure (class) is defined using an adjacency list correctly and it has a description and is well commented<\/p>\n
____\/ 2 \u00a0 \u00a0 \u00a0the Floyd-Warshall function for the graph is defined correctly (and it produces the correct output) and it has a description and is well commented<\/p>\n
____\/ 2 \u00a0 \u00a0 \u00a0the perfectMatching and sortEdges functions for the graph are defined correctly (and it produces the correct output) and it has a description and is well commented<\/p>\n
____\/ 2 \u00a0 \u00a0 \u00a0the DFS and DFS_VISIT functions for the graph are defined correctly (and it produces the correct output) and it has a description and is well commented<\/p>\n
____\/ 1 \u00a0 \u00a0 \u00a0the insertEdge function for the linked list and the insertEdge function for the graph are defined correctly (and it produces the correct output) and it has a description and is well commented<\/p>\n
____\/ 1 \u00a0 \u00a0 \u00a0the push and pop functions for the stack are defined correctly (and it produces the correct output) and it has a description and is well commented<\/p>\n
____\/ 16 \u00a0 \u00a0 correct outputs including correct vertices, edges, degrees, correct graph content, intermediate circuit\/stack contents, and the final circuit result for all outputs.<\/p>\n","protected":false},"excerpt":{"rendered":"
Files To be Submitted: You are required to turn in the following source file(s) in C++: Assignment8.cpp\u00a0 LinkedList.h Graph.h Stack.h Makefile README.txt You can also submit additional files. \u00a0 \u00a0 Objectives: This is to practice making graphs and perform some operations. \u00a0 Assignment Description: This assignment is to implement a graph data structure using an […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[10],"class_list":["post-79064","post","type-post","status-publish","format-standard","hentry","category-research-paper-writing","tag-writing"],"_links":{"self":[{"href":"https:\/\/papersspot.com\/blog\/wp-json\/wp\/v2\/posts\/79064","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/papersspot.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/papersspot.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/papersspot.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/papersspot.com\/blog\/wp-json\/wp\/v2\/comments?post=79064"}],"version-history":[{"count":0,"href":"https:\/\/papersspot.com\/blog\/wp-json\/wp\/v2\/posts\/79064\/revisions"}],"wp:attachment":[{"href":"https:\/\/papersspot.com\/blog\/wp-json\/wp\/v2\/media?parent=79064"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/papersspot.com\/blog\/wp-json\/wp\/v2\/categories?post=79064"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/papersspot.com\/blog\/wp-json\/wp\/v2\/tags?post=79064"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}