octave-lyh: scripts/sparse/treelayout.m annotate

annotate scripts/sparse/treelayout.m @ 9051:1bf0ce0930be

Grammar check TexInfo in all .m files Cleanup documentation sources to follow a few consistent rules. Spellcheck was NOT done. (but will be in another changeset)

author	Rik <rdrider0-list@yahoo.com>
date	Fri, 27 Mar 2009 22:31:03 -0700
parents	eb63fbe60fab
children	95c3e38098bf

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

Mercurial > hg > octave-lyh

annotate scripts/sparse/treelayout.m @ 9051:1bf0ce0930be