octave_packages/m/sparse/treelayout.m

   1 ## Copyright (C) 2008-2012 Ivana Varekova & Radek Salac
   2 ##
   3 ## This file is part of Octave.
   4 ##
   5 ## Octave is free software; you can redistribute it and/or modify it
   6 ## under the terms of the GNU General Public License as published by
   7 ## the Free Software Foundation; either version 3 of the License, or (at
   8 ## your option) any later version.
   9 ##
  10 ## Octave is distributed in the hope that it will be useful, but
  11 ## WITHOUT ANY WARRANTY; without even the implied warranty of
  12 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13 ## General Public License for more details.
  14 ##
  15 ## You should have received a copy of the GNU General Public License
  16 ## along with Octave; see the file COPYING.  If not, see
  17 ## <http://www.gnu.org/licenses/>.
  18
  19 ## -*- texinfo -*-
  20 ## @deftypefn  {Function File} {} treelayout (@var{tree})
  21 ## @deftypefnx {Function File} {} treelayout (@var{tree}, @var{permutation})
  22 ## treelayout lays out a tree or a forest.  The first argument @var{tree} is a
  23 ## vector of
  24 ## predecessors, optional parameter @var{permutation} is an optional postorder
  25 ## permutation.
  26 ## The complexity of the algorithm is O(n) in
  27 ## terms of time and memory requirements.
  28 ## @seealso{etreeplot, gplot, treeplot}
  29 ## @end deftypefn
  30
  31 function [x_coordinate, y_coordinate, height, s] = treelayout (tree, permutation)
  32   if (nargin < 1 || nargin > 2 || nargout > 4)
  33     print_usage ();
  34   elseif (! isvector (tree) || rows (tree) != 1 || ! isnumeric (tree)
  35           ||  any (tree > length (tree)) || any (tree < 0))
  36     error ("treelayout: the first input argument must be a vector of predecessors");
  37   else
  38     ## Make it a row vector.
  39     tree = tree(:)';
  40
  41     ## The count of nodes of the graph.
  42     num_nodes = length (tree);
  43     ## The number of children.
  44     num_children = zeros (1, num_nodes + 1);
  45
  46     ## Checking vector of predecessors.
  47     for i = 1 : num_nodes
  48       if (tree(i) < i)
  49         ## This part of graph was checked before.
  50         continue;
  51       endif
  52
  53       ## Try to find cicle in this part of graph using modified Floyd's
  54       ## cycle-finding algorithm.
  55       tortoise = tree(i);
  56       hare = tree(tortoise);
  57
  58       while (tortoise != hare)
  59         ## End after finding a cicle or reaching a checked part of graph.
  60
  61         if (hare < i)
  62           ## This part of graph was checked before.
  63           break
  64         endif
  65
  66         tortoise = tree(tortoise);
  67         ## Hare will move faster than tortoise so in cicle hare must
  68         ## reach tortoise.
  69         hare = tree(tree(hare));
  70
  71       endwhile
  72
  73       if (tortoise == hare)
  74         ## If hare reach tortoise we found circle.
  75         error ("treelayout: vector of predecessors has bad format");
  76       endif
  77
  78     endfor
  79     ## Vector of predecessors has right format.
  80
  81     for i = 1:num_nodes
  82       ## vec_of_child is helping vector which is used to speed up the
  83       ## choice of descendant nodes.
  84
  85       num_children(tree(i)+1) = num_children(tree(i)+1) + 1;
  86     endfor
  87
  88     pos = 1;
  89     start = zeros (1, num_nodes+1);
  90     xhelp = zeros (1, num_nodes+1);
  91     stop = zeros (1, num_nodes+1);
  92     for i = 1 : num_nodes + 1
  93       start(i) = pos;
  94       xhelp(i) = pos;
  95       pos += num_children(i);
  96       stop(i) = pos;
  97     endfor
  98
  99     if (nargin == 1)
 100       for i = 1:num_nodes
 101         vec_of_child(xhelp(tree(i)+1)) = i;
 102         xhelp(tree(i)+1) = xhelp(tree(i)+1) + 1;
 103       endfor
 104     else
 105       vec_of_child = permutation;
 106     endif
 107
 108     ## The number of "parent" (actual) node (it's descendants will be
 109     ## browse in the next iteration).
 110     par_number = 0;
 111
 112     ## The x-coordinate of the left most descendant of "parent node"
 113     ## this value is increased in each leaf.
 114     left_most = 0;
 115
 116     ## The level of "parent" node (root level is num_nodes).
 117     level = num_nodes;
 118
 119     ## num_nodes - max_ht is the height of this graph.
 120     max_ht = num_nodes;
 121
 122     ## Main stack - each item consists of two numbers - the number of
 123     ## node and the number it's of parent node on the top of stack
 124     ## there is "parent node".
 125     stk = [-1, 0];
 126
 127     ## Number of vertices s in the top-level separator.
 128     s = 0;
 129     ## Flag which says if we are in top level separator.
 130     top_level = 1;
 131     ## The top of the stack.
 132     while (par_number != -1)
 133       if (start(par_number+1) < stop(par_number+1))
 134         idx = vec_of_child(start(par_number+1) : stop(par_number+1) - 1);
 135       else
 136         idx = zeros (1, 0);
 137       endif
 138
 139       ## Add to idx the vector of parent descendants.
 140       stk = [stk; [idx', ones(fliplr(size(idx))) * par_number]];
 141
 142       ## We are in top level separator when we have one child and the
 143       ## flag is 1
 144       if (columns(idx) == 1 && top_level == 1)
 145         s++;
 146       else
 147         # We aren't in top level separator now.
 148         top_level = 0;
 149       endif
 150       ## If there is not any descendant of "parent node":
 151       if (stk(end,2) != par_number)
 152        left_most++;
 153        x_coordinate_r(par_number) = left_most;
 154        max_ht = min (max_ht, level);
 155        if (length(stk) > 1 && find ((shift(stk,1)-stk) == 0) > 1
 156            && stk(end,2) != stk(end-1,2))
 157           ## Return to the nearest branching the position to return
 158           ## position is the position on the stack, where should be
 159           ## started further search (there are two nodes which has the
 160           ## same parent node).
 161
 162           position = (find ((shift (stk(:,2), 1) - stk(:,2)) == 0))(end) + 1;
 163           par_number_vec = stk(position:end,2);
 164
 165           ## The vector of removed nodes (the content of stack form
 166           ## position to end).
 167
 168           level += length (par_number_vec);
 169
 170           ## The level have to be decreased.
 171
 172           x_coordinate_r(par_number_vec) = left_most;
 173           stk(position:end,:) = [];
 174         endif
 175
 176         ## Remove the next node from "searched branch".
 177
 178         stk(end,:) = [];
 179         ## Choose new "parent node".
 180         par_number = stk(end,1);
 181         ## If there is another branch start to search it.
 182         if (par_number != -1)
 183           y_coordinate(par_number) = level;
 184           x_coordinate_l(par_number) = left_most + 1;
 185         endif
 186       else
 187
 188         ## There were descendants of "parent nod" choose the last of
 189         ## them and go on through it.
 190         level--;
 191         par_number = stk(end,1);
 192         y_coordinate(par_number) = level;
 193         x_coordinate_l(par_number) = left_most + 1;
 194       endif
 195     endwhile
 196
 197     ## Calculate the x coordinates (the known values are the position
 198     ## of most left and most right descendants).
 199     x_coordinate = (x_coordinate_l + x_coordinate_r) / 2;
 200
 201     height = num_nodes - max_ht - 1;
 202   endif
 203 endfunction
 204
 205 %!test
 206 %! % Compute a simple tree layout
 207 %! [x, y, h, s] = treelayout ([0, 1, 2, 2]);
 208 %! assert (x, [1.5, 1.5, 2, 1]);
 209 %! assert (y, [3, 2, 1, 1]);
 210 %! assert (h, 2);
 211 %! assert (s, 2);
 212
 213 %!test
 214 %! % Compute a simple tree layout with defined postorder permutation
 215 %! [x, y, h, s] = treelayout ([0, 1, 2, 2], [1, 2, 4, 3]);
 216 %! assert (x, [1.5, 1.5, 1, 2]);
 217 %! assert (y, [3, 2, 1, 1]);
 218 %! assert (h, 2);
 219 %! assert (s, 2);
 220
 221 %!test
 222 %! % Compute a simple tree layout with defined postorder permutation
 223 %! [x, y, h, s] = treelayout ([0, 1, 2, 2], [4, 2, 3, 1]);
 224 %! assert (x, [0, 0, 0, 1]);
 225 %! assert (y, [0, 0, 0, 3]);
 226 %! assert (h, 0);
 227 %! assert (s, 1);