Mercurial > octave-antonio

comparison scripts/sparse/treelayout.m @ 8507:cadc73247d65

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
style fixes
author John W. Eaton <jwe@octave.org>
date Tue, 13 Jan 2009 14:08:36 -0500
parents bc982528de11
children eb63fbe60fab
comparison
equal deleted inserted replaced
8506:bc982528de11 8507:cadc73247d65
16 ## along with Octave; see the file COPYING. If not, see 16 ## along with Octave; see the file COPYING. If not, see
17 ## <http://www.gnu.org/licenses/>. 17 ## <http://www.gnu.org/licenses/>.
18 18
19 ## -*- texinfo -*- 19 ## -*- texinfo -*-
20 ## @deftypefn {Function File} {} treelayout (@var{Tree}) 20 ## @deftypefn {Function File} {} treelayout (@var{Tree})
21 ## @deftypefnx {Function File} {} treelayout (@var{Tree}, @var{Permutation}) 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 vector of 22 ## treelayout lays out a tree or a forest. The first argument @var{Tree} is a vector of
23 ## predecessors, optional parameter @var{Permutation} is an optional postorder permutation. 23 ## predecessors, optional parameter @var{permutation} is an optional postorder permutation.
24 ## The complexity of the algorithm is O(n) in 24 ## The complexity of the algorithm is O(n) in
25 ## terms of time and memory requirements. 25 ## terms of time and memory requirements.
26 ## @seealso{etreeplot, gplot,treeplot} 26 ## @seealso{etreeplot, gplot,treeplot}
27 ## @end deftypefn 27 ## @end deftypefn
28 28
29 function [XCoordinate, YCoordinate, Height, s] = treelayout (Tree, Permutation) 29 function [x_coordinate, y_coordinate, height, s] = treelayout (tree, permutation)
30 if (nargin < 1 || nargin > 2 || nargout > 4) 30 if (nargin < 1 || nargin > 2 || nargout > 4)
31 print_usage (); 31 print_usage ();
32 elseif (! isvector (Tree) || rows (Tree) != 1 || ! isnumeric (Tree) 32 elseif (! isvector (tree) || rows (tree) != 1 || ! isnumeric (tree)
33 || any (Tree > length (Tree)) || any (Tree < 0) ) 33 || any (tree > length (tree)) || any (tree < 0))
34 error ("treelayout: the first input argument must be a vector of predecessors"); 34 error ("treelayout: the first input argument must be a vector of predecessors");
35 else 35 else
36 ## Make it a row vector. 36 ## Make it a row vector.
37 Tree = Tree(:)'; 37 tree = tree(:)';
38 38
39 ## The count of nodes of the graph. 39 ## The count of nodes of the graph.
40 NodNumber = length (Tree); 40 num_nodes = length (tree);
41 ## The number of children. 41 ## The number of children.
42 ChildNumber = zeros (1, NodNumber + 1); 42 num_children = zeros (1, num_nodes + 1);
43 43
44 ## Checking vector of predecessors. 44 ## Checking vector of predecessors.
45 for i = 1 : NodNumber 45 for i = 1 : num_nodes
46 if (Tree (i) < i) 46 if (tree(i) < i)
47 ## This part of graph was checked before. 47 ## This part of graph was checked before.
48 continue; 48 continue;
49 endif 49 endif
50 50
51 ## Try to find cicle in this part of graph using modified Floyd's 51 ## Try to find cicle in this part of graph using modified Floyd's
52 ## cycle-finding algorithm. 52 ## cycle-finding algorithm.
53 tortoise = Tree (i); 53 tortoise = tree(i);
54 hare = Tree (tortoise); 54 hare = tree(tortoise);
55 55
56 while (tortoise != hare) 56 while (tortoise != hare)
57 ## End after finding a cicle or reaching a checked part of graph. 57 ## End after finding a cicle or reaching a checked part of graph.
58 58
59 if (hare < i) 59 if (hare < i)
60 ## This part of graph was checked before. 60 ## This part of graph was checked before.
61 break 61 break
62 endif 62 endif
63 63
64 tortoise = Tree (tortoise); 64 tortoise = tree(tortoise);
65 ## Hare will move faster than tortoise so in cicle hare must 65 ## Hare will move faster than tortoise so in cicle hare must
66 ## reach tortoise. 66 ## reach tortoise.
67 hare = Tree (Tree (hare)); 67 hare = tree(tree(hare));
68 68
69 endwhile 69 endwhile
70 70
71 if (tortoise == hare) 71 if (tortoise == hare)
72 ## If hare reach tortoise we found circle. 72 ## If hare reach tortoise we found circle.
74 endif 74 endif
75 75
76 endfor 76 endfor
77 ## Vector of predecessors has right format. 77 ## Vector of predecessors has right format.
78 78
79 for i = 1:NodNumber 79 for i = 1:num_nodes
80 ## VecOfChild is helping vector which is used to speed up the 80 ## vec_of_child is helping vector which is used to speed up the
81 ## choice of descendant nodes. 81 ## choice of descendant nodes.
82 82
83 ChildNumber (Tree (i) + 1) = ChildNumber (Tree (i) + 1) + 1; 83 num_children(tree(i)+1) = num_children(tree(i)+1) + 1;
84 endfor 84 endfor
85 85
86 Pos = 1; 86 pos = 1;
87 for i = 1 : NodNumber + 1 87 start = zeros (1, num_nodes+1);
88 Start (i) = Pos; 88 xhelp = zeros (1, num_nodes+1);
89 Help (i) = Pos; 89 stop = zeros (1, num_nodes+1);
90 Pos += ChildNumber (i); 90 for i = 1 : num_nodes + 1
91 Stop (i) = Pos; 91 start(i) = pos;
92 xhelp(i) = pos;
93 pos += num_children(i);
94 stop(i) = pos;
92 endfor 95 endfor
93 96
94 if (nargin == 1) 97 if (nargin == 1)
95 for i = 1 : NodNumber 98 for i = 1:num_nodes
96 VecOfChild (Help (Tree (i) + 1)) = i; 99 vec_of_child(xhelp(tree(i)+1)) = i;
97 Help (Tree (i) + 1) = Help (Tree (i) + 1) + 1; 100 xhelp(tree(i)+1) = xhelp(tree(i)+1) + 1;
98 endfor 101 endfor
99 else 102 else
100 VecOfChild = Permutation; 103 vec_of_child = permutation;
101 endif 104 endif
102 105
103 ## The number of "parent" (actual) node (it's descendants will be 106 ## The number of "parent" (actual) node (it's descendants will be
104 ## browse in the next iteration). 107 ## browse in the next iteration).
105 ParNumber = 0; 108 par_number = 0;
106 109
107 ## The x-coordinate of the left most descendant of "parent node" 110 ## The x-coordinate of the left most descendant of "parent node"
108 ## this value is increased in each leaf. 111 ## this value is increased in each leaf.
109 LeftMost = 0; 112 left_most = 0;
110 113
111 ## The level of "parent" node (root level is NodNumber). 114 ## The level of "parent" node (root level is num_nodes).
112 Level = NodNumber; 115 level = num_nodes;
113 116
114 ## NodNumber - Max is the height of this graph. 117 ## num_nodes - max_ht is the height of this graph.
115 Max = NodNumber; 118 max_ht = num_nodes;
116 119
117 ## Main stack - each item consists of two numbers - the number of 120 ## Main stack - each item consists of two numbers - the number of
118 ## node and the number it's of parent node on the top of stack 121 ## node and the number it's of parent node on the top of stack
119 ## there is "parent node". 122 ## there is "parent node".
120 St = [-1, 0]; 123 stk = [-1, 0];
121 124
122 ## Number of vertices s in the top-level separator. 125 ## Number of vertices s in the top-level separator.
123 s = 0; 126 s = 0;
124 ## Flag which says if we are in top level separator. 127 ## Flag which says if we are in top level separator.
125 topLevel = 1; 128 top_level = 1;
126 ## The top of the stack. 129 ## The top of the stack.
127 while (ParNumber != -1) 130 while (par_number != -1)
128 if (Start(ParNumber + 1) < Stop(ParNumber + 1)) 131 if (start(par_number+1) < stop(par_number+1))
129 idx = VecOfChild (Start (ParNumber + 1) : Stop (ParNumber + 1) - 1); 132 idx = vec_of_child(start(par_number+1) : stop(par_number+1) - 1);
130 else 133 else
131 idx = zeros (1, 0); 134 idx = zeros (1, 0);
132 endif 135 endif
133 136
134 ## Add to idx the vector of parent descendants. 137 ## Add to idx the vector of parent descendants.
135 St = [St ; [idx', ones(fliplr(size(idx))) * ParNumber]]; 138 stk = [stk; [idx', ones(fliplr(size(idx))) * par_number]];
136 139
137 ## We are in top level separator when we have one child and the 140 ## We are in top level separator when we have one child and the
138 ## flag is 1 141 ## flag is 1
139 if (columns(idx) == 1 && topLevel ==1 ) 142 if (columns(idx) == 1 && top_level == 1)
140 s += 1; 143 s++;
141 else 144 else
142 # We aren't in top level separator now. 145 # We aren't in top level separator now.
143 topLevel = 0; 146 top_level = 0;
144 endif 147 endif
145 ## If there is not any descendant of "parent node": 148 ## If there is not any descendant of "parent node":
146 if (St(end,2) != ParNumber) 149 if (stk(end,2) != par_number)
147 LeftMost = LeftMost + 1; 150 left_most++;
148 XCoordinateR(ParNumber) = LeftMost; 151 x_coordinate_r(par_number) = left_most;
149 Max = min (Max, Level); 152 max_ht = min (max_ht, level);
150 if ((length(St) > 1) && (find((shift(St,1)-St) == 0) >1) 153 if (length(stk) > 1 && find ((shift(stk,1)-stk) == 0) > 1
151 && St(end,2) != St(end-1,2)) 154 && stk(end,2) != stk(end-1,2))
152 ## Return to the nearest branching the position to return 155 ## Return to the nearest branching the position to return
153 ## position is the position on the stack, where should be 156 ## position is the position on the stack, where should be
154 ## started further search (there are two nodes which has the 157 ## started further search (there are two nodes which has the
155 ## same parent node). 158 ## same parent node).
156 159
157 Position = (find ((shift (St(:, 2), 1) - St(:, 2)) == 0))(end)+1; 160 position = (find ((shift (stk(:,2), 1) - stk(:,2)) == 0))(end) + 1;
158 ParNumberVec = St(Position : end, 2); 161 par_number_vec = stk(position:end,2);
159 162
160 ## The vector of removed nodes (the content of stack form 163 ## The vector of removed nodes (the content of stack form
161 ## position to end). 164 ## position to end).
162 165
163 Level = Level + length(ParNumberVec); 166 level += length (par_number_vec);
164 167
165 ## The level have to be decreased. 168 ## The level have to be decreased.
166 169
167 XCoordinateR(ParNumberVec) = LeftMost; 170 x_coordinate_r(par_number_vec) = left_most;
168 St(Position:end, :) = []; 171 stk(position:end,:) = [];
169 endif 172 endif
170 173
171 ## Remove the next node from "searched branch". 174 ## Remove the next node from "searched branch".
172 175
173 St(end, :) = []; 176 stk(end,:) = [];
174 ## Choose new "parent node". 177 ## Choose new "parent node".
175 ParNumber = St(end, 1); 178 par_number = stk(end,1);
176 ## If there is another branch start to search it. 179 ## If there is another branch start to search it.
177 if (ParNumber != -1) 180 if (par_number != -1)
178 YCoordinate(ParNumber) = Level; 181 y_coordinate(par_number) = level;
179 XCoordinateL(ParNumber) = LeftMost + 1; 182 x_coordinate_l(par_number) = left_most + 1;
180 endif 183 endif
181 else 184 else
182 185
183 ## There were descendants of "parent nod" choose the last of 186 ## There were descendants of "parent nod" choose the last of
184 ## them and go on through it. 187 ## them and go on through it.
185 Level--; 188 level--;
186 ParNumber = St(end, 1); 189 par_number = stk(end,1);
187 YCoordinate(ParNumber) = Level; 190 y_coordinate(par_number) = level;
188 XCoordinateL(ParNumber) = LeftMost+1; 191 x_coordinate_l(par_number) = left_most + 1;
189 endif 192 endif
190 endwhile 193 endwhile
191 194
192 ## Calculate the x coordinates (the known values are the position 195 ## Calculate the x coordinates (the known values are the position
193 ## of most left and most right descendants). 196 ## of most left and most right descendants).
194 XCoordinate = (XCoordinateL + XCoordinateR) / 2; 197 x_coordinate = (x_coordinate_l + x_coordinate_r) / 2;
195 198
196 Height = NodNumber - Max - 1; 199 height = num_nodes - max_ht - 1;
197 endif 200 endif
198 endfunction 201 endfunction
199 202
200 %!demo 203 %!demo
201 %! % Compute a simple tree layout 204 %! % Compute a simple tree layout