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:
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.
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.
There is a fairly clean separation of concerns here:
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.
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.
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.