In this part of the lab, we will be creating our own implementation of the Graph ADT. Because this is the last lab of the semester, you will have more freedom than previous labs to design your graph however you wish, so long as it adheres to the following guidelines.
To begin, we will need a class to represent a vertex in the graph. You should create a class called Vertex in a file called Vertex.java.
You are free to add whatever instance variables and methods that you wish to your Vertex class. The only requirement is that it have the following instance variable:
public String name, which stores the name of the vertex (e.g., FWGC| from the Warmup).ReadMe
As you are implementing your solutions, do not forget to include documentation using Javadocs! This is important practice to get into the habit of, and it will be a portion of your solution grade. The class itself (at the top), each instance variable, and each method should have a short Javadoc comment.
You will also need a class to represent the graph itself. You should create a class called Graph in a file called Graph.java.
You are again free to add whatever instance variables and methods that you wish to your Graph class. The only requirements are that it have the following two methods:
Vertex to the Graph:public void addVertex(Vertex vertex)
Graph:public void addEdge(Vertex source, Vertex destination, String label)
ReadMe
It is your choice if you want to represent the edge collection in your Graph as (1) an edge list, (2) adjacency lists, or (3) an adjacency matrix.
You can also choose whether you want to make an explicit Edge class (in a file called Edge.java) or if you want to store the information about each edge in a different manner (e.g., this might not be needed for an adjacency matrix).
You might want to consider that each edge has a label and there might be very many vertices when making these design decisions. We mention in Part 3 how to keep track of paths through a Graph with an Edge class, but it is also possible to do so without an Edge class, if you prefer not to implement one.
You are also free to choose any data structure we have talked about this semester to store your vertex collection.
Hint
One extra functionality that is not necessary but might make your assignment easier to implement is to provide the ability to lookup a Vertex object by its name. A HashMap<String, Vertex> data structure might be very useful here!
Before moving on to the application in this lab, we should create unit tests to verify the implementation of our graph data structure and help us find and remove any bugs. As in previous labs, we can create a Java file that will contain our unit tests by right clicking anywhere in the Graph.java file and selecting “Source Action” from the right click menu. Then, select “Generate Tests”. Use the default name proposed by the IDE of GraphTest. Next, it will prompt you to ask which methods you want to create tests for. You can choose both addVertex and addEdge, as well as any other public methods that you have created.
Your tests should verify that you can create and add Vertex objects and edges to the Graph. You should also verify that your chosen representation properly stores this information (e.g., in adjacency lists or an adjacency matrix).
Hint
To help you debug, you can use the answers to the Warmup to help you test whether your representation matches the one you wrote in representations.txt if you recreate the puzzle example graph.
Don’t forget to frequently save your progress to GitHub using the add/commit/push commands with git.