Contents:
Part 1: Choosing a representation
Part 2: Abstraction functions and representation invariants
Part 4: Additional tests and changes to specifications
Introduction
In this assignment, you will be implementing the directed labeled graph that you have written specifications, method stubs, and tests for in HW5. 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.
Part 1: Choosing a representation
There are many ways to represent a graph. Here are a few:
As a collection of nodes and a collection of edges.
-
As an adjacency list, in which each node is associated with a list of its outgoing edges.
-
As an adjacency matrix, which explicitly represents, for every pair 〈A,B〉 of nodes, whether there is a link from A to B, and how many.
Answer the following questions in the
hw-graph/src/main/java/graph/answers-hw6.txt
file in your repo:
-
In two or three sentences, explain an advantage and a disadvantage of each representation (for example, in terms of runtime complexity, space complexity, or ease of implementation).
-
In two to three sentences, describe the representation you chose and explain why you chose it. If you chose to use a different representation than one of the three we described above, be sure to list its advantages and disadvantages, too.
Selecting a representation can be challenging. So use the questions as inspiration for different considerations you should make, and don't be afraid to come to office hours or ask on ed if your need some guidance or want help to see if something makes sense.
Part 2: Abstraction functions and representation invariants
Place a proper abstraction function and representation invariant for your Graph data type (and any other ADTs you create) in your source code. See the Writing Representation Invariants and Abstraction Functions handout and review your hw4 feedback for guidance.
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 checkRep()
method, which will help in
finding errors in your implementation. Be sure to call your
checkRep()
wherever it is appropriate.
Part 3: Implementation
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.
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.
Part 4: Additional tests and changes to specifications
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 the
answers-hw6.txt
file from earlier, 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 the
answers-hw6.txt
file.
All of your answers in the answers-hw6.txt
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.
Part 5: Write the Test Driver for the Graph
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
PrintWriter
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 System.out.println()
).
Hints
Test timeouts
Once you are done with your test driver, you can run all of your Junit and script tests. If they are not passing you can use them to debug your code (although, since you wrote your tests it's good to check them for bugs too).
If you have a bug in your graph implementation, 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
Abstraction function, representation invariant, and checkRep
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 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. As an example, you can create a DEBUG
variable like in the example code below, and make sure that its value is
false
before turning in your assignment:
class Graph { public static final boolean DEBUG = true; // other methods/constructors/fields in your class go here private void checkRep() { // Cheap asserts go here if (DEBUG) { // Expensive asserts go here } } }
A warning about equals and hashCode
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
(HashMap
and HashSet
, to name a couple) have
requirements on implementing methods like hashCode
and
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.
How to Turn In Your Homework
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 hw6-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/answers-hw6.txt
-
hw-graph/src/main/java/graph/*.java
- [Java Graph classes from HW5, but with implementations] hw-graph/src/test/resources/testScripts/*.test
hw-graph/src/test/resources/testScripts/*.expected
-
hw-graph/src/test/java/graph/scriptTestRunner/GraphTestDriver.java
Updates to the Test Driver -
hw-graph/src/test/java/graph/junitTests/*.java
- [Other JUnit test classes you create]