Practice depth-first-search on a directed graph represented by an adjacency-list. Assignment Description 1. You need to implement a graph data structure using an adjacency list to keep track of which university football team beat which team. Thus the nodes of your graph will be university names, and each edge, AUniversity -> BUniversity, represents that AUniversity football team beat BUniversity in some games. Also, university names need to be stored in alphabetical order, i.e., the node names that represent from nodes should be in alphabetical order, and also to nodes from each from nodes should be stored in each linked list in alphabetical order. 2. Your program needs to read from two files, the first file contains all the commands the drivers program will execute and the second file contains the graphs information. After compiling your program using makefile, it should generate an executable file named A7p1. For example, it will be executed using the following command: ./A7p1 commands1.txt edges1.txt For testing simplicity, always assume the first files name is commands1.txt and the seconds file name is edges1.txt. commands1.txt contains a list of commands and edges1.txt contains the information on edges of the graph. 3. Your drivers program will only takes the following commands: graph end_graph print_graph depth_first_search quit Objectives 1 The program should print out each entered command before processing it. Below please find the description for each command. graph,startLine,endLine A real example of this command can be: graph,0,4 When your driver program sees this command, it should start reading from edges1.txt which contains the graph edges information. It should read from the line specified by the first number after graph, and read up to the line specified by the second number, and populate its data into your graph, and create an adjacency list representation of the graph. For above example, the driver program should read from line 0 to 4 of edges1.txt, which means that it should read 5 lines (5 edges), and create a graph from them. In case the second number is larger than the last line of the file, the program should just read till the end of the file. File edges1.txt contains the information on edges in the following format: Arizona State,34,New Mexico,10 Boise State,52,Idaho State,24 Florida State,14,Boston College,7 Akron,52,Savannah State,9 Arizona,77,Northern Arizona,13 Arkansas State,70,Missouri State,7 ...... Each line contains a result of a college football game where: the first string is the university that won the game, the second string is the winners score, the third string is the university that lost the game, the forth string is the losers score. Above four strings are separated by commas. For this assignment, you may consider using an array of linked list to store the graph information. The university names need to be stored in alphabetical order, both for the from nodes in the array and also to nodes in each linked list. Your program needs to read edges from edges1.txt within the specified lines to determine all university names that are used as either a from node or a to node, and create an array of linked lists with the size being the number of such universities. end_graph This command should free the memory allocated for your graph, i.e., free memory of the adjacency list 2 print_graph This command should print the content of the graph, using the following format: Arizona State beat: Florida State(43-14), New Mexico(58-23), Oregon(12-9) Southern Arizona beat: none Texas A&M beat: New Mexico(32-12) UCLA beat: Arizona State(62-27) Arizona State beat: Florida State(43-14), New Mexico(58-23), Oregon(12-9) means that: There is an edge from Arizona State to Florida State, an edge from Arizona State to New Mexico, and an edge from Arizona State to Oregon. The numbers within parentheses indicates their scores for each game where the first number is the winning score and the second number is the losing score. From every university that is used within the specified lines of the edges1.txt needs to be listed here, and to which university that it has an edge. Please print none if there is no edge coming out of some university (see above example). depth_first_search For this command, starting from the node (the university) that comes first in alphabetical order, it should perform a Depth First Search on the graph and prints out: the pi array values (DFS . attribute for each node) starting time array values (DFS .d attribute for each node) finishing time array values (DFS .f attribute for each node) It should use the following format: The array pi content: pi[Arizona State] = none pi[Arkansas] = Florida State pi[Florida State] = Arizona State pi[Mississippi State] = none pi[New Mexico] = Arizona State pi[Oregon] = Arizona State pi[Texas A&M] = Mississippi State pi[UCLA] = Oregon The array discoverTime content: discoverTime[Arizona State] = number 1 discoverTime[Arkansas] = number 3 discoverTime[Florida State] = number 2 discoverTime[Mississippi State] = number 13 discoverTime[New Mexico] = number 6 3 discoverTime[Oregon] = number 8 discoverTime[Texas A&M] = number 14 discoverTime[UCLA] = number 9 The array finishTime content: finishTime[Arizona State] = number 12 finishTime[Arkansas] = number 4 finishTime[Florida State] = number 5 finishTime[Mississippi State] = number 16 finishTime[New Mexico] = number 7 finishTime[Oregon] = number 11 finishTime[Texas A&M] = number 15 finishTime[UCLA] = number 10 quit This command quits the program and exit. Please see the sample input files, commands1.txt, edges1.txt, and sample output file output1.txt. Note that all outputs should be printed to a console instead of writing to a file. Implementation/Documentation Requirements You need implement this program using C++ and it has to read from two files (argv[1] and argv[2]) . Your program needs to compile and execute in general.asu.edu. You need to define graphInsertNode, graphInsertEdge, depthFirstSearch, and destructor to free the memory for your graph. You must use the provided data sets. You are not allowed to use any predefined data structures (such as ones in the library in C++, etc.) except arrays and strings, you need to build your own data structures and operations associated with them (such as insert or search). Copy any codes from other peoples programs is considered to be cheating and will lead to a report to the Dean and you will be penalized. Also check the rules stated in the syllabus of the course regarding the academic integrity. At the top of each source code file, add the following information: // Name of Author(s): // ASU ID: // Homework Number: // Description: A sample test case provided commands1.txt edges1.txt output1.txt 4 What to turn in Under the submission link on Blackboard, submit a zip file named youFirstNameyourLastName. zip containing the following: 1. One or more files of your well documented C++ source code (with a file extension .cpp or .h) implementing the commands required. 2. A Makefile that compiles your program to an executable named A7p1 on the Linux machine general.asu.edu. Our TA will write a script to compile and run all student submissions on general.asu.edu; therefore executing the make command must produce the executable file A7p1 in the same folder as your source code files. After such A7p1 file is produced, then we should be able to execute your program using the command: ./A7p1 command1.txt edges1.txt where command1.txt and edges1.txt are file names, but we should be able to use files with a different name with a content in the format specified in the project statement.. Your program must read from a keyboard, not a file. Error Handling Your program will be tested with other input besides the sample input given, thus is expected to be robust. Grading Rubric 2 pts 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) 1 pt makefile is submitted and it works correctly to generate A7p1 executable file 12 pts Each of the following functions are defined correctly: graphInsertNode, graphInsertEdge, depthFirstSearch, and destructor. 14 pts Correct output for the test case(s) Total points: 30 commands1.txt graph,0,10 print_graph depth_first_search end_graph graph,2,25 print_graph depth_first_search end_graph quit edges1.txt Oregon,31,Florida State,25 Mississippi State,29,Arkansas,17 Mississippi State,31,Texas A&M,25 UCLA,62,Arizona State,27 Florida State,22,Arkansas,17 Arizona State,12,Oregon,9 New Mexico,14,Arkansas,10 Texas A&M,32,New Mexico,12 Arizona State,43,Florida State,14 Arizona State,58,New Mexico,23 Oregon,25,UCLA,13 Oregon,18,Washington State,15 Washington State,28,Utah,27 Utah,39,Florida State,15