In this assignment, you will be implementing the directed labeled graph that you have written specifications, method stubs, and tests for in part 1 of this assignment. 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 previous assignments.
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:
Create a new PDF file containing your answers to these questions, and submit it to Gradescope.
Place a proper abstraction function and representation invariant for your Graph data type (and
any other ADTs you create) in your source code. Remember that abstraction functions and representation
invariants are implementation details and shouldn't be visible to clients of your Graph, so they
should be in a regular comment, not a javadoc comment. Also implement a private
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 (thousands of nodes and tens of thousands of edges), so the scalability of your Graph implementation will be important. We recommend that your graph building and manipulating operations should be reasonably efficient.
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 your PDF file from Part 1, put a description of any new tests you added and why you added them, 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 your PDF file.
All of your answers in this part and other parts of the answers file should be brief and to the point. Short bullet lists are fine. Excessive verbosity or irrelevant remarks should not be included and will not receive full credit.
The staff-supplied testing driver GraphTestDriver in the
graph/scriptTestRunner 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
TODO comments to
perform the appropriate operations on your ADT. Please be sure to use the
stored in the
output field in the tester to print the desired output (i.e., when
implementing the test driver, use
output.println() instead of
If you have a bug, your program might run forever. To avoid such problems, you must add, to each JUnit 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
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 this assignment.) 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 boolean in your class that is checked in your
checkRep() such that it only runs
when the constant variable is true. If your
checkRep() function includes some expensive
computations and some that are quick, you might want to selectively disable just the expensive ones.
However be aware that when your code is evaluated, there will be a fairly short timeout on each staff
test and an expensive
checkRep() could easily cause tests to fail because do not
terminate quickly enough. There will be enough time for the actual work needed, provided your code is
straightforward and does not do excessive computation.
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 11 in the 3rd edition). Remember that
many data structures (
HashSet, to name a couple) have
requirements on implementing methods like
equals before you can
properly store objects in them. Be sure to read the documentation for data structures you use and
understand the requirements for using them.
Refer to the Assignment Submission Handout and closely follow the steps listed to submit your assignment. Do not forget to double check your submission as described in that handout - you are responsible for any issues if your code does not run when we try to grade it.
Use the tag name hw5-part2-final for this assignment. To verify your assignment on attu,
use the gradle task:
hw-graph:validate to check for common errors such as your code not compiling
or not passing tests. However, validation is not guaranteed to catch all errors in your code.
Your TA should be able to find the following in your repository:
hw-graph/src/main/java/graph/*.java- [Java Graph classes from part1, but with implementations]
hw-graph/src/test/java/graph/scriptTestRunner/GraphTestDriver.javaUpdates to the Test Driver
hw-graph/src/test/java/graph/junitTests/*.java- [Other JUnit test classes you create]
Don't forget to submit your written answers to Gradescope, in addition to submitting the code through GitLab.