CSci2110 - Assignment 5

Due: Tuesday April 3rd  before 11:55 pm

Revisions History:
- Created Feb. 27th, 2007

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.

Question 0: Implementing the UndirectedGraph ADT 

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):

    image1.jpg (29545 bytes)

  2. Call TestGraphClass.printAdjacencies(G) on this graph.
  3. Design a sequence of tests on this graph the exercises all of the methods in your undirected graph class
  4. Perform the following actions:
  5. Perform a sequence of experiments to determine for a randomly created undirected graph with n vertices and m Î {n...((n2-n)/2)}edges what the expected max and min degree is. Draw some conclusions.

Summary

Question 1: Implementing Depth First Search & Breadth First Search  

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.

You will test your DFS and BSF methods using the GraphAlgorithms class with a main() method that performs the following actions:

  1. For the graph shown above print the depth first and breadth first traversals of this graph starting from A and I.
  2. Perform the following action:
  3. Perform the following action five (5) different times in a loop:

Summary