Description
Problem 1
Goal
Work with graphs.
Background
You are part of the city’s accessibility office in charge of helping people navigate the city.
Google maps doesn’t exist yet. Your job is to tell people how to get from their current location
to a destination in the city by walking
We describe the city by its intersections. Each intersection has (x, y) coordinates (both integers)
to tell you where the intersection is. We identify a part of a road by telling you the coordinates
of the two intersections at either end of the road.
When someone calls you, they will give you the coordinates of their current intersection and
will give you the coordinates of their destination intersection. Your response should be the
sequence of intersections to cross, using only city roads, to reach the destination in the shortest
distance. That sequence will begin with the coordinates of their current location and will end
with the coordinates of their destination intersection.
Problem
Write a class called “HalifaxMap” that accepts city map data, a current location, and a
destination and then prints the sequence of intersections to traverse to get to the destination.
The class has at least 3 methods:
– Boolean newIntersection( int x, int, y ) – record a new intersection for the city. Return
true if we acknowledge the intersection and we didn’t know about it before. Return
false otherwise.
– Boolean defineRoad( int x1, int y1, int x2, int y2 ) — record the existence of a road from
(x1, y1) to (x2, y2) in the city. Return true if this road is a new one for the map and has
been added to requests to consider. Return false otherwise.
– Void navigate( int x1, int y1, int x2, int y2 ) – print to the screen the sequence of
intersection coordinates to follow to go from (x1, y1) to (x2, y2) in the shortest distance
while staying on roads. Print “no path” if you can’t get from the location to the
destination.
Dijkstra’s algorithm for shortest paths in graphs is one possible approach to solving this
problem. You are welcome to use others.
Inputs
All the inputs will be determined by the parameters used in calling your methods.
Outputs
The navigate( ) method produces output to the screen. It produces a list of coordinates, one
per line. The x and y coordinates are separated by a tab character. The first line is the current
location of the person who is calling you. The last line is the location of the destination.
Assumptions
You may assume that
– You do not need to worry about round off error in the lengths of the paths when
determining the shortest path. You can safely round the length of any road to an
integer.
– The roads are straight lines between the intersections. A road from (x1, y1) to (x2, y2)
has length square_root( (x2 – x1)
2 + (y2 – y1)
2 )
Constraints
• You may use any data structures from the Java Collection Framework.
• You may not use a library package to for your graph or for the algorithm to do
matchings on your graph.
• If in doubt for testing, I will be running your program on bluenose.cs.dal.ca. Correct
operation of your program shouldn’t rely on any packages that aren’t available on that
system.
Notes
– You will need a class to store each vertex of the graph. Following that, you will need to
choose whether to store the graph as an adjacency matrix, as an adjacency list, or as an
incidence matrix. Your best bet will likely be an adjacency list.
Marking scheme
• Documentation (internal and external), program organization, clarity, modularity, style –
4 marks
• List of test cases for the problem – 3 marks
• Ability to create the graph from the inputs and to return appropriately in error
conditions –3marks
• Ability to provide a path between two intersections – 10 marks
