Lab 6: 15-111 Fall 2002

Lab 6: Reimplementing the Graph Class

Due Date: midnight Sunday, October 27

Background:

Lab 6 will allow you to get some familiarity with linked lists. You will re-implement the graph class using an adjacency list format instead of an adjacency matrix. Once you're done, you will use the Intro-CS Assignment Dropoff form to hand in your finished program.

What You'll Need

Download the lab6.zip file from the 15-111 course web site. Unzip the file and you should see the following:

IntList.java, the code we developed in lecture (to be used as a model for your code) along with a main to test it
Edge.java, a complete class for use in this lab
Graph.java, a stubbed version of graph, almost identical to the initial file for Lab 5 (the signature for getMyEdges is the only one that's changed)
graph.txt, the data file, same as in Lab 5

You can either copy your Graph.java file from the last lab into the folder you're using for this lab and change the method implementations as needed or start from scratch again with the stubbed version provided here. Just make sure you're working on the correct version!!

You may want to fiddle around with the IntList class BEFORE launching into modifying the graph. You may want to add some new methods. You should definitely make an EdgeList class and satisfy yourself that it is working correctly before working with the adjacency list in the graph.

Assignment

You are re-implementing the Graph class with an Adjacency List, in essence an array of EdgeLists. Each entry in the array will be the list of edges emanating from that vertex. I've provided you with an Edge class to serve as the data object for the nodes of your EdgeList. You will need to first implement an EdgeList class and then replace the 2-d array used in Lab 5 with an adjacency list (EdgeList[ ] adjList). Once you've changed the private instance variable, you should see what changes this causes in the implementations of the methods. You should NOT alter the signature of any of the methods (except getMyEdges) - only their implementations should change. The public interface to the graph should stay the same with that one exception.

As in the Adjacency Matrix implementation, you may NOT assume that an edge is not already present between the two vertices in your new implementation of addEdge (if it is, overwrite its cost with the new value) and you may NOT assume that an edge is in the graph in your new implementation of removeEdge. Your code should behave analogously to that which was present in the Adjacency Matrix implementation and should still perform that Max/Min Degree functions from Lab 5. If you implemented Dijkstra's algorithm in Lab 5, feel free to reimplement it here as well (no new extra credit, though). If you didn't in Lab 5, you may do so here for extra credit.

Handing in your Solution

Your solution should be in the form of a .zip file. When we grade your solution we will unzip the folder and execute the project.

Use the Intro Programming dropoff form to submit your zip file.