octave_packages/m/sparse/treeplot.m

   1 ## Copyright (C) 2005-2012 Ivana Varekova
   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} {} treeplot (@var{tree})
  21 ## @deftypefnx {Function File} {} treeplot (@var{tree}, @var{node_style}, @var{edge_style})
  22 ## Produce a graph of tree or forest.  The first argument is vector of
  23 ## predecessors, optional parameters @var{node_style} and @var{edge_style}
  24 ## define the output style.  The complexity of the algorithm is O(n) in
  25 ## terms of is time and memory requirements.
  26 ## @seealso{etreeplot, gplot}
  27 ## @end deftypefn
  28
  29 function treeplot (tree, node_style = "ko", edge_style = "r")
  30
  31   if (nargin < 1 || nargin > 3 || nargout > 0)
  32     print_usage ();
  33   endif
  34
  35   if (! ismatrix (tree) || rows (tree) != 1 || ! isnumeric (tree)
  36       || ! isvector (tree) || any (tree > length (tree)))
  37     error ("treeplot: TREE must be a vector of predecessors");
  38   endif
  39
  40   ##  Verify node_style
  41   if (nargin > 1)
  42     if (isempty (regexp (node_style, '[ox+*]', 'once')))
  43       node_style = [node_style, "o"];
  44     endif
  45   endif
  46
  47   ## Make it a row vector.
  48   tree = tree(:)';
  49
  50   ## The count of nodes of the graph.
  51   num_nodes = length (tree);
  52
  53   ## The number of children.
  54   num_children = zeros (1, num_nodes+1);
  55
  56   for i = 1:num_nodes
  57     ## VEC_OF_CHILD is helping vector which is used to speed up the
  58     ## choose of descendant nodes.
  59
  60     num_children(tree(i)+1) = num_children(tree(i)+1) + 1;
  61   endfor
  62   pos = 1;
  63   start = zeros (1, num_nodes+1);
  64   xhelp = zeros (1, num_nodes+1);
  65   stop = zeros (1, num_nodes+1);
  66   for i = 1:num_nodes+1
  67     start(i) = pos;
  68     xhelp(i) = pos;
  69     pos += num_children(i);
  70     stop(i) = pos;
  71   endfor
  72   for i = 1:num_nodes
  73     vec_of_child(xhelp(tree(i)+1)) = i;
  74     xhelp(tree(i)+1) = xhelp(tree(i)+1)+1;
  75   endfor
  76
  77   ## The number of "parent" (actual) node (it's descendants will be
  78   ## browse in the next iteration).
  79   par_number = 0;
  80
  81   ## The x-coordinate of the left most descendant of "parent node"
  82   ## this value is increased in each leaf.
  83   left_most = 0;
  84
  85   ## The level of "parent" node (root level is num_nodes).
  86   level = num_nodes;
  87
  88   ## Num_nodes - max_ht is the height of this graph.
  89   max_ht = num_nodes;
  90
  91   ## Main stack - each item consists of two numbers - the number of
  92   ## node and the number it's of parent node on the top of stack
  93   ## there is "parent node".
  94   stk = [-1, 0];
  95
  96   ## Stack which is use to draw the graph edge (it have to be
  97   ## uninterupted line).
  98   skelet = 0;
  99
 100   ## The top of the stack.
 101   while (par_number != -1)
 102     if (start(par_number+1) < stop(par_number+1))
 103       idx = vec_of_child(start(par_number+1):stop(par_number+1)-1);
 104     else
 105       idx = zeros (1, 0);
 106     endif
 107     ## Add to idx the vector of parent descendants.
 108     stk = [stk; [idx', ones(fliplr(size(idx)))*par_number]];
 109     ## Add to stack the records relevant to parent descandant s.
 110     if (par_number != 0)
 111       skelet = [skelet; ([ones(size(idx))*par_number; idx])(:)];
 112     endif
 113
 114     ## If there is not any descendant of "parent node":
 115     if (stk(end,2) != par_number)
 116       left_most++;
 117       x_coordinate_r(par_number) = left_most;
 118       max_ht = min (max_ht, level);
 119       if (length(stk) > 1 && find ((shift(stk,1)-stk) == 0) > 1
 120           && stk(end,2) != stk(end-1,2))
 121         ## Return to the nearest branching the position to return
 122         ## position is the position on the stack, where should be
 123         ## started further search (there are two nodes which has the
 124         ## same parent node).
 125         position = (find ((shift(stk(:,2),1)-stk(:,2)) == 0))(end) + 1;
 126         par_number_vec = stk(position:end,2);
 127         ## The vector of removed nodes (the content of stack form
 128         ## position to end).
 129         skelet = [skelet; flipud(par_number_vec)];
 130         level += length (par_number_vec);
 131         ## The level have to be decreased.
 132         x_coordinate_r(par_number_vec) = left_most;
 133         stk(position:end,:) = [];
 134       endif
 135       ## Remove the next node from "searched branch".
 136       stk(end,:) = [];
 137       ## Choose new "parent node".
 138       par_number = stk(end,1);
 139       ## If there is another branch start to search it.
 140       if (par_number != -1)
 141         skelet = [skelet; stk(end,2); par_number];
 142         y_coordinate(par_number) = level;
 143         x_coordinate_l(par_number) = left_most + 1;
 144       endif
 145     else
 146       ## There were descendants of "parent nod" choose the last of
 147       ## them and go on through it.
 148       level--;
 149       par_number = stk(end,1);
 150       y_coordinate(par_number) = level;
 151       x_coordinate_l(par_number) = left_most + 1;
 152     endif
 153   endwhile
 154
 155   ## Calculate the x coordinates (the known values are the position
 156   ## of most left and most right descendants).
 157   x_coordinate = (x_coordinate_l + x_coordinate_r) / 2;
 158
 159   ## FIXME -- we should probably stuff all the arguments into a cell
 160   ## array and make a single call to plot here so we can avoid
 161   ## setting the hold state...
 162
 163   hold_is_on = ishold ();
 164   unwind_protect
 165     ## Plot graph nodes.
 166     plot (x_coordinate, y_coordinate, node_style);
 167
 168     ## Helping command - usable for plotting edges
 169     skelet = [skelet; 0];
 170
 171     ## Draw graph edges.
 172     idx = find (skelet == 0);
 173
 174     hold ("on");
 175     ## Plot each tree component in one loop.
 176     for i = 2:length(idx)
 177       ## Tree component start.
 178       istart = idx(i-1) + 1;
 179       ## Tree component end.
 180       istop = idx(i) - 1;
 181       if (istop - istart < 1)
 182         continue;
 183       endif
 184       plot (x_coordinate(skelet(istart:istop)),
 185             y_coordinate(skelet(istart:istop)), edge_style);
 186     endfor
 187
 188     ## Set axis and graph size.
 189     axis ([0.5, left_most+0.5, max_ht-0.5, num_nodes-0.5], "nolabel");
 190
 191   unwind_protect_cleanup
 192     if (! hold_is_on)
 193       hold ("off");
 194     endif
 195   end_unwind_protect
 196
 197 endfunction
 198
 199 %!demo
 200 %! % Plot a simple tree plot
 201 %! treeplot([2 4 2 0 6 4 6])
 202
 203 %!demo
 204 %! % Plot a simple tree plot defining the edge and node styles
 205 %! treeplot([2 4 2 0 6 4 6], "b+", "g")