| CPSC 327 | Data Structures and Algorithms | Spring 2024 |
Using the provided interfaces and class skeletons in /classes/cs327/graph, implement the Graph ADT using either an adjacency list representation (AdjacencyListGraph) or an adjacency matrix representation (AdjacencyMatrixGraph) as discussed below.
Follow the adjacency list and adjacency matrix implementations as discussed in class. (You only need to implement one!)
Do not change the interfaces Graph, Vertex, and Edge or change or remove public elements in other classes.
AbstractGraph, AbstractVertex, and AbstractEdge should contain the elements common to both adjacency matrix and adjacency list implementations, while AdjacencyListGraph/Vertex/Edge and AdjacencyMatrixGraph/Vertex/Edge should contain the elements specific to a particular implementation. In both cases, instance variables should be private. You can add parameters to the (non-public) constructors as needed. You can add getter, setter, and/or other mutator methods as needed; they should be protected. Methods which can be fully implemented using only the instance variables in AbstractGraph/Vertex/Edge should be implemented there. (Replace the default body which throws an UnsupportedOperationException.) Methods whose bodies are implementation-specific should be implemented in AdjacencyListGraph/Vertex/Edge and AdjacencyMatrixGraph/Vertex/Edge — copy the method header from AbstractGraph/Vertex/Edge and replace the default body (which throws an UnsupportedOperationException) with the actual implementation.
For full credit, your implementation should achieve the runtimes discussed in class. This means that you will need doubly-linked lists for the lists of vertices, edges, and (for the adjacent list) incident edges and you'll need to store references to the list node(s) for each vertex and edge so deletion can be O(1). (You will need to create node class(es) for your list nodes. These can (and should) be inner classes in AbstractGraph, AdjacencyListGraph, or AdjacencyMatrixGraph.) For partial credit (a passing grade), you can use Java Lists instead. A recommendation is that you start with List for the lists and then implement doubly-linked lists and store references once everything else is working.
You'll need doubly-linked list ListNodes for a list of vertices and for a list of edges. For extra credit, rather than create two very similar ListNode classes for your doubly-linked lists, utilize generics in your implementation. See Simple Generic Classes for more information.
For methods that return Iterable, the simplest solution is to return an instance of some already-existing collection that implements Iterable, such as a List of some kind (e.g. ArrayList or LinkedList). If your items are not already in that kind of collection, you can build one. This, of course, takes more time but it doesn't change the big-Oh (as long as your collection insert is O(1)) — actually iterating through the collection returned already takes O(size of collection) so adding another O(size of collection) to build the collection comes for "free" (in the big-Oh sense).
For data structure librarieas, which will be used as building blocks in many applications, it is worth investing some time and effort in reducing constant factors as well. For extra credit, avoid creating a new collection for the sake of returning an Iterable — instead, write a class which implements Iterable, which has a method to create an iterator in order to support the for-each loop syntax, and a class which implements Iterator, which has methods hasNext and next to actually support the traversal of the structure. (more information and an example — since your doubly-linked lists aren't contained in a class just for the list, you'll want a separate class implementing Iterable with just a constructor taking the head of the list and an iterator method; also, you don't need remove in the Iterator) Both of these classes can be inner classes; make them protected if you define them in AbstractGraph so that subclasses of AbstractGraph can access them.
Make your code robust — identify (by adding to the public comments) and check (by throwing IllegalArgumentExceptions) preconditions. For the most part these will involve whether or not null is valid for parameter values but there may be some others.
The organization of the provided code illustrates how one might implement an ADT as part of a library when there is a choice of implementations. It is similar to the design of the Java Collections classes, for example the List ADT with List, AbstractList, ArrayList, and LinkedList and the Map ADT with Map, AbstractMap, HashMap, and TreeMap.
The top-level interfaces (Graph, Vertex, and Edge) provide the public view and allow for coding to the interface — a program using the Graph ADT can be written in terms of these interfaces, and only when it comes to creating an actual graph object (with new) is it necessary to specify a particular concrete implementation.
The actual implementation is split: AbstractGraph (and its inner classes AbstractVertex and AbstractEdge) contain elements common to both adjacency list and adjacency matrix implementations, while AdjacencyListGraph (and its inner classes AdjacencyListVertex and AdjacencyListEdge) and AdjacencyMatrixGraph (and its inner classes AdjacencyMatrixVertex and AdjacencyMatrixEdge) contain the implementation-specific elements. AbstractGraph/Vertex/Edge allow for factoring out common code and reduces repeated code.
Packages: The provided classes are in a package graph. Packages provide a way to organize the many classes available in libraries so as to avoid filling up the available namespace, and also correspond to a directory structure for organizing the files where those classes are defined — .java files in package pkg must go in a subdirectory pkg of your main source code directory. If you are using Eclipse, the main thing is to import the provided code into the right place — if that doesn't happen, accept the quick fix that moves them to the package graph). Eclipse will manage compiling, running, and handling the correct import statements if you write a main program to test (which should go in the default package). If you are not using Eclipse, see The Problem of Packages and Using Classes from Packages and ask if you need more help.
Inner classes: Inner classes are to classes as helper methods are to methods — a class which exists only to help with the implementation of another class. A key thing to be aware of, as it explains the choice of access modifiers, is the containing class has full access to the members of the inner class (even private ones) and the inner class has full access to the members of the containing class (even private ones). This means that technically an inner class does not need to provide getters and setters, as its private instance variables can be accessed directly by the containing class, but it is reasonable to continue to do so and access instance variables only through methods. (more on nested and inner classes - sections 5.8.1 and 5.8.2)
About Iterable: A return type of Iterable means that you can write a for-each loop to go through the collection:
for ( Vertex v : g.vertices() ) {
...
}
Why return an Iterable instead of a collection such as a List or an array? One reason is for efficiency — there are a lot of kinds of things you can iterate through, and your things will not necessarily already be in the kind of collection you want to return. The other is for encapsulation — collections are often mutable, and if a method simply returns the same object that it is using internally, the caller now has access to a private object and can make changes to it directly. Returning an Iterable means that the caller only sees the Iterable hat, which does not provide any way to modify the underlying collection regardless of what that object may be underneath.
Object vs generics: To handle weights, labels, and any other information that might be associated with vertices and edges, Vertex and Edge have an associated object. As can be seen from the getObject() headers in Vertex and Edge, this will be of type Object — since every class implicitly inherits from Object, any kind of object can be stored. The drawback of this is that type-checking is shifted to runtime - the caller will need to cast a retrieved Object in order to use methods specific to its actual type. The alternative is to use generics (see Simple Generic Classes) — this makes the element type part of the overall type (e.g. Stack<String>, a Stack of Strings) so it can be checked/enforced by the compiler. However, because Edge involves Vertex, it would have to have type parameters for both the associated edge object and the associated vertex object and the idea of the edge type including the kind of object associated with a vertex has its own drawbacks.
/classes/cs327/graph/Tester.java is a main program to help you test your implementation. (It uses all the methods but is not necessarily comprehensive — feel free to add to it.)
You are encouraged to use Eclipse, though it is not required. It is recommended that you use Java 17 though probably everything will be fine with an older (or newer) version. This software is available on the lab computers in Rosenberg 009 and Lansing 310, or you can set up your own computer. Note that you do not need JavaFX for this assignment so you can skip that part for now.
Hand in your code by copying your Java files into a folder called graph within your handin directory (/classes/cs327/handin/username).