Contents:

Introduction

In this assignment, you will design, implement, and test a graph ADT. Given an abstract, high-level description of the desired ADT, you will develop a working Java implementation. You get to choose both the public interface and internal representation, then decide what unit tests to write to demonstrate that your implementation works correctly.

Although this is an individual assignment, in the design stage you will learn more and produce a better design by bouncing your ideas off others and incorporating their own ideas. To encourage discussion, we are relaxing the standard collaboration policy somewhat for Problem 2 (the interface design stage). You must first attempt to come up with an interface design on your own, but then you are strongly encouraged to discuss your design with your classmates who have also attempted a design (as well as the course staff during office hours) as much as you like, without restrictions on what materials you can bring to or from meetings. On the other parts of this assignment, including the implementation stage, the standard collaboration policy still applies.

This assignment is the first of a multi-part project. Read Homework 6 to get an idea of one application for your graph ADT, but there will be more. By the end of the quarter, you will build a full application for getting directions to travel between two buildings on the UW campus.

Problem 1: Written Exercises [23 points]

This part is designed to test your understanding of some of the ADT concepts from lecture. To get started, update your working copy of your repository using git pull to get the files for this assignment. Place your answers in the file hw5/answers.txt.

  1. For each of the classes below, write the abstraction function and representation invariant, referring to the source code provided in the hw5/problem1 package of your project.
    1. IntQueue1
    2. IntQueue2
  2. Below are several snapshots of an IntQueue2 object's internal state at different points in a program. Which snapshots are equivalent to each other at the abstract level? In other words, partition the snapshots into groups based on which are identical to each other from the client's perspective.
    Diagrams of a queue in various states
  3. Below are signatures for various methods and constructors. For each, state and justify in 1-2 sentences (per problem) whether the method or constructor could possibly expose the representation, given the information available. Explain any assumptions you made.
    1. public int solveEquations(int x, int y, int z)
    2. public String[] decode(boolean slowly)
    3. private Date myBirthday()
    4. public String toString()
    5. public Iterator<Integer> elements()
    6. public Deck(List<Card> cards)

Building a Graph

Definitions and Terminology

In the rest of this assignment you will design, implement, and test a directed labeled multi-graph.

A graph is a collection of nodes (also called vertices) and edges. Each edge connects two nodes. In a directed graph, edges are one-way: an edge e = ⟨A,B⟩ indicates B that is directly reachable from A. To indicate that B is directly reachable from A and A from B, a directed graph would have edges ⟨A,B⟩ and ⟨B,A⟩.

The children of node B are the nodes to which there is an edge from B. In Fig. 1, the children of B are A and C. Similarly, the parents of B are the nodes from which there is an edge to B. In Fig. 1, B has only one parent, A.

A path is a sequence of edges ⟨node1,node2⟩, ⟨node2,node3⟩, ⟨node3,node4⟩, .... In other words, a path is an ordered list of edges, where an edge to some node is immediately followed by an edge from that node. In Fig. 1, one possible path is ⟨B,A⟩,⟨A,B⟩,⟨B,C⟩. This path represents traveling from B to A to B to C. A path may traverse a particular edge any number of times.

A simple directed graph
Figure 1: A simple directed graph with four nodes.
A multigraph
Figure 2: A directed multigraph.
A labeled graph
Figure 2: A directed labeled multigraph.

In a multigraph, there can be any number of edges (zero, one, or more) between a pair of nodes. Fig. 2 shows a multigraph with 2 edges from A to C.

In a labeled graph (Fig. 3), every edge has a label containing information of some sort. Labels are not unique: multiple edges may have the same label. In theory a graph could contain two "identical" edges with the same starting point, ending point, and label, but for this project you may decide whether or not to allow identical edges in your implementation. (Whatever you decide, make sure it is clearly documented so clients understand how they can use your ADT.)

If you want to learn more, read Wikipedia's definition of a graph. Graphs are also a major topic in CSE332. If you still have questions, ask the course staff.

Many interesting problems can be represented with graphs. For example:

Problem 2: Write a Specification for Graph [25 points]

To start, you will specify the API for a Java class or classes representing a directed labeled multigraph. The API, or public interface, is the collection of public classes and methods that clients of your graph ADT can use. We recommend that you work in iterative layers of detail. Start rough — preferably with pencil and paper — by identifying what operations the ADT needs to support, how it might be logically broken into classes and interfaces, and how these classes and interfaces rely on each other. Then, jot down a list of methods for each class that provide these operations. Think through some possible client applications, particularly the application in Homework 6, to get an idea for what operations are needed. Perhaps write some pseudocode (or even real code) for the application in Homework 6 and make sure your graph interface meets its needs. (Note: don't worry about implementing the breadth-first search algorithm described in Homework 6 for this assignment. We prefer that you focus on the lower-level operations needed to build the graph and to be able to perform breadth-first search.)

Keep your initial design rough — don't write formal class and method specifications with all the proper clauses right away. Your design will likely go through multiple iterations, and it's easier to throw away parts if you have invested less effort in them.

Once you are satisfied with your high-level design, write a Javadoc specification for each class and method. Follow the format we have been using in CSE 331, remembering to use both standard Javadoc tags (param, returns, throws) and ones introduced for this course (requires, effects, modifies). A good approach is to create skeleton implementations of your classes containing only method “stubs”, then write your specifications in the right place in the source file. A stub is a not-yet-implemented method whose body simply throws an exception, as you saw in the Homework 4 starter code. Stub methods give you the flexibility to run client code and tests before all your methods are implemented correctly.

As you write the JavaDoc specifications and implement the stub methods, take advantage of the JavaDoc tool to generate formatted JavaDoc web pages. Reviewing specifications in this format can provide useful feedback on the quality and completeness of the work you've done. There are detailed JavaDoc instructions in the handout on running Java programs, but briefly, in Eclipse, right-click the hw5/build.xml file and select the ant doc build target. The generated JavaDoc files will be in the top-level doc folder; double-click or open doc/index.html in a web browser to see the results.

You may assume nodes are uniquely identified by their data contents: that is, no two nodes store entirely equal data.

For this assignment, you may restrict your graph to store the data in nodes and edge labels as Strings. We strongly recommend you DO NOT use Java generics for this assignment, but we do not absolutely forbid it. If you do use generics, you MUST heed the warning about compiling your code in the hints section. In a future assignment, you will use generics to make your ADT work with other data types — text, integers, doubles, etc.

Design problems such as this one are open-ended by nature: we are not looking for one “right” design. There are principles of good design you have learned in lecture, however. You will also find suggestions of what to consider and how to approach the problem in the hints section. Also, designs naturally evolve as requirements change, so try to make your code easy to expand without making it overly general right away.

In hw5/answers.txt, write a brief description (one to two sentences for each operation) of why you included the operations you did and why you feel they are a sufficient interface to a graph. If your design includes multiple classes or interfaces, explain why you included each one; if not, explain whether you considered additional classes and why you decided not to include them. So your total work in this problem is this brief write-up plus the Javadoc class and method specifications as they appear in the source code you submit in Problem 4; you do not need to submit your Javadoc in a separate file.

Problem 3: Write Tests for Graph [12 points]

Write a high-quality test suite for your Graph specifications. It's important to write your tests before your code, but your tests will not pass until you have completed Problem 4.

Make sure you are familiar with the difference between implementation and specification tests, described in the testing handout. Specifically, specification tests must satisfy the staff-provided format and layout; in other words, they must be valid tests for any solution to this assignment. By contrast, implementation tests are unit tests for methods from the unique specification and implementation you designed in Problem 2.

  1. Implementation Tests: Write unit tests for the methods of your classes in one or more JUnit test classes, just like you saw in Homework 4. Create one test class per public ADT class, and be sure to write tests for every public method. Add your test classes to test/ImplementationTests.java, mimicking the structure of the provided SpecificationTests.java from Homework 3 and 4.
  2. Specification Tests: Because we didn't specify any of the class or method names you need to write for this assignment, specification tests cannot test your interface directly. Instead, you will construct specification test cases in the format specified in the Test Script File Format section. Each test case should consist of a “test” file containing a series of commands, and an “expected” file containing the output that the commands should produce. The file names should have the same base name but end with .test and .expected, respectively. For example, you may have a command file named testAdd.test with expected output in testAdd.expected. These files must be in the test directory alongside ScriptFileTests.java. They should have descriptive file names and comments that explain what case is being tested, and just like methods in unit tests, each test file should test only one distinct condition.

    When you run the provided JUnit Test ScriptFileTests (which is also run by the JUnit Test Suite SpecificationTests), it will find all of the test files in that directory and run them, saving their output as "testAdd.actual" (for example) in the bin/hw5 directory of your project. It then compares the actual file to the expected file and fails if they are different. (Hint for Eclipse users: the bin directory is not visible from inside Eclipse, so you'll need to access it directly through the file system.)

  3. Documentation: In hw5/answers.txt, write a few paragraphs documenting and explaining your testing strategy.

It is important to check every aspect of the output files to make sure that your tests are running correctly, including whitespace. We use an automated script to compare the expected and actual output of your files and report if they don't match.

What to turn in: you are required to commit any new JUnit test classes you add, your updated version of ImplementationTests.java listing these new classes, and the .test and.expected files you write. You should not modify SpecificationTests.java.

Problem 4: Implement Graph [25 points]

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

  1. In hw5/answers.txt, write a few paragraphs briefly describe your representation. For at least the three representations above and your representation (if it is not one of the ones above), explain an advantage of that representation. Explain why you chose the representation you did.
  2. Include an explicit 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.
  3. Provide an implementation of your graph data type. Strive first for a good design before worrying about performance right now. Eventually, however, your path-finding application will create and operate on very large 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.
  4. Be sure to call your checkRep() where appropriate.
  5. Once you've finished your implementation, think about whether or not new tests are needed in addition to those you wrote before you started coding. If so, add these to your test suite. Furthermore, append to the end of your test strategy writeup in Problem 3 a description of any new tests you added, or why you feel that your original tests are sufficient.

Problem 5: Write a Test Driver for Graph [5 points]

The staff-supplied testing driver HW5TestDriver 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.

Warning: Although the code for the test driver itself is only worth a few points, if it does not work properly it will likely cause some or all tests to fail when your assignment is graded. That could result in significant deductions for other parts of the project since they cannot be verified to work, even if they have been implemented correctly.

Test script file format

Because you and your classmates will have different specifications for the class(es) in this assignment, it is important that there is a standardized interface to use and test your code. To that end, we specify a text-based scripting format used to write instructions that will be executed by your graph.

The testing script is a simple text file with one command listed per line. Each line consists of words separated by white space. The first word on each line is a command name. The remaining words are arguments to that command. To simplify parsing the file, graph names and node and edge data may contain only alphanumeric ASCII characters (in other words, numbers and English letters (upper or lower case)).

There are example programs in the hw5/test directory.

The following is a description of the valid commands. Each command has an associated output which should be printed to standard output (typically, the console) when the command is executed. Lines that have a hash (#) as their first character are considered comment lines and are only echoed to the output when running the test script. Lines that are blank should cause a blank line to be printed to the output. These commands were chosen for ease of testing and are not meant to suggest what methods you should include in your graph specifications or how you should implement them. For example, it is unlikely to make sense for your graph ADT to store a name for the graph.

CreateGraph graphName
Creates a new graph named graphName. The graph is initially empty (has no nodes and no edges). The command's output is:
created graph graphName
If the graph already exists, the output of this command is not defined.

Note that graph names are used purely in the test script; it is unlikely to make sense for your graph ADT to store a name.

AddNode graphName nodeData
Adds a node represented by the string nodeData to the graph named graphName. The command's output is:
added node nodeData to graphName
If a node with this data is already in the graph, the output of this command is not defined.
AddEdge graphName parentNode childNode edgeLabel
Creates an edge from parentNode to childNode with label edgeLabel in the graph named graphName. The command's output is:
added edge edgeLabel from parentNode to childNode in graphName
If either node does not exist in the graph, the output of this command is not defined. If an identical edge (same parent, child, and label) already exists, the output of this command is not defined either, as it is left to your discretion whether to allow identical edges in your implementation.
ListNodes graphName
This command has no effect on the graph. Its output starts with:
graphName contains:
and is followed, on the same line, by a space-separated list of the node data contained in each node of the graph. The nodes should appear in alphabetical order. There is a single space between the colon and the first node name, but no space if there are no nodes.
ListChildren graphName parentNode
This command has no effect on the graph. Its output starts with:
the children of parentNode in graphName are: 
and is followed, on the same line, by a space-separated list of entries of the form node(edgeLabel), where node is a node in graphName to which there is an edge from parentNode and edgeLabel is the label on that edge. If there are multiple edges between two nodes, there should be a separate node(edgeLabel) entry for each edge. The nodes should appear in alphabetical order by node name and secondarily by edge label, e.g. firstNode(someEdge) secondNode(edgeA) secondNode(edgeB) secondEdge(edgeC) thirdNode(anotherEdge). There is a single space between the colon and the first node name, but no space if there are no children.

Sample input and output

We have provided example input and output files in your hw5/test directory. The behavior of the test driver on malformed input files is not defined; you may assume the input files are well-formed.

In addition, HW5TestDriver has a main method that allows it to be run directly through Eclipse or from the command line. You can enter commands at the console, and it will echo the results.

To run from the command line, execute the appropriate version below, adjusting pathnames as necessary.

Linux or Mac:

# Compile your program
cd ~/workspace331/cse331/src/hw5
ant build
# Run HW5TestDriver
cd ~/workspace331/cse331/bin
java hw5.test.HW5TestDriver
Windows:
# Compile your program
Z:
cd Z:\workspace331\cse331\src\hw5
ant build
# Run HW5TestDriver
cd Z:\workspace331\cse331\bin
java hw5.test.HW5TestDriver

To stop, press the key combination control-d if you are running it from the command-line, or press the red square button above the console if you are running it from Eclipse.

Hints

Writing Specifications

To give you some sense of the kinds of issues you should be considering in your design, here are some questions worth considering. These don't in general have simple answers. You'll need to exercise judgment, and think carefully about how different decisions may interfere with each other.

In choosing what operations/methods to include, strive to include enough that the ADT will be convenient and useful for a client, but avoid the temptation to write an “everything but the kitchen sink” API. Generally speaking, it is better to design a minimal than a maximal API. In the real world, you can always add methods later. However, you can never remove them from a published API, and such methods may over-constrain the implementation in the future.

Make good use of the course staff. If you have concrete questions, then take your specification to office hours for feedback on your design and style. Doing so could save you a lot of time.

Working Incrementally

Although it is generally a bad idea to start coding before you have thought deeply, it often makes sense to work incrementally, interleaving design and coding. Once you have a sketch of your specification, you may want to write some experimental code. This should give you some concrete feedback on how easy it is to implement the methods you've specified. You may also want to write code that uses your type even before finishing your ADT implementation, so that you can be confident that the methods you provide will be sufficient.

This strategy can backfire and degenerate into mindless hacking, leaving you with a pile of low-quality code and an incoherent specification. To avoid that:

Designing Tests

It can be difficult to come up with a good test suite. You would like to test a variety of “interesting” graphs, but what are interesting graphs? One possible approach is a “0, 1, 2” case analysis: test scripts with 0, 1, and 2 graphs are interesting; graphs with 0, 1, and 2 nodes and 0, 1, and 2 edges are interesting. For each method, 0, 1, and 2 parameters and 0, 1, and 2 results are interesting; for example: AddEdge on nodes that currently have 0, 1, and 2 children; ListChildren on nodes with 0, 1, and 2 children; etc. This approach, while certainly not required, can give a good way to structure your tests to cover many important cases without too much redundancy.

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.

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 Homework 5 or 6, checkRep() is a good place to start looking for problems.

A warning about equals and hashCode

You may find it useful to define a class or classes that implement method equals, overrding the definition in Object. If you do, 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) — we will also discuss it in an upcoming lecture but have not yet had time.

A warning about using generics

You are permitted but discouraged from implementing generic classes on this assignment (that will come later). A generic class is one defined as something like:

public class Graph<N,E> {
   ...
}

where a client could then construct a Graph<String,String>, Graph<City,Road>, etc.

If you choose to write a generic class, be aware that Eclipse's built-in compiler sometimes handles generics differently from javac, the standard command-line compiler. This means code that compiles in Eclipse may not compile when we run our grading scripts, leaving us unable to test your code and significantly impacting your grade. So be sure to check regularly that your code compiles (builds) with javac by running ant build from the hw5 directory. You can do this in one of two ways:

If Ant reports that the build succeeded, all is well: your code compiles with javac.

Hint: after encountering build errors in Ant, you may find that classes which previously compiled are now reporting "[some class] cannot be resolved" errors in Eclipse. You can fix these errors by doing a clean build: go to Project >> Properties >> Clean..., select your cse331 project, and hit OK.

This warning is directed only at students writing their own generic classes. Simply using, say, a List<String> or Comparator<Foo> (as you have been doing all along) should be fine.

What to Turn In [2 points]

You should add, commit, and push the following files to your CSE 331 GitLab repository:

Additionally, be sure to commit and push any updates to hw5/test/ImplementationTests and hw5/test/HW5TestDriver.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 named hw5-final 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.

Remember to run the validate tool on a fresh copy of your GitLab repository to verify that you have submitted all files and that your code compiles and runs correctly when compiled with javac on attu (which sometimes behaves differently from the Eclipse compiler).

Turnin (2 points)

If you correctly push the required code to your repository and properly tag it with hw5-final so that it will build without errors when we clone the repository on attu and check out that tag, you will receive 2 points. If this is not done correctly, in addition to losing these points, you may lose significant additional credit if your program cannot be built or run to test it for grading.

Q & A

Q: Does the graph ADT have to support an edge connecting a node to itself?

A: Yes. Although this won't be necessary for Homework 6, it's common for graphs to have these kind of nodes, so your ADT should allow them.

Q: Does the graph ADT have to support multiple edges between the same nodes with the same text?

A: No, you can choose how to handle this case.