The Data Structures Library in Java

JDSL Tutorial

Previous Lesson
Table of Contents
Next Lesson


Lesson 6: Tree Drawing

This demo application constructs a random tree and draws it to the screen. The tree's nodes hold the names of employees in a company. Internal nodes are colored red, while external nodes are black. The application provides an introduction to the JDSL Tree, which is a type of non-linear PositionalContainer.

New concepts covered:


There are five files in this application: To run the demo program, type java SimpleTreeDraw in a shell.

So far, we have looked at fairly traditional containers.  In this lesson, we look at the tree, a positional container type that is non-linear, so there is no concept of a rank.  The Position objects in a Tree are connected as a tree structure.  For example, look at the following figure:

In this tree, each position stores a String that represents a person's last name (this could be an organization chart).  We refer to Positions of a tree as nodes.  The node labeled "DUNN" is called the root of the tree.  The nodes connected below a node are called its children.  Similarly, the node connected above is called its parent.  Nodes without children are called or leaves or external nodes.  Nodes with children are called internal.  For a complete discussion of trees, see the textbook.

This application looks at drawing trees, that is, finding a readable layout on the screen.  We implement a simple tree drawing algorithm that finds for each node a bounding box that completely surrounds the drawing of the subtree.  The width of the subtree is the maximum of the width of the drawing of its node and the sum of the widths of the drawing of its children.  The height of the drawing is some constant times the height of the subtree.  For example, the following figure has the bounding boxes added in for the tree drawn above:

First, we look at the methods to build a tree.  The class RandomTreeBuilder.java uses a random number generator to construct a tree.  There is one public method:
    protected Tree tree;
    protected Sequence names;

    public Tree randomTree(int n) {
        tree = new NodeTree();
        names = NameGenerator.getNames();
        build(tree.root(), n);  // auxiliary recursive method
        return tree;
    }

This method builds a random tree with n nodes.  We build an instance tree of the interface jdsl.core.api.Tree by instantiating the jdsl.core.ref.NodeTree class.  The constructor builds a NodeTree with one node.  This is very different from the Sequence implementations where you start with an empty Sequence.  The NameGenerator object returns a Sequence of last names that will be used as the elements on the nodes of the tree.  The real work for building the tree is done by the build(Position,int) method:
    protected void build(Position p, int n) {
        int toBuild = n-1;
        Sequence sizes=new ArraySequence();
        if(tree.isExternal(p)) {
           while(toBuild>0) {
           int size = randomInteger(1, toBuild);
                sizes.insertLast(new Integer(size));
                toBuild-=size;
            }
           permute(sizes);
           for(int i=0; i&ltsizes.size();i++){
           Position pos = tree.insertLastChild(p,null);
           int size = ((Integer)sizes.atRank(i).element()).intValue();
           build(pos,size);
            }
            tree.replaceElement(p,pickName());
        }
    }
This method actually builds the Tree.  It is a bit tricky.  The idea is that if we want to build a Tree with n nodes, and we already have built the root, then the sum of the sizes of the subtrees will be n-1.  First, we randomly pick integers that add up to n-1 and put them in a Sequence.  We then permute the list to add a bit more randomness.  Finally, for each generated integer, we attach a root for the subtree, and recursively build the subtree.  The recursion bottoms out when n=1 and the node is already build.

There is only one new JDSL concept in this method.  We attach a new node with the insertLastChild(Position parent,Object element) method.  All insertions into a Tree are accomplished though methods like this.  There are a series of insert methods to insert nodes at various places in the Tree.  Here, we insert a final child of the parent node.  What is returned is a Position representing the new tree node.

The tree drawing is done by extending an algorithm class known as EulerTour.  An Euler tour visits nodes in the same order as if you started at the root and walked along the tree, keeping the tree to your left.  In the tree above, an Euler tour would visit the nodes in the following order: DUNN, JOHNSON, FLORES, JOHNSON, OWENS, JOHNSON, DUNN, THOMPSON, DUNN, LEE, DUNN.

The EulerTour class is abstract.  There are four methods you can override.  Three for internal nodes: visitFirstTime(Position pos), visitBetweenChildren(Position pos), visitLastTime(Position pos), indicating when in the ordering they will be called; and one for external nodes:   visitExternal(Position pos). Note that visitBetweenChildren(Position pos) can be called on a node many times in one EulerTour.  None of these methods are abstract in the EulerTour class.  You only need to override the methods you want to use.

We use two different subclasses of EulerTour to draw the tree, BoundingBoxCalculator that calculates the bounding boxes, and TreeDrawer that performs the actual drawing. In the tutorial we will look at BoundingBoxCalculator.  The TreeDrawer class is similar.
 

  protected int offset = 50;  // size of the grid squares
  protected int width  = 0;   // total width of the explored tree drawing
  protected int depth = 0;    // depth of the current node
  protected Graphics g;       // where the tree will be drawn
  protected FontMetrics fm;   // the fontMetrics object for g

  protected void visitFirstTime(Position pos){
    pos.set("y", new Integer(depth));
    pos.set("x", new Integer(width));
    depth += offset;
  }

The BoundingBoxCalculator overrides the visitFirstTime(Position pos) and visitLastTime(Position pos)methods.  When we visit the node the first time we have completed all visits to the nodes left siblings.  We keep in the variables width the total width of the drawing of the nodes fully explored so far.  We maintain the variable depth to keep the depth of the bounding box of the subtree rooted at pos.  (We'll see how these values are maintained in a moment.)  In this way, we know the (x,y) coordinates of the upper-left corner of the bounding box for the subtree rooted at node pos.

The Position interface extends the Decorable interface.  A decoration is a way to attach a value to an object, without having to subclass the object.  The set() method takes two objects as parameters, the first a key and the second a value.  In this method, we attach two decorations with keys "x" and "y".   There is a corresponding get(Object key) that returns the value associated with the key.

  protected void visitLastTime(Position pos){
    int textWidth = textWidth(pos);
    int shift = 0;
    int x =((Integer)pos.get("x")).intValue();
    int boxWidth = width-x;
    if(textWidth>boxWidth) {
      int delta = textWidth-boxWidth;
      boxWidth = textWidth;
      width += delta;
      shift = delta/2;
    }
    pos.set("width", new Integer(boxWidth));
    // The distance that the children's bounding boxes need to
    // be shifted in the drawing.
    pos.set("shift", new Integer(shift));
    depth -= offset;
  }
This method looks more complicated than it is  When we visit a node for the last time there are two possibilities:  If the node is external, then the width of its bounding box is the width of its label.  We set the "width" decoration to be the textwidth and increase the width variable by textwidth.  If the node is internal, then the width of its bounding box is the maximum of its textwidth and the sum of the widths of its children.  If the text is wider than the children, then we need to increase the width variable and store a positive "shift", to indicate that in the drawing, the children bounding boxes need to be shifted to keep them centered under the node.

    protected void visitExternal( Position pos ) {
      pos.set("y", new Integer(depth));
      pos.set("x", new Integer(width));
      int textWidth = textWidth(pos);
      width+=textWidth;
      pos.set("width", new Integer(textWidth));
      pos.set("shift", new Integer(0));
    }
 

For external nodes, the situation is simpler.  We simply set the value of all decorations.  Notice that we set the "shift" decoration to be 0.  This allows us to treat all nodes uniformly when drawing the tree with the TreeDrawer class.


Previous Lesson
Table of Contents
Next Lesson
Problems, comments?

Last modified: Mon Sep 27 13:39:19 CEST 2004