Assignment for the students that are working independently.

The previous homework that dealt with social network of buddies represented instances of common problems in graph theory. Your goal is to create a framework for dealing with graph traversals and other graph-related problems that would work with any kind of graph.

We will use the cities in the USA, especially the list of capitals of the 48 contiguous states as examples for our problem. However, the solution should be general, so that we can substitute other types of data (within the given constraints.)

1. Design a generic representation of graphs that consists of a collection of nodes , where each node consists of a key, data, and neighbors. My choice for this collection is a HashMap.

   The key must be unique for each node. The data is other information we know about the node, and may include the key as well. The neighbors is probably best represented as a Java ArrayList. If you choose something else, you should defend your choice. However, do not use Java arrays.

2. We want to be able to draw the graphs as well, and so each node should have a way to specify its location. Choose something that will let you display the node on the Canvas, compute the distance between the nodes, and determine the direction of travel from one node to the other one.

3. Make examples of data. Make sure you work with at least two different sets of examples. One may be the list of cities, the other could be Manhattan restaurants, downtown hotels, network nodes, etc.

4. Draw the graph on the canvas. Make sure the abstractions allow you to reuse the same code for any graph that satisfies your graph interface.

5. Define a path in the graph, add methods that make sure it is a valid path, draw the path.

6. Compute the length of the path.

7. Translate the path into a list of Strings that narrate your way through them.

   Your results will look somewhat like this:

   • Go 200 miles North to Albany
   • Turn left
   • Go 600 miles East to Columbus
   • Turn right
   • Go 500 miles north to Chicago

Due Date Wednesday, February 25 2009, 10:00 pm.

There is no real due date for this assignment. By next Wednesday I want to see what you have done. The project will expand to finding the path, finding the shortest path, and possibly more.

We will arrange a time when the whole group can meet - or a time when I can meet with each group to go over the work they have done.

Meanwhile, you should make sure you understand the abstractions covered in the lectures, in the labs, and in the regular assignments.

Ask questions any time.