Handout P3

Contents:

We recommend that you read the entire problem set before you begin work.

Purpose

This assignment gives you the opportunity to design your own specifications for an abstract data type (ADT). You will have the chance to implement your specification and write tests for the implementation. You will also implement and test an algorithm that uses your ADT. Your solution needs not, and should not, depend on any of the previous problem sets.

Getting Started

Update the psets module from your repository. If you don't remember how to do this, take a look at the Version Control document. Then, work through the problems below.

We have provided the following files:

When you are done with this problem set, you should have committed the following additional files to CVS:

Introduction

To review, Problem Sets 2, 3, 4, and 6 address different aspects of the design, implementation, documentation, and testing of MapQuick, a Google Maps-like system for giving directions between locations in Boston and Cambridge.

In Problem Set 2, you built basic data abstractions such as Route, GeoFeature, GeoPoint and GeoSegment. This problem set involves building a graph abstraction and implementing a shortest path algorithm.

In order to give useful directions, the MapQuick system needs a means of finding the shortest path between two points. MapQuick requires abstractions to represent information about streets, the connectivity between streets, and possible paths of travel. While the next problem set will deal with creating data structures to represent the streets themselves, this problem set will focus on developing the ability to find the shortest path between two points.

To do so, MapQuick will need a graph abstraction to represent connectivity, a path abstraction to describe the cost of traveling a particular course, and a path-finding algorithm to search for the shortest possible path.

While we do not specify the names, method signatures, or specifications of your graph abstraction, we do provide a specification of Path and provide you with a file format for your testing driver. The testing driver will execute a script of commands and output results to standard output.

Graphs

MapQuick represents street connectivity with a directed graph. You will implement a generic graph representation which can be used for different purposes, including MapQuick's.

A directed graph consists of a set of nodes some of which may be connected by edges. In a directed graph, the edges have direction: node B might have an edge to node C, but node C is not necessarily connected to node B. For our purposes there cannot be more than one edge from a given node to another given node, but there can be an edge from A to B and an edge from B to A.

A simple directed graph
A simple directed graph with four nodes.

The children of node B are the nodes to which there is an edge from B. In the example above 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 the example above B only has one parent, A.

Node-weighted means that the nodes in our graphs will carry some cost value with them, representing the amount it costs to pass through that node.

Conceptually, a graph consists of nodes and of edges that connect the nodes. (In practice an implementation often represents the graph in a rather different manner than that, however.) If you have any questions regarding the the definition of a graph, you should review other materials (for instance, wikipedia) before proceeding.

Nodes represent streets

In MapQuick's graph representation, streets are nodes and connections between streets (intersections) are represented by edges between them in the graph. This has a number of benefits over the alternative approach (in which nodes represent intersections and edges represent streets); here we list just a few of them.

Part 1: Graph ADT

Problem 1: Determine Requirements for Graph [3 points]

Read the path-finder pseudocode and test script file format below and list all the operations that the algorithm and test files perform on graphs. List these operations in ps3/answers/problem1.txt.

In order to implement the path-finding algorithm, your graph must support at least these operations. However, there may be no motivation for it to support more than that; for this problem set (and in general!), it is better to design a minimal than a maximal API. In the real world, you can always add methods later (though in some cases clients may be unhappy if obvious ones are not provided). However, you can never remove them from a published API, and such methods may over-constrain the implementation in the future.

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

Design an abstract data type representing a directed, node-weighted graph. You should begin by considering what sorts of methods and operations you feel you should include in your graph abstraction (see the hints section). Start from the list of requirements that you created in problem 1. You can also find suggestions on how to go about choosing operations for your abstract data type in the Liskov text in sections 5.1 and 5.1.1 (pp. 79-83). (Your graph specification should not ape the test script file format, which is intended for a different purpose. For example, if your specification of graphs includes a name for the graph, then there is something wrong with your design.)

Write a specification for each method you decide to support using the format and notation we have been using in 6.170 (in particular, remember to include requires/effects/modifies clauses in your Javadocs). If you are in doubt about how to write and generate Javadocs, refer to the 6.170 Class and Method Specifications. After finishing your specification, it is good practice to write empty implementations of all operations you decide to support (also called stubs), so that you can write client code and tests for your Graph before you actually implement it.

To allow for a general purpose abstraction, any cost (weight) information should be stored directly in the object associated with each node. That is, the Graph itself should not, for example, store a separate map of cost values for its nodes. Note that edge weights are not necessarily easy to support here, but we are designing our abstraction with a node-weighted graph in mind, and future problem set will only require node weight functionality. (Remember, nodes correspond to streets, and edges to intersections.) Nonetheless, if, for whatever reason, you want to support edge costs, keep in mind that you might need to modify the shortest paths algorithm later in this problem set, as it was written for a node-weighted graph.

Furthermore, the Graph abstraction should not assume that node objects are of any particular runtime type. In fact, your Graph data type's operations should be valid on nodes of any type, including Object; you should use Java's generic type system to accomplish this goal.

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. This should be placed in ps3/answers/problem2.txt.

Hint: We recommend that you not specify a stronger equals method than the one defined in Object (which tests object identity); neither this problem set nor any future one will require you to compare graphs to each other.

Problem 3: Write Tests for Graph [10 points]

Write a black-box test suite for your Graph specifications. Although some initial test cases are provided, you will have to write your own test cases. Do not attempt to run your tests until you have completed Problem 4.

As in previous problem sets, you will write JUnit unit tests for the methods of your Graph class. You should write your unit tests in one or more JUnit test classes and add them to test/ImplementationTests.java (because they are based on your implementation, not on a staff-provided specification).

In addition to JUnit tests, you will construct additional test cases in the format specified in the Test Script File Format section. Each test case should consist of an "test" file containing a series of commands, and an "expected" file containing the output that the commands should produce. The file names should start with "p3" and have the same base name but end with ".test" and ".expected" respectively. For example, you may have a command file named "p3TestAdd.test" with expected output in "p3TestAdd.expected". Your test file names should be informative, and the tests should have comments that make the purpose of each test clear. These files must be in the test directory alongside ScriptFileTests.java. When you run ScriptFileTests (which is also run by SpecificationTests), it will find all of the test files in that directory and run them, saving their output as "p3TestAdd.actual" (for example). It then compares the actual file to the expected file and fails if they are different. (Hint for Eclipse users: the actual file may not show up in the PackageExplorer until you relaunch Eclipse or select Refresh (F5).)

Include with your test cases a few paragraphs of documentation explaining your testing strategy. Place this writeup in ps3/answers/problem3.txt. Remember, any tests you add to SpecificationTests should satisfy the staff-provided specification; in other words, they must be valid tests for any working implementation for this problem set. Any other tests should go in ImplementationTests. This implies that unit tests for methods that are specific to your implementation, even if you have declared those methods to be public and have written Javadoc specifications for them, should go in ImplementationTests.

For turnin, you are required to commit your updated versions of the provided test classes and any new JUnit test classes you may have added (and call from either ImplementationTests or SpecificationTests), along with the .test and.expected files.

Problem 4: Implement Graph [15 points]

  1. Provide an implementation of your directed graph data type. We ask that you strive first for a good design before worrying about performance. Nonetheless, keep in mind that eventually your path-finding application will create and operate on very large sized 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.
  2. In a few paragraphs, briefly describe your representation and explain why you chose it. Compare it to at least one other representation that you considered. You should place this discussion in a file called ps3/answers/problem4.txt.
  3. Place a proper abstraction function and representation invariant of your Graph data type (as well as any other ADTs that you may create along the way) in your source code. At this point, you should also implement a private checkRep() method. This will help in finding errors in your implementation.
  4. Once you've finished your implementation, you should think about whether or not new tests are needed in addition to those you wrote before you started coding. If so, you should add these tests to either SpecificationTests or ImplementationTests, depending on whether or not you are testing things guaranteed by our specification. You should append to your test strategy writeup in Problem 3 a description of any new tests you added, or why you feel that your original tests alone are sufficient.

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

The testing driver PS3TestDriver 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. In order to help you parse the input file format, we have provided a skeleton implementation of the parser. You should fill in this file with your own code. Please be sure to use the PrintWriter stored in the output field in the tester to print the desired output.

Part 2: PathFinder

In this part of the problem set you will exercise your Graph ADT by running pathfinding searches on it. We provide you with most of the pathfinding code, and your job is to interface the staff-supplied pathfinding code with your Graph code.

Path

When searching for the best means of travel between two points, MapQuick will attempt to minimize the distance traveled. A generic shortest path algorithm, on the other hand, attempts to minimize some arbitrary cost function of the route traveled. Since the Graph abstraction is generic and can support any type of node, you need an abstraction to represent the cost of some path through the graph. The Path interface provides an abstraction for both representing a given path and for obtaining the cost of that path.

Path is a Java interface, not a class: that is, it just specifies a set of required methods, cannot be directly instantiated, and provides no code to classes which implement it. By separating the notion of a Path (through the use of a Java interface) from the generic Graph abstraction, graphs with any types of nodes can be searched on as long as an appropriate implementation of the interface is provided.

Finding Shortest Paths

The sources we provide implement a modified version of Dijkstra's algorithm, which you can find in any algorithms textbook (for instance, Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein). The pseudocode for the algorithm is below. In the pseudocode, the notation [a,b,c] stands for the three-element sequence consisting of a, b, and c; here, we use it to represent a path. When applied to sequences, "+" means concatenation; for instance, [a,b] + [c,d] = [a,b,c,d]. If m represents a map, then m(key) represents the value associated to key by the Map m.

    // Return a shortest path from any element of starts to any
    // element of goals in a node-weighted graph.
    Algorithm node-weighted-shortest-path(Set starts, Set goals) {

      // maps nodes -> paths
      Map paths = { forall start in starts | (start, [start]) }

      // The priority queue contains nodes with priority equal to the cost
      // of the shortest path to reach that node.  Initially it contains 
      // the start nodes.
      PriorityQueue active = starts

      // The set of finished nodes are those for which we know the shortest paths
      // from starts and whose children we have already examined.
      Set finished = { }

      while active is non-empty do {
        // queueMin is the element of active with least cost path
        queueMin = active.extractMin()
        queueMinPath = paths(queueMin)

        if (queueMin in goals) {
            return queueMinPath
        }

        // iterate over edges (queueMin, c) in queueMin.edges
        for each child c of queueMin {
          cpath = queueMinPath + [c]

          if (c not in finished) and (c not in active) {
            paths(c) = cpath
            insert c in active with priority equal to cpath's cost
          }
        }
        insert queueMin in finished
      }
      // execution reaches this point only if active becomes empty
      return No Path Exists
    }

This algorithm uses a priority queue, a collection data structure that supports inserting elements and extracting the highest-priority element. (we use path costs as priorities, so shorter paths have higher priority.)

Explanation of the algorithm

The algorithm keeps track of two disjoint collections of nodes. One collection contains "finished" nodes for which we know the shortest path from starts, and we have already examined all edges that leave the node. The other set contains "active" nodes for which we know the shortest path from starts, but we have not yet considered paths that extend it. The paths map associates each active node with the shortest path from starts to that node.

A key property of this algorithm is that if x is a finished node, and y is not a finished node (either it is active, or we don't know the shortest path yet), then the length of the shortest path from starts to x is no more than the length of the shortest path from starts to y.

The algorithm starts with a set of active nodes starts, each element of which is associated with a path consisting of just that node. When any of the nodes contained in goals is reached, the algorithm terminates and returns the associated path with that element in goals.

The basic step of the algorithm (which is repeated over and over) is to find, in the set of active nodes, the one for which the associated shortest path has lowest total weight. Call this node queueMin. Now consider every edge that leaves queueMin; say that edge goes to the child c. If c is finished or active, ignore the (queueMin, c) edge, because we already know of a shorter path to c than the one that goes through queueMin. Otherwise, add c to the collection of active nodes, and associate with it the path cpath which extends the path associated to queueMin by adding c at the end. cpath is the shortest path from starts to c. After all the edges leaving queueMin have been examined, move queueMin from the active collection to the finished collection.

Shortest path example

Consider the following graph:

Small example graph

The nodes a, b, c, d, and e have weights 2, 1, 3, 1, and 4, respectively. We want to find the shortest path from a to e.

Initially:

paths = { (a, [a]) }
active = { a }
finished = { }
Remove a from active; its path has cost 2.
Consider each neighbor of a:
   add b to active
   set paths(b) = [a,b]
   add c to active
   set paths(c) = [a,c]
Add a to finished.
Now:
   paths = { (a, [a]), (b, [a,b]), (c, [a,c]) }
   active = { b, c }
   finished = { a }
Remove b from active; its path has cost 3,
which is the lowest in active.
Consider each neighbor of b:
   do not add c to active, as c already appears in active
   add d to active
   set paths(d) = [a,b,d]
Add b to finished.
Now:
   paths = { (a, [a]), (b, [a,b]), (c, [a,c]), (d, [a,b,d]) }
   active = { c, d }
   finished = { a, b }
Remove d from active; its path has cost 4,
which is the lowest in active.
Consider neighbor of d:
   add e to active
   set paths(e) = [a,b,d,e]
Add d to finished.
Now:
   paths = { (a, [a]), (b, [a,b]), (c, [a,c]), (d, [a,b,d]), (e, [a,b,d,e]) }
   active = { c, e }
   finished = { a, b, d }
Remove c from active; its path has cost 5,
which is the lowest in active.
Consider neighbor of c:
   d in finished, e in active, so don't add neighbors
Add c to finished.
Now:
   paths = { (a, [a]), (b, [a,b]), (c, [a,c]), (d, [a,b,d]), (e, [a,b,d,e]) }
   active = { e }
   finished = { a, b, d, c }
Remove e from active; its path has cost 8,
which is the lowest in active.
   e is in goals, so we return its path [a,b,d,e]
DONE :
   paths = { (a, [a]), (b, [a,b]), (c, [a,c]), (d, [a,b,d]), (e, [a,b,d,e]) }
   active = { }
   finished = { a, b, d, c } e would have been added but we return

Notice that the algorithm actually calculates the shortest route from node a to all other nodes until it reaches a goal node. This information is stored in the paths structure.

The algorithm shown is capable of finding all the shortest paths given multiple start nodes and multiple destinations. MapQuick uses this capability because different directions of a street are represented as different nodes. For instance, starting from 77 Mass Ave, it is possible to initially proceed either north or south, and ending at 32 Vassar St, it is possible to approach the destination from either east or west.

Part 2: PathFinder

Problem 6: Complete the Shortest Path Algorithm Implementation [10 points]

We provide you with almost-complete pathfinding code in ps3/graph/PathFinder.java and ps3/graph/PathFinderSpecializer.java. The PathFinder class closely follows the pseudocode above, but leaves some details flexible to facilitate possible modifications (such as changing search from Dijkstra's to faster A* search that you will do in PS4). Additional flexibility is also required for PathFinder to be able to operate on any Graph ADT that you come up with. This flexibility is accomplished by having PathFinder take in a PathFinderSpecializer object. PathFinderSpecializer actually accomplishes two goals - 1) it acts as a facade in front of your Graph ADT, providing a simple interface to the required graph functionality, and 2) it tweaks the pathfinding algorithm by allowing the client to specify path ordering. You will learn more about the Facade and Strategy design patterns used by this interface later in the course. Your job is to implement a Specializer for the PathFinder that interacts with your Graph ADT, and define the proper ordering for search paths. Both should be very straighforward - note that simply using the path's natural ordering (i.e. their cost) will result in exactly right behavior for the Dijkstra's algorithm. Write a class called DijkstraSpecializer that implements PathFinderSpecializer interface and submit it in DijkstraSpecializer.java

Problem 7: Write Tests for Shortest Path Algorithm [10 points]

The testing framework used to test Graph is also used to test PathFinder. Extend the testing framework to support the FindPath command. Please note that you are free to modify the WeightedNodePath class to make it interact with your Graph ADT and the PathFinder.

In order to test the functionality of PathFinder, you should create a set of test cases, similar to what you did in Problem 3, in files called p7[any].test and provide their expected output in p7[any].expected, where [any] is any string. Also include an explanation of your testing strategy. Place this writeup in ps3/answers/problem7.txt.

Reflection [1 point]

Please answer the following questions in a file named reflection.txt in your answers/ directory.

  1. How many hours did you spend on each problem of this problem set?
  2. In retrospect, what could you have done better to reduce the time you spent solving this problem set?
  3. What could the 6.170 staff have done better to improve your learning experience in this problem set?

Collaboration [1 point]

Please answer the following questions in a file named collaboration.txt in your answers/ directory.

The standard collaboration policy applies to this problem set.

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.

Returnin [22 points]

After you receive your corrected problem set back from your TA, you will need to resubmit a corrected version of the code. You will have until Wednesday, October 10 at 11:59pm to to returnin your code. The returnin script will be enabled a week earlier, at 11:59pm, October 3.

You will only receive credit if you pass all the tests, and you have a fixed number of trials without penalty. See the returnin6170 documentation for details.

Test script file format

Because you and your classmates will have different specifications for the classes in this problem set, there needs to be a standardized interface to use, test, and grade your code. To that end, we specify a text-based scripting format used to write instructions that will be executed by your graph and path finder.

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 the command and have an interpretation which is dependent on the particular command they follow. Lines that have a hash (#) as their first character are considered comment lines and should be echoed to the output when running the test script. Lines that are blank should cause a blank line to be printed to the output.

The testing script manipulates graphs of WeightedNode elements. Each WeightedNode has a name and a cost. After a WeightedNode is created, it can be referred to later on in the testing file by using its name. We have also provided a WeightedNodePath which implements the Path interface for sequences of WeightedNodes. When the testing driver outputs a node, it should do so by displaying that node's name, which is a String. The name for each Graph is also a String. The testing driver must manage the mapping of names to graphs in addition to the mappings from names to nodes. This can be accomplished by maintaining two HashMaps in the testing driver code. The first HashMap could map names (Strings) to Graphs and the second could be used to map names to WeightedNodes. To simplify the parsing of the file, names of nodes and graphs must contain only alphanumeric characters.

The following is a list of the valid commands, and the meaning of their arguments. Each command has an associated output which should be printed to standard output (typically, the console) when the command is executed.

CreateGraph graphName
Creates a new graph which shall be 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.
CreateNode nodeName cost
Creates a new node named by the string nodeName with the cost specified by the non-negative integer cost. You can refer to the node by name after you have created it using this command. The command's output is:
created node nodeName with cost cost
If the node already exists, the output of this command is not defined.
AddNode graphName nodeName
Adds a node represented by the string nodeName to the graph named graphName. The command's output is:
added node nodeName to graphName
If the node is already in the graph, the output of this command is not defined.
AddEdge graphName parentNode childNode
Creates an edge in graph graphName from parentNode to childNode. The command's output is:
added edge from parentNode to childNode in graphName
If the edge already exists, the output of this command is not defined.
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 names of 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.
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 the names of nodes to which there is an edge from parentNode. The nodes should appear in alphabetical order. There is a single space between the colon and the first node name.
FindPath graphName from1 [from2 [from3 ... ] ] -> to1 [ to2 [ to3 ... ] ]
The -> symbol is separated from node names by whitespace on both sides.

The square brackets indicate optional elements. The square brackets do not appear in the input file, but an arbitrary positive number of from and to nodes may be specified.

This command has no effect on the graph. It finds and outputs the shortest path amongst all of the possible paths from any of the "from" nodes to any of the "to" nodes. The output starts with:

shortest path in graphName: 

and is followed, on the same line, by a space-separated list of nodes in the order of traversal from fromX to toY.

If no path exists the output should be:

no path found in graphName

Note that in in the first case, there should be a single space after the colon.

Sample input and output

Given the following as input for the testing driver:

# Problem set 3 test script, from ps3 handout

CreateNode n1 5
CreateNode n3 1
CreateGraph A
AddNode A n1
CreateNode n2 10
AddNode A n2 
CreateGraph B
ListNodes B
AddNode A n3
AddEdge A n3 n1 
AddNode B n1
AddNode B n2
AddEdge B n2 n1
AddEdge A n1 n3
AddEdge A n1 n2
ListNodes A
ListChildren A n1
AddEdge A n3 n3
ListChildren A n3
FindPath A n3 -> n2

A correct implementation would output the following:

# Problem set 3 test script, from ps3 handout

created node n1 with cost 5
created node n3 with cost 1
created graph A
added node n1 to A
created node n2 with cost 10
added node n2 to A
created graph B
B contains: 
added node n3 to A
added edge from n3 to n1 in A
added node n1 to B
added node n2 to B
added edge from n2 to n1 in B
added edge from n1 to n3 in A
added edge from n1 to n2 in A
A contains: n1 n2 n3
the children of n1 in A are: n2 n3
added edge from n3 to n3 in A
the children of n3 in A are: n1 n3
shortest path in A: n3 n1 n2

The behavior of the testing driver on malformed input files is not defined; you may assume the input files are well-formed.

Since it is possible that your specification throws exceptions for certain inputs, the testing file format provides for one additional feature. If the command in the input file results in an exception, the command, rather than outputting its normal string, should output "Exception: <toString value of exception>". This exception-output behavior is already implemented in the executeCommand method of the provided PS3TestDriver starter file.

Hints

Problem set 3 does not depend on problem set 2 (though problem set 4 depends on both of them). If you are behind on problem set 2, don't let that stop you from starting problem set 3 (though you will have to work very hard to catch up in the class!).

Writing Specifications

For both your graph class and your path-finding method, follow this methodology. First, write the specification. After writing the spec, write test cases based on the spec. Only after your test cases are complete should you begin the implementation. This will save time in the long run.

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 careful judgment, and think carefully about how decisions you make interfere with each other.

Make good use of your TA. Take your specification to office hours before going to the lab and get some feedback on your design and style. This is likely to 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 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 was the point of Problem 1; you should follow this methodology on your own in the future, without an explicit problem to force you to do it.

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.

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: getChildren on nodes with 0, 1, and 2 children, findPath with 0, 1,and 2 start nodes, 0, 1,and 2 goal nodes, and 0, 1,and 2 paths found. 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.

Q & A

This section will list clarifications and answers to common questions about problem sets. 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 problem set handout and the specifications) when you have a problem.

Q. What do we mean by having a "directed, node-weighted graph" yet also "the Graph abstraction should not assume that node objects are of any particular runtime type"?

A. The graph should be node-weighted, meaning the nodes are the ones with the associated cost and not the edge (cross-reference edge-weighted graphs). However, we do not want your graph to be hardcoded to a particular runtime type, i.e. your graph should not just use the WeightedNode class internally. Eventually, you will be using this graph class for other types, namely GeoSegments and the like. As such, we are asking that you use Java Generics to implement your Graph, so that you may have a node-weighted graph that can support other node types, other than the WeightedNode class that we provide.

Q. Do we have to create the testing architecture to process the script files ourselves?

A. Nope. We have provided a PS3TestDriver class for you to use that parses the test script files you write (following the format we give). This PS3TestDriver class acts as a in-between between the test files and your Graph class. If you look closely at the PS3TestDriver, we have left (in comments) places you should modify in order to support different operations like adding nodes or edges to your Graph. Because we want you to complete this problem set without any reference to GeoSegments yet, we have provided a WeightedNode class for you to use as the generic node type for your graph in testing with this PS3TestDriver.

Errata

When you first checkout ps3 from your psets module, you will need to add this line to the ScriptFileTests.java file after package ps3.test; so that the beginning looks like:

package ps3.test;

import java.io.BufferedReader;
...
We apologize for this error.