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