home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 10 / 10.iso / l / l460 / 2.ddi / SPARFUN.DI$ / TREELAYO.M < prev    next >
Encoding:
Text File  |  1993-03-07  |  2.2 KB  |  81 lines
  1. function [x,y,h,s] = treelayout(parent,post)
  2. %TREELAYOUT Lay out a tree or forest.
  3. %    [x,y,h,s] = treelayout(parent,post)
  4. %        parent is the vector of parent pointers, with 0 for a root.
  5. %        post is a postorder permutation on the the tree nodes.
  6. %        (If post is omitted we compute it here.)
  7. %        x and y are vectors of coordinates in the unit square at which 
  8. %        to lay out the nodes of the tree to make a nice picture.
  9. %        Optionally, h is the height of the tree and s is the 
  10. %        number of vertices in the top-level separator.
  11. %
  12. %    See also ETREE, TREEPLOT, ETREEPLOT.
  13.  
  14. %    Copyright (c) 1984-93 by The MathWorks, Inc.
  15.  
  16. % This is based on the C code in sptrees.c by John Gilbert.
  17. % Leaves are spaced evenly on the x axis, and internal
  18. % nodes are centered over their descendant leaves with
  19. % y coordinate proportional to height in the tree.
  20.  
  21. n = max(size(parent));
  22.  
  23. if nargin < 2,
  24.  
  25.     % Create the adjacency matrix A of the given tree,
  26.     % and get the postorder with another call to etree.
  27.  
  28.     j = find(parent);
  29.     A = sparse (parent(j), j, 1, n, n);
  30.     A = A + A' + speye(n,n);
  31.     [ignore, post] = etree(A);
  32.  
  33. end;
  34.  
  35. % Add a dummy root node #n+1, and identify the leaves.
  36.  
  37. parent = rem (parent+n, n+1) + 1;  % change all 0s to n+1s
  38. isaleaf = ones(1,n+1);
  39. isaleaf(parent) = zeros(n,1);
  40.  
  41. % In postorder, compute heights and descendant leaf intervals.
  42. % Space leaves evenly in x (in postorder).
  43.  
  44. xmin = n*ones(1,n+1);
  45. xmax = zeros(1,n+1);
  46. height = zeros(1,n+1);
  47. nkids = zeros(1,n+1);
  48. nleaves = 0;
  49.  
  50. for i = 1:n,
  51.     node = post(i);
  52.     if isaleaf(node),
  53.         nleaves = nleaves+1;
  54.         xmin(node) = nleaves;
  55.         xmax(node) = nleaves;
  56.     end;
  57.     dad = parent(node);
  58.     height(dad) = max (height(dad), height(node)+1);
  59.     xmin(dad)   = min (xmin(dad),   xmin(node));
  60.     xmax(dad)   = max (xmax(dad),   xmax(node));
  61.     nkids(dad)  = nkids(dad)+1;
  62. end;
  63.  
  64. % Compute coordinates, leaving a little space on all sides.
  65.  
  66. treeht = height(n+1) - 1;
  67. deltax = 1/(nleaves+1);
  68. deltay = 1/(treeht+2);
  69. x = deltax * (xmin+xmax)/2;
  70. y = deltay * (height+1);
  71.  
  72. % Omit the dummy node.
  73.  
  74. x = x(1:n);
  75. y = y(1:n);
  76.  
  77. % Return the height and top separator size.
  78.  
  79. h = treeht;
  80. s = n+1 - max(find(nkids~=1));
  81.