Zip file with source files, documentation, &c.
Browsable version of the files above
In this homework, you'll be implementing a general graph
class, and then implementing two separate algorithms for
finding shortest paths in graphs:
Goals
- Gain experience in determining how to represent abstract structures using the data structures you are already accustomed to.
- Gain experience using the basic data structures in more complicated ways than before.
- Implement a general graph class.
- Implement two different algorithms for searching graphs, one of which is a good example of a Dynamic Programming (DP) algorithm.
The Graph Class (30 points)
The core of this assignment is the GeneralGraph
class, which implements the Graph interface. The
graphs we are dealing with are
In previous assignments, such as the queue, hashtable, and priority queue, there was not much choice in how to implement the interface we gave you. This assignment is a bit more open-ended; we give you the interface for the graph, but there are many possibly ways of implementing it. You should look over the Graph interface and understand it well before starting on your graph implementation.
Ideally, your implementation should be:
- Simple and clean. You don't want every vertex to be stored in seven separate structures, for example; not only would that be inefficient, but it would be easy to forget to update some of them during some operations, leaving your graph class in an inconsistent state.
- Efficient. The operations you have to implement should be fast; ideally, constant-time. Furthermore, your representation should be space-efficient; if I make a graph with no edges at all, for example, it would probably be best not to allocate space for every possible edge.
- Short. This class can be implemented by adding about 50 lines of code. If you are adding more than 100 lines, you should consider cleaning up your code.
Of course, there are tradeoffs, and you should think about what representation will do best overall.
Since you have already written your own implementations of many of the more interesting data structures, there are no restrictions on which classes in the Java standard library you may use.
Dijkstra's Algorithm (30 points)
Your first task, once your graph class is working well, is to implement Dijkstra's shortest-path algorithm. The algorithm should stop as soon as it has found the shortest path from the start vertex to the end vertex, and it should return the list of edges in the path (from that list, the vertices in the path as well as the cost of the path can both be found pretty easily).
Of course, Dijkstra's algorithm does not work in all cases on graphs with edges of negative weight; as you've seen, Dijkstra's algorithm can fail on such graphs, and your implementation should throw an IllegalArgumentException if it is given a graph with a negative-weight edge. However, our graph class allows such edges, so we will also implement a less efficient algorithm that succeeds in such cases: the Bellman-Ford algorithm.
Your implementation should run in time O((|V|+|E|)\log(|V|)), including the cost of the operations inside the graph class.
The Bellman-Ford Algorithm (20 points)
The interface for the Bellman-Ford algorithm is exactly the same as with Dijkstra's algorithm; it should behave the same way, except that it should give correct results on graphs with negative-weight edges as long as there are no negative-weight cycles. Your implementation should throw an IllegalArgumentException if the graph it is given contains a negative-weight cycle.
Your implementation should run in time O(|V|*|E|).
Hints
- The collections returned by vertices, outgoingEdge, and neighbors in your graph class must be read-only; any attempts to modify them should throw an UnsupportedOperationException. You will likely want to take advantage of some of the functions in the Collections API in the Java standard library; in particular, the functions beginning with "unmodifiable"!
- Furthermore, the collection returned by vertices should represent a view of the vertex set and not a snapshot of it; that is, if I call vertices and later add a new vertex to the graph, the collection I got should now include the new vertex (even though I haven't called vertices again).
-
This assignment makes heavier use of generics than did
previous assignments; it is important to understand exactly
what's happening.
The Graph interface takes two generic types. V is a type for vertices; there are no restrictions on it --- you can choose any class you want in the vertices of your graphs. E is the type for edges, but there are certain restrictions: we must, at the minimum, be able to ask an edge for its source vertex, destination vertex, and weight. Therefore, E must extend the Edge class.
The shortestPath function is a function that uses generics, even though its class doesn't. Specifically, it takes V (the type for vertices) and E (the type for edges, which must extend the Edge class) as parameters, and operates on a Graph<V,E>. Even though it uses generic types, you can call the function normally (as if it didn't use generics at all): Java will figure out what types it must use for V and E.
You may want to read the Java generics tutorial for a more complete reference; section 5 discusses generic methods.
- To help with debugging, we are providing a GraphVisualizer class which can output GraphViz files of graphs you give it.
Coding Style: 10 points
It should go without saying that your submission must have good style. This is needed so that the TAs can understand your code and give you partial credit. It's also a good habit.
Theory Questions: 10 points
In the file theory.txt there are some theory questions. Please answer the questions in this file and submit it along with your .java files.