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 p2p2. It will be executed using the following command: ./p2p2 commands3.txt edges3.txt Note that the name of the files such as commands3.txt and edges3.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. In addition to the commands implemented in the phase 1, you need to implement the commands: compute_transpose, and find_cycles that will be in the first file. The program should print out each entered command before processing it.
It needs to compute the transpose GT of the graph and prints its content. The transpose of the graph G contains exactly the same set of node as the original graph G, but with the edges of G with their directions reversed. Another adjacency list needs to be created to store the content of the transpose where university names are stored in alphabetical order, and then it should print the content the transpose using the following format (they need to be in alphabetical order just like print_graph command from the phase1):
Arizona is beaten by: California(43-33)
Colorado State is beaten by: Arizona(21-12), Washington State(38-25)
Florida State is beaten by: Arizona(21-20), Arizona State(23-15), Colorado State(29- 25)
Oregon is beaten by: Colorado State(47-43), Florida State(22-11)
There are cases where UniversityA beat UniversityB, UniversityB beat UniversityC, and UniversityC beat UniversityA. This will create a cycle in the graph. Universities in such cycle might be considered to be in the same level in their strength. This command needs to find all cycles by following the algorithm:
1. Perform depth-first-search on the graph and compute finishing time for each node (university).
2. Compute the transpose GT of the graph. The transpose of the graph G contains exactly the same set of node as the original graph G, but with the edges of G with their directions reversed.
3. Perform depth-first-search on the transpose GT of the graph, but in the main loop of DFS, visit the nodes (university names) in order of decreasing order of their finishing time computed in the step 1.
4. Output the nodes of each tree in the depth-first-search formed in the step 3 as a separate cycle. This means that for each iteration of the main loop (outer loop) of DFS in the step 3, there will be a group of universities in a cycle. You do not need to print out a cycle group with one university. Print only the cycle groups with at least two universities, using the following format:
Cycle group 0 size: 2
Arizona, California
Cycle group 1 size: 5
Colorado State, Washington State, Texas A&M, Oregon, Florida State
The above output indicates that there are two cycle groups, one containing two universities with their names listed below, and another containing 5 universities with their names listed below. Note that the order of universities in each cycle group does not matter, but your program needs to compute the correct sets of universities.