DSA coursework 2 2019 PDF

Preview

Summary

The second coursework of DSA this year 2019, which is about graphs and railway network...

Description

Data Structures & Algorithms Coursework Assignment 2 Spring Term 2019 Due date: 4pm, Thursday 9th May

This assignment will involve a simple model of a rail transport network. A rail transport network must be encoded as an undirected graph, where the vertices of the graph represent stations and edges represent direct lines between them. Your graph implementation must be based on the adjacency list structure and should implement the GraphADT interface especially provided for this exercise. The assignment comes in two parts: • Part 1 is worth 60 marks overall, and requires you to provide a means of modelling a rail transport network as an undirected graph, where the graph vertices represent the stations and edges represent direct rail links between them. You will need to write a Java class implementing a simplified ADT for undirected graphs. This class must be based on the adjacency list structure, and it should implement a GraphADT interface especially provided for this exercise. The Java implementation should allow a new graph to be constructed from a collection of nodes and a collection of edges and should support a number of basic operations, as detailed below. • Part 2 is worth 35 marks overall, and builds on your implementation for part 1. It requires you to implement a number of additional ‘network algorithms’, as detailed below. A further 5 marks are available for documenting the code appropriately. (More details of the marking scheme can be found in the separate, Assignment 2 Marking Guide.)

Part 1: Core Exercise Graph representation The graph representation should be based on the adjacency list structure. You must write a class called Graph that implements the GraphADT interface provided. You may want to review the lecture notes and look at the description of graph representations in the Goodrich and Tamassia textbook. * You are very likely to come across other people’s code if you are browsing. By all means stare at it: reading other people’s code is a good way of improving your own programming skills. But of course, you should then sit down and implement your own solution to the exercise. Note that the specification is not going to be matched by any “solution” that you find online. And clearly it is not OK to pass off anyone else’s code as your own, so do not plagiarise or collude with fellow students.

Vertices and edges You will also need to implement a class Vertex, representing graph vertices (i.e. stations) and a class Edge, representing edges (i.e. train lines). NB: you must name your vertex and edge classes Vertex and Edge, respectively. Both Vertex and Edge objects should be capable of storing String objects as data elements (names). For example, vertices may represent stations with names such as “London Euston” or “Glasgow Central”. Edges may represent rails links such as “East Coast Mainline”, or “Brighton-London Mainline”.

The Graph Constructor Your Graph class must support a constructor with two parameters: the first parameter is an ArrayList of Vertex objects and the second is an ArrayList of Edge objects. So, the constructor must start like this: public Graph(ArrayList vertices, ArrayList edges) {…

The constructor should initialise a new graph object with the specified vertices and edges. You may also want to provide a more elementary constructor, with no parameters, that simply constructs an initially empty graph object.

Graph Operations Your graph class must implement the Java interface GraphADT that is provided. If you aren’t sure what this means, then see https://docs.oracle.com/javase/tutorial/java/concepts/interface.html or similar, or ask! Your class should (minimally) support the following basic operations: insertVertex(n) insert a new vertex with name n – return the new vertex removeVertex(v) remove the vertex v – return the vertex name insertEdge(v,w,n) Insert new edge with endpoints v and w and name n removeEdge(e) remove the edge e - return the edge name opposite(e,v) Return endpoint of edge e that is opposite endpoint v vertices() return an iterable collection of all the graph vertices edges() return an iterable collection of all the graph edges areAdjacent(v,w) return true if v, w are adjacent; false otherwise incidentEdges(v) return an iterable collection of the edges incident to v rename(v,n) rename existing vertex v as n; return old vertex name rename(e,n) rename existing edge e as n; return old edge name For more details of the precise signatures of the corresponding methods, please refer to the GraphADT interface provided.

Part 2: Solving Rail Network Problems In addition to the operations above, you should try to implement some or all of the following methods. public void bftraverse(Vertex v) – perform a breadth-first traversal of the rail network, starting from a given station. public void bftraverse() – perform a breadth-first traversal of the whole rail network (i.e. this method should work for both connected and non-connected graphs). public ArrayList allReachable(Vertex v) – return a list (ArrayList) of all of the stations (vertices) that can be reached by rail when starting from v. public boolean allConnected() – return true if all the stations in the entire rail network can be reached from one another, and otherwise, return false. public ArrayList mostDirectRoute(Vertex u, Vertex v) – given two stations u and v, return a shortest route (path) between them, if one can be found; or return null to indicate that the two stations cannot be reached from one another. NB: The returned path is represented as a list of edges. Also, by ‘shortest’ route here we mean that the route should involve the fewest possible number of direct rail links (i.e. edges).

Documentation Your code should be suitably documented. The code must be commented appropriately and API documentation should be produced using javadoc with sufficient information about your classes and their public interfaces to allow other programmers to make use of your code....