Homework 1 Framework Guide
What is this document?
This document is meant to assist you in using the framework by:
- Presenting a high-level overview of the framework
- Describing usage of the framework's GUI and command-line components
- Defining the graph definition file format
- Explaining how to integrate your code into the framework
- Identifying reported bugs, requested features, and known "gotcha's"
- Providing a method for feedback and bugs
What this document is not
An description of framework internals. Try the javadocs.The Framework Overview
The first thing you should know about the framework is, IT IS EXPERIMENTALIn fact:
int number = 1;
while (true) {
System.out.println("The number " + number + " think you should know is");
}
System.out.println("!!The framework is EXPERIMENTAL!!");
number++;
if (student.isConvinced(FRAMEWORK_IS_EXPERIMENTAL)) break;
Now that I have convinced you that the framework is experimental, you will understand that
- The code has bugs
- The code is still being documented
- The code may not have all of the features it should
- The code may be sloppy in some places.
The primary goal of the homework1 framework is to allow you to implement your UCS algorithm without worrying about things like priority queues and GUI calls. To that end, we wrote a reference implementation of UCS, made sure it worked, and then ripped out about twenty lines of code that define the algorithm.
The bonus for the student is that it shouldn't take to long to write the UCS algorithm.
The downside is that it doesn't leave a lot of room for experimentation. In fact, we worry that the framework we are providing may force the student into a particular implementation.
NOTE: If you want to deviate from the existing framework to create your own implementation of UCS, please feel free. You may find it difficult to link into the GUI, but working with the existing command line interface should be straight forward. Please contact the TA's (mostly Seth Nielson) with any questions.
As an additional help, we have provided a complete implementation of BFS traversal. Not only does this provide clues about implementing UCS, but it also demonstrates how to use the provided hooks for linking into the GUI.
The reason for providing the GUI is to allow the student to visually see how the algorithm actually functions. We feel that this is useful to understanding and remembering the algorithm in the future. The command line remains an alternative for those who don't feel the need for visual animations. One secondary goal that influenced the design of this system was extensibility. Hopefully, many of these components will be reusable for different homeworks in the future. That is why, for instance, we provide a base graph interface that is parameterized on types and values. We wanted to balance this, however, with the students needs for this homework, which is why we provide the SimpleAdjMatrixGraph that implements from Graph and sets the key and value types to Integer.
Excuting the Algorithms
To run the command line versions:
java -classpath "." comp314.algorithms.GraphBFS
java -classpath "." comp314.algorithms.GraphUCS
Obviously, if your classpath is set appropriately, you can call these programs without the "-classpath" option.
The arguments to GraphBFS and GraphUCS are the same:
- -iFILE, --in FILE - the graph definition file. Defaults to default.save.
- -rROOT,--root ROOT - set the root node for the traversal. Defaults to 0
- -lLEVEL,--loglevel LEVEL - set the global logging level. Defaults to OFF.
java --classpath "." comp314.jtraverser.AdjacencyMatrixViewer
It can accept one command line argument: -lLEVEL, --loglevel LEVEL to set the global logging level. The default is OFF. (See Sun's Level class for more details about logging levels). The GUI provides a special view for logging information.
The GUI itself is (hopefully) somewhat straightforward and easy to use. The main view allows for creating, viewing, and visually manipulating graphs. One either lateral side of this are tables for viewing parent vertex assignments and distances for nodes from the root. The top and bottom panels provide the controls.
TO CREATE A NEW GRAPH
- If there are already nodes on the drawing view, Clear the graph
- To insert Vertices, select Insert Vertex and click with the mouse in the drawing view.
- To insert an edge, select Insert Edge and click a vertex with a mouse. A line should be drawn from the vertex to the mouse's current location. To finish creating an edge, click on another vertex (or anywhere else on the drawing view to cancel).
- To adjust the weight of an edge, click on the current weight and "drag" the mouse up to increase the weight, or down to decrease the weight.
- Vertices are moved around by clicking dragging (in any modes Select or Insert Edge).
Save and Load provide standard interfaces for saving and re-loading graphs. At present, there is no auto-save. And you must name the file every time you save. Also, there is, as yet, no way to delete vertices or edges, so the creation of a large graph should be punctuated by repeated saves.
Clear clears the current graph out of memory completely. Reset just resets the graph after (or during!) a traversal.
Breadth First and Uniform Cost run their respective algorithms on the current graph using the currently selected node as the root. If no node is selected, the traversal starts from node '0'.
The Slider speeds up or slows down the animation. The numbers represent milliseconds of delay between events. So the range is 0 to 5 seconds per event.
Graph Definition File
Graph definition files are in plain text. They have the following format:
- Line 1: A comment, or header. Ignored when read.
- Vertex Lines: V[vertex-number]:[X],[Y]
- Edge Lines: E:[vertex-number],[vertex-number],[weight]
PLEASE NOTE
It is absolutely ESSENTIAL that the vertices be numbered contiguously from 0 to n. Any gaps will cause the traversals to fail.Code Integration
When writing your UCS algorithm and you want it to integrate into the GUI, plese use the following calls:
- publish.initParent and publish.setParent to set the parent hash map (p)
- publish.initDistance and publish.setDistance to set the distance hash map (d)
- publish.initColor and publish.setColor to set the color hash map (colormap)
- publish.getWeight to check the weight between edges.
The GraphBFS algorithm uses all of these calls except for getWeight (which it obviously doesn't need).
The basic idea for the set(/init) methods is instead of setting the map directly:
colorMap.put(vertex, NodeColor.WHITE);
To use the corresponding set call:
setColor(colorMap, vertex, NodeColor.WHITE);
The getweight method is used in a similar fashion.
The init calls are identical to their set counterparts except that the GUI won't delay for them. This is good, because you'd like the GUI to not slowly step through each call of the setup.
Bugs, Feature Requests, and More,
In the absence of a bugs database, reported bugs, etc., will be listed and updated here. The severity is values listed are not just arbitrary. Here is what they mean:
- CATASTROPHIC - This bug will prevent you from completing the homework
- MAJOR - This bug requires a work around to complete the homework
- MINOR - This bug prevents the use of a non-essential feature
- ANNOYANCE - This bug annoys you
BUGS:
| Number | Severity | Description | Reported By/Date | Status |
|---|---|---|---|---|
| 1 | MINOR | Sometimes vertices cannot be drawn on the right side of the drawing area. | Seth Nielson (1/27/2006) | Not Fixed |
| 2 | MINOR | Sometimes the GUI starts up blank. | Seth Nielson (1/27/2006) | Not Fixed |
| 3 | MAJOR | Sometimes vertices get lost (gaps between numbers). This causes traversal to fail. | Seth Nielson (1/27/2006) | Not Fixed |
| 4 | MINOR | Loading a graph after inserting nodes is broken. | Seth Nielson (1/27/2006) | Not Fixed |
| 5 | ANNOYANCE | When altering the weight of an edge, moving the mouse down, if above the edge, still causes the weight to increase | Gregory Malecha (1/27/2006) | Not Fixed |
| 6 | MAJOR | If there are non-contiugous vertex numbers, the traversal fails | Seth Nielson (1/27/2006 | Not Fixed |
Feature Requests:
- Delete Vertex/Edge
- Step through annimation
Feedback and Bug Reporting
Please report feedback and bugs by email to "sethn AT cs.rice.edu".
When reporting a bug, please use the following subject line:
-
COMP314-HW1-FRAMEWORK-BUG-severity
Any other feedback or feature requests, please just use a descriptive subject line. Feedback or feature requests can go to the newsgroup if you wish.