CSC 212: Programming with Data Structures

Lab 10: Graphs

Due: Friday, April 22, 11:59pm, note different deadline!

Credit for this lab: Nick Howe

Overview

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.

Stage I -- Graph Implementation

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 public

Here 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.
  1. First create two classes: TestGraph.java and Graph.java. The testing class is very important and this is where you should test each function you create. The Graph class should be generic and parametrized by two types.

  2. Now add two nested classes to Graph.java: the Node class and the Edge class. They are generic too. Based off of our class discussions, think about what fields each class should have.

  3. Add a linked list field for both the Nodes and the Edges inside the Graph class.

  4. Create a constructor that does not take in any arguments and creates a new empty Graph.

  5. Create and test the following methods:
    • addEdge
    • addNode
    • numEdges
    • numNodes
    • check (no duplicate edges, etc)
    • getEdge
    • getEdgeRef
    • getNode
    • print
    • removeEdge (takes in an edge)
    • removeEdge (takes in a head and tail)
    • removeNode
You will probably want additional methods with more limited access to accomplish tasks that would be potentially dangerous (lead to an inconsistent data structure) if made available for public use. You are not required to follow the given methods exactly, and may wish to make some changes. Nevertheless it is probably a good idea to consider any changes carefully. In general, you should feel free to add methods that seem useful, so long as they don't expose internal structure that should be hidden.

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.

To Submit -- Stage I

  • Graph.java, containing your implementation

  • TestGraph.java, showing how you tested your work

  • Any other files needed for compilation

  • readme.txt

  • typescript, with the results of all your tests