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