Perform a benchmark analysis of the following problems:
Problem 1: Write an algorithm to classify the edges of a directed graph G into the four categories: tree edge, back edge, forward edge and cross edge (defined in 22.3 Depth First Search - Classification of edges).
Problem 2: An Euler circuit in an undirected graph is a circuit (i.e. a cycle that may go through some vertices more than once) that includes every edge exactly once. Give an algorithm that finds an Euler circuit in a graph, or tells that the graph doesn't have one.
Problem 3: Write a depth-first search algorithm to determine if an undirected graph has a cycle.
Problem 4: Write a breadth-first search algorithm to determine if a directed graph has a cycle
Implementation, testing and documentation required for each of the above 4 problems.
Note on SUBMITTING
1. Format: You should submit for each of the four problems: (1) all the source files (.java files under the src folder; please do not sent the class files or other files), (2) a screenshot sample file (the output displayed while running your application to show the required functionalities) and (3) a documentation file. The documentation should contain at least the design decisions, the test plan, the output for the runs. The documentation should be no more than two pages in length and no less than one page. The font size should be 12 point, the page margins one inch, and the paragraphs single spaced.
2. Input data: you should test all your algorithms for at least 2 input graph data (the data does not have to be read from the input; hard-coded is good enough, for full grade). One input data per problem is of your own choice, while the other one is mandatory as follows:
Problem 1- the directed graph G=(V, E) with the following sets of vertices and edges:
V=(A, B, C, D, E, F, G};
E={(A, D), (A, F), (B, A), (C, A), (C, B), (C, D), (C, E), (C, F), (D, B), (D, G), (E, G), (F, A), (G, E)};
Problem 2- the undirected graph G=(V, E) with the following sets of vertices and edges:
V={1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
E={(1,2), (1,10), (2,3), (3,4), (3,6), (3,9), (4,5), (5,6), (6,7), (6,9), (7,8), (8,9), (9,10)}. Please notice that the graph is undirected; thus
although an edge (n1,n2)ÎE occurs only once in the edges set, it goes both ways, that is (n1,n2) AND (n2,n1);
Problem 3- the undirected graph G=(V, E) with the following sets of vertices and edges:
V= {1, 2, 3, 4, 5, 6, 7}
E= {(1, 2), (1, 6), (2, 3), (2, 4), (2, 5), (3, 5), (4, 5), (5, 1),(6, 4), (6, 7)};
Problem 4- the directed graph G=(V, E) with the following sets of vertices and edges:
V=(A, B, C, D, E, F, G);
E={(A, B), (A, C), (A, F), (B, C), (B, D), (D, A), (D, C), (E, C), (E, G), (F, A), (F, C), (G, D), (G, E)}.