Homerolled Hierarchies

C++ objects to manage and draw trees dynamically

By Eric Rosé, cp3a@andrew.cmu.edu

Introduction

In the past thirty years, a considerable amount of research has been done on the automatic drawing of graphs (that’s the node-and-arc kind - not the Excel kind). Of special interest to interface designers are algorithms which can be used to display a special kind of graph: the hierarchical tree. Trees are a natural way to represent information which can be hierarchically subdivided, such as: organizational charts, design spaces, directory structures, common data structures like binary search trees, B-trees, and AVL-trees. In the last ten years or so there have been many papers which discuss algorithms for aesthetically laying out hierarchical trees (see references), though few of them are intended to do so dynamically. This article discusses two strategies for drawing dynamically changing hierarchical trees, and provides a set of five C++ classes which use these strategies to draw trees while taking into account several customizable display options.

Since the code is rather sizable, I will only present the class interfaces and important parts of the method implementations. The source code disk includes not only the full source code for these classes, but the code for an application which I wrote to test all of the features of both tree algorithms.

Algorithms

Both of the following algorithms assume that each node in a tree consists of a pointer back to its parent, a linked list of child nodes, and a block of data which it can compute the size of. This provides a structure which is very easy to recursively traverse.

Algorithm ER

The first algorithm is a recursive routine which I devised in response to a challenge in a data structures class. It positions nodes by recursively calculating rectangles which enclose successively larger subtrees and justifying the parent of the subtree within that rectangle.

Figure 1. Decomposition of a tree by algorithm ER

ER takes as parameters a node to place, and its desired top left corner. If the node does not have any children, the node’s top left corner is assigned to be the passed-in coordinate. If the node does have children, ER calls itself for each child, accumulating the width of all previous subtrees and adding it to the passed-in coordinate at each call. This insures that every node will be to the right of the subtrees which come before it. When all the children have been considered, the algorithm centers the parent over the children and then exits. A pseudo-code version of ER is shown below.

1ER (Point topLeft, node NodeToPlace) {
2Point  TL = topLeft 

3if nodeToPlace has children  
 {
4TL.v += child/parent margin
5for each child of NodeToPlace 
 {
6ER (TL, child)
7TL.h += width of child's subtree + sibling margin
 }
8justify NodeToPlace over its children
 }
9else
10 NodeToPlace's top left corner = topLeft
 }

Note that if we simply change lines 4 and 7 as shown below, we get a tree which is oriented horizontally rather than vertically.

4TL.h += child/parent margin
7TL.v += height of child's subtree + sibling margin

The trees drawn by algorithm ER are aesthetically pleasing, and good for displaying trees with fairly evenly sized subtrees. A drawback is that it does not make any attempts to reduce white space by packing nodes more closely together. For example, opportunistic compression of the subtree whose root is “Paul” would produce the subtree shown in Figure 2, which is approximately 75% as wide.

Figure 2. Opportunistic Compression of the sample tree

Algorithm SG

The second algorithm, also recursion-based, is used in a graphics visualization tool called SAGE, developed at Carnegie Mellon’s robotics institute. It works by making position estimates which place each node as close as possible to its siblings, and then calculating their real positions as it comes back out of the recursion. A pseudo-code version of SG is shown below, followed by an English description.

1SG (Node NodeToPlace, short level, short levelOffset) {
2if NodeToPlace's estTopLeft.h is greater than Contour[level]
3  set estTopLeft.h to Contour[level];
4if NodeToPlace has children
 {
5for each child of NodeToPlace
 {
6estimate the child's topleft position
7SG (child, level+1, levelOffset);
 }
 }
8Justify the node and fix its position
9Contour[level] = the node's rightmost position
 }

Again, note that changing lines 2, 3, and 9 as shown below will effectively change the orientation of the tree to horizontal instead of vertical.

2if NodeToPlace's estTopLeft.v is greater than Contour[level]
3  set estTopLeft.v to Contour[level];
9Contour[level] = the node's bottommost position

Before SG begins, we create an array called Contour with an entry for each level of the tree. This array is used to store the rightmost position where a node may be placed; all entries are initialized to zero. SG takes as parameters a node to place, its level in the tree, and the vertical distance between it and its parent. If the node has children, then for each child it first estimates the position of the child’s top left corner and then calls SG on it. Estimates are made in the following way: it places the first child by taking the cumulative width of all the children, dividing that width in half, and subtracting it from its estimated center (i.e., its estimated top-left position plus half its width). Each subsequent child is placed by adding the between-node margin to the value in the Contour array for that level of the tree.

When SG first considers a node (i.e., on its way into the recursion) it checks the node’s estimated top-left position against the value in the Contour array. If it is smaller than the value in the array, it is replaced with the value in the array plus the between-node margin. This insures that each node is placed as close as possible to its left sibling. When SG considers the same node on its way out of the recursion, it revises its estimate of the node’s position by centering it over its children. If it has no children, the estimate is not revised at all. Having fixed the top left position, SG updates the value of the Contour array to correspond to the node’s right border. In this way, SG insures that the node’s right sibling will be placed correctly.

Figure 3 provides a visual walk-through of the way in which SG would operate on a simple tree. (Gray frames indicate nodes whose positions are estimations. Black frames indicate nodes whose positions have been fixed.)

Figure 3. Visual trace of algorithm SG

The Creeping Feature Creature

Many of the algorithms which are discussed in the literature have been developed to address specific instances of the tree drawing problem; ie. top-down binary trees, trees with fixed-size nodes, etc. When I set about designing the tree-drawing classes, I decided that it would be useful to build in a lot of flexibility. For example, it would be nice to be able to change the orientation of a tree from top-down to left-right by just tweaking a parameter. I finally decided on seven characteristics which should be dynamically modifiable:

1. size, shape, and data content of nodes in the tree

2. number of children per node

3. justification (left, center, right) of nodes over their children.

4. minimum distance between a node and its siblings

5. minimum distance between a node and its children

6. orientation (top-down, bottom-up, left-to-right, right-to-left) of the tree

7. how lines are drawn between nodes and their children (right-angle, point-to-point)

Since the point of the exercise is to be able to dynamically modify the tree, here’s the list of operations we want to support:

1. Add a child

2. Insert a child

3. Insert a parent

4. Delete a child and promote its children

5. Delete a child and all of its children

6. Change the content (and so possibly the size and shape) of a node

As if that wasn’t enough, we will also add the restriction that the only nodes which should be redrawn when the above operations are performed are the ones whose contents or positions change. There are two reasons for this. The first is to reduce unsightly flicker. For those who respond to this reason by saying “use an offscreen GWorld, dummy”, the second reason is to save time spent doing redraw. While offscreen GWorlds do reduce flicker, redrawing every node on every operation causes unpleasant delays if you have a large number of moderately complex nodes (trust me - I fought this problem all summer long.)

Anybody appalled yet? Relax - everything except the last restriction is pretty straightforward (though the switch statements do get a bit daunting in places!).

OOP(s)!

“The time has come”, the Walrus said, “to talk of implementation details.” In other words, given the algorithms we are using and the features we want, how can we partition everything into classes? One intuitive approach (and, in fact, the one I use) is to treat both the tree and the nodes within the tree as independent objects. Since nodes are objects, their data content (and consequently their size and shape) can be controlled through subclassing. This provides the first feature on our list. The second feature is easily provided by keeping children in an expandable linked-list. The last five features really apply to each tree as a whole since it could be kind of jarring to have orientation, justification, etc. change from node to node. We will, therefore, store information for the last five features in the tree object.

The drawing algorithms we use also map naturally onto the object model proposed above, since they both work by considering successively larger subtrees, rather than dealing with the tree as a whole. This should (and does) allow us to shift the burden of calculation onto the nodes themselves.

CPPTree and CPPTreeNode

Since trees are such massively useful data structures, I decided to start by building two classes which would let me build trees in memory without having to keep track of any display-specific information. The interfaces for the tree class is shown below.

class CPPTree : public CPPGossipMonger {
public:
 CPPTree (void);
 ~CPPTree (void);
 virtualBoolean  Member (char *className);
 virtualchar *ClassName (void);
 
 void   SetTopMostNode (CPPTreeNode *theNode);
 inline CPPTreeNode*GetTopMostNode (void) 
 {return this->topNode;}
 virtualvoidReceiveMessage (CPPGossipMonger *toldBy, 
 short reason, void* info);
 short  Depth (void);

 CPPTreeNode*topNode;
};

CPPTree is descended from a class called GossipMonger, which is functionally identical to the CCollaborator object in the TCL. For those of you unfamiliar with CCollaborator, it lets you form dependencies between objects so that messages can be automatically propagated between them. Messages are sent using a method called BroadcastMessage. The ReceiveMessage method in the target object is responsible for catching these messages and either delegating or dealing with them appropriately. Note that if you have a pointer to CPPTree you don’t have to form a specific dependency; you can just call ReceiveMessage directly.

The only data which the tree class stores is topNode - a pointer to a CPPTreeNode object which is the root node of the tree. GetTopMostNode and SetTopMostNode let the user of the class retrieve or change the root node, and the Depth function returns the number of levels in the tree.

The interface for the tree node class is more elaborate, since it has to deal with all of the operations we listed earlier. Its interface is shown below.

class CPPTreeNode : public CPPObjectList {
public:
 CPPTree*Root;
 CPPTreeNode*Parent;
 
 CPPTreeNode (CPPObject *NodeData, 
 CPPTree *BelongsTo, 
 Boolean becomeOwner);
 ~CPPTreeNode (void);
 virtualchar     *ClassName (void);
 virtualBoolean  Member (char *className);
 virtual CPPObject *Clone(void);

 void TellParent (short Message, void *data);

 CPPTreeNode*NthChild (long whichChild);

 void AddNode (CPPTreeNode *NewNode);
 void InsertNode (CPPTreeNode *NewNode, long insertWhere);     
 
 Boolean InsertParent (CPPTreeNode *NewNode);
 void RemoveChild (CPPTreeNode *theChild);
 void SwitchParents (CPPTreeNode *OldParent, 
 CPPTreeNode *NewParent);

 short  FamilyDepth (short currentDepth);

 CPPObject*GetNodeData (void);
 void   SetNodeData (CPPObject *NewData, 
 Boolean becomeOwner);

 virtualvoidReceiveMessage (CPPGossipMonger *toldBy, 
 short reason, void* info);
 virtualvoidGetFamilyBounds (Rect *bounds);

 static Boolean  DeleteNode (CPPTreeNode *theNode);
 static void   DeleteFamily (CPPTreeNode *theNode);
 static voidClearFamily (CPPTreeNode *theNode);
 static longFamilySize (CPPTreeNode *theNode);
 
protected:
 CPPObject*nodeData;
 BooleanownsData;
};

CPPTreeNode is descended from CPPObjectList, which lets you store an ordered list of C++ objects. The contents of the list, in this case, will be the children of the node. CPPTreeNode holds four pieces of data. The first is a pointer to its own parent. This is kept so that it can pass messages up to its parent if either it or its children change. The second is a pointer to the CPPTree to which the node belongs. This effectively lets the node inform the tree directly if it changes (kind of like going over your boss’ head to the CEO). Lastly, CPPTreeNode keeps a pointer to an object which contains node-specific data, and a flag indicating whether or not the node owns (and therefore is responsible for disposing of) that object.

Why, you may ask, did I choose to have each node track a separate object instead of letting them track their own specific data and information about drawing it? Primarily to preserve modularity and provide for object reuse. By way of example, if I wanted a node which displays pictures, I could put all the picture-specific retrieving, sizing, and drawing functions inside the node. This would contaminate the object by mixing information about two completely different tasks - fiddling with pictures and being a node in a tree. If I instead create an object which knows all about pictures and let the node manage that object I win in two ways: 1) I can preserve the modularity of both the node and the picture objects, and 2) I can use the picture object anywhere else in my program without dragging along all the baggage needed to maintain tree information (and vice versa).

Enough about the data; let’s quickly review the methods which CPPTreeNode offers. The first significant method is TellParent which lets the node pass a message to its parent (if any). This method is used heavily in the subclass of CPPTreeNode which handles the display of the node. NthChild is used to return a pointer to one of the children of the current node. AddNode and InsertNode let you add a child either to the end or middle of the node’s list of children. InsertParent lets you insert a node between your parent and yourself (I know it sounds odd, but it is nice to have around sometimes). RemoveChild detaches the specified child and its subtree from the parent without deleting the subtree. SwitchParents lets you move a subtree from one parent to another in one step. FamilyDepth gives the number of levels in the node’s subtree; calling FamilyDepth on the top node of the tree will give you the same result as CPPTree::Depth. GetNodeData and SetNodeData let you retrieve and change the data held by the node. GetFamilyBounds is a virtual method which doesn’t do anything in CPPTreeNode.

Finally there are four class methods - DeleteNode, DeleteFamily, ClearFamily, and FamilySize. DeleteNode deletes the passed-in node, but adds all of its children to the node’s parent. DeleteFamily deletes the passed-in node and its entire subtree. These two methods should be called to get rid of structures which are being displayed on the screen. ClearFamily performs the same function as DeleteFamily, but assumes that you are deleting a structure which is not being displayed. The last routine - FamilySize - simply returns the number of nodes in the passed-in subtree.

Two more useful functions defined in CPPVisualTreeNode.h are ApplyToFamily and BApplyToFamily - shown below:

void  ApplyToFamily (CPPTreeNode *familyHead, ApplyProc theProc, 
      long param);
Boolean BApplyToFamily (CPPTreeNode *familyHead, BApplyProc theProc, 

 long param);

These routines let you do a postorder traversal of the subtree whose head is passed in familyHead, applying a routine which accepts a long parameter to each node it encounters. Using these routines saves you the trouble of having to write code to traverse subtrees yourself. For example, the FamilySize routine is implemented in the following way:

long  CPPTreeNode::FamilySize (CPPTreeNode *theNode)
{
 long count = 0;
 if (theNode)
 ApplyToFamily (theNode, CountChildren, (long)(&count));
 return count;
}

void  CountChildren (CPPTreeNode *theNode, long param)
{
 (*((long *)param))++;
}

CPPVisualTree

CPPVisualTree is the class which deals with displaying trees on the screen. To save space here, its interface - considerably more complex than that of its superclass - is shown at the end of the article. To support the last five features from our feature list, it defines the following variables:

 orientStyleorientation;
 justStylejustification;
 short  branchLength;
 short  nodeMargin;
 joinTypeswhichJoin;

Orientation determines the orientation in which the tree is drawn. It can have one of four values: kTopDown, kBottomUp, kLeft2Right, and kRight2Left. Justification determines how nodes are placed over their children. It can have one of five values: kJustCenter, kJustRight, kJustLeft, kJustTop, and kJustBottom. kJustTop and kJustRight are equivalent, as are kJustBottom and kJustLeft; the different name is included for readability since its hard to imagine what right justification means in a horizontally oriented tree. BranchLength determines the minimum distance between a child and its parent, and nodeMargin determines the minimum distance between sibling nodes.

WhichJoin determines how lines are drawn between nodes. It has three predefined settings - kRightAngle (which is the style used in the examples), kPointToPoint (which simply draws lines directly from a parent to its children), and kNone (which results in no lines being drawn at all). CPPVisualTree’s protected methods DrawPoint2Point, and DrawRightAngle handle drawing the first two kinds of joins for you. You can add other kinds of joins by either adding constants and methods to CPPVisualTree or subclassing the DrawJoin method in the visual tree node class. More on that later.

CPPVisualTree has one accessor and one setter method for each of the variables defined above. The setter methods (one of which is shown below) all have a similar structure - differing predictably in lines 1 and 5:

1void CPPVisualTree::SetBranchLength (short newLength)
 {
2if (this->branchLength != newLength)
   {
3  this->Prepare(this);
4CPPTree::BroadcastMessage (kEraseFamily, (void *)TRUE);
5this->branchLength = newLength;
6CPPTree::BroadcastMessage (kResizeFamily, NULL);
7CPPTree::BroadcastMessage (kDrawFamily, (void *)TRUE);
8this->Restore(this);
   }
 }

Line 2 tests to see if the new setting and the old are, indeed, different. If so, it calls Prepare which sets up the grafport so that the tree can draw properly. It then uses BroadcastMessage to erase the tree, changes the old setting, then calls it again to tell the tree to resize and draw itself before restoring the drawing environment.

A short note on Prepare and Restore. The object which is passed to them is used as a sort of key so that Prepare will not actually set up the drawing environment more than once when a tree is drawn. Whenever a node is drawn it first calls Prepare, draws itself, then calls Restore. This is because we cannot guarantee that the tree’s window is the front window when a node is added or deleted. Whenever Prepare is called it first checks the class variable isPrepared to see if the grafport is already set up. If it isn’t, it saves a reference to the object in the variable preparedBy, saves the current grafport in the variable SavePort, and sets the current port to the window where the tree lives. When Restore is called, it checks the passed-in object against the one in preparedBy, and, if they are identical, restores the drawing environment in SavePort. Make sense? If not, don’t worry - we’ll see more about how this mechanism is used later. Two protected virtual methods - UserSpecificPrepare and UserSpecificRestore let your tree class do any special setup which might be necessary for the tree’s grafport.

Five methods are provided for dealing with the display of the tree. The first, ForceRedraw, causes the entire tree to draw itself (after optionally erasing itself). The second, ForceResize, causes all of the nodes to recalculate their sizes and positions. You can ask this method to explicitly erase the whole tree and then draw it afterwards. The third method, ForceMove, causes the entire tree to move to a new location. When a CPPVisualTree object is created, you pass it a point to use as its top left corner; ForceMove changes this top left corner and causes all of the nodes to reposition themselves accordingly. The fourth method, DrawAllJoins, causes all of the joins in the tree to be drawn or erased, depending on a boolean which you pass in. The last method is used to draw the tree in response to an update event, and is called (rather predictably) Draw.

Since CPPVisualTree is intended for use with dynamically modifiable trees, two methods - DoTreeClick and DoCommand - are provided for responding to user input. Passing an event record to DoTreeClick will handle all click/drag-selection of nodes within the tree. DoCommand is provided to let you respond to commands like Cut, Copy, Paste, Clear, etc. although currently only Clear is implemented.

CPPVisualTreeNode

CPPVisualTreeNode is the base class for all nodes which appear in visual trees. Rather than have it be merely a virtual base class, I set it up to implement algorithm ER which, despite its shortcomings, is perfectly adequate as a default positioning routine. Its interface is also quite lengthy, and is provided for your perusal at the end of this article. Following is a discussion of its key features.

A node and its subtree can be described by four (yes, four!) overlapping rectangles, each of which is a class variable. A diagram of these rectangles is shown in Figure 4.

Figure 4. Rectangles used to describe A’s subtree

NodeRect is the smallest rectangle which encompasses the current node. gChildRect is the smallest rectangle which encompasses all of its immediate children. FamilyRect is the smallest rectangle which encompasses the entire subtree of which A is the head, and ChildRect is the smallest rectangle which encompasses the FamilyRect’s of A’s immediate children. If you look back at Figure 1, you can see that the rectangles which ER uses to position subtrees correspond to the FamilyRect frame in Figure 4. No coincidence! These four rectangles are defined by a method called DoCalcFamilyBounds which is actually the heart of the implementation of algorithm ER. I’m not going to go into a discussion of this method, except to point out the parts that implement the “draw only when necessary” feature, since the C code is a fairly straightforward implementation of the pseudo-code.

CPPVisualTreeNode also stores three points - nodeSize, childSize, and familySize, which track the horizontal and vertical extents of the rectangles described above. These extents are filled in by a method called CalcFamilySize which is always called before CalcFamilyBounds. The reason for this is that all of the extents can be computed without having to know exactly where the frames go. We’ll get into more depth on how CalcFamilyBounds and CalcFamilySize work together in a minute.

But first, let’s quickly go over the routines which the node uses to draw itself and its subtrees. CPPVisualTreeNode has five routines corresponding to the accessor routines from CPPVisualTree (GetOrientation, etc.) which simply call the tree’s accessor routines through the Root field of CPPTreeNode. These are used to get the orientation/justification information which ER uses to position everything. There are two routines - DrawJoin and EraseJoin which draw and erase the line between a node and its children. Currently they both call CPPVisualTree’s DrawDefaultJoin method, but they can be overridden to provide any kind of custom join you want. Associated with DrawJoin and EraseJoin is a routine called GetAnchorPoints which returns the points on the left, right, top, and bottom of the node where joins are to be drawn to and from. Currently these points are calculated as the centers of each side of the node.

Two more routines - DrawNode and EraseNode - set up the drawing environment for the tree, then draw or erase either the single node or its entire subtree. A virtual routine called DrawNodeData (which you have to provide the guts for) does the actual drawing of the special data held by the node. Another virtual routine which you have to provide the guts for is CalcNodeSize, which should figure out how big the node’s data is and store it’s extent in the nodeSize variable.

We are now ready to talk about how the “redraw when necessary” feature is implemented for the operations we want to perform on our tree. You will notice three variables - needsResize, needsMove, and needsDraw - and one method - CanDraw - in CPPVisualTreeNode’s interface. These flags are used to keep nodes which do not need to be resized, moved, or drawn from passing through CalcNodeSize, CalcFamilyBounds, and DrawNode. This lets us be even more efficient, since it reduces unnecessary size and boundary calculations as well as unnecessary drawing. Whenever a node passes through ER, needsResize and needsMove are set to FALSE, and needsDraw is set to TRUE only if the node has actually moved. From this point on, no node is moved or resized unless one of the first two flags is explicitly set to TRUE.

But where do they get set to TRUE? Glad you asked. They get set in CPPVisualTreeNode’s ReceiveMessage method, shown below.

 void CPPVisualTreeNode::ReceiveMessage (CPPGossipMonger *toldBy, 
 short reason, void* info)
 {
 Point  oldTopLeft = {this->familyRect.top,
 this->familyRect.left};
 Rect oldFamilyRect = this->familyRect;
 Point  OldFamilySize = this->familySize,
 OldChildSize = this->childSize, 
 OldNodeSize = this->nodeSize;
 BooleanchildChanged, familyChanged;
 RgnHandleRgn1, Rgn2;
 static short  timesCalled = 0;  // tracks recursion
 
 switch (reason) {
 case kEraseFamily :
 EraseNode ((Boolean)info);
 break;
 
 case kDrawFamily:
 DrawNode ((Boolean)info, TRUE);
 break;
 
 case kResizeFamily:
 ResizeFamily (TRUE);
 if (this->Root)
   ((CPPVisualTree *)this->Root)->AdjustTree();
 break;
 
 case kMoveFamily:
 MoveFamily ((Point *)info);
 if (this->Root)
   ((CPPVisualTree *)this->Root)->AdjustTree();
 break;
 
 case kPrepareRemove :
 case kPrepareDelete :
 ((CPPVisualTreeNode *)info)->EraseNode(TRUE);
 ApplyToFamily((CPPVisualTreeNode *)info, 
 SetNotYetPlaced, TRUE);
 break;
 
 case kChildRemoved:
 case kChildDeleted:
 case kNodeAdded : 
 case kNodeChangedData :
1timesCalled++;
2if (timesCalled == 1)
3  if (this->Root)
4    ((CPPVisualTree *)this->Root)->
 Prepare((CPPObject *)1313L);
 
5this->needsResize = TRUE;
6this->needsMove = TRUE;
7CalcFamilySize();
8CalcFamilyBounds (oldTopLeft);    
9if (info)
10   this->needsDraw = TRUE;

11 if (this->Parent && !EqualRect(&oldFamilyRect,
  &this->familyRect))
12   TellParent (reason, NULL);

13 if (this->needsDraw)
   {
14    this->DrawNode(TRUE, FALSE);
15    if (this->Root)
16       ((CPPVisualTree *)this->Root)->
 DrawAllJoins(TRUE);
17    if ((OldFamilySize.h > this->familySize.h) || 
  (OldFamilySize.v > this->familySize.v))
     {
18      Rgn1 = NewRgn();
19      Rgn2 = NewRgn();
20      RectRgn(Rgn1, &oldFamilyRect);
21      RectRgn(Rgn2, &this->familyRect);
22      XorRgn (Rgn1, Rgn2, Rgn1);
23      EraseRgn (Rgn1);
24      DisposeRgn(Rgn1);
25      DisposeRgn(Rgn2);
     }
26    if (this->Root)
27   ((CPPVisualTree *)this->Root)->AdjustTree();
   }
   
28 timesCalled--;
29 if (timesCalled == 0)
30   if (this->Root)
31 ((CPPVisualTree *)this->Root)->
 Restore((CPPObject *)1313L);
 break;
 
 default:
 CPPTreeNode::ReceiveMessage (toldBy, reason, info);
 break;
 }
 }

Remember when we talked about ReceiveMessage back in the discussion of CPPTree? Whenever we call a method in CPPTreeNode corresponding to one of the six operations (InsertNode, RemoveChild, etc.) it uses ReceiveMessage to tell the visual display to update. The implementation of InsertNode is shown below as an example.

 void CPPTreeNode::InsertNode (CPPTreeNode *NewNode, 
 long insertWhere) {
 if (NewNode) {
   NewNode->Parent = this;
   ApplyToFamily (NewNode, SetRoot, (long)this->Root);
   InsertItem (NewNode, insertWhere);
   this->ReceiveMessage (this, kNodeAdded, (void *)NewNode);
 }
 }

The sixth case in ReceiveMessage is the code segment we are really interested in. This is the heart of the “redraw when necessary” technique. You will notice that it gets called whenever a node is inserted, deleted, removed, or when the node’s contents change. When you consider that operations 3 and 4 (insert parent, delete & promote children) use operations 1, 2, and 4, you can see that this bit of code gets called eventually for every one of the six operations we support on trees.

So how does this piece of code work? Well, let’s consider the case where we want to add a child to node “Two” in the tree shown below.

Figure 5. Before and After inserting a node into the tree

When InsertNode calls ReceiveMessage, lines 1-4 will cause timesCalled to be set to 1, and will prepare the tree’s port for drawing. Notice that we pass it a bogus value (1313) so that the port will not get prematurely restored when we actually draw the nodes in the tree. Lines 5 and 6 then note that the parent must be resized and may need to move. The child, recall, having just been added, is already marked as needing to be resized, moved, and drawn. Line 7 calls CalcFamilySize on the subtree whose root is “two”. CalcFamilySize will calculate all of the extents for node “five” and then modify the extents for node “two.” In the process it will set their needsResize flags to FALSE. Note that node “four” will not have its extents recalculated, since it’s needsResize flag is still FALSE.

At this point, line 8 runs algorithm ER on node “two”, causing all three nodes to have their bounds recalculated. An addition to the ER algorithm, shown below, considers each node as it comes out of the recursion.

if (!EqualRect (&OldNodeRect, &newNodeRect))
  {
   if (!EqualRect (&emptyRect, &OldNodeRect))
     EraseNode (FALSE);
    this->needsDraw = eraseKidJoins = TRUE;
  }
else  // if the node’s children have moved, redraw it too
if (Just != kJustCenter)
  {
   if ((Orient == kBottomUp) || (Orient == kTopDown))
     {
      if (OldGChildRect.right - OldGChildRect.left != 
        newGChildRect.right - newGChildRect.left)
        this->needsDraw = eraseKidJoins = TRUE;
     }
   else
     {
      if (OldGChildRect.bottom - OldGChildRect.top != 
        newGChildRect.bottom - newGChildRect.top)
        this->needsDraw =  eraseKidJoins = TRUE;
     }
  }
if (eraseKidJoins)
  for (i = 1; i <= this->numItems; i++)
    EraseJoin (this, (CPPVisualTreeNode *)NthChild(i));

In this code segment, the node’s new node rectangle is compared to its old one. If either the node or its children have moved, the node and its join to its parent are erased, and the node is marked as needing to be redrawn. If necessary the joins between the parent and its children are then erased.

When we pop out to lines 9 and 10 of ReceiveMessage, we set needsDraw to TRUE if the node we are considering was the one to which the message was passed; this is so that even if the addition of the child did not cause the node to move, it will redraw itself and the child which was added. Line 11 then checks to see if the node moved as a result of the child being added. If it did, it will probably cause its parent to move, so line 12 passes the kNodeAdded message to that node’s parent. This process repeats itself until it reaches a node which does not move, or until it reaches the root. At each stage, the nodes which move and the lines which connect them to their children are erased by the special segment shown above.

When we finally reach the root or a nonmoving node, the recursion stops and we reach line 13. If the node needs to be drawn, line 14 draws not only that node, but the entire subtree which it is the head of. This will cause all of the nodes which have been erased and marked as needing to be drawn to draw themselves and their joins. At this point, there are no nodes in the tree which are marked as needing to be drawn. Lines 15 and 16 will then force all of the joins in the entire tree to be redrawn - admittedly this is overkill, but the cost in terms of time is practically negligible, and it makes the code much simpler.

Lines 17-25 are executed only when the tree shrinks in size, and makes sure that there are no remains of the old tree lurking about on the screen. Finally the node calls AdjustTree (I will discuss the point of this routine later). It is clear that lines 14-27 will only be executed once for each operation, since once the tree is drawn, no other nodes need to be drawn. We will then step out of the recursion until we reach the top level, where lines 29-31 will restore the drawing environment to what it was before the operation started.

Now let’s tackle AdjustTree. It is possible, during ER’s execution, for some of the nodes to be given negative positions - especially in the bottom-up and right-to-left orientations. Consider a bottom-up tree which has just had a child added to its topmost node. The new node’s top left corner will be given a position of branchLength + the node’s height, which is clearly at some negative vertical coordinate, if it’s parent’s top left corner was at x,0. AdjustTree, shown below, simply gets the bounding rectangle of the root of the tree, checks to see if its top-left corner matches the desired top left corner of the tree, and, if it does not, forces it to move over.

 void CPPVisualTree::AdjustTree (void)
 {
 Rect tempRect;
 if (this->topNode)
   topNode->GetFamilyBounds (&tempRect);       
 if ((tempRect.left != this->topLeft.h) ||
     (tempRect.top != this->topLeft.v))
   ForceMove (TRUE, this->topLeft);
 }

One last piece of magic remains. You may have noticed that while it is the routine DoCalcFamilyBounds which performs algorithm ER, ReceiveMessage calls a glue routine named CalcFamilyBounds. The code for this routine is shown below.

void  CPPVisualTreeNode::CalcFamilyBounds (Point TopLeftCorner)
{
 short  deltaH = TopLeftCorner.h - this->familyRect.left,
 deltaV = TopLeftCorner.v - this->familyRect.top;
 Point  TopRight = {this->familyRect.top + deltaV, 
 this->familyRect.right + deltaH},
 BottomLeft = {this->familyRect.bottom + deltaV, 
 this->familyRect.left + deltaH};
 if (!this->needsMove) return;
 this->needsMove = FALSE;
 switch (GetOrientation()) {
 case kTopDown:
 case kLeft2Right :
 DoCalcFamilyBounds (TopLeftCorner);
 break;
 case kBottomUp:
 DoCalcFamilyBounds (BottomLeft);
 break;
 case kRight2Left:
 DoCalcFamilyBounds (TopRight);
 break;
 }
}

When we discussed the pseudo-code for algorithm ER we mentioned that one of the parameters we passed into the algorithm was the top left corner of the family. When we are drawing a tree which is oriented from bottom to top or from right to left, however, calculations are done a little differently. In a top-down or left-to-right tree we compute a node’s rectangle by adding the node height to the top left corner. When we are computing the node’s rectangle in a bottom-up tree, it simplifies the computation in ER to assume that we are given the bottom left corner and can subtract the height from that point to get the top left corner. Similarly, when we are drawing right-to-left, it is simpler to assume that we are given the top right corner and can subtract the width of the node in order to get the top left corner. The glue code in CalcFamilyBounds manufactures the top right and bottom left points for these two cases, then calls DoCalcFamilyBounds to run algorithm ER on the subtree. Once the point is passed in, its sense (ie. is it the top-left, bottom-left, top-right corner) remains the same until ER exits.

That’s all the magic there is, folks. By erasing and redrawing only the nodes which move, we satisfy our minimum redraw restriction and also minimize the number of times in which a node’s width and boundaries have to be recalculated.

Like CPPVisualTree, CPPVisualTreeNode has a few routines to handle direct-manipulation by the user. DoDoubleClick and DoSingleClick are virtual functions which you can customize to perform some action when the user double or single clicks on a node. DoOnFamilyInRect lets you perform some action if a node is partially or fully inside a specified rectangle. This is useful for setting the class’ isSelected field to TRUE if it is inside a selection rectangle. The PointInNode method lets you do hit detection within a family; calling this method for the root of a tree will return a reference to any node which was clicked on in the entire tree.

CPPPackedTreeNode

There is one class remaining - the one which implements algorithm SG. Actually it implements SG+, since it makes a second pass through the tree to make sure that all of the childless nodes are properly centered between nodes with children on either side of them. Figure 6 provides a comparison of output produced by algorithm SG and SG+; note that the inverted node is properly centered by SG+, but not by SG.

Figure 6. Comparison of SG and SG+

CPPPackedTreeNode is subclassed off of CPPVisualTreeNode. This means that it can take advantage of all the direct-manipulation, selection, etc. methods which CPPVisualTreeNode defines and only redefine the methods which receive messages and do the size and boundary calculations, as shown in its definition below.

class CPPPackedTreeNode : public CPPVisualTreeNode {
 friend class CPPVisualTree;
public:
 CPPPackedTreeNode (CPPObject *NodeData, CPPTree *BelongsTo, 
    Boolean becomeOwner, Boolean selected);
 ~CPPPackedTreeNode (void);
 virtualchar *ClassName (void);
 virtualBoolean  Member (char *className);
 virtual CPPObject *Clone(void);

 virtualvoidEraseNode (Boolean wholeFamily);
 virtualvoidReceiveMessage (CPPGossipMonger *toldBy, 
 short reason, void* info);
protected:
 Point  estTopLeft;

 virtualvoid   DoCalcFamilySize(void);
 virtualvoid   DoCalcFamilyBounds (Point TopLeftCorner);
 void   CPBRightTraverse (short level, short levelOffset);
 void   CPBLeftTraverse (short level, short levelOffset);
 void   CPBTopTraverse (short level, short levelOffset);
 void   CPBBottomTraverse (short level, short levelOffset);
 void   PostProcess (Boolean isVertical);
private:
 void   ShiftNode (Point newTopLeft);
};

CPPPackedTreeNode also overrides EraseNode. In CPPVisualTreeNode the separation between subtrees allowed us to erase a node’s family by simply erasing the node’s FamilyRect, but since subtrees can be ‘pushed together’ by SG, we have to take a more sophisticated approach - explicitly traversing the whole subtree and erasing each node individually.

CPPPackedTreeNode defines one new variable - estTopLeft - and defines six new methods - all protected or private. The four CPBxxxTraverse methods implement the SG algorithm for each different orientation, and so essentially take the place of CalcFamilyBounds in CPPVisualTreeNode. Why four instead of one? Because the calculations in SG are sufficiently involved that a single routine would very long and therefore very hard to follow. The PostProcess routine performs the “+” part of SG+ - making sure that the nodes at each level of the subtree are properly centered. PostProcess is called after DoCalcFamilyBounds positions the entire subtree. PostProcess calls ShiftNode, which simply erase a node and its join, moves it over, and redraws it. If many nodes have to be centered in this way, there is a loss of efficiency, since each one will have to be drawn twice; the price we pay for aesthetics.

Looking at the key segment of code for ReceiveMessage (shown below), shows that it is much simpler than the one in the CPPVisualTreeNode class.

 case kNodeAdded :
 case kNodeChangedData :
 case kChildDeleted:
 case kChildRemoved: 
1if (this->Root)
   {
2    ((CPPVisualTree *)this->Root)->
 Prepare((CPPObject *)1313L);
3((CPPVisualTree *)this->Root)->ForceResize (FALSE);
4  topNode->DrawNode(TRUE, FALSE);
5    ((CPPVisualTree *)this->Root)->DrawAllJoins(TRUE);
6  if ((OldFamilySize.h > topNode->familySize.h) || 
  (OldFamilySize.v > topNode->familySize.v))
     {
7     Rgn1 = NewRgn();
8     Rgn2 = NewRgn();
9     RectRgn(Rgn1, &oldFamilyRect);
10      RectRgn(Rgn2, &topNode->familyRect);
11      XorRgn (Rgn1, Rgn2, Rgn1);
12      EraseRgn (Rgn1);
13      DisposeRgn(Rgn1);
14      DisposeRgn(Rgn2);
     }
15    ((CPPVisualTree *)this->Root)->AdjustTree();
16 ((CPPVisualTree *)this->Root)->
 Restore((CPPObject *)1313L);
   }
 break;

The packed tree node class does not use recursion to limit the number of size and frame calculations as the visual tree node class does, since changes in one node can have effects on other nodes which are at the same level but in entirely different subtrees. Instead, after setting up the drawing environment in line 2, it calls ForceResize in line 3 which sets the needsMove and needsResize flags to true and calls CalcFamilySize and CalcFamilyBounds on the entire tree. As before, if any nodes move as a result, they erase themselves, their joins, and the joins of their siblings. Once everyone has recalculated their frames and extents, line 4 tells the topmost node to draw its entire family - which passes the ‘draw’ message to every node. The “redraw when necessary” criterion is preserved, however, because the needsDraw flag (which will be set to false in any node which did not move) prevents them from being drawn again. Lines 6-15 then perform the same functions as lines 13-27 in the visual tree node’s ReceiveMessage method.

Guess what? We’ve finished talking about CPPPackedTreeNode; simple, eh? I won’t go over the code which implements algorithm SG, since, as before, it follows fairly logically from the pseudo-code.

In Conclusion

That’s all folks. Hopefully the discussion of tree-drawing algorithms has helped clarify things for those of you who have wondered how it’s done. I’ve spent a lot of time getting these classes as bug-free and generally useful as possible, so if anyone finds any bugs, or finds a way to add functionality to them, please snail/e-mail me and let me know. For those of you who are still wondering how they can use all the options which these classes provide, let me suggest the following:

• Top-Down or Left-to-Right orientations:

Great for displaying linguistic parse trees, hierarchical search spaces, computer directory structures, and corporate org. charts (not to mention all those juicy tree-based data structures!)

• Bottom-Up orientation:

Family trees

• Right-to-Left orientation:

Match-trees for sports competitions

Now, let’s see what you can come up with!

Related Articles

Moen, Sven, Drawing Dynamic Trees, Technical report from the Department of Information and Computer Science, Linköping University, Sweden.

Radack, Gerald M., Tidy Drawing of m-ary Trees, Case Western Reserve University, November 1988.

Reingold, Edward M. and Tilford, John S., “Tidier Drawing of Trees”, IEEE Transactions on Software Engineering, Vol. SE-7, No. 2, March 1981.

Tilford, John S., Tree Drawing Algorithms, Master’s Thesis, University of Illinois at Urbana-Champaign, 1981.

Wetherell, Charles and Shannon, Alfred, “Tidy Drawing of Trees”, IEEE Transactions on Software Engineering, Vol. SE-5, No. 5, September, 1979.

Interface of the CPPVisualTree class

class CPPVisualTree : public CPPTree {
public:
 CPPObject*lastClicked;
 BooleanforceDraw;
 
 CPPVisualTree (WindowPtr itsWindow, 
    Point  newTopLeft,
    orientStyle orientation = kTopDown,
    justStyle justification = kJustCenter,
    joinTypes join = kRightAngle,
    short branchLength = 25);
 ~CPPVisualTree (void);
 
 virtualBoolean  Member (char *className);

 virtualchar *ClassName (void);
 
 void Prepare (CPPObject *caller);
 void Restore (CPPObject *caller);
 
 void ForceRedraw (Boolean doErase);
 void ForceResize (Boolean doDraw);
 void DrawAllJoins (Boolean doDraw);
 void ForceMove (Boolean doDraw, Point topLeft);
 void AdjustTree (void);
 
 void DrawDefaultJoin (CPPVisualTreeNode *FromNode, 
  CPPVisualTreeNode *ToNode);

 void SetOrientation (orientStyle newOrient);
 void SetJustification (justStyle newJust);
 void SetJoinType (joinTypes newJoin);
 void SetBranchLength (short newLength);
 void SetNodeMargin (short newMargin);

 inline orientStyleGetOrientation (void) { return 
 this->orientation;}
 inline justStyleGetJustification (void) { return 
 this->justification;}
 inline joinTypesGetJoinType (void) { return 
 this->whichJoin;}
 inline short    GetBranchLength (void) { return 
 this->branchLength;}
 inline short    GetNodeMargin (void) { return                 
 this->nodeMargin;}
 
 virtualvoidDraw (void);

 virtualBoolean  DoCommand (short commandID);

 virtualBoolean  DoTreeClick (EventRecord *theEvent);
 virtualvoidDoCut (void);
 virtualvoidDoCopy (void);
 virtualvoidDoPaste (void);
 virtualvoidDoClear (void);
 virtualvoidDoSelectAll (void);

 void GetTreeBounds (Rect *itsBounds);
 PicHandleGetTreePicture (Boolean asQDPICT, 
 Boolean placeInClipboard);
 
protected:
 WindowPtrtheWindow;
 Point  topLeft;
 
 BooleanisPrepared;
 CPPObject  *preparedBy;
 GrafPtrSavePort;

 long   lastClickTime;
 
 orientStyleorientation;
 justStylejustification;
 joinTypeswhichJoin;
 short  branchLength;
 short  nodeMargin;

 virtualvoidUserSpecificPrepare (void);
 virtualvoidUserSpecificRestore (void);
 virtualvoidDrawPoint2Point (Point FromPt, Point ToPt);
 virtualvoidDrawRightAngle (Point FromPt, Point ToPt, 
 orientStyle orientation);

};

Interface of the CPPVisualTreeNode class.

class CPPVisualTreeNode : public CPPTreeNode {
 friend class CPPVisualTree;
public:
 BooleanneedsResize;
 BooleanneedsMove;
 BooleanneedsDraw;
 BooleannotYetPlaced;
 
 CPPVisualTreeNode (CPPObject *NodeData, CPPTree *BelongsTo, 
    Boolean becomeOwner, Boolean selected);
 ~CPPVisualTreeNode (void);
 
 virtualchar *ClassName (void);
 virtualBoolean  Member (char *className);
 
 virtual CPPObject *Clone(void);

 virtualvoidDrawJoin (CPPVisualTreeNode *FromNode,
   CPPVisualTreeNode *ToNode);
 virtualvoidEraseJoin (CPPVisualTreeNode *FromNode,
   CPPVisualTreeNode *ToNode);
 virtualvoidDrawNodeData (void);
 
 void DrawNode (Boolean wholeFamily, Boolean forceDraw);
 virtualvoidEraseNode (Boolean wholeFamily);
 void ResizeFamily (Boolean wholeFamily);
 void MoveFamily (Point *topLeft);
 
 virtualvoidCalcNodeSize (void);   
 void   CalcFamilySize(void);
 void   CalcFamilyBounds(Point TopLeftCorner);
 
 static longNumSelectedNodes (CPPVisualTreeNode *theNode);

 BooleanCanDraw (void);

 inline Boolean  IsSelected (void) {return this->isSelected;}
 void SetSelect (short selectType, 
 Boolean selectFamily,Boolean doRedraw);
 
 void GetAnchorPoints (Point *Left, Point *Right, 
   Point *Top, Point *Bottom);
 
 virtualvoidReceiveMessage (CPPGossipMonger *toldBy, 
 short reason, void* info);
 virtualvoidGetFamilyBounds (Rect *bounds);
 
 CPPVisualTreeNode *PointInNode (Point clickPt);

 void DoOnFamilyInRect (Rect *theRect, 
 Boolean fullyInside, ApplyProc theProc, long param);
 
 virtualvoidDoDoubleClick (short modifiers);
 virtualvoidDoSingleClick (short modifiers);
 
protected:
 BooleanisSelected;
 Point  nodeSize,
 childSize,
 familySize;
 Rect   nodeRect,// the rectangle surrounding the node
 childRect, // surrounds the node’s immediate children
 gChildRect,// surrounds all of the node’s descendants
 familyRect;// surrounds the node & all its descendants
 
 virtualvoid     DoCalcFamilySize(void);
 virtualvoid     DoCalcFamilyBounds (Point TopLeftCorner);
 
 short  GetNodeMargin (void);
 orientStyleGetOrientation (void);
 justStyleGetJustification (void);
 joinTypesGetJoinType (void);
 short  GetBranchLength (void);
};