Data Structures and Algorithms Assignment 5 Bus Trip Planning Solution

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).




S
line a


line b
line c
D








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

node的顺序是从左往右。




接着换行依次递增 ，但是在这里不重要






















你会有一个# change line




然后如果一个dfs search找不到得回去 unmark







S







line a
0
1
2
3
4
5
6
7





line b




8 9 10 11




line c

D




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.




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 adja-cency 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
Implementation Issues



3.1 Input File




The input file is a text file with the following format:




CWHK

RLRLRL· · ·RLR




LL···LL RLRLRL· · ·RLR
LLL···LL

.

.

.

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 desti-nation.



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:




30431




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.




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 dis-play the map and the solution computed by your algorithm:




DisplayMap(String inputFile): Displays the map on the computer’s screen. The param-eter 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 im-plementation 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.




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
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 con-tain 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.



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.



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