So, we got out of class a little early on one day and that gets me to thinking - what kind of assignment can I really give to the students to help them not only better understand graphs, but also their possible representation schemes in programs. I was not allowed to think too long because I was running late to the AA meeting (Array-Haters Anonymous). As usual, they ask us to speak, so I got up:
Adrienne: "Hello, my name is Adrienne."
Group: "Hello Adrienne."
Adrienne: "I have a problem."
Phil: "Acknowledging you have a problem is the first step."
Adrienne (after a comment that is not suitable for this posting): "I was presenting the adjacency matrix representation scheme for graphs to my Discrete Structures class, and aside from the few algorithms that I know of that are easier when you have a matrix representation, the idea of using an array to represent it is just so icky."
Group (Chorus of): "Arrays bad." "Arrays- yick." "Boo - Arrays."
.... (Much bad-mouthing of arrays ensues, but then a suggestion emerges.)
Suggestion: Why not use a Hash Set as the storage scheme for the adjacency matrix? Think about it, you are going to store in the i-j entry in the matrix whether or not a pair is present, instead, just store the ordered pair (i,j) in a Hash Set. It saves the problems of a mostly empty array structure, but allows the easier searching power of a Hash Set. It is also not a nested structure like a Hash Map of Hash Maps or Linked List of Linked Lists.
Adrienne: "That's right - the adjacency relation! I wonder what the issues are for each of the types of implementations? ..."
You are to build a class that models the graph. Recall the two representation schemes for graphs. The first is an adjacency list and the second is an adjacency matrix. We discussed that an adjacency list could be a hash map of hash maps or a linked list of linked lists. Either is acceptable. We also discussed the adjacency matrix and said that it is most often represented in the system by an array. As the suggestion above brings up, you will use a Hash Set to mimic the adjacency relation. You will store instances of the OrderedPair class in the Hash Set. OrderedPair.java is in the Set package we showed earlier in the semester. You will also create a graph class that uses an array for the storage of the adjacency matrix. The graph object must implement the interface below. Basically, you will write three graph classes, one using an adjacency list, one using an adjacency matrix stored in an array, and one using an adjacency relation stored as a Hash Set. Your implementations should work for both directed and undirected graphs.
The design decisions are totally up to you regarding how you are going to model Vertices and Edges. You should justify your design decisions for your implementation in your discussion document described below. The algorithms for Warshalls, DFS, BFS, and EulerPath are all discussed in Chapter 6 of your book. They present pseudo-code that you may use to guide your implementation. If you choose to use algorithms that differ from the pseudo-code presented in the book, you need to give appropriate citation for your sources. Any decisions that you deem important should be discussed in your document to clarify how your Graph works.
You should also provide an Application program that tests your code. You should show that for all three types of graphs all the methods work correctly. This program should be easy to read and give good output as to what is going on.
Along with the code for the graph and the code to test it and show it works, you are required to do a write-up about your experiences with the different representation schemes for graphs. In this write up, please analyze how easy/difficult it was to code the methods of the interface depending on the representation scheme. Big-oh analysis of efficiencies of the various algorithms is encouraged but not necessary. Especially of interest to me is your opinion of which representation scheme seems best, not only for efficiency and ease-of-coding, but also for ease of understanding. The answer for each of those sections does not have to be the same, but I would like you to make a stand about which way is the best and justify your position. (There is no right or wrong for this part).
I am not requiring that you use Java to complete this extra credit assignment. You may use C/C++ if you wish. You also have the option of using some other language if you get approval from me first. If you are using a language other than Java, you need to provide the appropriate makefile and documentation about your submission so it can be run. If I have any issues with running your code because I can not understand how to do so, the extra credit will not be graded at all. If you are using Java, your test code should be in a file named App.java. You should also create a package named Graph for your submission.
Please submit a zip of all your files named Graph.zip using the submission
command submit_cse191. If you have never submitted anything on our
systems, or need an account to do this program on, please see Adrienne
immediately if not sooner. The extra credit code should be submitted no
later that 11:59:59pm on Thursday, May 8th. Friday,
May 9th