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 0: Familiarize yourself with the starter code.

• Download this starter code.
• Skim each file and ask yourself—what does it do? Many of the files you’ve already seen as parts of examples from class.
• Next, look at the APIs for Java’s LinkedList and Vector classes. You’ll be using those later.

Task 1: Complete the Directed Graph Implementation

Complete the implementation of the DiGraph interface in the AdjListsDiGraph<T> class. You can test your code in a new file called Driver.java, storing the output of your testing in Tests.txt.

Tips:

• Take it one method at a time, make sure to include appropriate comments/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.

To help you test your code, we’ve included a folder of graphs, tgf_graphs, that contains .tgf files of graphs. You’re welcome to use these graphs in your testing. To visualize the graphs, you can open the files with the yED Live browser app. To load the graphs into your code, we’ve provided you with the method AdjListsGraphFromFile.

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.