OKlibrary  0.2.1.6
ReingoldTilford.hpp File Reference

Plans regarding Reingold-Tilford algorithm in Maxima/Lisp. More...

Go to the source code of this file.


Detailed Description

Plans regarding Reingold-Tilford algorithm in Maxima/Lisp.

Todo:
Create milestones
Todo:
Reingold-Tilford algorithm at abstract level
  • See "Four aesthetic criterions for Reingold-Tilford algorithm" in Visualisation/GraphDrawing/plans/Trees.hpp.
  • Reingold-Tilford algorithm.
    • Input: a binary tree T.
    • Output: a layered drawing of T.
    • Base case: If T consists of a single node, its drawing is trivially defined.
    • Divide: Recursively apply the algorithm to draw the left and right subtrees of T.
    • Conquer:
      1. Move the drawings of the subtrees towards each other until their horizontal distance becomes equal to 2.
      2. Place the root r of T vertically one unit above and horizontally half way between its children.
      3. If r has only one subtree, say the left one, then place r at horizontal distance 1 to the right of its left child.
  • Pseudocode
    • Define a type Tree and type Node.
             Type Tree {
               Tree leftsubtree, rightsubtree;
               Node leftmost, rightmost;
               Node root;
             }
       
             Type Node {
               Integer x, y;
               Integer level;
             }
            
    •        Function Tree RT(Tree T) {
       
              If T.leftsubtree == empty && T.rightsubtree == empty
                 
                 T.leftmost.x=0, T.rightmost.x=0;
                 T.root.x=0, T.root.y=T.root.level;
                 Return T;
              
              Else
                
                T.leftsubtree = RT(T.leftsubtree);
                T.rightsubtree = RT(T.rightsubtree);
       
                tempx = (T.leftsubtree.rightmost.x-T.rightsubtree.leftmost.x+2)/2; 
                T.leftsubtree = Translating(T.leftsubtree, [-tempx-T.leftsubtree.root.x, 0]);
                T.rightsubtree = Translating(T.rightsubtree, [tempx-T.rightsubtree.root.x, 0]);
                T.leftmost.x = T.leftsubtree.leftmost.x - tempx;
                T.rightmost.x = T.rightsubtree.rightmost.x + tempx;
                T.root.x = 0, T.root.y = T.root.level;
       
              Return T;
            }
            
Todo:
The full Reingold-Tilford algorithm
  • First we implement the "abstract" algorithm, which elegantly implements the idea, without taking care of efficiency.
  • Then, additionally, the full algorithm is implemented, which refines the abstract version, making it linear-time. Here now we describe the full version.
  • The Reingold-Tilford algorithm can be simply considered as a recursive algorithm, which consists of two traversals. The first one is a post-order traversal, and the second one is pre-order traversal. The post-order traversal determines the preliminary x coordinate and offset value of each node. Pre-order traversal produces final x coordinates. Y coordinates can be easily defined as same as its level in the tree.
  • Steps of coordinates computation:
    • Post-order traversal, recursively do the following steps from leaves.
      1. If current node is the left child of its parent, its preliminary x coordinate is 0. If current node is the right child of its parent, its preliminary x coordinate is 0 plus the defined minimum distance between two nodes. In the case, the defined minimum distance is 2, so its preliminary x coordinate is 0+2=2.( If the current node is the only one child of its parent, we define it as the left child.)
      2. Set the offset value of each node from leaves to root. The offset is calculated by subtracting the average value of preliminary x coordinates of the children of current node from the preliminary x coordinate of current node. For example, p is the parent of left child l and right child r. The preliminary x coordinates of p, l and r are 2, 0 and 2 respectively so the offset of r is 2-(0+2)/2=1. If current node has only one child (left child), the offset is the preliminary x coordinate of current node minus 1 (1 is the result of the minimum distance 2 divided by 2). The offset of leaves are 0.
      3. In each level, the distance between the right most node of left subtree and left most node of right subtree must be at least 2 which can be determined by rl-lr, which the lr is the preliminary x coordinate of the right most node of left subtree plus the accumulation of all its ancestors in left subtrees, rl is the preliminary x coordinate of the left most node of right subtree plus the accumulation of all its ancestors in right subtrees. If the distance is strictly less than 2, both the preliminary x coordinate and the offset of the root of right subtree need to be plus by 2-(RL-LR). This checking must be performed in each level from the roots of left and right subtree until leaves. The step is performed every time before the post-order traversal go up to a higher level.
    • Pre-order traversal, recursively do the following step from root.
      1. Set the final x coordinate of each node from root by accumulating the offset of all the ancestors of current node, then plus its preliminary x coordinate.
  • An example:
    • Define a tree T: [A, [B,[C,[D]],[E,[F],[G]]], [H,[I],[J,[K],[L]]]], which has 12 nodes.
                 A
               /  \
               B   H 
              /\   /\
             C E  I J
            / /\   /\ 
           D F G  K L
           
      • Post-order traversal, order D,C,F,G,E,B,I,K,L,J,H,A
        1. D is a leaf and left child, thus its preliminary x coordinate is 0, offset is 0.
        2. C is a left child and the parent of D, so its preliminary x coordinate is 0, because D is the only one child of C, so the offset of C is 0-1=-1.
        3. F is the same as D, so px=0, offset=0, px is used to indicate the preliminary x coordinate, it will be used in all of the following example.
        4. G is the right child of E, so px=0+2=2, offset=0.
        5. E is the right child of C, and the parent of F and G, so px=0+2=2, offset=2-(0+2)/2=1.
        6. Determine the separation between the right most node of left subtree and the left most node of right subtree in same level, in the case, they are D and F .So use the method given above to calculate the distance between the two nodes, (0+1)-(0+(-1))=2, thus no further move needed.
        7. B px=0, offset=0-(0+2)/2=-1.
        8. I, K px=0, offset=0.
        9. L px=0+2=2, offset=0.
        10. J px=0+2=2, offset=2-(0+2)/2=1.
        11. I doesn't have any child, so we don't need perform the distance check between the two subtrees of H.
        12. H px=0+2=2, offset=2-(0+2)/2=1.
        13. Check the separation of E and I, (0+1)-(2+(-1))=0<2. So the px and offset of H, which is the root of the subtree, need to be added by 2-0=2.
        14. Updated H, px=2+2=4, offset=1+2=3.
        15. Go down the lower level of subtrees to check the separation of G and K, (0+1+3)-(2+(-1)+1)=2.
        16. It's the bottom of subtrees, so checking is completed.
        17. A px=0, offset=0-(0+4)/2=-2.
        18. Now, post-order traversal is finished.
      • Pre-order traversal, order A,B,C,D,E,F,G,H,I,J,K,L
        1. A x=0, x indicates x coordinates, the followings are the same meaning.
        2. B x=0+(-2)=-2.
        3. C x=0+(-2)+(-1)=-3.
        4. D x=0+(-2)+(-1)+(-1)=-4.
        5. E x=2+(-2)+(-1)=-1.
        6. F x=0+(-2)+(-1)+1=-2.
        7. G x=2+(-2)+(-1)+1=0.
        8. H x=4+(-2)=2.
        9. I x=0+(-2)+3=1.
        10. J x=2+(-2)+3=3.
        11. K x=0+(-2)+3+1=2.
        12. L x=2+(-2)+3+1=4.
Todo:
Reingold-Tilford algorithm in Maxima.
  • Define a Maxima function reingold_tilford_rt(T,[x,y]) (for the abstract version).
    • Input: An "unlabelled rooted binary tree" T and the coordinates [x, y] of its root.
    • An "unlabelled rooted binary tree" is recursively defined as a list [T_1, ..., T_n], where the T_i are the subtrees and the maximum value of n is 2. (The case n=0, i.e., the empty list, represents the trivial tree.)
    • Output: labelled T with coordinates at each node.
  • Examples:
    • Input: reingold_tilford_rt([], [x,y]); Output: [[x,y]]
    • Input: reingold_tilford_rt([[],[]], [x,y]); Output: [[x,y],[[x-1,y-1]],[[x+1,y-1]]].

Definition in file ReingoldTilford.hpp.