Assignment 5 Bus Trip Planning

CS 2210a — Data Structures and Algorithms
Assignment 5
Bus Trip Planning
Total marks: 20
1 Overview
For this assignment you will write a program that given the map of a city with bus lines, it will
find a way (if any) of traveling by bus from a given starting point to a destination so that at most a
given number of bus changes is needed. Your program will receive as input a file with a description
of the city streets and bus lines, the starting point S, the destination D, and the allowed number
k of bus changes. Your program will find a path from S to D that can be traveled by bus and
requires at most k bus changes, if such a path exists. Note that there might be several ways of
traveling from S to D while changing buses at most k times; your program only needs to find one
of them.
Your program will store the city map and bus lines as an undirected graph. Every edge of the
graph represents a street and every node represents either the intersection of two streets or the end
of a dead-end street. There are two special nodes in this graph denoting the starting point S and
the destination D. A modified depth first search traversal, for example, can be used to find a path
as required.
The following figure shows an example of a map with three bus lines, a (pink), b (yellow), and
c (blue). The starting point is marked S and the destination is D. In all the maps that we will
consider for this assignment, the streets will be arranged in a grid. Furthermore, only buses of one
bus line will run on any given street (so buses from two different lines cannot drive along the same
street; however, they can go through intersections with streets where buses from other lines run).
D
S
line b
line c
line a
Figure 1: A city map with bus lines.
The above map is represented with the following graph. Each edge is marked with the bus line
that it represents. The nodes of the graph are numbered consecutively, starting at zero from left to
right and top to bottom; hence, for a graph with n nodes, the nodes are numbered 0, 1, 2, . . . , n−1.
If, for example, we want to find a path from S to D that uses only one bus line change, a
possible solution is the path 0, 1, 5, 6, 10. Observe that the path 0, 4, 5, 6, 10 is not a valid solution
as it requires three bus changes: at node 4 a change is needed from line a to line c, at node 5 a
second bus change is needed from line c to line a, and at node 6 a third bus change is needed from
8 9 10 11
4 5 6 7
0 1 2 3
D
S
line c
line b
line a
Figure 2: The graph representation for the above map.
line a to line c. Even though this last path is formed by edges belonging to only two bus lines,
three bus changes are needed.
2 Classes to Implement
You are to implement at least four Java classes: GraphNode, GraphEdge, Graph, and BusLines.
You can implement more classes if you need to, as long as you follow good program design and
information-hiding principles.
You must write all code yourself. You cannot use code from the textbook, the Internet, other
students, or any other sources. However, you are allowed to use the algorithms discussed in class.
For each one of the classes below, you can implement more private methods if you want to, but
you cannot implement additional public methods.
2.1 GraphNode
This class implements a node of the graph. You must implement these public methods:
• GraphNode(int name): This is the constructor for the class and it creates an unmarked node
(see below) with the given name. The name of a node is an integer value between 0 and n−1,
where n is the number of nodes in the graph.
A node can be marked with a value that is either true or false using method setMark. This
is useful when traversing the graph to know which vertices have already been visited.
• setMark(boolean mark): Marks the node with the specified value.
• boolean getMark(): Returns the value with which the node has been marked.
• int getName(): Returns the name of the node.
2.2 GraphEdge
This class implements an edge of the graph. You must implement these public methods:
• GraphEdge(GraphNode u, GraphNode v, char busLine): The constructor for the class.
The first two parameters are the endpoints of the edge. The last parameter is the bus line to
which the street represented by the edge belongs. Each bus line has a name that consists of
2
a single character: Either a digit or a letter, except ’S’ and ’D’ which are used to mark the
starting point and the destination. For example ’a’, ’I’, and ’2’ might be the names of three
bus lines. Note that case matters, so a bus line might have name ’a’ and another might have
name ’A’. There might be bus lines called ’s’ or ’d’, but no bus line can be called ’S’ or ’D’.
• GraphNode firstEndpoint(): Returns the first endpoint of the edge.
• GraphNode secondEndpoint(): Returns the second endpoint of the edge.
• char getBusLine(): Returns the name of the busLine to which the edge belongs.
2.3 Graph
This class implements an undirected graph. You must use an adjacency matrix or an adjacency list representation for the graph. This class must implement the GraphADT.java interface.
The methods from GraphADT.java are described below.
• Graph(n): Creates a graph with n nodes and no edges. This is the constructor for the class.
The names of the nodes are 0, 1, . . . , n−1.
• insertEdge(GraphNode u, GraphNode v, char busLine): Adds an edge connecting u and
v and belonging to the specified bus line. This method throws a GraphException if either
node does not exist or if in the graph there is already an edge connecting the given nodes.
• GraphNode getNode(int name): Returns the node with the specified name. If no node with
this name exists, the method should throw a GraphException.
• Iterator<GraphEdge incidentEdges(GraphNode u): Returns a Java Iterator storing all
the edges incident on node u. It returns null if u does not have any edges incident on it.
• GraphEdge getEdge(GraphNode u, GraphNode v): Returns the edge connecting nodes u
and v. This method throws a GraphException if there is no edge between u and v.
• boolean areAdjacent(GraphNode u, GraphNode v): Returns true if nodes u and v are
adjacent; it returns false otherwise.
The last three methods throw a GraphException if u or v are not nodes of the graph.
2.4 BusLines
This class represents the city map with bus lines. As mentioned above, a graph will be used to
model the map and to find a path from the starting point to the destination. For this class you
must implement the following public methods:
• BusLines(String inputFile): Constructor for building a city map with its bus lines from
the input file. If the input file does not exist, this method should throw a MapException.
Read below to learn about the format of the input file.
• Graph getGraph(): Returns the graph representing the map. This method throws a MapException
if the graph could not be created.
• Iterator<GraphNode trip(): Returns a Java Iterator containing the nodes along the path
from the starting point to the destination, if such a path exists. If the path does not exist,
this method returns the value null. For example for the map and path described above the
Iterator returned by this method should contain the nodes 0, 1, 5, 6, and 10.
Hint. In this class you need to store references to the starting and destination nodes.
3
3 Implementation Issues
3.1 Input File
The input file is a text file with the following format:
C W H K
RLRLRL· · ·RLR
L L L · · ·L L
RLRLRL· · ·RLR
L L L · · ·L L
...
RLRLRL· · ·RLR
The first line contains the following 4 numbers (separated by spaces):
• C is the scale factor used to display the map on the screen. Your java code will not use this
value; it is used by the programs supplied to you. If the map appears too small on your
screen, increase this value. Similarly, if the map is too large, choose a smaller value for the
scale.
• W is the width of the map. The streets of the map are arranged in a grid. The number of
vertical streets in each row of this grid is the width of the map.
• H is the length of the map, or the number of horizontal streets in each column of the grid.
• K is the number of bus line changes allowed in the trip from the starting point to the destination.
For the rest of the file, R is any of the following characters: ’S’, ’D’, or ’.’. L could be ’ ’ (space),
a letter (except ’S’ or ’D’) or a digit. The meaning of the above characters is as follows:
• ’S’: starting point
• ’D’: destination
• ’.’: intersection of two streets or dead-end
• ’ ’: houses
• letter or digit: street belonging to the bus line whose name is specified by the letter or digit.
There is only one starting point and one destination, and each line of the file (except the first) must
have the same length. Here is an example of an input file representing the map shown in Figure 1:
30 4 3 1
Sa. .a.
a a a a
.c.a.a.
c b b
.c.bDb.
The fourth number in the first line of this input file specifies that for this instance at most one
bus change can be made to try to reach the destination.
4
3.2 Finding a Path
Your program must find any path from the starting vertex to the destination vertex that uses at
most the specified number of bus line changes. A bus line change happens when in the path there
are two adjacent edges belonging to different bus lines. If there are several paths from the starting
vertex to the destination with at most the allowed number of bus line changes, your program can
return any one of them.
Please try to design your own solution for the problem. There are some hints about how to
compute the required path, but do not read the hints unless you are completely stuck.
4 Code Provided
You can download from the course’s website the following files: DisplayMap.java, Board.java,
FindPath.java, GraphADT.java, GraphException, MapException, house1.jpg, house2.jpg, house3.jpg,
and house4.jpg. Class DisplayMap provides the following public methods that you will use to display the map and the solution computed by your algorithm:
• DisplayMap(String inputFile): Displays the map on the computer’s screen. The parameter is the name of the input file.
• drawLine(GraphNode u, GraphNode v): draws an edge connecting the specified nodes.
Read carefully class FindPath.java to learn how to invoke the methods from the BusLines
class to find the required path. FindPath.java also shows how to use the iterator returned
by the BusLines.findPath() method to display the solution found by your algorithm. Class
FindPath.java contains the main method for your program so you should use it to test your implementation of the BusLines.java class. Class Board.java is an auxiliary class for DisplayMap,
and GraphADT.java contains the Graph ADT. The .jpg files are used to display the map on the
screen.
You can also download from the course’s website some examples of input files that we will use
to test your program. We will also post a program that we will use to test your implementation
for the Graph class.
To run your program you need to type
java FindPath input file
You can also type
java FindPath input file delay
where delay is the number of milliseconds that the program will wait before drawing every edge
of your solution.
5 Hints
You might find the Vector and Stack classes useful. However, you do not have to use them if
you do not want to. Recall that the java class Iterator is an interface, so you cannot create
objects of type Iterator. The methods provided by this interface are hasNext(), next(), and
remove(). An Iterator can be obtained, for example, from a Vector or Stack object by using the
method iterator(). Hence, if your algorithm stores the path in a Stack S, then an iterator can
be obtained from S by invoking S.iterator().
5
6 Coding Style
Your mark will be based partly on your coding style.
• Variable and method names should be chosen to reflect their purpose in the program.
• Comments, indenting, and white spaces should be used to improve readability.
• No variable declarations should appear outside methods (instance variables) unless they contain data which is to be maintained in the object from call to call. In other words, variables
which are needed only inside methods, whose values do not have to be remembered until the
next method call, should be declared inside those methods.
• All variables declared outside methods (instance variables) should be declared private, to
maximize information hiding. Any access to the variables should be done with accessor
methods.
7 Marking
Your mark will be computed as follows.
• Program compiles, produces meaningful output: 2 marks.
• Tests for the Graph class: 4 marks.
• Tests for the BusLines class: 4 marks.
• Coding style: 2 marks.
• Graph implementation: 4 marks.
• BusLines implementation: 4 marks.
8 Handing In Your Program
You must submit an electronic copy of your program through OWL. Please DO NOT put your
code in sub-directories. Please DO NOT submit a .zip or .rar file containing your code; submit
the individual .java files.
When you submit your program, we will receive a copy of it with a datestamp and timestamp.
You can submit your program more than once if you need to. We will take the latest program
submitted as the final version, and will deduct marks accordingly if it is late. Please send me an
email if you make multiple submissions so we can ensure that your last submission is marked.
6