data structures

Coursework 1 (15 marks) Introduction This coursework requires you to write software to process networks of train or bus stations, which will be stored as text files, and can be displayed in a manner similar to that illustrated in Figure 1.

Figure 1 An Example Network The text strings in the diagram represent stations, the lines indicate the connections between them, and the numbers indicate the distance you would travel if you traversed those connections (you can assume that these are measured in kilometres, but the units make no difference to the coursework). For example there is a direct route from Kingsand to Rame that is 20 kilometres long. The connections are undirected so, for example if there is a connection from Kingsand to Rame, then there is also a connection from Rame to Kingsand. Networks such as that shown in Figure 1 are examples of data structures known as graphs. We will describe graphs more formally in weeks 4 and 5, but hopefully the figure makes the general idea clear.

For this coursework, you are required to create a GUI application that reads text files that describe networks such as that shown in Figure 1, and which analyses them in various ways. The syntax of the text files is set out in Appendix A. Here are the functional and non-functional requirements that your application must meet. Functional Requirements FR1 The GUI should contain the following elements:

1. An area in which a graphic view of the network can be displayed. We will call this the “graph area”. 2. A separate area in which a list of stations can be displayed. We will call this the “list area”. 3. Buttons marked “Read”, “Breadth”, and “Depth”.

FR2 When the “Read” button is clicked, the user should be presented with a dialog that allows him/her to pick a file. If this file contains text that meets the syntax set out in Appendix A, then the network that it represents should be displayed in the graph area. The network should be displayed in such a way as to respect the positions of stations, and the connections between them, that are described in the text file. If the text file does not follow the syntax set out in Appendix A, then an error message should be displayed. This message does not need to contain any details about the syntax error; it simply needs to state that there was an error. Hint: The files that you have been given include a file GraphicsUtil.java that contains a graphical method that you will find useful. You can use this file without modification, or with modification, or not use it at all, as you desire.

FR3 When the user clicks on the “Breadth” button, the “list” area should be updated so that it displays a list of all the stations in the network, in breadth first order (see Appendix B). The start station for this traversal should be the first station defined in the text file from which the network was read.

FR4 When the user clicks on the “Depth” button, the list area should be updated so that it displays a list of all the stations in the network, in depth first order (see Appendix B). The start station for this Traversal should be the first station defined in the text file from which the network was read.

Non-functional Requirements NFR1 The program should contain classes that implement the Connection,

Network, Station, StationQueue, and StationStack interfaces that you will find on the module website. You may use inner classes where this is appropriate. For example the class that implements the Station interface could be an inner class of the one that implements the Network interface. Hint: You may find that it helps if the class implementing Network has a private field with this declaration private Map<String,Station> stationMap;

NFR2 The breadth first, and depth first, traversals referred to in FR3 and FR4 should be carried out using the iterative algorithms set out in Appendix B, and the queue and stack referred to in that appendix should be implemented using classes that implement the StationStack and StationQueue interfaces NFR3 The program should be constructed without the use

NFR3 When the user clicks on the “Breadth” button, the “list” area should be updated so that it displays a list of all the stations in the network, in breadth first order (see Appendix B). The start station for this traversal should be the first station defined in the text file from which the network was read.

What you have to submit: You should submit two files: 1) A .zip file containing all of your code, preferably as a Netbeans project. 2) A .doc, or .docx file containing a short reflection on the degree to which you have met the functional and non-functional requirements set out above. Mark Scheme

Appendix A: Format of the text files used. The networks that are to be processed will be represented by text files having the following format (illustrated in Table 1): Each station is represented by text in the form Station: StationName XDisplay YDisplay where StationName is the name of the station, which may contain alphabetic characters and underscores, but no other characters, and XDisplay and YDisplay are decimal integers in the range 0-255 which are used to indicate where the station should appear when the network is displayed on screen. XDisplay and YDisplay are used to indicate where the stations would appear if the graph area was of size 255x255 pixels. You do not have to set the graph area to actually be 255x255 pixels, so long as you scale the displayed graph in an appropriate way. For example, if the text file assigned co-ordinates 100,100 to a particular station, then that station could be displayed at position 100,100 on a 255x255 graph area, or 200,200 on a 512x512 graph area, and so on. Also the XDisplay and YDisplay co- ordinates should not be taken as representing the real world geographical positions of stations. Stations that are displayed in a way that makes them look far apart may actually be quite close in the real world (for example Kingsand and Cawsand are quite far apart in Figure 1, but the numbers on the graph indicate that you can get from one to the other by travelling only 5 kilometres). N.B. You can make use of the GraphicsUtil class provided in order to display the network. You should not assume that the text representing a station will be all on one line. You should not assume that all stations will be defined before all connections. However you can assume that, if a connection refers to a station, then that station will be defined before it is referred to. Connections between stations are represented by lines of the form Connection: StationName1 StationName2 Distance Where StationName1 and StationName2 are the names of the two stations connected (as specified by the bits of text beginning with “Station:”) and Distance is the distance value for the connection expressed as an number which may or may not include a decimal point. Hint #1: You can read the text files using a Scanner. The use of a Scanner to read input streams coming from files was explained in module U08009.

Hint #2: Because you cannot assume that each connection is on a separate line, you should not use the nextLine() method of the Scanner class. Use the next() and nextDouble() methods instead. The network shown in Figure 1 might be represented by the text shown in Table 2. The line breaks in the text are deliberate, and illustrate that you should not assume that the text representing a station or connection will be on one single line. The fact that the definition of the Treninnow station comes after some of the connection definitions is also deliberate. Note that the definition of the Treninnow station comes before any connections that refer to it.

Table 1 Text representation of network in Figure 1

Station: Rame 65 120 Station: Antony 20 100 Station: Cawsand 130 60 Station: Kingsand 160 140 Station: Millbrook 65 100 Station: Penlee 110 120 Station: Polbathic 20 120 Connection: Rame Penlee 10 Connection: Rame Millbrook 15 Connection: Millbrook Cawsand 23 Connection: Cawsand Kingsand 5 Connection: Kingsand Rame 20 Station: Treninnow 110 100 Connection: Millbrook Treninnow 30 Connection: Millbrook Antony 35.3 Connection: Antony Polbathic 22 Connection: Polbathic Rame 20

Appendix B: Breadth First and Depth First Traversal Breadth First Traversal In a breadth first traversal of a graph we visit all of the nodes that can be reached from a given start point by traversing one connection, then all those that can be reached by traversing two connections, and so on. So a possible breadth first traversal of the graph in Figure 1, starting at Rame would be: Rame Penlee Kingsand Polbathic Millbrook Cawsand Antony Treninnow. You should use the following iterative algorithm to create a list of nodes in breadth- first order, beginning with a specified start station. Let Q be a queue of Stations Create an initially empty list of Stations, which we will call L Add the start station to the back of Q While Q is not empty BEGIN

Remove the Station at the front of Q, call this Station S Add S to the end of L For each station S2 that is adjacent to S BEGIN

If S2 is not in the list L then add it to the back of queue Q END (For)

END (While) Return L Clarification: in the algorithm two stations are “adjacent” if that you can get from one station to the other without passing through any other station. So for example in Figure 1 Antony is adjacent to Millbrook, but not to Rame. Note: it is possible to write a recursive algorithm for breadth first traversal, but you should not do so. We want an iterative algorithm as set out above.

Depth First Traversal In a depth first traversal of a graph we visit all of the nodes that can be reached from a given start point in the following manner: We begin at the start point, then visit a station S2 that is adjacent the start point, then we try to visit an unvisited a station S3 that is adjacent to S2, and so on. If we arrive on a node from which we can go nowhere (because there are no adjacent nodes that we have not already visited) then we “backtrack” to a node which we have already visited but which has adjacent nodes that we have not visited. So a depth first traversal of the graph in Figure 1, starting at Rame would be: Rame Millbrook Antony Polbathic Treninnow Cawsand Kingsand Penlee. You should use the following iterative algorithm to create a list of stations in depth first order, beginning with a specified start station.

Let S be a stack of Stations Create an initially empty list of Stations, which we will call L Push the start station onto the stack S While S is not empty BEGIN

Pop the Station at the top of the stack. Call this Station T. If T is not already in list L then add it to the back of that list. For each station T2 that is adjacent to T BEGIN

If T2 is not in the list L then push it on to the top of the stack S END (For)

END (While) Return L Note: it is possible to write a recursive algorithm for depth first traversal, but you should not do so. We want an iterative algorithm, as set out above.