- 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. By the end of the quarter, you will build a fully-fledged 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 to the questions below in the file hw4/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 only has 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 given edge twice.
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 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.)
Read Wikipedia's definition of a graph. Then if you still have a question, ask the course staff.
Many interesting problems can be represented with graphs. For example:
To start, you will specify the public interface for a Java class or classes representing a directed labeled multigraph. We recommend that you work in iterative layers of detail. Start rough — preferably with pencil and paper — by brainstorming what operations the ADT needs to support, how it might be logically broken into modules (classes/interfaces), and how these modules connect to 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 5, to get an idea for what operations are needed. Perhaps write some pseudocode (or even real code) for the application in Homework 5 and make sure your graph interface meets its needs. (Note: don't worry about implementing the breadth-first search algorithm described in Homework 5 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.)
Initially you should keep your 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 before you've invested too much 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 (specfield, derivedfield, requires, effects, modifies). A good approach is to create skeleton implementations of your classes containing only method “stubs”, then write your specifications in place in the code. A stub is a not-yet-implemented method whose body simply throws an exception, as you saw in the Homework 3 starter code. Stubbing out a class gives you the flexibility to write client code and tests that use it before completing the implementation. The skeleton code will not behave correctly or pass tests, but the program will compile and run.
For this assignment, you may restrict your graph to store the data in nodes and edge labels as Strings. (In a future assignment, you will use generics to make your ADT work with other data types — text, integers, doubles, etc. You are permitted to use generics on this assignment, but we do not recommend it, and you MUST heed the warning about compiling your code in the hints section.) You may assume nodes are uniquely identified by their data contents: that is, no two nodes store the same data.
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.
Please include in your turnin 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. This should be placed in hw4/answers/problem2.txt.
Write a black-box test suite for your Graph specifications. Do not attempt to run your tests 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 specification; in other words, they must be valid tests for any other student's implementation for this assignment. By contrast, implementation tests are unit tests for methods from the unique specification and implementation you designed in problems 2 and 3.
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.
For turnin, 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 testing driver HW4TestDriver 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.
Please answer the following questions in a file named reflection.txt in your answers/ directory.
Please answer the following questions in a file named collaboration.txt in your answers/ directory.
The standard collaboration policy applies to this assignment, with the exceptions described in the Introduction.
State whether or not you collaborated with other students. If you did collaborate with other students, put their names and a brief description of how you collaborated.
After you receive your corrected assignment back from your TA, you will need to resubmit a corrected version of the code. You will have until Friday, May 11 at 11pm to returnin your code. The returnin script will be enabled a week earlier, at 11pm Friday, May 4.
You will only receive credit if you pass all the tests, and you have a fixed number of trials without penalty. See the returnin331 documentation for details.
Because you and your classmates will have different specifications for the classes 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.
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 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 of the nodes 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 data in all nodes in 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 two example input and output files in your hw4/test directory. The behavior of the testing driver on malformed input files is not defined; you may assume the input files are well-formed.
In addition, HW4TestDriver 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 it from the command line, issue commands like the following (Linux version):
# Compile your program cd ~/workspace331/cse331/src/hw4 ant build # Run HW4TestDriver cd ~/workspace331/cse331/bin java hw4.test.HW4TestDriver
The following commands should work on Windows machines in the software labs (with possible adjustments to the pathnames depending on where you checked out your repository):
# Compile your program Z: cd Z:\workspace331\cse331\src\hw4 ant build # Run HW4TestDriver cd Z:\workspace331\cse331\bin java hw4.test.HW4TestDriver
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 you might want to consider. These don't in general have simple answers. You'll need to exercise judgment, and think carefully about how decisions you make 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 to get some feedback on your design and style. This is likely to 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 even want to start at the end, and write the code that uses your type, 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, bear three things in mind. First, you must be willing to start again: experimental code isn't experimental if you're not prepared to throw it away. Second, whenever you start coding, you must have a firm idea of what you're trying to implement. There's no point starting to code to a specification that is vague and missing crucial details. That doesn't mean that your specification must be complete and polished, but it does mean that you shouldn't start coding a method until at least you have its own specification written. Third, you must write down the specification of a method and not just imagine it; it's too easy to delude yourself. Try to write it on paper and mull it over before you start any coding. It's tempting to sit in front of an editor, write some specification as comments, and then start coding around them, but this tends not to be nearly so effective.
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 having too much redundancy.
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> {
...
}
where a client could then construct a Graph<String>, Graph<Integer>, etc.
If you choose to write a generic class, be aware that the built-in Eclipse compiler handles generics differently from javac, meaning code that compiles in Eclipse may not compile in our grading scripts. Therefore, you MUST verify that your code compiles with javac by running ant build from your hw4 directory. Run this early and often and at least some of the time on attu. If you see the message "BUILD FAILED," review the error messages for more details about the problem.
This is not an empty warning: such compilation errors have happened relatively frequently to students in past quarters. They will severely impact your grade because they prevent us from running any tests on your code. Note that ant validate also builds your code with javac, so you are in good shape if everything succeeds there.
This warning is only directed 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 hw4/test/ImplementationTests and hw4/test/HW4TestDriver.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).
In Problem 4, the phrase "You should append to the end of your test strategy writeup in Problem 4..." was supposed to refer to Problem 3. So, put that content in problem3.txt. Don't worry if you already put it in problem4.txt and see this too late, though — we'll accept either location when grading.
This section will list clarifications and answers to common questions about assignments. We'll try to keep it as up-to-date as possible, so this should be the first place to look (after carefully rereading the assignment handout and the specifications) when you have a problem.