Reference Manual

Design Specification

This manual describes the design of the applet. The requirements for the assignment were clearly specified by the instructor’s assignment page, but it was left to the student to choose a reasonable design and implementation.

Organization of Modules

From the beginning, I wanted to create something more visually appealing than simply a text box that displayed a solution. After all, we were told to use an Applet, not to implement a text-based program, so it made sense to take this as a challenge and produce something visually appealing.

At the same time, I wanted to keep a clear distinction between the user interface elements and the algorithm to solve the graph so that I might be able to change the user interface without affecting the code for the implementation.

I further decided to separate the code to read the graph files from the code to solve them. I thought this would allow me to create several different methods to solve a graph in case one implementation worked better than another. For example, I wanted to be able to change only a line of code to switch between solving a graph using a brute force solver and a smarter algorithm like the one I described in my paper.

The result was three main categories of functionality in the applet, and this is shown below. The functionality of the files is not completely separated as they are shown in the diagram, but generally this is how the code is organized.

I will describe each component in greater detail below, but first I will mention the algorithms and data structures used in the applet.

Algorithms

The applet uses three “interesting” algorithms. The first and by far the most important is the algorithm used to solve the graphs. The implementation is identical to the algorithm described in the paper, so I won't go into any great detail how it works here. For more information, see my paper.

The second algorithm of interest is the one to determine whether or not the graph read from a file is a connected graph. This works very similarly to the algorithm to solve the graph because they both use a BFS algorithm. This second algorith, however, is simpler in that it traverses the graph and marks the vertices that it has reached. When it finishes, it verifies the number of vertices visited is equal to the number of vertices in the tree. If it is, then it is clear the graph is a fully connected graph. If it is not, then it is clear the graph is not fully connected.

The third algorithm of interest is the one to create random graphs. Because this one is not based on any known algorithm (the other two were based on BFS), I will discuss this one in the greatest detail here.

The randomization algorithm starts by creating an array the size of the vertices in the graph. It initializes the elements of this array with the index of each vertex. Then it randomly swaps each element in the array. The result is a random, connected graph with no loops.

Then, the algorithm again loops over each element in the array. It considers the current element to be the root of a subtree. It randomly selects some number of the remaining elements to be children of this tree and then recursively visits those child nodes.

For example, in the graph above, on the first element of the array, 4, the algorithm might randomly select three of the remaining elements to be children in the graph. The remaining element, 3, would therefore connect directly to 4, and the algorithm would recusively deal with the children 5, 1, and 2 in the same way. If in the recursion, the random selection of children was 0, then elements 5, 1, and 2 would all become children of 5. Graphically, this is shown below.

The corresponding graph at this point would be the following.

At this point in the algorithm, a fully-connected graph has been created, but there are no loops. To create the loops, an adjacency matrix is created, and the algorithm loops over each element in this matrix. If two nodes are not connected, the algorithm randomly determines if it should created a loop by connecting the two vertices. The algorithm connects on average 25% of these unconnected, possible edges, and that produces a fully-connected graph containing trees and loops.

The corresponding completed, random graph at this point would be the following.

Data Structures

The applet implements several important data structures. The two generic data structures implemented are a queue and a matrix. The queue is used in the BFS algorithms, and the matrix is used whenever an adjacency matrix is needed.

The applet also implements a data structure to manage the data from the graph file. The applet splits this work into two classes, the Edge class and the Graph class. Both of these classes are immutable, and they try to represent the file structure as closely as possible. In other words, they do not implement anything “smart” like an adjacency matrix.

The JadeSolver class implements the main graph solving algorithm, and before it begins to execute its BFS portion, it first puts the graph vertices and edges into its own smart objects. I decided to separate this code from the Graph and Edge classes because data structures are an important part in the implementation of an algorithm, and the choice of what data structures to use might change depending on the algorithm. In my case, I used an adjacency matrix, a queue, and an inner class that keeps information about the vertices of the graph in such a way that the algorithm can ask for a collection of neighboring nodes for a vertex and get the result very quickly, O(1) time.

Classes

This section describes the classes in the applet implementation and how they interact with each other. I will describe each category described above: user interface classes, graph classes, and algorithm classes.

Algorithm Classes

These classes were designed to solve graphs. The GraphSolution class connects these classes to the rest of the applet. In other words, when a graph is solved, the solution is put into a GraphSolution and returned to the rest of the applet.

To support multiple implementation of graph solving algorithms, I created an abstract class called GraphSolver that contains one abstract method, solve. The applet solves graphs through derived classes of this class. This class also implements base functionality that allows the solutions to be animated by the user interface of the applet.

The JadeSolver extends the GraphSolver class and implements the solve method. This is the class that implements the algorithm described in my paper.

Two other classes, LinkedListQueue and Matrix were implemented to help the main algorithm solve the graph using reasonable data structures. The LinkedListQueue was implemented only because the JDK installed on uhunix2 was old, outdated, and did not support the Queue collections that JRE version 6 provides.

Graphs

The classes in this category were designed primarily to deal with loading or creating graph files. One exception class was created, GraphException, and it is thrown from the classes in this category when something wrong is detected in a graph file.

The GraphRandomizer class implements an object that can create pseudo-random graphs. The algorithm for this class was described above.

The main classes in this category, however, are the Graph and Edge graphs. These classes were designed to load and verify graph files. These classes are immutable, so they are easily shared between objects.

Lastly, the GraphListener class is used to connect the algorithm category and the user interface category by providing a method to pass progress on the solution of a graph from a solver to the user interface. When graphs are animated, for example, this class is important in transferring partial solutions to the applet display.

User Interface

The user interface classes were designed to display output for and receive input from the user. The SpanningTreeApplet is the main class in this category, and the entry point for the web browser. It implements the code to add components to the screen, animate graphs, resize itself based on the container size, handle button clicks, and other user interface functionality.

The AnchorLayoutManager class implements a standard java layout manager. It is responsible for aligning controls quickly as the applet is resized. The code in this class is somewhat long and boring, but it is straightforward.

The GraphBox class is the largest class in the applet. It is responsible for displaying the graph. It can display a partial solution or a complete solution. It draws a scale, some information about the graph, and of course the vertices and edges. The GraphBox class is also responsible for displaying a popup window that displays full details about the graph.

The StatusLabel class is one of the simplest classes, and it is responsible for displaying the status of the applet. This class extends a JLabel and adds the functionality of a timer so it can “flash” an error message for a few seconds at the top of the display when something goes wrong.

Last, the BackgroundWorker class implements a thread that downloads and solves graphs while the user interface remains responsive. For example, as the graph is solved, it can be animated, and this class makes this possible. The need for this class is because the old JDK installed on uhunix2 does not have support for certain classes available with Version 6 of the JRE swing package. It was not difficult to implement, though, using existing code in the latest JRE as an example.

JavaDoc

All classes, methods, and fields in the implementation are commented using JavaDoc syntax, and as a result, it is straightforward to produce HTML documentation for the code. These low-level details of the source code may be found here.