OKlibrary  0.2.1.6
ReingoldTilford.mac
Go to the documentation of this file.
00001 /* Rui Wang, 28.9.2009 (Swansea) */
00002 /* Copyright 2009 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_include("OKlib/ComputerAlgebra/Trees/Lisp/Basics.mac")$
00023 
00024 
00025 /* ******************************
00026    * Reingold-Tilford algorithm *
00027    ******************************
00028 */
00029 
00030 /* Produce a binary labelled rooted tree with 2-dimensional coordinates from a
00031    binary unlabelled rooted tree T with specified root coordinates x, y:
00032    Reingold-Tilford: 
00033           {reingold_tilford_rt(T,p)|T=[T_1, ..., T_n],p=[x,y]}
00034           Base case: If T consists of a single node, the coordinates of the 
00035                      single node is defined equal to p.
00036           Divide   : Recursively apply the algorithm to each subtree of T.
00037           Conquer  : 1. Make the distance 1 or 2 between the right most node of
00038                         the left subtree and the left most node of the right
00039                         subtree.
00040                      2. Make the root r of T one unit higher than and 
00041                         horizontally half way between its children.
00042                         If r has only one subtree, say the left one, then place
00043                         r at horizontal distance 1 to the right of its left
00044                         child.      
00045    Input: A binary unlabelled rooted tree T which is recursively defined as a 
00046           list [T_1, ..., T_n], 0 <= n <= 2, where the T_i are the subtrees.
00047           The root coordinates p which is a list [x,y] contains a pair of 
00048           coordinates.
00049    Output: A binary labelled rooted tree with 2-dimensional coordinates, which
00050            is a binary labelled rooted tree, where each label is a list 
00051            containing a list of 2 elements (the coordinates) as first element.
00052 */
00053 /* (A "binary labelled rooted tree" is recursively defined as a list 
00054    [L, T_1, ..., T_n], 0 <= n <= 2, where L is the label, and the T_i are the
00055    subtrees.)
00056 */
00057 reingold_tilford_rt(T,p) := reingold_tilford_remove_annotations(reingold_tilford_annotated(T,p))$
00058 
00059 /* Remove the data regarding the left-most node and right-most node from
00060    the result of reingold_tilford_annotated:
00061    Input: A binary labelled rooted tree with 2-dimensional coordinates, and
00062           the x-coordinates of the left-most node and right-most
00063           node, where each label is a list containing two lists of 2
00064           elements (the coordinates) as first element.
00065           [[[x,y],[xmin,xmax]], ... ]
00066    Output: A binary labelled rooted tree with 2-dimensional coordinates, which
00067            is a binary labelled rooted tree, where each label is a list 
00068            containing a list of 2 elements (the coordinates) as first element. 
00069            [[[x,y],[xmin,xmax]], ... ] -> [[[x,y]], ... ]
00070 */
00071 reingold_tilford_remove_annotations(T) := cons([T[1][1]],map(reingold_tilford_remove_annotations,rest(T)))$
00072 
00073 /* Coordinates computation using Reingold-Tilford algorithm. The input is
00074    an unlabelled rooted tree T with specified root coordinates p which is
00075    defined as a list [x,y].
00076    The function will produce a labelled rooted tree with 2-dimensional 
00077    coordinates. Furthermore, it contains additional data in each node which
00078    are the x-coordinates of the left-most node and the right-most node.
00079 */
00080 reingold_tilford_annotated(T,p) := block(
00081  [left_subtr,right_subtr,offset],
00082   if emptyp(T) then 
00083     [[[p[1],p[2]],[p[1],p[1]]]] else
00084   if length(T) = 2 then (
00085     [left_subtr,right_subtr]:map(reingold_tilford_annotated,
00086                                  T,create_list([p[1],p[2]-1],i,1,length(T))),
00087     offset:(rightmost_x(left_subtr)-x_tdlrt(left_subtr))-(leftmost_x(right_subtr)-x_tdlrt(right_subtr)),
00088     if mod((offset+1),2)=0
00089     then offset:(offset+1)/2
00090     else offset:(offset+2)/2,
00091     left_subtr:trans_lrt(left_subtr,[-offset-x_tdlrt(left_subtr)+p[1],0]),
00092     right_subtr:trans_lrt(right_subtr,[offset-x_tdlrt(right_subtr)+p[1],0]),
00093     cons([[p[1],p[2]],[leftmost_x(left_subtr)-offset,rightmost_x(right_subtr)+offset]],
00094          [left_subtr,right_subtr])
00095   )
00096   else (
00097     [left_subtr]:map(reingold_tilford_annotated,T,[[p[1],p[2]-1]]),
00098     cons([[p[1],p[2]],[leftmost_x(left_subtr),rightmost_x(left_subtr)]],[left_subtr])
00099   )
00100 )$
00101 
00102 /* Access-functions for reingold_tilford_annotated: */
00103 leftmost_x(T) := T[1][2][1]$
00104 rightmost_x(T) := T[1][2][2]$
00105 
00106