Problem Specification:

Using Java programming language, do a Depth-first search of the directed graph, starting at the node with the value S (not case sensitive). List the starting and finishing times of each Node, and the class of each Edge (tree edge(T), forward edge(F), back edge(B), cross edge(C)). Make the starting time of the source node time 1. At many points in the search, you may have to choose which node to explore next. Here are the rules to do so:

1. If you have a choice among two or more unexplored Node to explore next, there are two cases:

1. If the values of all Edges are all integers, choose the Edge with the lowest value. If there is a tie, choose the Edge to the Node whose name comes first in lexicographic order. (All node names are unique.)
2. Otherwise, if the values of the Edges are not all integers (at least one general alphabetical character or non-positive integer), choose the Edge to the Node whose name comes first in lexicographic order.

2. If you have explored as far as possible from the starting node without exploring every node of the graph, continue from the Node whose name comes first lexicographically from among all unexplored Nodes.

The sample input which must be provided through text file

~ val AAA BB C DDD E Alfa S ~ > ~ 99 fig Bravo 67 999 -42 3 x == Charlie ~ ~ 4 ~ yz 9 Delta 4e 3 22 x ~ !=2 Echo yes ~ ~ ~ d>e 33

Tree Edge: It is an edge that is present in the tree obtained after applying DFS on the graph. All the Green edges are tree edges.

Forward Edge: It is an edge (u, v) such that v is a descendant but not part of the DFS tree. Edge from 1 to 8 is a forward edge.

Back edge: It is an edge (u, v) such that v is the ancestor of node u but not part of the DFS tree. Edge from 6 to 2 is a back edge.

Cross Edge: It is an edge that connects two-node such that they do not have any ancestor and a descendant relationship between them. Edge from node 5 to 4 is a cross edge.

The sooner is the better and your help is very much appreciated.

Thanks

The output for this file should be: Node Alpha Bravo Charlie Delta Echo Start Time 1 2 3 4 5 End Time 10 9 8 7 6 Edge AAA-BB AAA-DDD AAA-EEE BB-AAA BB-BB BB-C BB-DDD BB-E C-BB C-DDD C-E DDD-AAA DDD-BB DDD-C DDD-E E-DDD E-E Type F F B B T F F B F B B B T B B 1 N 3 4 5 8 7 6 The output for this file should be: Node Alpha Bravo Charlie Delta Echo Start Time 1 2 3 4 5 End Time 10 9 8 7 6 Edge AAA-BB AAA-DDD AAA-EEE BB-AAA BB-BB BB-C BB-DDD BB-E C-BB C-DDD C-E DDD-AAA DDD-BB DDD-C DDD-E E-DDD E-E Type F F B B T F F B F B B B T B B 1 N 3 4 5 8 7 6