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