Contents:

Introduction

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. You must implement your Graph individually, working from the specifications and tests that you created in that part of the assignment, and incorporating any feedback from the staff from that part. If you find it necessary to change some of your previous work or specifications, you should do that. With luck, the changes should not need to be too drastic, but if significant changes are needed you should make them.

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.

In addition to this writeup, this video has an overview of the assignment that you may find to be a useful supplement to the details here.

Part 1: Choosing a representation

There are many ways to represent a graph. Here are a few:

Answer the following questions in the hw-graph/src/main/java/graph/answers-part2.txt file in your repo:

  1. 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).
  2. 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.

Part 2: Abstraction functions and representation invariants

Add 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 that must not be visible to clients of your Graph, so they should be in a regular comment, not a javadoc comment (i.e., not part of the spec). 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. You should start off by focusing on writing clean code. Once you have well designed code, you can think more about detailed efficiency issues if, in fact, that becomes an issue.

Eventually, your path-finding application will create and operate on very large 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, and that will usually be a function of picking a good representation for the graph where the necessary operations can be implemented with algorithms that run quickly.

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

As you work on 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-part2.txt file from earlier, write a short 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-part2.txt file.

All of your answers in the answers-part2.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.

Write the Test Driver for the Graph

The staff-supplied testing driver GraphTestDriver in the graph/scriptTestRunner package reads script test files from either standard input (usually the keyboard) or a specified file using the format described in the Part 1 Test Script File Format section and prints the results of running those tests to standard output. We have provided a skeleton implementation that takes care of parsing the input file format. You need to complete this file by adding code where specified by TODO comments to perform the appropriate operations (i.e., call the appropriate methods) 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()).

Once your GraphTestDriver is complete you will be able to run the script tests you wrote in hw5 part 1 using the hw-graph:test Gradle task -this will run all of your script and JUnit tests.

When script tests run, the contents of the .test files are read and the output for each command is printed to corresponding .actual files. Tests pass or fail based on if the contents of the .actual file matches that of the .expected file you wrote. The .actual files will be generated in hw-graph/build/resources/test/testScripts/, but you can also click the "Click to show difference" link in your test output in IntelliJ for any test to get a side by side of the .actual and .expected files. If you are failing a test, looking at the differences between these files should be your first step to fixing the bug.

Comparing the file contents is useful for typical debugging issues (bugs in your graph implementation); its also useful to detect bugs in your script tests or GraphTestDriver. When we give you a test suite in your starter code, we assure you that bugs are highly unlikely since it has been well tested, but you will be running these script tests for the first time, so bugs in the tests are very possible. This doesn't mean, however, that you should just modify tests to get them to pass without understaning the bug. The example tests we give are a good sanity check -you should be able to pass them without modifying their contents. We will run them and other tests that follow the specified Test Script File Format on your code too, so following that format is required.

Test timeouts

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 add this line at the top of each JUnit test class definition:

@Rule public Timeout globalTimeout = Timeout.seconds(10); // 10 seconds max per method tested

Hints

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 the staff tests don't timeout when your code is evaluated. A good way to do this is to have a static final constant boolean in your class that is used by your checkRep() to control when very expensive tests are run. 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

    public void checkRep() {
        // Cheap tests go here
        if (DEBUG)  {
            // Expensive tests go here
        }
    }
}

A warning about equals and hashCode

You may find it useful to define a class or classes that implement method equals (although almost certainly not for the entire graph ADT itself). If you do that, you must 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). See the equals and hashCode Java documentation . and lecture slides for more. 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 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: