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:

a. 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.)

b. 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.

Graph Class:

import java.util.*;

//Graph is a class whose objects represent graphs. public class Graph { ArrayList nodeList; ArrayList edgeList; public Graph() { nodeList = new ArrayList(); edgeList = new ArrayList(); } public ArrayList getNodeList() { return nodeList;

}

public ArrayList getEdgeList() { return edgeList;

}

public void addNode(Node n) { nodeList.add(n);

}

public void addEdge(Edge e) { edgeList.add(e);

}

public String toString() { String s = "Graph g. "; if (nodeList.size() > 0) { for (Node n : nodeList) { // Print node info String t = " Node " + n.getName() + ", abbrev " + n.getAbbrev() + ", value " + n.getVal() + " "; s = s.concat(t); } s = s.concat(" "); } return s; } }

Node Class: public class Node {

String name; String val; // The value of the Node String abbrev; // The abbreviation for the Node ArrayList outgoingEdges; ArrayList incomingEdges; public Node( String theAbbrev ) { setAbbrev( theAbbrev ); val = null; name = null; outgoingEdges = new ArrayList(); incomingEdges = new ArrayList(); } public String getAbbrev() { return abbrev; } public String getName() { return name; } public String getVal() { return val; } public ArrayList getOutgoingEdges() { return outgoingEdges; } public ArrayList getIncomingEdges() { return incomingEdges; } public void setAbbrev( String theAbbrev ) { abbrev = theAbbrev; } public void setName( String theName ) { name = theName; } public void setVal( String theVal ) { val = theVal; } public void addOutgoingEdge( Edge e ) { outgoingEdges.add( e ); } public void addIncomingEdge( Edge e ) { incomingEdges.add( e ); } } Edge Class: public class Edge { String label; int dest; int dist; Node tail; Node head; public Edge( Node tailNode, Node headNode, String theLabel ) { setLabel( theLabel ); setTail( tailNode ); setHead( headNode ); } public Edge(int dest, int dist,String label) { //Create the destination Vertex Index this.dest = dest; this.dist = dist; // Source Vertex index this.label=label; // Label of Edge } public String getLabel() { return label; } public Node getTail() { return tail; } public Node getHead() { return head; } public int getDist() { return dist; } public void setLabel( String s ) { label = s; } public void setTail( Node n ) { tail = n; } public void setHead( Node n ) { head = n; } public void setDist( String s ) { try { dist = Integer.parseInt( s ); } catch ( NumberFormatException nfe ) { dist = Integer.MAX_VALUE; } } }

DelivB Class (DelivB Need to be implemented) :

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 re-tests outputFile.delete(); } try { output = new PrintWriter(outputFile); } catch (Exception x ) { System.err.format("Exception: %s%n", x); System.exit(0); } } }

Output: Here is sample output for one graph ABO.tct. val AAA BB CDDD E Alfa s S 99 fig Bravo 67 999 -42 3 x Charlie 4 yz 9 Delta 4e 3 22 Echo yes 33 U? ? x 2 2 3 The output for this file should be: Node Start Time Alpha 1 Bravo 2 Charlie 3 Delta Echo 5 End Time 10 9 8 7 6 Type 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 T h- H- HE TEEE THE BE TER The output for graph .txt should be written to file _out.txt, and should be written to the console, too. Output: Here is sample output for one graph ABO.tct. val AAA BB CDDD E Alfa s S 99 fig Bravo 67 999 -42 3 x Charlie 4 yz 9 Delta 4e 3 22 Echo yes 33 U? ? x 2 2 3 The output for this file should be: Node Start Time Alpha 1 Bravo 2 Charlie 3 Delta Echo 5 End Time 10 9 8 7 6 Type 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 T h- H- HE TEEE THE BE TER The output for graph .txt should be written to file _out.txt, and should be written to the console, too