CS 201: Data Structures (Spring 2017)

Lab5: Graph Implementations

1. Goals

To get familiar with how to implement a graph, and think through extensions.

2. Setting up

Download the files for this lab. You'll be writing your code in AdjacencyListGraph.java and AdjacencyMatrixGraph.java. You may wish to refer to the Javadocs for Graph and friends.

3. Graph Implementations

You'll be comparing and contrasting the efficiency and ease of implementation of several different graph methods with the two types of implementations. For now, assume that the graph is undirected.

Open up both graph implementations (AdjacencyListGraph.java and AdjacencyMatrixGraph.java) and note that the instance variables are provided for you. Check in with your partner about what each instance variable is storing and how this differs between the two implementations: make sure you both agree before you continue. You might talk through what the state of the instance variables should be for the graph below:

Next, write the constructor for each implementation. After the constructor has run, the instance variables should not be null.

There are 11 methods in the graph implementations. 6 of them have been provided for you in each implementation:

  1. addVertex
  2. getNeighbors
  3. numVerts
  4. isDirected
  5. isEmpty
  6. clear

Take a look at each of these methods: do what they are doing make sense given your understanding of the organization of the graph data? If not, talk with your partner and/or ask someone before continuing. Are there any differences between the two implementations in the time complexity of any of these methods? Write down any differences. We will compare notes next class.

Now you're ready to write the remaining 5 methods:

  1. Start with hasEdge. Choose either graph implementation to start. Once you've completed one version, go to the other graph implementation and try writing the hasEdge method. Which implementation is easier to write? Which one is more efficient?
  2. Once you've written both hasEdges, write an addEdge method. Can hasEdge be a helper method here? Just as for hasEdge, start off with one graph implementation and get that one working first. Then move to the other implementation. Check and make sure that both hasEdge and addEdge work properly: main has some tests that may be helpful for checking your implementation. Many tests will still fail because you don't yet have a complete implementation yet.
  3. Brainstorm how to write a getDegree method. How will this method differ in the two implementations? Try writing the code in each method, and compare the efficiency across the two implementations.
  4. You should now have a good understanding of how edges are stored in each implementation. How should getInDegree differ from getDegree? Implement getInDegree next, and again, talk with your partner about differences in ease of writing the code and in the efficiency of this method between the two implementations.
  5. If you have time, finish up by implementing the final method: numEdges. Think carefully about how to avoid counting edges twice.

4. Extensions

If you have extra time, think about the following extensions. After you've thought through all of them, you may code the ones that interest you.

Directed Graphs

You implemented an undirected graph. Would it be easier or harder to implement a directed graph? Brainstorm ways of making your class able to represent both directed and undirected graphs.

Weighted Graph

In the previous section, you implemented an unweighted graph. Read through the WeightedGraph interface to remind yourself of how weighted graphs differ. Discuss with your partner how you would implement a weighted graph. Try to come up with a way that would preserve the general structure of your existing code.

Labelled Graphs

The included LabelledGraph interface is very similar to the Graph interface, except rather than methods referring to vertices by integers, they refer to vertices by labels. For example, the labels might be Strings or ZooAnimals. Choose either AdjacencyListGraph or AdjacencyMatrixGraph and extend it as a subclass that implements LabelledGraph<T>. It needs only one instance variable and it should not duplicate the code you have in the graph implementation. (This is the power of inheritance!) What type of instance variable would you need? Sketch out how you would implement hasEdge(T begin, T end). Are there any advantages or disadvantages of implementing the labelled graph as a subclass rather than a separate graph that has a Graph as an instance variable?

getNeighbors()

In the adjacency list implementation, there's a note about how the provided implementation isn't a great one: it could allow a client to change the structure of your graph by doing something to the returned list. Brainstorm ways to prevent this from happening without increasing the time complexity of the method. Hint: Using a nested inner class might help.

This lab modified from one designed by Anna Rafferty.