Project 4: Building Graphs

due by Midnight on Thursday, December 10, 2009
(email your Graph.java source file to Joel Carver)

Below is Bob Lafore's application program (from chapter 13) that builds a graph and does a depth-first traversal of that graph.

	class DFSApp {
   public static void main(String[] args) {
      Graph theGraph = new Graph();
      theGraph.addVertex('A');    // 0  (start for dfs)
      theGraph.addVertex('B');    // 1
      theGraph.addVertex('C');    // 2
      theGraph.addVertex('D');    // 3
      theGraph.addVertex('E');    // 4

      theGraph.addEdge(0, 1);     // AB
      theGraph.addEdge(1, 2);     // BC
      theGraph.addEdge(0, 3);     // AD
      theGraph.addEdge(3, 4);     // DE

      System.out.print("Visits: ");
      theGraph.dfs();             // depth-first search
      System.out.println();
      }  // end main()
   }  // end class DFSApp
	

Your job for this project is to make some improvements to the underlying Graph class in order to add some versatility and to make the application programmer's job a bit easier. In particular:

• The application programmer shouldn't have to know or remember which vertex is vertex 0, which is vertex 1, etc. The application programmer should be able to refer to vertices by their character values 'A', 'B', etc at any time.
• The application programmer should have some ability to use the results of a depth-first traversal, but this will only be possible if the results of that traversal are returned to the application program (rather than just being displayed on the console).
• The application programmer should be able to specify a starting vertex for the depth-first search.

For these reasons, Bob Lafore's original application program has been rewritten (below) to reflect these improvements.

class DFSApp {
   public static void main(String[] args) {
      Graph theGraph = new Graph();
      char [] searchOrder;
       
      theGraph.addVertex('A');    // 0  (start for dfs)
      theGraph.addVertex('B');    // 1
      theGraph.addVertex('C');    // 2
      theGraph.addVertex('D');    // 3
      theGraph.addVertex('E');    // 4

      theGraph.addEdge('A', 'B');     // AB
      theGraph.addEdge('B', 'C');     // BC
      theGraph.addEdge('A', 'D');     // AD
      theGraph.addEdge('D', 'E');     // DE
      
      searchOrder = theGraph.dfs('A");
      System.out.print("Order of dfs visits when starting at A");
      for (int i=0; i<searchOrder.length; i++) {
         System.out.print(i+":"+searchOrder[i]+"\t");   
      }
      System.out.println();  // 0:A    1:B    2:C    3:D    4:E

      searchOrder = theGraph.dfs('B");
      System.out.print("Order of dfs visits when starting at B");
      for (int i=0; i<searchOrder.length; i++) {
         System.out.print(i+":"+searchOrder[i]+"\t");   
      }
      System.out.println();    // 0:B    1:A    2:D    3:E    4: C
      
      searchOrder = theGraph.dfs('D");
      System.out.print("Order of dfs visits when starting at D");
      for (int i=0; i<searchOrder.length; i++) {
         System.out.print(i+":"+searchOrder[i]+"\t");   
      }
      System.out.println();    // 0:D    1:A    2:B    3:C    4: E
      
   }  // end main()
}  // end class DFSApp
	

Your job is to make the necessary changes to Bob Lafore's original implementation so that this new application program will run correctly.