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:
addVertex
getNeighbors
numVerts
isDirected
isEmpty
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:
-
Start with
hasEdge
. Choose either graph implementation to start. Once you've completed one version, go to the other graph implementation and try writing thehasEdge
method. Which implementation is easier to write? Which one is more efficient? -
Once you've written both
hasEdge
s, write anaddEdge
method. CanhasEdge
be a helper method here? Just as forhasEdge
, start off with one graph implementation and get that one working first. Then move to the other implementation. Check and make sure that bothhasEdge
andaddEdge
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. -
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. -
You should now have a good understanding of how edges are stored in each
implementation. How should
getInDegree
differ fromgetDegree
? ImplementgetInDegree
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. -
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 String
s or ZooAnimal
s. 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.