Mercurial > octave-nkf
annotate scripts/sparse/treelayout.m @ 10549:95c3e38098bf
Untabify .m scripts
| author | Rik <code@nomad.inbox5.com> |
|---|---|
| date | Fri, 23 Apr 2010 11:28:50 -0700 |
| parents | 1bf0ce0930be |
| children | be55736a0783 |
| rev | line source |
|---|---|
| 8920 | 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 | 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 | 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 | 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 | 32 elseif (! isvector (tree) || rows (tree) != 1 || ! isnumeric (tree) |
| 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 | 36 ## Make it a row vector. |
| 8507 | 37 tree = tree(:)'; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
38 |
| 8506 | 39 ## The count of nodes of the graph. |
| 8507 | 40 num_nodes = length (tree); |
| 8506 | 41 ## The number of children. |
| 8507 | 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 | 44 ## Checking vector of predecessors. |
| 8507 | 45 for i = 1 : num_nodes |
| 46 if (tree(i) < i) | |
| 10549 | 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 | 51 ## Try to find cicle in this part of graph using modified Floyd's |
| 52 ## cycle-finding algorithm. | |
| 8507 | 53 tortoise = tree(i); |
| 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) |
| 10549 | 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 | 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 | 64 tortoise = tree(tortoise); |
| 10549 | 65 ## Hare will move faster than tortoise so in cicle hare must |
| 66 ## reach tortoise. | |
| 8507 | 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) |
| 10549 | 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 | 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 | 79 for i = 1:num_nodes |
| 80 ## vec_of_child is helping vector which is used to speed up the | |
| 8506 | 81 ## choice of descendant nodes. |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
82 |
| 8507 | 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 | 86 pos = 1; |
| 87 start = zeros (1, num_nodes+1); | |
| 88 xhelp = zeros (1, num_nodes+1); | |
| 89 stop = zeros (1, num_nodes+1); | |
| 90 for i = 1 : num_nodes + 1 | |
| 91 start(i) = pos; | |
| 92 xhelp(i) = pos; | |
| 93 pos += num_children(i); | |
| 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 | 98 for i = 1:num_nodes |
| 99 vec_of_child(xhelp(tree(i)+1)) = i; | |
| 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 | 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 | 106 ## The number of "parent" (actual) node (it's descendants will be |
| 107 ## browse in the next iteration). | |
| 8507 | 108 par_number = 0; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
109 |
| 8506 | 110 ## The x-coordinate of the left most descendant of "parent node" |
| 111 ## this value is increased in each leaf. | |
| 8507 | 112 left_most = 0; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
113 |
| 8507 | 114 ## The level of "parent" node (root level is num_nodes). |
| 115 level = num_nodes; | |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
116 |
| 8507 | 117 ## num_nodes - max_ht is the height of this graph. |
| 118 max_ht = num_nodes; | |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
119 |
| 8506 | 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 | 122 ## there is "parent node". |
| 8507 | 123 stk = [-1, 0]; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
124 |
| 8506 | 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 | 127 ## Flag which says if we are in top level separator. |
| 8507 | 128 top_level = 1; |
| 8506 | 129 ## The top of the stack. |
| 8507 | 130 while (par_number != -1) |
| 131 if (start(par_number+1) < stop(par_number+1)) | |
| 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 | 137 ## Add to idx the vector of parent descendants. |
| 8507 | 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 | 140 ## We are in top level separator when we have one child and the |
| 141 ## flag is 1 | |
| 8507 | 142 if (columns(idx) == 1 && top_level == 1) |
| 143 s++; | |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
144 else |
| 8506 | 145 # We aren't in top level separator now. |
| 8507 | 146 top_level = 0; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
147 endif |
| 8506 | 148 ## If there is not any descendant of "parent node": |
| 8507 | 149 if (stk(end,2) != par_number) |
| 150 left_most++; | |
| 151 x_coordinate_r(par_number) = left_most; | |
| 152 max_ht = min (max_ht, level); | |
| 153 if (length(stk) > 1 && find ((shift(stk,1)-stk) == 0) > 1 | |
| 10549 | 154 && stk(end,2) != stk(end-1,2)) |
| 155 ## Return to the nearest branching the position to return | |
| 156 ## position is the position on the stack, where should be | |
|
8338
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 | 158 ## same parent node). |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
159 |
| 8507 | 160 position = (find ((shift (stk(:,2), 1) - stk(:,2)) == 0))(end) + 1; |
| 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 | 163 ## The vector of removed nodes (the content of stack form |
| 164 ## position to end). | |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
165 |
| 8507 | 166 level += length (par_number_vec); |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
167 |
| 10549 | 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 | 170 x_coordinate_r(par_number_vec) = left_most; |
| 171 stk(position:end,:) = []; | |
| 10549 | 172 endif |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
173 |
| 8506 | 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 | 176 stk(end,:) = []; |
| 10549 | 177 ## Choose new "parent node". |
| 8507 | 178 par_number = stk(end,1); |
| 10549 | 179 ## If there is another branch start to search it. |
| 180 if (par_number != -1) | |
| 181 y_coordinate(par_number) = level; | |
| 8507 | 182 x_coordinate_l(par_number) = left_most + 1; |
| 10549 | 183 endif |
|
8338
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 | 186 ## There were descendants of "parent nod" choose the last of |
| 187 ## them and go on through it. | |
| 8507 | 188 level--; |
| 189 par_number = stk(end,1); | |
| 190 y_coordinate(par_number) = level; | |
| 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 | 195 ## Calculate the x coordinates (the known values are the position |
| 196 ## of most left and most right descendants). | |
| 8507 | 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 | 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]) |