Description
1 Overview
For this assignment you need to write a program that finds a path between two specified locations
in a roadmap that satisfies certain conditions specified below. The roadmap has 3 kinds of roads:
public roads, private roads that have a fee to be used, and construction roads that are under repair,
so the traffic through them is slow.
Your program will receive as input a file with a description of the roadmap, the starting point
s, the destination e, the maximum number p of private roads that the path from s to e can use,
and the maximum number c of construction roads that the path from s to e can use. Your program
then will try to find a path from s to e as specified.
You must store the roadmap as an undirected graph. Every edge of the graph represents a road
and every node represents either the intersection of two roads or the end of a road. There are two
special nodes in this graph denoting the starting point s and the destination e. A modified depth
first search traversal, for example, can be used to find a path as required, if one exists.
2 Classes to Implement
You are to implement at least four Java classes: Node, Edge, Graph, and MyMap. 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 Node
This class represent a node of the graph. You must implement these public methods:
Node(int id): This is the constructor for the class and it creates a node with the given id.
The id of a node is an integer value between 0 and n − 1, where n is the number of nodes in
the graph.
markNode(boolean mark): Marks the node with the specified value, either true or false.
This is useful when traversing the graph to know which nodes have already been visited.
boolean getMark(): Returns the value with which the node has been marked.
int getId(): Returns the id of this node.
2.2 Edge
This class represents an edge of the graph. You must implement these public methods:
Edge(Node u, Node v, String type): The constructor for the class. The first two parameters are the endpoints of the edge. The last parameter is the type of the edge, which for this
assignment can be either ”public” (if the edge represents a public road), ”private” (if the edge
represents a private road), or ”construction” (if the edge represents a road with construction
work on it).
Node firstNode(): Returns the first endpoint of the edge.
Node secondNode(): Returns the second endpoint of the edge.
String getType(): Returns the type of the edge.
2.3 Graph
This class represents an undirected graph. You must use an adjacency matrix or an adjacency
list representation for the graph. For this class, you must implement all the public methods specified
in the provided GraphADT interface plus the constructor. Hence, this class must be declared as
follows:
public class Graph implements GraphADT
The public methods in this class are described below.
Graph(int n): Creates a graph with n nodes and no edges. This is the constructor for the
class. The ids of the nodes are 0, 1, . . . , n−1.
Node getNode(int id): Returns the node with the specified id. If no node with this id
exists, the method should throw a GraphException.
addEdge(Node u, Node v, String edgeType): Adds an edge of the given type connecting
u and v. 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.
Iterator incidentEdges(Node 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.
Edge getEdge(Node u, Node 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(Node u, Node v): Returns true if nodes u and v are adjacent; it
returns false otherwise.
The last four methods throw a GraphException if u or v are not nodes of the graph.
2.4 MyMap
This class represents the roadmap. A graph will be used to store the map and to try to find a path
from the starting point to the destination satisfying the conditions stated above. For this class you
must implement the following public methods:
MyMap(String inputFile): Constructor for building a graph from the input file specified
in the parameter; this graph represents the roadmap. 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 roadmap.
int getStartingNode(): Returns the id of the starting node (this value and the next three
values are specified in the input file).
2
int getDestinationNode(): Returns the id of the destination node.
int maxPrivateRoads(): Returns the maximum number allowed of private roads in the path
from the starting node to the destination.
int maxConstructionRoads(): Returns the maximum number allowed of construction roads
in the path from the starting node to the destination.
Iterator findPath(int start, int destination, maxPrivate, maxConstruction): Returns a Java Iterator containing the nodes of a path from the start node to the destination
node such that the path uses at most maxPrivate private roads and maxConstruction construction roads, if such a path exists. If the path does not exist, this method returns the value
null. For example for the roadmap described below the Iterator returned by this method
should contain the nodes 0, 1, 5, 6, and 10.
3 Implementation Issues
3.1 Input File
The input file is a text file with the following format:
SCALE
START
END
WIDTH
LENGTH
PRIVATE ROADS
CONSTRUCTION ROADS
RHRHRH· · ·RHR
HXHXHX· · ·HXH
RHRHRH· · ·RHR
HXHXHX· · ·HXH
…
RHRHRH· · ·RHR
Each one of the first seven lines of the input file contains one number:
SCALE is the scale factor used to display the map on the screen. Your program will not use this
value. If the map appears too small on your screen, you must increase this value. Similarly,
if the map is too large, choose a smaller value for the scale.
START is the starting node.
END is the destination node.
WIDTH is the width of the map. The roads of the map are arranged in a grid. The number of
vertical roads in each row of this grid is the width of the map.
LENGTH is the length of the map, or the number of horizontal roads in each column of the
grid. So the total number of nodes in the corresponding graph is WIDTH × LENGTH.
PRIVATE ROADS is the maximum allowed number of private roads in the path from START to
END.
CONSTRUCTION ROADS is the maximum allowed number of construction roads in the path from
START to END.
3
For the rest of the input file, R can be any of the following characters: ’+’ or ’B’. H could be
’B’, ’V’, ’C’, or ’P’. The meaning of the above characters is as follows:
’+’: denotes either and intersection of two roads, or a dead end
’V’: denotes a private road
’P’: denotes a public road
’C’: denotes a construction road
’B’: denotes a block of houses, a building, or a park
Each line of the file (except the first eight lines) must have the same length because, as mentioned
above, the only roadmaps that we will consider are grid roadmaps. Here is an example of an input
file:
30
0
10
4
3
1
1
+P+B+V+
PBCBPBP
+V+V+P+
BBVBPBP
+P+V+V+
This input represents the following roadmap
starting point
destination
private road
public road
construction
road
For the above example, a path from node with id 0 to node with id 10 is sought that uses at
most one private and one construction roads.
3.2 Graph Construction
The roadmap is represented as a graph in which node ids are numbered consecutively, starting at
zero from left to right and top to bottom. For example, the above roadmap is represented with
this graph:
4
98 10 11
4 5 6 7
0 1 2 3
starting point
destination
where dotted edges represent private roads, solid edges represent public roads, and wavy edges
represent construction roads. In the MyMap class you need to keep a reference to the starting and
destination nodes.
3.3 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 private and construction roads. The path can use any number of
public roads. If there are several such paths, your program might return any one of them.
The solution can be found, for example, by using a modified DFS traversal. While traversing the
graph, your algorithm needs to keep track of the vertices along the path that the DFS traversal has
followed. If the current path has already used all allowed private roads, then no more private-road
edges can be added to it. Similarly, if the current path has already used all allowed construction
roads, no more construction-road edges can be added to the path.
For example, consider the above graph and let the maximum allowed number of private roads be
1 and the maximum allowed number of construction roads be 1. Assume that the algorithm visits
vertex 0, then 4, and then 5. As the algorithm traverses the graph, all visited vertices get marked.
While at vertex 5, the algorithm cannot next visit vertices 6 or 9, since then two private roads
would have been used by the current path. Hence, the algorithm goes next to vertex 1. However,
the destination cannot be reached from here, so the algorithm must go back to vertex 5, and then
back to vertices 4 and 0. Note that vertices 1, 5 and 4 must be unmarked when the algorithm
steps back, as otherwise the algorithm will not be able to find a solution. Next, the algorithm will
move from vertex 0 to vertex 1, and then to 5. Since edge (1, 5) represents a construction road, the
current path has used 1 construction road and no private roads. The algorithm can then move to
node 6 and then to 10 as the rest of the path uses only one private road. Therefore, the solution
produced by the algorithm is: 0, 1, 5, 6, and 10.
You do not have to implement the above algorithm if you do not want to. Please feel free to
design your own solution for the problem.
4 Code Provided
You can download from the course’s website the following files: TestGraph.java, DrawMap.java,
Board.java, Path.java, GraphADT.java, GraphException, MapException, and several image files.
The main method is in class Path.java , so to run your program you will type
java Path input file
5 CS 2210a Assignment 5
You can also type
java Path input file delay
where delay is the number of milliseconds that the program will wait before drawing the next edge
of the solution.
You can use TestDict.java to test your implementation of the Graph.java class. You can
also download from the course’s website some examples of input files that we will use to test your
program.
5 Hints
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 instance, from a Vector or Stack object by using the method iterator(). For
example, if your algorithm stores the path from the starting node to the destination in a Stack S,
then an iterator can be obtained from S by invoking S.iterator().
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 unnecessary instance variables must be used in your code.
All instance variables must be declared private, to maximize information hiding.
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 MyMap class: 4 marks.
Coding style: 2 marks.
Graph implementation: 4 marks.
MyMap 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 file or other compressed file containing
your code; submit the individual .java files.
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.
6 CS 2210a Assignment 5
