Do a Depth-first search of the directed graph, starting at the node with value S (not case sensitive). List the starting and finishing times of each Node, and the class of each Edge (tree edge, forward edge, back edge, cross edge). 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 Nodes 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 cones first in lexicographic order. (All 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.

Dont Break Existing Functionality

Note that a couple tests will be regression tests. That is, we will run Deliverable A on them. It should work. Actually, it should always work for any test file in any deliverable.

Extra Credit (10 points)

Using Kosarajus algorithm, find the set of Strongly Connected Components, and print out each component. Note that this will require you to:

1. Push the Nodes of graph G onto a Stack in the proper order.
2. Create the inverse graph G of the original graph G.
3. Do a DFS of the inverse graph.

Administrative Details

The prog340 handout describes the format of the input file for this and all program deliverables.

As will always be the case in this class, the program must be written in Java and must run on the University Windows computer systems. To ensure this I strongly recommend that you:

1. Use only Oracle Java 8 SE and earlier constructs, and
2. Test it on the University systems before submission if you have any doubts about its ability to run on the University Windows.
3. As before, minimize disruption to the existing codebase. I realize that you will have to do some machinations to deal with Graphs having Edges with positive integral values differently from more general edges. See Design Thoughts below.

Output:

Here is sample output for one graph AB0.txt.

~ 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

The output for this file should be:

Node Start Time End Time

Alpha 1 10

Bravo 2 9

Charlie 3 8

Delta 4 7

Echo 5 6

Edge Type

AAA-BB T

AAA-DDD F

AAA-EEE F

BB-AAA B

BB-BB B

BB-C T

BB-DDD F

BB-E F

C-BB B

C-DDD T

C-E F

DDD-AAA B

DDD-BB B

DDD-C B

DDD-E T

E-DDD B

E-E B

Strongly connected components:

{AAA,BB,C,DDD,E}

The output for graph .txt should be written to file _out.txt, and may be written to the console, too.

Submit:

Submit the Java source code to the open Deliverable B submission folder. You may submit either the source code or a full Eclipse package, as with Deliverable A.

Test 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

Test File

~ Val NE MD BB NY BR PS CL CI HT IC TT JJ KC LA DB OR NewEngland S x > > > ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Miami ~ < x > > ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Buffalo ~ < < x > ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ NewYorkJ ~ < < < x ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Baltimore C ~ ~ ~ ~ x > > > ~ ~ ~ ~ ~ ~ ~ ~ Pittsburgh ~ ~ ~ ~ ~ < x > > ~ ~ ~ ~ ~ ~ ~ ~ Cleveland ~ ~ ~ ~ ~ < < x > ~ ~ ~ ~ ~ ~ ~ ~ Cincinnati ~ ~ ~ ~ ~ < < < x ~ ~ ~ ~ ~ ~ ~ ~ Houston C ~ ~ ~ ~ ~ ~ ~ ~ x > > > ~ ~ ~ ~ Indianapolis P ~ ~ ~ ~ ~ ~ ~ ~ < x > > ~ ~ ~ ~ Tennessee ~ ~ ~ ~ ~ ~ ~ ~ ~ < < x > ~ ~ ~ ~ Jacksonville ~ ~ ~ ~ ~ ~ ~ ~ ~ < < < x ~ ~ ~ ~ KansasCity C ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ x = > > LosAngelesC P ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ = x > > Denver ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ < < x > Oakland ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ < < < x