Algorithm
Development Kit 1.0

Package algs.debug

Defines core abstractions for generating visualizations to track the progress of an algorithm.

See:
          Description

Interface Summary
IDebugSearch Used by animation and other purposes to track the status of a Search.
IGraphEntity All graphical state drawing depends on the individual nodes to be able to return a labeled string to represent itself.
INodeDrawer Interface to define functionality for drawing nodes in Dotty format.
ISelectFont Should a graphical entity choose to select a different font for its node drawing (for example, to show symbols) then it must implement this interface.
 

Class Summary
DottyDebugger Produces a text string that can be used as input to the DOT program [http://www.graphviz.org].
IGraphEntity.Formatter Useful Format for special characters.
Legend Key information about a drawn graph can be represented as a graph legend.
 

Package algs.debug Description

Defines core abstractions for generating visualizations to track the progress of an algorithm. The debugging interface(s) in this package are used to generate many of the images within the Algorithms in a Nutshell book published by O'Reilly Publishers.

We use the GraphViz visualization package developed by AT&T and freely released under the Common Public License Version 1.0. This software provides a DOT language which can encode information about a graph to be viewed by a tool known as dotty. This software has been ported from Unix to Windows and many of the generated images in our book were produced by creating a DOT source file to be used as input to dotty. While dotty supports many forms of output, we chose to output postscript files which were then converted to PDF using the Adobe Distiller utility.

DottyDebugger

The primary entry point for debugging is the DottyDebugger class. This class implements the IDebugSearch interface which powers the debugging.

We distribute the logic to the individual entities themselves, which simplifies the drawing of debugging information at the expense of adding this extra method to classes which otherwise should be unaware of the debugging infrastructure. For example, the TicTacToeState class implements nodeLabel() as follows:

public String nodeLabel() {
   // dotty requires column-ordered state, so we rotate information.
   StringBuilder sb = new StringBuilder();
   for (int c = 0; c <= TicTacToeBoard.MaxC; c++) {
      sb.append("{");
      for (int r = 0; r <= TicTacToeBoard.MaxR; r++) {
         char val = board.get(c, r);
         if (val == TicTacToeBoard.EMPTY) {
            sb.append(" ");
         } else {
            sb.append (val);
         }

         if (r <= TicTacToeBoard.MaxR-1) { sb.append ("|"); }
      }
      sb.append("}");
      if (c <= TicTacToeBoard.MaxC-1) { sb.append ("|"); }
   }    
   return sb.toString();
}
This method constructs a string of the form "{O| |X}{ |X| }{O|X| }" which represents the state of the board in column-oriented format. All elements of the DOT language can be used within the implementation of nodeLabel(), which naturally couples these classes with the specifics of the debugging infrastructure. It was decided to add this complication to each individual class since only the class knows the full information that is to be used when visually drawing the node representing that state within the debugging output.


Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.