- IntQueue1
- IntQueue2
- public int solveEquations(int x, int y, int z)
- public String[] decode(boolean slowly)
- private Date myBirthday()
- public String toString()
- public Iterator<Integer> elements()
- public Deck(List<Card> cards)
Contents:
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 and facilitate discussion, we are relaxing the standard collaboration policy somewhat for Problem 3 (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.
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 to get the files for this assignment. Place your answers in the file hw5/answers/problem1.txt.
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.
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:
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 righ 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.
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/problem2.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.
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.
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.)
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.
There are many ways to represent a graph. Here are a few:
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.
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.
created graph graphNameIf 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.
added node nodeData to graphNameIf a node with this data is already in the graph, the output of this command is not defined.
added edge edgeLabel from parentNode to childNode in graphNameIf 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.
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.
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.
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.HW5TestDriverWindows:
# 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.
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.
entrySet method of java.util.Map?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.
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:
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.
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.
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..
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.
You should add and commit the following files to SVN:
Additionally, make sure to commit any updates to hw5/test/ImplementationTests and hw5/test/HW5TestDriver.java.
Remember to run the validate tool 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).
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 kinda 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 have a choice of what to do in this case.