Files To be Submitted:
You are required to turn in the following source file(s) in C++:
Assignment8.cpp
LinkedList.h
Graph.h
Stack.h
Makefile
README.txt
You can also submit additional files.
Objectives:
This is to practice making graphs and perform some operations.
Assignment Description:
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.
Assignment8.cpp file (a driver program) needs to be created to process the information from the file named “graph.txt”. The file “graph.txt” will have some information on an undirected graph, and its first line has the format of:
n m
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, … n. A real example for this can be:
12 35
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:
s e
where s and e are two nodes/vertices of the edge. You can assume that each edge read from the file has a weight of 1. A real example for this can be:
1 2
In this case, there is an edge between the vertex 1 and the vertex 2, with its weight of 1.
Here is a sample graph.txt file:
graph.txt Download graph.txt
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 “notUsed” and variable “virtual1” 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:
vertex 1 to vertex 2, non-virtual, weight 1
vertex 1 to vertex 2, virtual, weight 1
vertex 1 to vertex 3, non-virtual, weight 1
Then the linked list of the vertex 1 needs to have its adjacent vertices in the following order:
head -> vertex 2, non-virtual, weight 1 -> vertex 2, virtual, weight 1 -> vertex 3, non virtual, weight 1
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.
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:
The odd-degree vertices in G: O = { 3 4 5 7 14 15 }
If the list is empty. Then you can print it as:
The odd-degree vertices in G: O = { }
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. 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:
Results of Floyd-Warshall on G: (distance)
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
— -+- — — — — — — — — — — — — — — —
1 | 0 1 1 2 2 2 3 4 3 3 3 3 4 4 4
2 | 1 0 1 1 1 2 3 4 2 2 2 3 4 4 4
3 | 1 1 0 2 2 1 2 3 2 2 3 2 3 3 3
4 | 2 1 2 0 1 2 3 4 1 2 2 3 4 4 4
5 | 2 1 2 1 0 1 2 3 2 1 1 2 3 3 3
6 | 2 2 1 2 1 0 1 2 1 1 2 1 2 2 2
7 | 3 3 2 3 2 1 0 1 2 2 3 2 1 1 1
8 | 4 4 3 4 3 2 1 0 3 3 4 3 2 2 1
9 | 3 2 2 1 2 1 2 3 0 2 3 2 3 3 3
10 | 3 2 2 2 1 1 2 3 2 0 2 2 3 3 3
11 | 3 2 3 2 1 2 3 4 3 2 0 1 4 4 4
12 | 3 3 2 3 2 1 2 3 2 2 1 0 3 3 3
13 | 4 4 3 4 3 2 1 2 3 3 4 3 0 1 2
14 | 4 4 3 4 3 2 1 2 3 3 4 3 1 0 1
15 | 4 4 3 4 3 2 1 1 3 3 4 3 2 1 0
Results of Floyd-Warshall on O:
| 3 4 5 7 14 15
— -+- — — — — — —
3 | 0 2 2 2 3 3
4 | 2 0 1 3 4 4
5 | 2 1 0 2 3 3
7 | 2 3 2 0 1 1
14 | 3 4 3 1 0 1
15 | 3 4 3 1 1 0
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:
The sorted edges of odd-degree vertices from Floyd-Warshall:
(4,5) with its weight 1
(7,14) with its weight 1
(7,15) with its weight 1
(14,15) with its weight 1
(3,4) with its weight 2
(3,5) with its weight 2
(3,7) with its weight 2
(5,7) with its weight 2
(3,14) with its weight 3
(3,15) with its weight 3
(4,7) with its weight 3
(5,14) with its weight 3
(5,15) with its weight 3
(4,14) with its weight 4
(4,15) with its weight 4
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:
The greedy perfect matching in O: M = { (4,5) (7,14) (3,15) }
The edges need to be listed in the order inserted. If the list is empty. Then you can print it as:
The greedy perfect matching in O: M = { }
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.
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 “circuit” and “tempStack” of this Stack data structure, initially being empty.
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 “used” (see the step 2 for this) and push the edge onto the “tempStack”. We mark such edge as “used” 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 “tempStack”. 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 “circuit”. 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 “circuit” 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) (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 “circuit” stack in this order. At this point, the search will need to back-track to the vertex u.
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:
Circuit: Empty
Stack: (1,2) (2,3) (3,1)
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.
Circuit: (1,3)
Stack: (1,2) (2,3)
After continuing to select more edges, we have:
Circuit: (1,3)
Stack: (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)
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 “circuit” stack in this order.
Circuit: (1,3) (3,6) (6,7) (7,15)
Stack: (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)
Once the DFS is completed, your program needs to print out the edges in the circuit using the following format:
The circuit is:
(1,3)
(3,6)
(6,7)
…
(2,1)
Note that your program can be tested with different inputs from the above sample input, but the format will be the same.
You must submit a file called “Makefile” that compiles your Assignment8.cpp, LinkedList.cpp, Graph.h, Stack.h files and generate an executable file called “Assignment8” to the gradescope. Make sure that your program is generating correct outputs when you submit your files.
—————-
The following is a partial Makefile. Makefile Download Makefile
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”.
——————————
EXEC = assignment8
CPP = g++
CFLAGS = -c -Wall
$(EXEC) : Assignment8.o Graph.o
$(CPP) -o $(EXEC) Assignment8.o Graph.o
Assignment8.o : Assignment8.cpp
$(CPP) $(CFLAGS) Assignment8.cpp
Graph.o : Graph.h Graph.cpp
$(CPP) $(CFLAGS) Graph.cpp
clean :
rm *.o
——————————–
To compile type (in a command line such as linux, ubuntu, mac terminal):
make
To execute:
./assignment8
You need to have the “graph.txt” file in the same folder as Makefile/Assignment8.cpp files
To store its output into a file named myout1.txt:
./assignment8 > myout1.txt
Then you can compare myout1.txt and output1.txt (its expected output given below)
output1.txt Download output1.txt
——————————–
Implementation/Documentation Requirements:
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).
Your program needs to compile and execute in general.asu.edu.
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.
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.
You need to define Stack class/struct with pop( ) and push( ) functions.
Your code should be well documented and commented.
You must use the provided data sets.
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.
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.
——————————–
What to turn in:
You must turn in C++ source code using the Gradescope.
The types of files that you can submit are .cpp, or .h files. Your program needs to compile and execute correctly in the gradescope.
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.)
———
Input
Here is a sample content of graph.txt file
graph.txt Download graph.txt
Output
Here is the output for the above graph.txt file
output1.txt Download output1.txt
Your program will be tested with more test cases other than these test cases.
————-
Error Handling
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.
Grading Criteria
____/ 1 Makefile is submitted and it works correctly. Your Makefile should compile your source code and should create an executable file name “assignment8”. If this part does not work, then you will get zero on this assignment
____/ 3 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
____/ 1 Assignment8.cpp file is provided to handle the file read.
____/ 1 the Graph data structure (class) is defined using an adjacency list correctly and it has a description and is well commented
____/ 2 the Floyd-Warshall function for the graph is defined correctly (and it produces the correct output) and it has a description and is well commented
____/ 2 the 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
____/ 2 the 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
____/ 1 the 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
____/ 1 the 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
____/ 16 correct outputs including correct vertices, edges, degrees, correct graph content, intermediate circuit/stack contents, and the final circuit result for all outputs.