import java.io.*;

// Class DelivB does the work for deliverable DelivB of the Prog340

public class DelivB {

File inputFile; File outputFile; PrintWriter output; Graph g; public DelivB( File in, Graph gr ) { inputFile = in; g = gr; // Get output file name. String inputFileName = inputFile.toString(); String baseFileName = inputFileName.substring( 0, inputFileName.length()-4 ); // Strip off ".txt" String outputFileName = baseFileName.concat( "_out.txt" ); outputFile = new File( outputFileName ); if ( outputFile.exists() ) { // For retests outputFile.delete(); } try { output = new PrintWriter(outputFile); } catch (Exception x ) { System.err.format("Exception: %s%n", x); System.exit(0); } System.out.println( "DelivB: To be implemented"); } }

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.

Below are Test File for this Program

~ 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

~ val A D E F I K L N O P Q S A ~ ~ ~ ~ 3 ~ ~ ~ ~ ~ ~ 1 ~ D ~ ~ ~ ~ ~ ~ 5 ~ ~ ~ ~ ~ ~ E ~ 2 ~ ~ ~ ~ 3 ~ ~ ~ ~ ~ ~ F ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ I ~ ~ ~ ~ ~ ~ ~ ~ 2 ~ ~ ~ ~ K ~ ~ 5 ~ ~ ~ ~ ~ ~ ~ ~ ~ 3 L ~ ~ ~ ~ 5 ~ ~ ~ 1 ~ ~ ~ ~ N ~ ~ ~ ~ ~ ~ ~ ~ ~ 2 1 ~ ~ O ~ ~ ~ ~ 4 ~ ~ 1 ~ ~ ~ ~ ~ P ~ ~ ~ ~ ~ I ~ ~ ~ ~ ~ ~ ~ Q ~ ~ 1 1 ~ ~ ~ ~ ~ ~ ~ ~ ~ S S ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~