Lab $3$: Graphs and Topological Sort Lab $3$ examines the use of the Graph data structure discussed in Lectures and lays the groundwork for Assignment $2.$ You are supplied with the Graph abstract class that defines a number of essential methods for operating on graphs. Checkpoints Checkpoint L$3\mathrm{.}1$: Adjacency List Graph Implementation You are required to create an implementation for the Graph interface that uses an adjacency list as the underlying data structure. You need to implement both an undirected graph model and a directed graph model, for example Graph g $=$ new AdjacencyListUndirectedGraph$()$; or Graph g $=$ new AdjacencyListDirectedGraph$()$; The main difference between the two implementations is the addEdge method. The undirected graph will be connected in both directions, whereas the directed will be connected in only one direction, i$.$e$.$ addEdge$("$a$","$b$")$ will connect only from vertex a to b$.$

Your graph data structure needs to maintain a store of the vertices and the edges between them. There are several ways to achieve this and Java gives you many options for data structures $($Lists$,$ Maps, Sets, arrays$).$ Think carefully about your choices and how your represent your adjacency $$list$.$ You may be tempted to use a Map because of the O$(1)$ lookup, but there are some limitations to the Java Map implementations that may be difficult to overcome. It is strongly suggested that you take the conceptually easier choice first and once you have it working you might like to optimise.

Your methods $($e$.$g$.$ getVertices$())$ for your Graph implementations should return Vertex objects $($or a representation of the Vertex$)$ in a sorted way. For this lab, that is lexicographically as defined by the String class on the label of the Vertex $($see the compareTo method in the Vertex class described below$).$ You have been provided with an implementation of the Vertex class to represent a vertex in the graph. The Vertex class needs to be able to represent the vertex and its data. At this point our vertex can have a label $($of type String$).$ Depending on your implementation, you might find the implementations of the methods equals, hashcode, the Comparable interface and the supplied compareTo method useful. You are welcome to modify this class suit your needs $($e$.$g$.$ add methods and variables for degree, in degree, out degree, etc.$)$ The Graph data structure also needs to maintain knowledge of state of the Vertex objects. It needs to maintain the state of being undiscovered, discovered and finished. To enable this a Graph class maintains an instance variable of type Map called stateMap of the states of each Vertex it contains. Feel free to choose a different way to represent the states of the Vertex objects, but this approach may side step the warning below.

The GraphDriver class provides some methods to test out your implementation. The method test$1($Graph g$)$ builds a graph with the following representation $($based on example in lectures$)$:

For an undirected graph, test$1$ from the GraphDriver class will give an output of $($user input denote with $<--$ user input$)$:

$1$ U $<--$ user input

test $1$: Build a graph

Vertices: $[$a$,$ b$,$ c$,$ d$,$ e$]$

a: b d

b: a c d

c: b d e

d: a b c

e: c For a directed graph, test$1$ from the GraphDriver class will give an output of:

$1$ D $<--$ user input

test $1$: Build a graph

Vertices: $[$a$,$ b$,$ c$,$ d$,$ e$]$

a: b

b: c d

c: d e

d: a

e:

You have been provided with a breadth first search class, BreadthFirstSearch, that takes a Graph and a starting Vertex and generates the breadth first traversal list, getBreadthFirstTraversalList$(),$ and also maintains search paths from the starting Vertex to a given Vertex, so that you can get the distance to a particular Vertex, getDistanceTo, and find the path to that Vertex as well, pathTo.

The method test$2()$ applies the breadth first search to the same graph as above. Your output might differ if the order of your adjacent Vertices differs from mine $($but it really should not differ!$)$

For an undirected graph, test$2$ from the GraphDriver class will give an output of:

$2$ U $<--$ user input

test $2$: Breadth First Search

Vertices: $[$a$,$ b$,$ c$,$ d$,$ e$]$

a: b d

b: a c d

c: b d e

d: a b c

e: c

$[$a$,$ b$,$ d$,$ c$,$ e$]$

dist from a to a: $0$

dist from a to b: $1$

dist from a to c: $2$

dist from a to d: $1$

dist from a to e: $3$

For a directed graph, test$2$ from the GraphDriver class will give an output of:

$2$ D $<--$ user input

test $2$: Breadth First Search

Vertices: $[$a$,$ b$,$ c$,$ d$,$ e$]$

a: b

b: c d

c: d e

d: a

e:

$[$a$,$ b$,$ c$,$ d$,$ e$]$

dist from a to a: $0$

dist from a to b: $1$

dist from a to c: $2$

dist from a to d: $2$

dist from a to e: $3$

An issue that may arise is determining if a vertex already exists in you Graph data structure and ensuring that you only have one instance of particular label, e$.$g$.$ all the $"$d$"$s refer to the Vertex with the label $"$d$".$

For example, GraphDriver.test$1$ adds the edge $("$b$","$d$"),$ then the edge $("$c$","$d$"),$ and then the edge $("$d$","$a$").$ You need to

ensure that the vertex $"$d$"$ in those edges are referring