Part 1: Written Exercises

We start the assignment with this worksheet, where you will practice some of the ADT concepts from lecture. In this worksheet you will work on the IntPoly ADT, which represents a polynomial with integer coefficients. You will think about how representation invariants can be chosen, how these invariants relate to the representations we have, and how they change our design process. Although the rest of this assignment won't use this specific ADT, we recommend you work on this part first, as it can be helpful in later parts, where you will design your own ADT.

Feel free to rewrite the problems on a separate sheet. You do not have to turn in these exact pages with the blanks filled in (though you can do that as well). It is okay to submit a scanned copy of a hand-written document as long as it is legible, so you can also print the worksheet, write your answers on that, and scan it when done.

After finishing, submit your solution as a PDF in Gradescope. Be sure to match the pages of your PDF to the problems. The rest of the homework will be submitted through tagging a commit on gitlab, as described later in the assignment; your PDF solution to part 1 is the only file you should manually submit on Gradescope.

Graph Definitions and Terminology

In the rest of this assignment you will design a directed labeled graph and write tests for it, but you will not implement it. What you eventually turn in will look very similar to the starter code we have given you for the previous homework. There should be full Javadoc comments, stubs for methods/constructors, tests, etc. but no implementation at all – that’s what we'll do in HW6.

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 that B 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.

In this class, your graphs can have any number of edges (zero, one, or more) between a pair of nodes (this kind of graph is often known as a multigraph). Fig. 2 shows a graph 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. For this project, you may assume that no 2 edges with the same parent and child nodes will have the same edge label. (Whether or not you do make the assumption, make sure it is clearly documented so clients understand how they can use your ADT.)

Figure 1: A simple directed graph with four nodes.

Figure 2: A directed graph.

Figure 3: A directed labeled graph.

If you want to learn more, read Wikipedia's definition of a graph . If you still have questions, ask the course staff.

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

• A graph can represent airline flights between cities, where each city is a node and an edge ⟨A,B⟩ indicates that there is a flight from A to B. The edge label might represent the cost in money (airfare), time (length of flight), or distance.

• To find walking routes across the UW campus, you can build a graph where nodes represent buildings and other locations and edges represent walking paths connecting two locations. The label/cost of an edge is the physical length of that path.

• The Web can be modeled as a graph with node for every webpage and an edge ⟨A,B⟩ if page A links to page B. The label could indicate the anchor text for a link on page A, or the number of links from page A to page B.

• Facebook is essentially a giant graph with nodes for users and edges between friends. (You can see a visualization of the Facebook graph .)

Part 2: Write a Specification for Graph

To start, you will specify the API for a Java class or classes representing a directed labeled graph. 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 UW campus map, to get an idea for what operations are needed.

Initially, don't write formal class and method specifications. Your design will likely go through multiple iterations, and it's easier to throw away parts if you have invested less effort in them.

You may find the Test Script File Format section helpful in determining, at minimum, the functionality your graph must be able to satisfy. Implementing the test script commands as a client of your graph should be a trivial matter.

Once you are satisfied with your high-level design, write a Javadoc specification for each class and method. Follow the CSE 331 format, remembering to use both standard Javadoc tags (param, return, throws) and ones introduced for this course (spec.requires, spec.effects, spec.modifies).

A good approach is to create skeleton implementations of your classes containing only method “stubs” for public methods, then write your specifications in the right place in the source file. A stub is a not-yet-implemented method whose body simply throws a RuntimeException with a message indicating that the method is not yet implemented. Stub methods give you the flexibility to compile client code and tests before all your methods are implemented correctly.

As you write the Javadoc specifications and create the stub methods, review the HTML API documentation produced by the javadoc tool. You can invoke the javadoc took by running the "javadoc" task under the "documentation" category for your gradle project. After you run the javadoc tool, you can view the generated docs by right clicking on the file hw-graph/build/docs/javadoc/index.html and choosing "Open in Browser." Reviewing specifications in this format can provide useful feedback on the quality and completeness of the work you've done.

You may assume nodes are uniquely identified by their data contents: that is, no two nodes store entirely equal data. For this assignment, you should restrict your graph to store node and edge labels as Strings.

Because you are defining a single abstraction (a graph), you should generally define a single top-level class. (You may choose to define a top-level interface as well.) It is OK to use helper classes, but they should be inner classes — much like Map.Entry , a nested interface of Map . Note that inner classes can be public and used by clients, as Map.Entry is. (If the inner class is an implementation detail, it should be private. If it is a publicized part of the ADT specification, it should be public.)

Why should there be only one top-level graph class? It would be bad style to spread a single abstraction across multiple public top-level classes. Using multiple public top-level classes leads to an implementation and a rep invariant that is distributed across multiple classes rather than being local as it should be. Putting your abstraction in a single top-level class makes it easier to understand and verify. In some cases (though not for public helper classes!), helper classes are implementation details, so their existence exposes the representation — a client could come to depend on them, restricting your ability to change the implementation in the future.

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. You are allowed to change the design in the future, and most students do, as they discover limitations of their original design or invent better designs.

In the file hw-graph/src/main/java/graph/answers-hw5.txt, write a brief description 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.

Your total work in this part is this brief write-up plus the Javadoc class and method specifications as they appear directly in the source code. You should verify that the javadoc Gradle task runs without any errors and produces complete, well-formatted documentation in the html files.

Part 3: Write Tests for Graph

Now, write a high-quality test suite for your Graph specifications. Because we have not yet implemented our graph ADT, these are specification tests (rather than implementation tests) which are important to include so we can test the behavior separately from our perspective as an implementer.

There are two kinds of tests we ask you to write:

1. Script Tests:

   Because we didn't specify any of the class or method names you need to write, we can't directly run tests on your code (how would we know what methods to call?). Instead, we will use script tests which allow us to specify a standard set of behaviors according to a standard set of string commands that will utilize an intermediate program which will call your actual methods appropriately upon reading the string commands.

   For this homework you will be writing script test cases. Each test consists of a .test and a .expected file. The .test contains string commands that indicate which task the graph should perform, and the .expected file will contain string output based on the expected result of performing the test commands. It is necessary that you construct script test cases in the exact format specified in the Test Script File Format section. All script test files must be in the hw-graph/src/test/resources/testScripts/ directory.

   Each test should have the same base file name for both its .test and .expected files, for example you may have a command file named testAdd.test with expected output in testAdd.expected. These file names should be descriptive to indicate which case the test tests, and you should include comments to explain further.

   Like methods in unit tests, each test file should test only one distinct condition. It is okay to include many operations in a single test, but those operations must be focused on testing one particular behavior. Think of each .test/.expected pair as the equivalent to one method in a JUnit test suit, so you'll probably probably have a large number of them.

   For now, don't worry about how these test will actually run on your code, your task is writing out test cases accoring to the format we specify.

2. JUnit Tests:

   For any behavior that you weren't able to fully test using the scipt tests, you should write JUnit tests like the tests you wrote in HW4 and like all staff given test suites in prior homeworks. Generally you want to have one JUnit test class for each public ADT class you specify. In these tests you can call the test stub methods that you created in your ADT classes. Once those stubs are implemented in the next homework, you should be able to run this test suite without making any changes.

   You should put junit tests you write in hw-graph/src/test/java/graph/junitTests. Note: You'll likely need to import your graph code (import graph.*;) in your JUnit tests in order for the code to compile.

The combination of script tests and JUnit tests should be a complete and thorough test suite for your graph. You should try to test as much behavior as possible using the script tests first, then add supplementary JUnit tests as needed for anything that you can't test with the script testing language. Depending on your design, this may mean that you have very few JUnit tests (if the majority of your program's behavior can be tested using the script language).

In the same answers-hw5.txt file from earlier, write a paragraph or two (max) documenting and explaining your testing strategy. Mention how your script tests differ from your JUnit tests (if they do) and why.

Test Script File Format

Because you and your classmates will have different specifications for class(es) and methods in this assignment, we need a standardized interface to test your code. We specify a text-based scripting format used to write instructions that will be executed by your graph. Because the script language is designed to be a standard interface for all students, you must implement the script language exactly as we describe it here.

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

Each test that you write will consist of two files with the same name, but one with the .test extension, and the other with the .expected extension. When the tests are run, a test driver will read each line in the .test file and execute the corresponding command (or simply echo it, as described below) then add the output of that command to a file that it generates with the same name but an .actual extension.

After the test is complete, the .actual file looks exactly like the .test file but every command has been replaced with the output of running that command. To determine if the test has passed, the test driver compares the contents of the .expected and .actual files. If they match exactly, the test passes. If there's some difference between what was "expected" and what "actuallly" happened, the test fails.

Remember, in this assignment, you haven't implemented graph or the test driver yet so your tests are expected to fail.

The following is a description of the valid commands. Each command has an associated output that's generated 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 doesn't make sense for your graph ADT to store a name for the graph.

created graph graphName

added node nodeData to graphName 

added edge edgeLabel from parentNode to childNode in graphName

graphName contains:

the children of parentNode in graphName are: 

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 have simple answers. You'll need to exercise judgment, and think carefully about how different decisions may interfere with each other.

• Will the graph be mutable or immutable?

• Will the graph be implemented as a single class, or will there be a Java interface for the Graph specification and a separate class for the implementation?

• Will edges be objects in their own right? Will they be visible to a client of the abstract type?

• Will nodes be objects in their own right? Will they be visible to a client of the abstract type?

• When will the user specify the nodes and/or edges in the graph? (In the constructor? With an insertion method? Both? Can the user add multiple nodes and/or edges at once?)

• What kind of iterators will the type provide?

• Will the type provide any views, like the set view returned by the entrySet method of java.util.Map ?

• Will the type implement any standard Java collection interfaces?

• Will the type use any standard Java collections in its implementation?

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.

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. Following only this approach doesn't guarantee that you've written a good test suite, though, so make sure you apply the knowledge you've gained in lecture and section and ask questions if you're confused.

You also may want to think about specific kinds of Graphs, and test those cases separately. For example: what might go wrong if your graph has a cycle in it? What if there are "islands" — multiple different groups of nodes that have no edges connecting them? What about other "odd" Graphs?

Q & A

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

A: Yes. 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 edge labels?

A: No, you can choose if you'd like to support this as part of your design.