Algorithm
Development Kit 1.0

algs.debug
Class DottyDebugger

java.lang.Object
  extended by algs.debug.DottyDebugger
All Implemented Interfaces:
IDebugSearch
Direct Known Subclasses:
BinaryTreeDebugger, RightThreadTreeDebugger, TicTacToeDebugger

public class DottyDebugger
extends java.lang.Object
implements IDebugSearch

Produces a text string that can be used as input to the DOT program [http://www.graphviz.org].

If the generated text string is too large it is placed into a file in the current working directory and the file name into this file is returned as the text string.

This class operates using the Visitor Design pattern exclusively. As an example we show the BinaryTreeDebugger class, which provides the logic to display a binary tree (and balanced binary trees). By extending the DottyDebugger class, you only need to declare the type of edge to use by overriding edgeType(). Then access the API provided by DottyDebugger to visit nodes using visitNode(IGraphEntity) and edges using visitEdge(IGraphEntity, IGraphEntity) methods. In this example, the BinaryTreeDebugger class implements the IVisitor interface which means it can be a visitor that traverses each node of the binary tree. When asked to visit a node, IVisitor.visit(algs.model.tree.BinaryNode, algs.model.tree.BinaryNode), BinaryTreeDebugger first invokes the inherited methods visitNode(IGraphEntity) on node n and its parent, but only if they have not yet been visited before. Note that nodes is inherited from the DottyDebugger class. This precaution is needed for arbitrary graphs but you actually need it here since visiting a tree with three nodes (a root with both left and right child) you need to ensure that you only invoke visitNode(IGraphEntity) using the parent root node a single time. Once both nodes are visited then it is possible to visit the edge between them, using visitEdge(IGraphEntity, IGraphEntity).

 public class BinaryTreeDebugger extends DottyDebugger implements 
     IVisitor, IBalancedVisitor {

  // Declare that edges are forward edges (and not undirected).
  public String edgeType() { return "dir=forward"; }
        
  // Visit (parent, child) pair by visit each node individually, then the edge.
  public void visit(BinaryNode parent, BinaryNode n) {
    // if not yet seen, visit node. Only have to check parent (for root).
    if (parent != null && !nodes.contains(parent)) {
      visitNode(parent);
    }
                
    if (!nodes.contains(n)) {
      visitNode(n);
    }
                
    if (parent != null) {
      visitEdge(parent, n);             
    }
  }

  // Corresponding method for balanced binary trees.
  public void visit(BalancedBinaryNode parent, BalancedBinaryNode n) {
    // if not yet seen, visit node. Only have to check parent (for root).
    if (parent != null && !nodes.contains(parent)) {
      visitNode(parent);
    }
        
    if (!nodes.contains(n)) {
      visitNode(n);
    }
                
    if (parent != null) {
      visitEdge(parent, n);             
    }
  }
 }
 
The full set of available debugger methods can be found in the IDebugSearch interface. They are:

There are several ways to configure this class for your needs.

  1. ordering(String) is used to layout the nodes. Choose one of two values to select DepthFirstOrdering ("in") or BreadthFirstOrdering ("out").
  2. rank(String) is used to change orientation. Set to "LR" if the ordering should be properly done from left to right instead of from top to bottom.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Field Summary
static int _ctr
           
static java.lang.String BreadthFirstOrdering
           
static java.lang.String defaultFontName
           
static int defaultFontSize
          These fonts are embeddable within PDF documents.
static java.lang.String DepthFirstOrdering
          Ordering types.
 java.util.ArrayList<java.lang.String> discarded
          Nodes that appear in the search output but which have now been discarded.
protected  List<algs.debug.EdgePair> edges
          Edges.
 java.lang.String goal
          Goal key.
protected  java.util.Hashtable<java.lang.String,IGraphEntity> nodes
          Nodes.
 java.lang.String start
          Start key.
static int TooLarge
          Max string size to return from getInputString().
 java.util.ArrayList<java.lang.String> unexplored
          Nodes that appear in the search output but which were never explored.
 
Constructor Summary
DottyDebugger()
           
 
Method Summary
 void complete()
          All is ready to be processed.
 java.lang.String edgeType()
          Edges should be undirected.
 java.lang.String getInputString()
          Resulting string available after calling complete.
protected  java.lang.String getKey(IGraphEntity value)
          Helper function to reverse locate the key.
 void labelEdge(IGraphEntity n1, IGraphEntity n2, java.lang.String label)
          Label edge with information.
 void markDiscarded(IGraphEntity n)
          Mark node as being discarded.
 void markEdge(IGraphEntity n1, IGraphEntity n2)
          Mark special edges in bold.
 void markGoal(IGraphEntity gl)
          Mark the goal node found.
 void markStart(IGraphEntity st)
          Mark the start node.
 void markUnexplored(IGraphEntity n)
          Mark node as being unexplored.
 java.lang.String nodeType()
          Default to having nodes with complex record shapes.
 int numNodes()
          Return the number of nodes in the generated tree.
 void ordering(java.lang.String ord)
          Ordering of children.
 void rank(java.lang.String r)
          Rank orientation of the figure.
 void visitEdge(IGraphEntity n1, IGraphEntity n2)
          If called multiple times, multiple edges result.
 void visitEdge(IGraphEntity n1, IGraphEntity n2, java.lang.String label)
          Assign label to the edge upon creation.
 void visitNode(IGraphEntity n)
          Mark node as being visited.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

_ctr

public static int _ctr

start

public java.lang.String start
Start key.


goal

public java.lang.String goal
Goal key.


unexplored

public java.util.ArrayList<java.lang.String> unexplored
Nodes that appear in the search output but which were never explored.


discarded

public java.util.ArrayList<java.lang.String> discarded
Nodes that appear in the search output but which have now been discarded.


nodes

protected java.util.Hashtable<java.lang.String,IGraphEntity> nodes
Nodes.


edges

protected List<algs.debug.EdgePair> edges
Edges.


TooLarge

public static int TooLarge
Max string size to return from getInputString().


defaultFontSize

public static final int defaultFontSize
These fonts are embeddable within PDF documents.

See Also:
Constant Field Values

defaultFontName

public static final java.lang.String defaultFontName
See Also:
Constant Field Values

DepthFirstOrdering

public static final java.lang.String DepthFirstOrdering
Ordering types.

See Also:
Constant Field Values

BreadthFirstOrdering

public static final java.lang.String BreadthFirstOrdering
See Also:
Constant Field Values
Constructor Detail

DottyDebugger

public DottyDebugger()
Method Detail

ordering

public void ordering(java.lang.String ord)
Ordering of children. IN for breadth-first, OUT for depth-first.

Parameters:
ord - either DepthFirstOrdering or BreadthFirstOrdering

rank

public void rank(java.lang.String r)
Rank orientation of the figure.

Parameters:
r - "LR" to make the graph left to right

numNodes

public int numNodes()
Return the number of nodes in the generated tree.


nodeType

public java.lang.String nodeType()
Default to having nodes with complex record shapes. Subclasses should override as needed.


edgeType

public java.lang.String edgeType()
Edges should be undirected. Subclasses should override as needed.


getInputString

public java.lang.String getInputString()
Resulting string available after calling complete. Note if there are more than TooLarge nodes in the tree, a File is created and that is returned instead of this string.


complete

public void complete()
All is ready to be processed.

Specified by:
complete in interface IDebugSearch

getKey

protected java.lang.String getKey(IGraphEntity value)
Helper function to reverse locate the key.


markStart

public void markStart(IGraphEntity st)
Mark the start node.

Specified by:
markStart in interface IDebugSearch
Parameters:
st - Node to be marked

markGoal

public void markGoal(IGraphEntity gl)
Mark the goal node found.

Specified by:
markGoal in interface IDebugSearch
Parameters:
gl - Node to be marked

markUnexplored

public void markUnexplored(IGraphEntity n)
Description copied from interface: IDebugSearch
Mark node as being unexplored. These are typically nodes placed on the OPEN list that were never explored. Since they appear in the output, we don't want to give the impression that they were considered.

Specified by:
markUnexplored in interface IDebugSearch
Parameters:
n - node to be marked

markDiscarded

public void markDiscarded(IGraphEntity n)
Description copied from interface: IDebugSearch
Mark node as being discarded. Currently not being used by any debugger.

Specified by:
markDiscarded in interface IDebugSearch

visitNode

public void visitNode(IGraphEntity n)
Mark node as being visited.

Specified by:
visitNode in interface IDebugSearch
Parameters:
n - node to be visited

visitEdge

public void visitEdge(IGraphEntity n1,
                      IGraphEntity n2)
If called multiple times, multiple edges result.

Specified by:
visitEdge in interface IDebugSearch
Parameters:
n1 - source node
n2 - target node

visitEdge

public void visitEdge(IGraphEntity n1,
                      IGraphEntity n2,
                      java.lang.String label)
Assign label to the edge upon creation.


labelEdge

public void labelEdge(IGraphEntity n1,
                      IGraphEntity n2,
                      java.lang.String label)
Label edge with information.


markEdge

public void markEdge(IGraphEntity n1,
                     IGraphEntity n2)
Mark special edges in bold.

Specified by:
markEdge in interface IDebugSearch
Parameters:
n1 - source of edge
n2 - target of edge

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.