Mercurial > hg > octave-lyh

annotate scripts/sparse/treelayout.m @ 8338:a35bf360b919

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add the cgs and treelayout functions
author Radek Salac <salac.r@gmail.com>
date Fri, 21 Nov 2008 15:03:03 +0100
parents
children bc982528de11
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
8338
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
1 ## Copyright (C) 2008 Ivana Varekova & Radek Salac
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})
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
21 ## @deftypefnx {Function File} {} treelayout (@var{Tree}, @var{Permutation})
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
22 ## treelayout lays out a tree or a forest. The first argument @var{Tree} is a vector of
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
23 ## predecessors, optional parameter @var{Permutation} is an optional postorder permutation.
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
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
29 function [XCoordinate, YCoordinate, Height, s] = treelayout (Tree, Permutation)
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 ();
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
32 elseif (! isvector (Tree) || rows (Tree) != 1 || ! isnumeric (Tree)
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
33 || any (Tree > length (Tree)) || any (Tree < 0) )
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
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
36 ## make it a row vector
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
37 Tree = Tree(:)';
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
38
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
39 ## the count of nodes of the graph
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
40 NodNumber = length (Tree);
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
41 ## the number of children
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
42 ChildNumber = zeros (1, NodNumber + 1);
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
43
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
44
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
45 ## checking vector of predecessors
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
46 for i = 1 : NodNumber
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
47 if (Tree (i) < i)
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
48 ## this part of graph was checked before
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
49 continue;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
50 endif
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
51
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
52 ## Try to find cicle in this part of graph
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
53 ## we use modified Floyd's cycle-finding algorithm
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
54 tortoise = Tree (i);
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
55 hare = Tree (tortoise);
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
56
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
57 while (tortoise != hare)
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
58 ## we end after find a cicle or when we reach a checked part of graph
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
59
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
60 if (hare < i)
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
61 ## this part of graph was checked before
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
62 break
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
63 endif
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
64
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
65 tortoise = Tree (tortoise);
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
66 ## hare will move faster than tortoise so in cicle hare
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
67 ## must reach tortoise
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
68 hare = Tree (Tree (hare));
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
69
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
70 endwhile
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
71
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
72 if (tortoise == hare)
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
73 ## if hare reach tortoise we find cicle
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
74 error ("treelayout: vector of predecessors has bad format");
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
75 endif
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
76
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
77 endfor
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
78 ## vector of predecessors has right format
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
79
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
80 for i = 1:NodNumber
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
81 ## VecOfChild is helping vector which is used to speed up the
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
82 ## choose of descendant nodes
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
83
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
84 ChildNumber (Tree (i) + 1) = ChildNumber (Tree (i) + 1) + 1;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
85 endfor
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
86
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
87 Pos = 1;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
88 for i = 1 : NodNumber + 1
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
89 Start (i) = Pos;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
90 Help (i) = Pos;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
91 Pos += ChildNumber (i);
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
92 Stop (i) = Pos;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
93 endfor
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
94
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
95 if (nargin == 1)
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
96 for i = 1 : NodNumber
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
97 VecOfChild (Help (Tree (i) + 1)) = i;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
98 Help (Tree (i) + 1) = Help (Tree (i) + 1) + 1;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
99 endfor
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
100 else
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
101 VecOfChild = Permutation;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
102 endif
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
103
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
104
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
105 ## the number of "parent" (actual) node (it's descendants will be
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
106 ## browse in the next iteration)
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
107 ParNumber = 0;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
108
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
109 ## the x-coordinate of the left most descendant of "parent node"
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
110 ## this value is increased in each leaf
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
111 LeftMost = 0;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
112
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
113 ## the level of "parent" node (root level is NodNumber)
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
114 Level = NodNumber;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
115
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
116 ## NodNumber - Max is the height of this graph
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
117 Max = NodNumber;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
118
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
119 ## main stack - each item consists of two numbers - the number of
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
120 ## node and the number it's of parent node on the top of stack
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
121 ## there is "parent node"
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
122 St = [-1, 0];
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
123
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
124 #number of vertices s in the top-level separator
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
125 s = 0;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
126 # flag which says if we are in top level separator
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
127 topLevel = 1;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
128 ## the top of the stack
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
129 while (ParNumber != -1)
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
130 if (Start(ParNumber + 1) < Stop(ParNumber + 1))
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
131 idx = VecOfChild (Start (ParNumber + 1) : Stop (ParNumber + 1) - 1);
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
132 else
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
133 idx = zeros (1, 0);
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
134 endif
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
135
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
136 ## add to idx the vector of parent descendants
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
137 St = [St ; [idx', ones(fliplr(size(idx))) * ParNumber]];
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
138
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
139 # we are in top level separator when we have one children
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
140 ## and the flag is 1
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
141 if (columns(idx) == 1 && topLevel ==1 )
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
142 s += 1;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
143 else
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
144 # we arent in top level separator now
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
145 topLevel = 0;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
146 endif
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
147 ## if there is not any descendant of "parent node":
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
148 if (St(end,2) != ParNumber)
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
149 LeftMost = LeftMost + 1;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
150 XCoordinateR(ParNumber) = LeftMost;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
151 Max = min (Max, Level);
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
152 if ((length(St) > 1) && (find((shift(St,1)-St) == 0) >1)
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
153 && St(end,2) != St(end-1,2))
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
154 ## return to the nearest branching the position to return
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
155 ## 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
156 ## started further search (there are two nodes which has the
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
157 ## same parent node)
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
158
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
159 Position = (find ((shift (St(:, 2), 1) - St(:, 2)) == 0))(end)+1;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
160 ParNumberVec = St(Position : end, 2);
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
161
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
162 ## the vector of removed nodes (the content of stack form
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
163 ## position to end)
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
164
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
165 Level = Level + length(ParNumberVec);
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
166
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
167 ## the level have to be decreased
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
168
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
169 XCoordinateR(ParNumberVec) = LeftMost;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
170 St(Position:end, :) = [];
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
171 endif
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
172
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
173 ## remove the next node from "searched branch"
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
174
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
175 St(end, :) = [];
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
176 ## choose new "parent node"
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
177 ParNumber = St(end, 1);
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
178 ## if there is another branch start to search it
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
179 if (ParNumber != -1)
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
180 YCoordinate(ParNumber) = Level;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
181 XCoordinateL(ParNumber) = LeftMost + 1;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
182 endif
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
183 else
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
184
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
185 ## there were descendants of "parent nod" choose the last of
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
186 ## them and go on through it
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
187 Level--;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
188 ParNumber = St(end, 1);
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
189 YCoordinate(ParNumber) = Level;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
190 XCoordinateL(ParNumber) = LeftMost+1;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
191 endif
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
192 endwhile
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
193
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
194 ## calculate the x coordinates (the known values are the position
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
195 ## of most left and most right descendants)
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
196 XCoordinate = (XCoordinateL + XCoordinateR) / 2;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
197
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
198 Height = NodNumber - Max - 1;
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
199 endif
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
200 endfunction
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
201
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
202 %!demo
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
203 %! % Compute a simple tree layout
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
204 %! [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
205
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
206 %!demo
a35bf360b919 Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff changeset
207 %! % 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
208 %! [x,y,h,s]=treelayout([0 1 2 2],[1 2 3 4])