Submission

Please zip your entire directory and submit it via moodle by Monday 4/23 at 11:59pm.

Goals

In this assignment, you will implement a basic directed graph data structure and support DFS and BFS traversals.

1. implement a basic graph data structure using an adjacency list representation
2. implement DFS and BFS traversals for the graph
3. create testing examples that demonstrate your implementation is working

Starter code

I would encourage you to try to write your code based only on what is described on this page.

That being said, you may wish to have some hints along the way. Within each part, you will find links from interface/class/method names to HINTS that provide starting code. If you don't want hints for a certain interface/class/method, don't click the links :)

Part 1 (50 points)

Implement a basic graph data structure that supports generics.

You should have

1. interfaces for the ADT Graph and GraphVertex
   1. A GraphVertex should support:
      1. an ID, stored as an int
         1. offer a getter, but not a setter
      2. attributes as a Map<String, Object> to allow the most flexible data storage
         1. offer a setter and getter for individual attributes
         2. offer a getter for attribute names; this should return an java.util.Iterator<String> instance
      3. methods for adding/removing/getting neighbors
         1. the getter should return an java.util.Iterator<GraphVertex> instance
   2. A Graph should support
      1. methods for adding/removing/getting vertices
         1. the getter should return an java.util.Iterator<GraphVertex> instance
      2. methods for adding/removing/getting edges
2. classes that implement those interfaces with an adjacency list representation
   1. Your DefaultGraphVertex should:
      1. Assign an ID to the vertex in the constructor
         1. Use a static variable to start ID values at 0 and assign them in order each time a new instance is constructed
      2. Use a List (and java.util.ArrayList implementation) to maintain the list of adjacent neighbors for a vertex
         1. To help with maintaining a canonical ordering, have the list store neighbors by increasing ID value
      3. Use a Map (and (you can use a java.util.HashMap implementation) to maintain your attributes, mapping from name/key --> value
         1. For example, a user of your implementation might want to put "id" keys mapped to values, such as "a", "b", etc.
   2. Your DirectedGraph should:
      1. Represent a directed graph
      2. Use a List (and java.util.ArrayList implementation) to maintain the vertices in your graph, sorted by increasing ID value
   3. For both classes, you should override the default Object class' toString() method to return a String that appropriately "prints out" your different objects
      1. Print your vertex as a triplet composed of (ID, attributes, neighborIDs)
      2. Print your directed graph as a pair (vertexIDs, edges)
      3. For example, the graph g1 shown below should print as:

((0,1,2,3),(0->1,1->2,1->3,2->3,3->0,3->1))

and vertex 1 should print as

(1,{key1:value1,...},(2,3))

Part 2 (30 points)

Modify your interfaces from Part 1 to include the following traversals:

public List<GraphVertex> depthFirst( int ID )

public List<GraphVertex> breadthFirst( int ID )

Update your graph implementation to produce DFS (recursive) and BFS (iterative) traversals; the methods should return a List of vertex objects in the traversal order.

Part 3 (20 points)

Create a JUnit tester that creates several test Graphs and prints both the depth-first and breadth-first traversals. This is where it important to have canonical representations and also where your toString methods will be important/helpful.

Choose demonstrative examples that emphasize the difference between the two traversals and include images of your graphs. You may make the images in OmniGraffle (on the CS lab machines) and save as a PDF, jpg, png or gif; or draw them and upload a picture.

You must have at least 1 new graph with at least 4 vertices where you test a DF and BF traversal. Please post your tests to Piazza, but you may only earn late days for additional graph/traversal tests.

Bonus

• Create a GUI that visualizes a graph and the two types of traversals.
• Create an XML file format for a graph; implement GraphFileReader and GraphFileWriter classes that support your format.
• The DFS from class is recursive -- implement an iterative version (using a stack!).