Homework 9

Learning Goals

• Use java’s Vector and LinkedList classes
• Implement a graph traversal
• Implement the DiGraph (Directed Graph) interface

Pair Programming

We will assign you a peer to collaborate with on this assignment. Please,

• Reach out to your partner ASAP to discuss when you will meet to work on the assignment. You will probably have to meet several times.
• Work together (pair programming) rather than divide and conquer.
• Discuss the ideas and diagrams before diving into coding.

Task 1: Complete the Directed Graph Implementation

Download this starter code. It contains the solutions from last week’s lab. Feel free to use your version, if you feel more comfortable with that one.

Complete the implementation of the DiGraph interface. Take it one method at a time, make sure to include appropriate javadoc, and test as you go. For the methods where you don’t immediately come up with a solution, write the pseudocode before writing the code for the method. Remember, arriving at a solution quickly that hasn’t been thought through and has mistakes will probably take longer to debug than thinking carefully - and slowly - of a solution that works for all cases you can think of.

Task 2: Graph Traversal

Together with your partner, take a look at the pseudocode for the depth-first search traversal seen in class. Now write code to implement it. Make sure to test it on a few different kinds of graphs/paths to make sure it works as expected.

Task 3: Graph Driver

Now you’re ready to test your implementation, before sending the graph off to your friends to play with.

Create a new driver program, Driver.java, and think carefully about where it should be placed in your project. Test each method thoroughly on all possible paths, marking clearly what result you expect and what you obtained. Store the outputs of your tests in Tests.txt.

Submission Checklist

• You submitted all .java files and all .txt files.
• Your files are named exactly as in the homework specification, including file extensions.
• You tested every possible pathway in your code.
• You signed every class (or file) with @author and @version, accompanied by a description of what the class does.
• You wrote javadoc for every function, which includes @param and @return.
• You wrote inline comments explaining the logic of your code.