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 game. 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. After compiling your program using makefile, it should generate an executable file named p2p1. It will be executed using the following command:
./p2p1 commands1.txt edges1.txt
Note that the name of the files such as commands1.txt and edges1.txt might be different, but your program will always be executed using two files and the first file will contain a list of commands and the second file will contain the information on edges for your graph.
3. You need to implement a driver program that takes the commands: graph, end_graph, print_graph, depth_first_search, and quit from the first file. The program should print out each entered command before processing it.
A real example of this command can be:
graph,0,4
Your program should start reading the second file that 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 their score, the third string is the university that lost the game, and the forth string is their score. These four strings are separated by commas in each line.
Your program needs to read the second file 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 an adjacency list needs to be created for the graph. For instance, if the command is graph 0, 4, then it should read from the line 0 to 4, which means that your program should read 5 lines (5 edges), and create a graph from them. If the second number is larger than the last line of the file, the program should just read until the end of the file.
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 the second file 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.
it should free the memory allocated for your graph, i.e., free memory of the adjacency list
it 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)
Here Arizona State beat: Florida State(43-14), New Mexico(58-23), Oregon(12-9) means that we have 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 second file 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 the example above).
It should perform Depth First Search starting with the university that comes first in alphabetical order, and prints out the pi array values, starting time array values, and finishing time array values using 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
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
the command quits the program and exit.
**You need implement this program using C++ and it has to read from two files (argv[1] and argv[2]) .
**You need to define graphInsertNode, graphInsertEdge, depthFirstSearch, and destructor to free the memory for your graph.
**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 need to build your own data structures and operations associated with them (such as insert or search).