|
Algorithm Development Kit 1.0 |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectalgs.debug.DottyDebugger
public class DottyDebugger
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:
visitNode(IGraphEntity)
and IDebugSearch.visitEdge(IGraphEntity, IGraphEntity)
)
allow the debugger to add a node to the resulting output or an edge. Be sure to only invoke
IDebugSearch.visitEdge(IGraphEntity, IGraphEntity)
if you have previously
visited both nodes in the edge relationship.
IDebugSearch.markStart(IGraphEntity)
identifies the node considered to be
the "start" of the output. This typically is drawn as the top-most node in the graph, which works
well for search trees and game tree. IDebugSearch.markGoal(IGraphEntity)
is the corresponding
method to declare the target node which is often appropriate for search trees. In an output graph
there may be only a single start and goal node identified using these methods.
IDebugSearch.markUnexplored(IGraphEntity)
identifies a node which can be drawn in grayscale
signifying that the node was (for some reason) not explored or considered for use. An additional
mark method, IDebugSearch.markUnexplored(IGraphEntity)
draws the node with a full grayscale
background that signifies a node that may have been considered or processed but no longer is of use.
This last mark method ultimately was never used by any existing debugger we wrote.
IDebugSearch.complete()
which might have some final computations
that need to be performed.
There are several ways to configure this class for your needs.
ordering(String)
is used to layout the nodes. Choose one
of two values to select DepthFirstOrdering
("in") or
BreadthFirstOrdering
("out").
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.
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 |
---|
public static int _ctr
public java.lang.String start
public java.lang.String goal
public java.util.ArrayList<java.lang.String> unexplored
public java.util.ArrayList<java.lang.String> discarded
protected java.util.Hashtable<java.lang.String,IGraphEntity> nodes
protected List<algs.debug.EdgePair> edges
public static int TooLarge
public static final int defaultFontSize
public static final java.lang.String defaultFontName
public static final java.lang.String DepthFirstOrdering
public static final java.lang.String BreadthFirstOrdering
Constructor Detail |
---|
public DottyDebugger()
Method Detail |
---|
public void ordering(java.lang.String ord)
ord
- either DepthFirstOrdering or BreadthFirstOrderingpublic void rank(java.lang.String r)
r
- "LR" to make the graph left to rightpublic int numNodes()
public java.lang.String nodeType()
public java.lang.String edgeType()
public java.lang.String getInputString()
TooLarge
nodes in the tree, a File is
created and that is returned instead of this string.
public void complete()
complete
in interface IDebugSearch
protected java.lang.String getKey(IGraphEntity value)
public void markStart(IGraphEntity st)
markStart
in interface IDebugSearch
st
- Node to be markedpublic void markGoal(IGraphEntity gl)
markGoal
in interface IDebugSearch
gl
- Node to be markedpublic void markUnexplored(IGraphEntity n)
IDebugSearch
markUnexplored
in interface IDebugSearch
n
- node to be markedpublic void markDiscarded(IGraphEntity n)
IDebugSearch
markDiscarded
in interface IDebugSearch
public void visitNode(IGraphEntity n)
visitNode
in interface IDebugSearch
n
- node to be visitedpublic void visitEdge(IGraphEntity n1, IGraphEntity n2)
visitEdge
in interface IDebugSearch
n1
- source noden2
- target nodepublic void visitEdge(IGraphEntity n1, IGraphEntity n2, java.lang.String label)
public void labelEdge(IGraphEntity n1, IGraphEntity n2, java.lang.String label)
public void markEdge(IGraphEntity n1, IGraphEntity n2)
markEdge
in interface IDebugSearch
n1
- source of edgen2
- target of edge
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |