Programming question for Homework 4

Part A

Design and implement Java classes for representing and manipulating graphs. A graph is determined by whether it is directed or undirected, by the number of its nodes, and by the set of its weighted edges. The number of nodes and the directed/undirected property are determined when the graph is instantiated, and do not change during the lifetime of the graph. The nodes of the graph are labeled by integers 0,1,..,(n-1), where n is the number of nodes. The set of edges of a graph is not fixed. Initially, a graph contains no edges at all. A graph implementation should support methods for inserting and removing (weighted) edges. No multiple edges from the same source to the same target node are allowed. You should implement (parts of) three different representations: one that uses an adjacency matrix to store edges, one that uses adjacency lists, and one that stores edges in a single linked list of edges.

Part B

Implement a Java method for determining the connected components of a given undirected graph using disjoint sets. Your algorithm should be very similar to that described on page 500 of your textbook. The disjoint set structure you should use is the one you implemented in Assignment 3. If you are not sure whether your code from Assignment 3 works properly, you can use the following binary Java class files that implement disjoint sets:

For more details, including exact specifications of the methods that you should implement, see the starter code. All of your work must be done inside the AdjMatrixGraph, AdjListsGraph, and ConnectedComponents classes, where indicated by comments that start with: "// TODO:". You may also add appropriate instance variables or helper methods.

Submission Instructions:

  1. Submit your code using the "submit" mechanism on fissue (by 5:30pm on the Thursday, March 22). Use the following command from the directory containing your solution: submit -N PGM4 cscb63s AdjMatrixGraph.java AdjListsGraph.java ConnectedComponents.java
    The command "man submit" contains general instructions for submitting your code electronically.

  2. Submit only three .java files: AdjMatrixGraph.java, AdjListsGraph.java, and ConnectedComponents.java (after you have implemented the missing parts) to the directory called PGM4. All the code that you implement should be inside those files.

  3. Do not submit any other files, and in particular, do not submit any class files. If you do, we will delete them before we compile your code.

  4. Do not submit any printout of the code.

  5. Do not rename the files, or any of the methods and variables found in our starter code.

  6. Fill in your name, student number and login name in the comment at the top of the ConnectedComponents.java file. If you have a partner, you should also fill in the corresponding information about your partner.

  7. We will test your code using our own tester code. The tester that we provide is very basic, running it successfully does not guarantee that your code is correct or will pass our marking tester routine. You are encouraged to derive your own  test cases.

  8. Your code must compile and run on the standard Unix/Linux system of your campus (cdf/fissure/cslinux). Test it there! Programs that do not compile and run get 0 marks.