Contents:
In this assignment, you will be implementing the directed labeled multi-graph that you have written specifications, method stubs, and tests for in homework 3. Unlike previous assignments, you must implement your Graph individually, following the specifications that you provided and incorporating any feedback that the staff have given you in HW3.
This assignment is the second part of a multi-part project, leading up to building a full application for getting directions to travel between two buildings on the UW campus.
There are many ways to represent a graph. Here are a few:
Place a proper abstraction function and representation invariant for your Graph data type (and any other ADTs you create) in your source code. Also implement a private checkRep() method, which will help in finding errors in your implementation.
Be sure to call your checkRep() wherever it is appropriate.
Provide an implementation of your graph data type. We ask that you start off by focusing on style. Once you have well designed code, you can think more about efficiency.
Eventually, your path-finding application will create and operate on very large sized graphs, so the scalability of your Graph implementation will be important. Since the path-finding algorithm must frequently look up the children for a given node, this operation should be performed quickly even for large graph sizes (aim for constant time here). Your graph building operations should also be reasonably efficient.
As your implementation will likely use classes in the Java Collections Framework, you should understand the computational complexity of classes such as HashMap and ArrayList.
Once you've finished your implementation, you should think about whether or not new tests are needed in addition to those you wrote before you started coding. If so, you should add these to your test suite. In hw4/answers.txt put a description of any new tests you added and why you added it, or why you feel that your original tests alone are sufficient.
Did you make any changes to your specifications as you were implementing your Graph? If so, describe your changes and why you made them in hw4/answers.txt.
The staff-supplied testing driver HW3TestDriver in your hw3 package should read input from standard input or a specified file using the format described under the Test Script File Format section and print its results to standard output. We have provided a skeleton implementation that takes care of parsing the input file format. Complete this file by adding code where specified by comments to perform the appropriate operations on your ADT. Please be sure to use the PrintWriter stored in the output field in the tester to print the desired output.
If you have a bug, your program might run forever. To avoid such problems,
you must add, to each test class, these two import
statements:
import org.junit.Rule; import org.junit.rules.Timeout;and this line within the class definition, at the top:
@Rule public Timeout globalTimeout = Timeout.seconds(10); // 10 seconds max per method tested
Include an abstraction function, representation invariant, and private checkRep() method in all new classes you create that represent an ADT. If a class does not represent an ADT, place a comment that explicitly says so where the AF and RI would normally go. (For example, classes that contain only static methods and are never constructed usually do not represent an ADT — though you are unlikely to write any such classes for HW4.) Please come to office hours if you feel unsure about what counts as an ADT and what doesn't.
Be conscious of how certain operations in checkRep(), particularly iterating over a large dataset, may affect the “big-O” runtime of your methods. If your program suffers performance problems in the next few homeworks, checkRep() is a good place to start looking for problems.
It is hard to balance the utility of the checkRep() method with how expensive it may be to run. A good approach is to call checkRep() as much as possible (generally at the beginning and end of every method), but to disable the checkRep() when you turn in your code so that our tests don't timeout. A good way to do this is to have a static final constant variable that is checked in your checkRep() such that it only runs when the constant variable is set.
You may find it useful to define a class or classes that implement method equals. If you do that, be sure to also provide a consistent definition of method hashCode, otherwise your objects may behave strangely if used in containers like HashMaps. There is a good discussion of the issues involved in Effective Java (item 9 in the 2nd edition).
Please answer the following questions in a file named hw4/collaboration.txt.
The standard collaboration policy applies to this assignment. State whether or
not you collaborated with other students. If you did collaborate with other
students, state their names and a brief description of how you collaborated.
To help us improve this course, please complete the Canvas Quiz associated with this assignment. You will receive full credit for this section if you complete the quiz. Your answers will be anonymous to the instructors. This quiz is due 24 hours after the assignment due date. You cannot use late days for this quiz.
You should add, commit, and push the following files to your CSE 331 GitLab repository:
Additionally, make sure to commit any updates to test/java/hw3/ImplementationTests and test/java/hw3/HW3TestDriver.java.
When you have committed and pushed all of your changes and are done with the assignment, you should create a git tag in your repository and push that tag to your repository. Once you have committed and pushed that tag, your assignment has been submitted and the staff will grade the files in your repository that are labeled with that tag.
Refer to the assignment submission handout for complete turnin instructions.