Lab 10: Graphs
Due: Friday, April 22, 11:59pm, note different deadline!
For your final project you will implement a graph data structure in Java, and use it to create an interactive application. This lab is the first stage, so that you can get this part working completely before moving on to the next. For both stages, the emphasis should be on code that works - it is much better to implement less and have it working than attempt more that does not work. Don't worry if you don't get through much during lab today, this part is due next Friday and it's good to spend time on the foundation so you can build on it successfully in Stage II.
Although graphs may be represented in many different ways, for this assignment you will use a sparse, list-based representation offering significant flexibility. Both nodes and edges will contain data; as a result, the Graph class will be a generic parameterized by two types.
To give you an idea of what is expected, you should browse the Graph javadoc of a sample Graph class. Keep in mind that this shows only the fields and methods declared publicHere is an outline for the methods and code to implement: You should implement much of the same functionality, so that your graph class may be used by a program expecting this interface.
You should test your classes thoroughly to ensure that they will function properly in the next stage of the project. Develop these tests in the file TestGraph.java, and submit that with the rest of your assignment. The contents of TestGraph should show that you understand how to thoroughly test a new class.
You are encouraged to use the Java core classes in this project wherever they seem applicable. In particular, the ArrayList class is recommended for storing lists/sequences, and HashSet when you have a collection that will be tested often for membership. Take advantage of the methods already defined by these classes, such as contains(), remove(), get(), etc. Please note in your readme file why you chose to use any predefined data classes that appear in your program.