CSCI
2600 Principles of Software
We recommend that you read the entire homework before you begin work. As always, you must commit and push to your Git repository, then submit on Submitty.
Submission Instructions
• Follow the directions in the version control handout for cloning your git repo.
• Be sure to commit and push the files to Submitty. Follow the directions in the version control handout for adding and committing files.
• Be sure to add any additional files to your repo using Team/Add to Index.
•
Important:
You must press the Grade
My Repository button, or your answers will not be graded.
You should have the package hw4
with the usual directory structure. Write your code under src/main/java/hw4
and your tests under src/test/java/hw4 (shows as hw4 under src/test/java
in Package Explorer). If your directory structure is incorrect autograding will fail resulting in a grade of 0!
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.
This assignment is the first of a multi-part project. In subsequent assignments
you will build several clients of your graph ADT.
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 more than once.
A reflexive edge is an edge which starts and ends at the same node. In Fig 1. there is a reflexive edge from A to A: ⟨A,A⟩. Your graph implementation must allow for reflexive edges.
Figure
1: A simple directed graph with four nodes.
Figure
2: A directed multigraph.
Figure
3: 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 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. Then if you still have a question, ask us.
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 will use. 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 provides these operations. Think through some possible client applications, particularly finding efficient routes between different nodes, to get an idea about what operations might be needed.
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 specification for each class and method. Follow the convention we have been using in this class, remembering to use both standard Javadoc tags (param, returns, throws) and the ones introduced for this course (requires, effects, modifies, etc.) Go over the slides for specifications again. 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. We strongly recommend you DO NOT use generics for this assignment. In a future assignment, you will use generics to make your ADT work with other data types — text, integers, doubles, etc. 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. Also, designs naturally evolve as requirements change, so try to make your code extensible, but don't over-generalize.
Once
you are done with the specification of your Graph ADT (overview, AF, and
representation invariant and Principle of Software specifications for each abstract operation) copy and
paste your specs and stubs into the file answers/hw4_problem1.pdf.
You can use RatNum.java
from hw3 as a guide.
Write a black-box test suite for your Graph specifications. It is important to write your tests before your code, but your tests will not pass until you have completed Problem 3.
• Documentation:
Include with your test cases one short paragraph of documentation explaining
your testing strategy, and which (if any) testing heuristics you used. Place
this write-up in answers/hw4_problem2.pdf.
Create and commit new JUnit test classes in directory src/test/java/hw4.
You must have a JUnit test case for GraphWrapper placed into file src/test/java/hw4/GraphWrapperTest.java which
should already exist in your repository. (GraphWrapper is explained in Problem 3.) You may need to add other files later on. To
create a new test case, right-click on hw4
under src/test/java, then New -> JUnit Test
Case, then type a name for the new test class. Don't forget to add JUnit to the build path!
Look back to Homework 0 and Homework 3 as examples of extensive test suites.
A
Java source code file GraphWrapper.java for the GraphWrapper class (it is explained
shortly after) should already exist in your repository. When you later need to
add other Java source code files, right-click on hw4 under src/main/java, then New -> Class,
Package: hw4, and then enter the name of
the class to be created. Be sure to use Team/Add to Index
to add the file to your repo.
There are many ways to represent a graph. Here are a few:
You have freedom to design the Graph ADT as you wish (you can name your
class, include operations at your discretion, and choose the rep as you like). However,
we require that you implement an additional class, GraphWrapper
, which has an
instance field of the type of your Graph ADT, and
implements the following weakly specified public methods. You don't have to
write the rep invariant, abstraction function, or checkRep()
for GraphWrapper
.
GraphWrapper
does not represent an ADT, it simply is an interface to your Graph ADT. You
do need to write a test suite GraphWrapperTest.java
in directory src/test/java/hw4. The purpose of GraphWrapper
is to allow us to test your Graph ADT through a common interface. Below is the
abstract description of the operations in GraphWrapper
.
public GraphWrapper()
This is the constructor of GraphWrapper. It initializes the instance field with a new empty
instance of your Graph ADT.
public void addNode(String nodeData)
Adds a node represented by the string nodeData to your graph. If an
identical node already exists in the graph, the output of addNode is not defined, that is, it
is left at your discretion.
public void addEdge(String parentNode, String
childNode, String edgeLabel)
Creates an edge from parentNode to childNode
with label edgeLabel in your graph. If 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 at your
discretion whether to allow identical edges in your implementation.
public
Iterator<String> listNodes()
This operation has no effect on your graph. It returns an
iterator which represents the nodes in lexicographical (alphabetical) order.
As an example, for the graph shown in Figure 3 above, a call to
listNodes() should return an iterator that goes through the following strings:
a
b
c
public
Iterator<String> listChildren(String parentNode)
This operation has no effect on your graph. It returns an
iterator which represents the list of childNode(edgeLabel) in lexicographical
(alphabetical) order by node name and secondarily by edge label. childNode(edgeLabel) means there is an edge with
label edgeLabel from parentNode to childNode. If there are multiple edges
from parentNode to some childNode, there should be a separate
entry for each edge. If there is a reflexive edge, parentNode(edgeLabel) should be in the list.
As an example, for the graph shown in Figure 3 above, a call to
listChildren("a") should return an iterator that goes through the following strings:
b(4)
c(4)
c(7)
Do not implement the graph ADT in GraphWrapper.java. Create a separate class for your graph.
Please answer the following questions in a file named hw4_reflection.pdf in your answers/ directory. Answer briefly, but in enough detail to help you improve your own practice via introspection and to enable the course staff to improve Principles of Software in the future.
Please answer the following questions in a file named hw4_collaboration.pdf in your answers/ directory.
The standard integrity policy applies to this assignment. All submitted work must be your own.
State whether you collaborated with other students. If you did collaborate
with other students, state their names and a brief description of how you
collaborated.
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. 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:
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. Use EclEmma to measure your coverage and gain even more
confidence in your tests.
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 HW4.) 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 Homework 4 or 5, 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 our tests don't timeout. A good way to do this is to have a
static final constant variable that is checked in your checkRep() such that it only runs when the constant
variable is set.
You may find it useful to define a class or classes that implement method
equals. If you do that, 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 10 in the 3rd edition). Eclipse will generate an equals
and hashcode for you, but if you use it, be sure that
it actually fits your needs.
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
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.
Push to git the following files. Don't forget to submit on Submitty!
Check the Submitty Discussion forum regularly. Updates to this homework will be posted there.