Revisions History:
- Created Mar. 11rd, 2013

This is an exercise in creating  your own reusable implementation of the UndirectedGraph ADT. Please read the chapter of your textbook covering graphs very carefully.  In completing this assignment you may use code you  have developed previously in this class, or code in the Java util package. You may also you the code fragments given in the text.

In order to help test your class I have created an application that creates files containing random graphs. By looking at the main in this class you can see how to read these files.

You may be interested in the graph drawing program Graphviz (available from http://www.graphviz.org/) with minimal work you can use it to visualize the graphs you create. This can be very handy for debugging purposes.

Construct your own reusable implementation of the UndirectedGraph ADT based on an adjacency list representation.

You are to also create a class, TestGraphClass, with a main() method that performs the following actions:

1. Create the UndirectedGraph G illustrated below (can be hard-coded into the main() method):

   

2. Call TestGraphClass.printAdjacencies(G) on this graph.
3. Using jUnit design a set of tests on this graph that exercises all of the methods in your undirected graph class
4. Perform the following actions:
   • Using the graph generator provides, create the following files
     • n=300, m=500, seed 349
     • n=100, m=300, seed 12554
     • n=1000, m=1200, seed 369
     • n=100, m=4800, seed 9873
   • For each file print the following statistics
     • Node with greatest degree (e.g. Max degree: Node 5 with degree 8)
     • Node with smallest degree (e.g. Min degree: Node 301 with degree 0)

Summary

• Create class MyUndirectedGraph that implements the UndirectedGraph interface
• Create class TestGraphClass that contains testing methods for class MyUndirectedGraph
• Do testing and experiments and write up the results

Create a class called TestGraphAlgorithms that tests classes DFS and BSF that implement your own reusable version of Depth first search (DFS) and Breadth First Search (BFS), respectively. These classes should be designed based on the Template Method Pattern as described in your textbook for DFS.  You may base your methods on the code fragment provided in the text.

Test these classes carefully.

Summary

• Create abstract classes DFS and BFS
• Create classes DFSOrder and BFSOrder that extends DFS and BFS, respectively.
• Create classes DFSpath and BFSpath that extends DFS and BFS, respectively.
• Create class DFSisConnected that extends DFS
• Create class TestGraphAlgorithms.
• Do testing and experiments and write up the results