6.170 Laboratory in Software Engineering
Spring 2000
Problem Set 5a: PathFinder
Due: March 13, 2000
Handout 11
Guidelines
To do this assignment as efficiently as possible, and to derive the most
benefit, we recommend that you:
-
Start as early as possible.
-
Read the entire text of the assignment before starting any part of it.
-
Think before you code. You'll find that sketching out a plan on paper before
you start will make your coding faster and less error-prone.
-
Follow the Java style guide.
-
Make sure that your answers to questions are succinct and to the point.
To hand in your solution for this part of the problem set, put the
source and compiled code in ~/6.170/ps5a directory, so you TA can
test your program.
Purpose
In this problem set you will design and implement PathFinder, a scaled-down version of MapQuest (www.mapquest.com), a service that calculates routes between various user-provided locations. The problem set is divided into two parts:
a. Command-line version (described in this handout)
b. Graphical interface to the version built in part a (described in a later handout)
However, you will turn in only one document for all of problem set
5, encompassing parts a and b. Your implementation of part a will
be due on March 13, 2000, but you will not turn in any documentation
at that time.
Completing this problem set will be difficult without a good
design. You are strongly encouraged to think about the problem in
detail before writing any code. You should be sure that your design
allows for an easy transition to a graphical interface for part b.
Background
The main job of your program will be to give
directions about how to get from one place to another. This requires
responding to user queries, and determining minimum distance
paths using a database that contains information about distances
between neighbors.
1. Initializing the Database
The database will be initialized from a database file with the
following format: the file contains a number of entries. Each entry
describes how to get from a start node to a neighboring end node; we
will refer to this as a segment of a path. Each entry lists: a
start node (a string), a destination node (a string), a distance (a
float), and a direction (a string). Thus:
<start_node> <destination_node> <distance> <direction>
Each individual component string in an entry has no intervening white
space. Each component of an entry is separated from the next by white
space (white space refers to one or more space, tab, or newline
characters). Successive entries are separated by white space. For
example:
corner_of_1st_and_main lechmere 1.2 east
Segments are uni-directional. Therefore the presence of the above
segment in the file does not imply that you can get from lechmere to
the corner of 1st and main by going west. Instead, if this is possible
the file will contain information about the opposite direction, e.g.,
it might contain:
lechmere corner_of_1st_and_main 1.2 west
Your program will need to read this file and produce a data structure
that makes it easy and efficient for you to answer queries about
paths. Queries are discussed in the following section.
2. Queries and Responses
Users will issue queries about how to get from a start node to an end
node. A query is a string listing the nodes separated by white space:
where source names the source node and dest names the
destination node. There should be no white space inside the nodes'
names. Note that the user might make a mistake while entering a
query. Such human errors should be handled gracefully by your
program. Queries are separated by white space. For example, a query that
asks for the path from LCS to the corner_of_vassar_and_mass_ave will
look like:
LCS corner_of_vassar_and_mass_ave
Your program must respond to a query with the minimum distance path
from the start node to the end node, given the information in the
database. A path is described by a sequence of lines. Every line but
the final one describes a segment of the path and has the following
format:
go <direction> <number> miles to <end-point><newline>
There should be one space character between the words above. The last
line should contain the total distance traveled in the following
format:
total travel distance is <number> miles
For example, if the path you come up with includes the segment from
the corner of first and main to lechmere, the query response will
contain the following line:
go east 1.2 miles to lechmere
Note that the line does not describe the start node for that segment;
that is either the destination node for the previous segment, or it is
the start node given in the query.
A user might pose a query for which there is no answer given
the information in the database. In this case your response will be
the following string:
where s is the given start node and t is the given end node.
For example suppose you have the database below:
LCS corner_of_vassar_and_main .1 east
corner_of_vassar_and_main corner_of_vassar_and_mass_ave .5 south
LCS corner_of_main_and_mass_ave .5 south
corner_of_main_and_mass_ave corner_of_vassar_and_mass_ave .5 east
Then given the query
LCS corner_of_vassar_and_mass_ave
your program should respond
go east 0.1 miles to corner_of_vassar_and_main
go south 0.5 miles to corner_of_vassar_and_mass_ave
total travel distance is 0.6 miles
Given the query
corner_of_vassar_and_mass_ave LCS
your program should respond
no path from corner_of_vassar_and_mass_ave to LCS
3. Processing Queries
Your program must find the minimum distance path from the source node
to the target node of a query, or determine that no such path
exists. We require that your program do this efficiently. This
requires:
1. You will need to read the information in the database
file into a data structure that stores the path information in an
easily accessible form. This operation should run in O(V^3)
time (where V is the number of nodes in the graph).
2. You will then need to implement a routine that responds to
a query in O(V) time. In other words, the routine should use
the data structures you initialized in step 1 to quickly find the
shortest path between a source and destination node in a
database.
One algorithm which will accomplish this is the Floyd-Warshall
algorithmm which is described in Appendix 2 to this problem
set. There are other algorithms to compute shortest paths, and you may
use them if you like.
Assignment
1. Database Engine
You must construct a program that will provide the
functionality described above. This involves designing and
implementing a database engine to process queries. To
accomplish this you should design appropriate abstractions, write your
own specifications for the abstractions, and then implement those
specifications. Don't forget to write abstraction functions and rep
invariants for your implementations, and to implement repOk and
toString for each.
In Appendix 1, we have provided specifications for the
following data abstractions, which you might find useful in your
implementation of the Database Engine: WtDigraph, DistanceChart, and
MapNode. Their *.class files are located in /mit/6.170/class/ps5a
directory. In order to use them, your CLASSPATH has to be set correctly,
as described in the "General Information" handout. You may assume that
these data abstractions have been carefully implemented and tested, thus
you can safely use them in your own implementation.
2. Command-Line Interface
Additionally, you should define a PathFinder class to provide
a command-line interface to the database engine. Your program must be
executable on the command line using the following syntax:
java ps5a.PathFinder <databasefile> [queryfile outputfile]
In order to do this, you need to put all of your code in the package
called ps5a. Arguments in <angle brackets> are required, while
arguments in [square brackets] are optional. Your program operates in
two modes - batch mode and interactive mode. All three arguments are
supplied for batch mode: the first argument is the name of the database
file, the second argument names a file to be used as the source of user
queries, and the third argument specifies a file to place the program's
output in. To enter interactive mode, only the database file is supplied
as an argument.
2.1 Batch Mode
In batch mode, multiple queries may be present in the query
file. The output of multiple queries consists of a sequence of query
responses, where the first query response corresponds to the first
query, and so on; each response starts on a new line. For example, if
the database file is the same as above and the input file contains the
following two queries:
LCS corner_of_vassar_and_mass_ave
corner_of_vassar_and_mass_ave LCS
your program should output:
go east 0.1 miles to corner_of_vassar_and_main
go south 0.5 miles to corner_of_vassar_and_mass_ave
total travel distance is 0.6 miles
no path from corner_of_vassar_and_mass_ave to LCS
(These examples are stored in test.query, test.database, and
test.results in /mit/6.170/src/ps5a/.) Note that you need to follow
this format exactly, since we will be using it when we run your
program on our hidden test cases.
2.2 Interactive Mode
In interactive mode, your program should present the user
with a prompt asking for a query. The user then enters a query (to
standard input, which can be accessed through System.in), terminated
with a newline. At that point your program should print its response
to the query to standard output (i.e., System.out). Any error messages
should go to standard error (i.e., System.err) and not standard out
(to facilitate separating normal and abnormal output). After
displaying its response, your program should present the user with the
option of either entering another query or exiting.
Unlike batch mode, you are free to embellish your program's
interactive mode however you wish.
3. Putting it all together
Place all of your code for this problem set in the ps5a
package, in directory ~/6.170/ps5a/ on Athena.
Your PathFinder class should not implement too much
functionality beyond the handling of the command-line arguments and
the interactive mode prompting. You will want to keep separate your
database engine and its command-line interface. In part b of this
problem set you will be asked to provide a Java applet interface to
the database engine.
At this point you should develop a battery of tests that you
can use for regression testing later on. This means that you should
create a well-designed series of database, query, and corresponding
output files. Then, after the second part of the problem set, you
should run regression tests to ensure that your modifications in part
b did not modify the previous behavior of your program.
4. Extensions
If you wish you can provide a program that does more than
what is discussed above. However, before doing this, you should be
certain that your program handles all the required commands and
formats. Also, you should discuss proposed extensions with your TA
before doing them.
Extensions might involve changing the database, or you might
provide more commands. You might, for example, provide an additional
command to incrementally alter the database by adding a new data point
to the database. Or you might consider 3D directions for getting from
one MIT room to another. For example, how do you get from 34-101 to
10-250?
What to turn in
1. Part a
There is no document due covering only part a. You should
email your TA informing him/her that you have completed your program for
part a; he/she will then evaluate your program using our hidden test
cases. The deadline for "submitting" your code in this fashion is
March 13, 2000. You should not modify any files in your
~/6.170/ps5a/ directory after you have turned in your code. You
should copy your entire ps5a directory to ps5b directory for use
with part b (you can do so with the command "cp -r ~/6.170/ps5a
~/6.170/ps5b"). You will be able to modify your files in a ps5b
directory after the due date for part a. However, it will not affect
your grade for part a.
2. Part b
For part b, you must supply an applet interface to your database
engine. This interface will be described in a later handout.
You do not need to turn in any hardcopies of your code or any
documentation covering only part a; however, after finishing part b
you must turn in documentation covering both parts a and b - so
make sure you document as you go along (please, refer to Handout 12 for
a proper way to document your problem set). This documentation, and
your final program (which should be able to be used both as a
command-line program and as an applet), are due on March 16. On this
date you must deliver hardcopies of both your documentation and your
executable code (as an appendix to your document) to your TA or to the
course secretary by 4:30 PM. Remember to indicate the name of your TA
on the first page.
Be sure that your documentation contains:
a. Data Model.
b. Module Dependency Diagram.
c. Design rationale (refer to Handout 12).
d. Implementation (in the appendix). You code should
contain specifications for all of your data abstractions. Each
implementaion should include a rep invariant, abstraction function,
and implementations of repOK and toString.
e. Testing strategy , both black box and glass box for
each individual data abstraction. Describe your integration testing for
the program as a whole. Also include the output of your testing.
Be concise - do not confuse length with content!
Good luck!
Appendix 1
public class WtDigraph {
/* Overview:
* A WtDigraph is a mutable weighted directed graph.
* It is a pair <N,E>, where
* N is the set of nodes in the graph and
* E is the set of edges between nodes in N.
* Each node is an Object.
* An edge is <from-node, to-node, w>, where from-node and to-node are in N,
* and w is a weight of type Object. There is at most one edge
* from any node to another node.
* Node n1 is a direct successor of node n2 if there exists
* an edge from n2 to n1.
*/
public WtDigraph()
// effects: Initializes this to be an empty digraph.
public void addNode(Object node) throws DuplicateNodeException
/* modifies: this
* effects: Adds <node> to this. Unless:
* <node> is already in this
* => DuplicateNodeException, no modification to this
*/
public void addEdge(Object initialNode, Object finalNode, Object w)
throws NoNodeException, DuplicateEdgeException
/* modifies: this
* effects: adds an edge from initialNode to finalNode unless:
* either initialNode or finalNode is not in this
* => NoNodeException,
* an edge already exists
* => DuplicateEdgeException, no modification to this
*/
public void addNodeAndEdge(Object initialNode, Object newNode, Object w)
throws NoNodeException, DuplicateNodeException
/* modifies: this
* effects: adds newNode and an edge from initialNode
* to newNode with weight w unless:
* initialNode is not in this => NoNodeException,
* newNode is already in this
* => DuplicateNodeException, no modification to this
*/
public void removeEdge(Object initialNode, Object finalNode)
throws NoEdgeException
/* modifies: this
* effects: removes the edge from initialNode to finalNode, unless:
* either initialNode or finalNode is not in this, or
* no edge exists from initialNode to finalNode
* => NoEdgeException, no modification to this
*/
public void changeWeight(Object initialNode, Object finalNode, Object w)
throws NoEdgeException
/* modifies: this
* effects: changes the weight of the edge to w unless:
* either initialNode or finalNode is not in this, or
* no edge exists from initialNode to finalNode
* => NoEdgeException, no modification to this
*/
public Object edgeWeight(Object initialNode, Object finalNode)
throws NoEdgeException
/* effects: returns the weight of the edge from initialNode to
* finalNode, unless:
* initialNode or finalNode is not in this, or
* no edge exists from initialNode to finalNode
* => NoEdgeException
*/
public Iterator nodes()
/* effects: Returns an Iterator that will produce each node in this
* exactly once, in arbitrary order.
* requires: this not be modified while the returned Iterator is in use.
*/
public Iterator successors(Object initialNode)
throws NoNodeException
/* effects: returns an Iterator that will produce each node
* that is a direct successor of initialNode exactly once, in
* arbitrary order. Unless:
* initialNode is not in this
* => NoNodeException
* requires: this not be modified while the returned Iterator is in use.
*/
public String toString()
}
public class DistanceChart {
/* Overview:
* A DistanceChart is a class that represents a mutable distance chart.
* It is a pair <N,E>, where
* N is the set of nodes in the chart and
* E is the set of segments between nodes in N.
* Each node is of type MapNode.
* A segment is <from-node, to-node, d>, where from-node and to-node are in N,
* and d is a distance of type float. There is at most one segment
* from any node to another node.
*/
public DistanceChart()
/* effects: Initializes this to be a new, empty distance chart. */
public void addNode(MapNode node) throws DuplicateNodeException
/* modifies: this
* effects: adds node to this, unless
* node is already in this => DuplicateNodeException. no modification
* to this
*/
public void addSegment(MapNode initialNode, MapNode finalNode, float distance)
throws NoNodeException, DuplicateEdgeException
/* modifies: this
* effects: adds a segment from initialNode to finalNode unless:
* either initialNode or finalNode is not in this
* => NoNodeException,
* a segment already exists
* => DuplicateEdgeException, no modification to this
*/
public void addNodeAndSegment(MapNode initialNode, MapNode newNode, float distance)
throws NoNodeException, DuplicateNodeException
/* modifies: this
* effects: adds newNode and a segment from initialNode
* to newNode unless:
* initialNode is not in this => NoNodeException,
* newNode is already in this
* => DuplicateNodeException, no modification to this
*/
public void removeSegment(MapNode initialNode, MapNode finalNode)
throws NoEdgeException
/* modifies: this
* effects: removes the segment from initialNode to finalNode,unless:
* either initialNode or finalNode is not in this, or
* no segment exists from initialNode to finalNode
* => NoEdgeException, no modification to this
*/
public void changeDistance(MapNode initialNode, MapNode finalNode, float distance)
throws NoEdgeException
/* modifies: this
* effects: changes the length of the segment to distance unless:
* either initialNode or finalNode is not in this, or
* no segment exists from initialNode to finalNode
* => NoEdgeException, no modification to this
*/
public float distance(MapNode initialNode, MapNode finalNode)
throws NoEdgeException
/* effects: returns the distance from initialNode to
* finalNode unless:
* initialNode or finalNode is not in this, or
* no segment exists from initialNode to finalNode
* => NoEdgeException
*/
public MapNode closest(MapNode node) throws NoNodeException, NoEdgeException
/* effects: returns a node n such that the segment (node,n,distance) is in this
* and distance<=u for all m, u such that segment <node,m,u>
* is in this. Unless:
* <node> is not in this
* => NoNodeException
* <node> has no successors
* => NoEdgeException
*/
public Iterator nodes()
/* effects: Returns an Iterator that will produce each node in this
* exactly once, in arbitrary order.
* requires: this not be modified while the returned Iterator is in use.
*/
public Iterator neighbors(MapNode initialNode) throws NoNodeException
/* effects: returns an Iterator that will produce each node c such
* that there exists a segment from initialNode to c,
* exactly once, in arbitrary order. Unless:
* initialNode is not in this
* => NoNodeException
* requires: this not be modified while the returned Iterator is in use.
*/
public String toString()
}
public class MapNode {
/* Overview: MapNodes are immutable objects representing
nodes in a
* distance chart.
*/
public MapNode(String name)
/* effects: initializes this to be the
MapNode corresponding to name */
public boolean equals (Object node)
/* effects: returns true if <node> is of class MapNode
* and has the same name as this.
* Returns false otherwise.
*/
public String toString()
}
Appendix 2
Click here to get the summary of Floyd-Warshall's algorithm.