Programming Assignment 1 - Graph Traversal and Search.

By three methods we may learn wisdom: First, by reflection, which is noblest; Second,
by imitation, which is easiest; and third by experience, which is the bitterest.
- Confucius

Due Wednesday November 2 at 11:59pm

Starting with the reference code implementation for either Java, C++, or C# perform the following tasks:

  1. Implement Depth-First Traversal using the Visitor design pattern
  2. Implement a concrete Visitor classes that searches for a particular node label, stops once it finds it, provides the nodeIndex and keeps track of how many nodes were explored (visited) before it found the node. Use a get method on the class (e.g., SearchVisitor) to retrieve this value.
  3. Implement a concrete Visitor classes that prints out the node labels to the console.
  4. Use a separate class hierarchy to access node and edge labels from your grid. I have provided a couple of samples on this: GridDataConstantValue, GridDataRandomIntValue. Implement GridDataRandomFloatValue and two other classes that have some interesting affects. Also implement a more interesting edge data accessor.
  5. Provide 5 test cases to verify your program is correct.

Where possible call the behavior through the graph interface as opposed to the grid type (i.e., your variable should be declared as type IGraph, not as type grid). Include a README.txt file that explains how to build and run your program, the test cases selected and other implementation details.

Design Notes:

We are not using a full blown Visitor pattern. It probably would be clearer if I called the method DoWork rather than PreAccept. You are suppose to inherit from the IGraphVisitor. So for a simple PrintVisitor, the Accept would just print a message (and information on the index and label) to the Console. The visitor needs to know that it is a graph to get the nodeLabel, but does not need to know anything else. The thing to remember about Design Patterns is they a patterns with many permutation, take the overall idea and mold it to your problem rather than try to plug and chug it in  directly.

Your GraphWalker class (or what ever you call it) should take an IGraphVisitor in the constructor as well have a set method that allows you to change the visitor. You should be able to traverse from any node including the root. This will only show the reachable set from this node. Note, you should not modify the IGraph or IGraphVisitor interfaces. Note, everything is read-only, so pointers and pointer-aliasing are not only OK, but a good way to do this.

Based on several questions, let me clarify further:

There is a fairly clean separation of concerns here:

  1. IGraph has NO behaviors - it just knows its structure and can return queries on its structure. It has no knowledge of graph walkers or visitors.
  2. Graphwalker is an iterator of sorts, it knows how to traverse a graph such that each node is only visited once. Much like a foreach iterator, it has no knowledge of what you want to do at each node or edge. It punts on that and simply calls preaccept each time a new node is discovered and postaccept once the traversal is finished. It takes both a graph and a visitor to accomplish its work. You may have several of these, random, in index order, depth-first, breadth-first, shortestest path, etc.
  3. IGraphVisitor should not query the nodes adjacency. It knows about a graph only so it can call the getNodeLabel or getEdgeLabel. These are very application specific: create a convex-hull, search for a node label, print out the graph structure, print out a path from A to B, draw the graph, etc. It knows nothing of how the graph is traversed: DS, BFS, other. Many applications will not have a need for the postaccept, so this is typically a no-op.

Now, we can take a arbitrary concrete implementation of a IGraph, any traversal algorithm we want / need, and any visitor and combine them to solve our problem. I can for instance, reuse my search visitor in a BFS to determine the number of edges on the shortest path.

Frameworks

You may use the following code base as a start. The sample provides an interface for the visitor and data accessor. It should run fine but produce incorrect results right now.

Submit Guidelines

Students in the 10:30 section should submit their labs to /submit/c680ab - use the UNIX command "submit c680ab lab1 projDir".

Make sure your directory is cleaned of any intermediate files (.obj files and .exe files) Do a Build->Clean Solution. Please do not zip the files if using submit. Non-CSE students can e-mail the grader if need be with a single zip file that does not have any .exe or .dll files in it.