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