To better learn about how graphs work by thinking about and then adding to two implementations.
This is a lab assignment that you’ll be handing in on Moodle. You should complete it on Monday Nov 1st, but it isn’t due until Wednesday Nov 3rd at 5:00pm Central.
You should work on this with your in-class partner, but you both need to submit separately.
If you finish it outside of class without your partner, note which sections you completed together and which you completed separately in your
Mount the COURSES drive and remember to save everything into STUWORK. If you don’t do this, everything you write will disappear when you log out!!!!
- Create a new folder in your STUWORK called
- Create your
Collaborations.txtdocument in that folder
- Download the starter code and put it into your GraphsLab folder
- Open your
GraphsLabfolder in VSCode
First let’s look at the files in the starter code.
AdjacencyListGraphImplementation.java and note what instance variables are there and how the constructor and
addVertex initializes the variables.
AdjacencyMatrixGraphImplementation.java and note what instance variables this implementation has and how they differ from the Adjacency List. Also look at the constructor and
addVertex and note the similarity/difference in initialization.
Now you’ll draw out some graph implementations on paper. You don’t need to submit these, but I highly recommend you actually do this to improve your understanding of how these implementations work!
Here is the graph you’ll be implementing on paper:
a. Draw the Adjacency Matrix implementation of this graph, making sure to accurately reflect the types of the underlying lists. You can assume that any array lists start with arrays of length 5.
When you’re done, check against my solution:
b. Draw the Adjacency List implementation of this graph, again showing the underlying list types correctly. Note that the ordering of the edges in the adjacency lists isn’t mandated by the graph representation, so any ordering of the nodes within each linked list is fine.
When you’re done, check against my solution:
Now let’s implement some of the remaining methods.
a. First implement
AdjacencyMatrixImplementation assuming there isn’t already an edge. Run
AdjacencyMatrixImplementation to see if you pass the
addEdge tests. There are other tests that will still be failing, in particular many that rely on
hasEdge, don’t worry about those for now. (Remember to refer to the Java Docs for ArrayList if you don’t remember how to do something with them.)
b. Now implement
hasEdge in the same implementation file and run the tests again. You should now be passing the relevant tests, though not all of them.
c. Even though you are passing the tests, you are not actually matching what the comment for
addEdge says it will do, update your code using
hasEdge to work correctly. (This is a place where there should really be a test, but I didn’t have a chance to write it yet. Feel free to write it if you want!) To throw an exception when the user tries to call
addEdge for vertices that don’t exist, you can use the following:
throw new IndexOutOfBoundsException();
d. Finally, implement
getDegree and verify you are passing all the tests for this implementation.
Finally, implement the same methods for
AdjacencyListImplementation. You’ll find they are somewhat similar, but you’ll need to adapt to the different implementation details of having linked lists instead of array lists.
If you have time and interest, here are some other things to do:
- Complete the other methods,
- Try to adapt your code to work with the
- Read the note about
getNeighborsin the adjacency list implementation and determine why there is a problem
- Think about how you would have to adapt your code for a directed graph
Compress your files as a zip, and upload that zip to Moodle under the appropriate assignment. Remember that partners need to submit their code separately and you should share the code you wrote in class with your partner.
This activity is not a homework assignment. That means that you’re evaluated on whether you attempted all parts of it, but your work will not be graded for correctness as long as a clear effort has been made. If you aren’t able to complete some parts, great ways to indicate clear effort are to reach out for help before the deadline (note ways you did so in your Collaborations.txt file) and to use comments in the code to indicate things you tried but what went wrong/where you got stuck.