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