Mercurial > hg > octave-lyh
annotate scripts/sparse/treeplot.m @ 9051:1bf0ce0930be
Grammar check TexInfo in all .m files
Cleanup documentation sources to follow a few consistent rules.
Spellcheck was NOT done. (but will be in another changeset)
| author | Rik <rdrider0-list@yahoo.com> |
|---|---|
| date | Fri, 27 Mar 2009 22:31:03 -0700 |
| parents | eb63fbe60fab |
| children | 95c3e38098bf |
| rev | line source |
|---|---|
| 8920 | 1 ## Copyright (C) 2005, 2006, 2007, 2009 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}) | |
|
9051
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
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} |
|
9051
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
24 ## define the output style. The complexity of the algorithm is O(n) in |
| 5576 | 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") |