Mercurial > octave-antonio
annotate scripts/sparse/treeplot.m @ 11589:b0084095098e
missing semicolons in script files
| author | John W. Eaton <jwe@octave.org> |
|---|---|
| date | Thu, 20 Jan 2011 18:26:09 -0500 |
| parents | c792872f8942 |
| children | bac54daffde2 |
| rev | line source |
|---|---|
| 11523 | 1 ## Copyright (C) 2005-2011 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 -*- | |
|
10793
be55736a0783
Grammarcheck the documentation from m-files.
Rik <octave@nomad.inbox5.com>
parents:
10549
diff
changeset
|
20 ## @deftypefn {Function File} {} treeplot (@var{tree}) |
|
11469
c776f063fefe
Overhaul m-script files to use common variable name between code and documentation.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
21 ## @deftypefnx {Function File} {} treeplot (@var{tree}, @var{node_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 |
|
11469
c776f063fefe
Overhaul m-script files to use common variable name between code and documentation.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
23 ## predecessors, optional parameters @var{node_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 |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
34 if (! ismatrix (tree) || rows (tree) != 1 || ! isnumeric (tree) |
| 8507 | 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*"; | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
40 edge_style = "r"; |
| 5576 | 41 if (nargin > 2) |
| 8507 | 42 edge_style = edge_s; |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
43 if (nargin > 1) |
| 10549 | 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"]; | |
| 48 else | |
| 49 node_style = node_s; | |
| 50 endif | |
| 5576 | 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); | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
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; | |
| 10549 | 75 xhelp(i) = pos; |
| 76 pos += num_children(i); | |
| 77 stop(i) = pos; | |
| 5576 | 78 endfor |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
79 for i = 1:num_nodes |
|
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
80 vec_of_child(xhelp(tree(i)+1)) = i; |
| 10549 | 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) | |
| 10549 | 109 if (start(par_number+1) < stop(par_number+1)) |
| 110 idx = vec_of_child(start(par_number+1):stop(par_number+1)-1); | |
| 111 else | |
| 112 idx = zeros (1, 0); | |
| 113 endif | |
| 8507 | 114 ## Add to idx the vector of parent descendants. |
| 10549 | 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])(:)]; | |
| 119 endif | |
| 6498 | 120 |
| 10549 | 121 ## If there is not any descendant of "parent node": |
| 122 if (stk(end,2) != par_number) | |
| 123 left_most++; | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
124 x_coordinate_r(par_number) = left_most; |
| 10549 | 125 max_ht = min (max_ht, level); |
| 8507 | 126 if (length(stk) > 1 && find ((shift(stk,1)-stk) == 0) > 1 |
| 10549 | 127 && stk(end,2) != stk(end-1,2)) |
| 128 ## Return to the nearest branching the position to return | |
| 129 ## position is the position on the stack, where should be | |
| 130 ## started further search (there are two nodes which has the | |
| 131 ## same parent node). | |
| 8507 | 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 | |
| 10549 | 135 ## position to end). |
| 8507 | 136 skelet = [skelet; flipud(par_number_vec)]; |
| 137 level += length (par_number_vec); | |
| 10549 | 138 ## The level have to be decreased. |
| 8507 | 139 x_coordinate_r(par_number_vec) = left_most; |
| 140 stk(position:end,:) = []; | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
141 endif |
| 10549 | 142 ## Remove the next node from "searched branch". |
| 143 stk(end,:) = []; | |
| 144 ## Choose new "parent node". | |
| 8507 | 145 par_number = stk(end,1); |
| 10549 | 146 ## If there is another branch start to search it. |
| 147 if (par_number != -1) | |
| 148 skelet = [skelet; stk(end,2); par_number]; | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
149 y_coordinate(par_number) = level; |
| 10549 | 150 x_coordinate_l(par_number) = left_most + 1; |
| 151 endif | |
| 152 else | |
| 8507 | 153 ## There were descendants of "parent nod" choose the last of |
| 10549 | 154 ## them and go on through it. |
| 8507 | 155 level--; |
| 10549 | 156 par_number = stk(end,1); |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
157 y_coordinate(par_number) = level; |
| 10549 | 158 x_coordinate_l(par_number) = left_most + 1; |
| 159 endif | |
| 5576 | 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 | |
| 10549 | 172 hold ("on"); |
| 8507 | 173 |
| 10549 | 174 ## Plot grah nodes. |
| 175 plot (x_coordinate, y_coordinate, node_style); | |
| 8507 | 176 |
| 10549 | 177 ## Helping command - usable for plotting edges |
| 178 skelet = [skelet; 0]; | |
| 8507 | 179 |
| 10549 | 180 ## Draw graph edges. |
| 181 idx = find (skelet == 0); | |
| 6498 | 182 |
| 10549 | 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; | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
189 if (istop - istart < 1) |
| 10549 | 190 continue; |
| 191 endif | |
| 192 plot (x_coordinate(skelet(istart:istop)), | |
|
11589
b0084095098e
missing semicolons in script files
John W. Eaton <jwe@octave.org>
parents:
11587
diff
changeset
|
193 y_coordinate(skelet(istart:istop)), edge_style); |
| 10549 | 194 endfor |
| 8507 | 195 |
| 10549 | 196 ## Set axis and graph size. |
| 197 axis ([0.5, left_most+0.5, max_ht-0.5, num_nodes-0.5], "nolabel"); | |
| 8507 | 198 |
| 199 unwind_protect_cleanup | |
| 10549 | 200 if (! hold_is_on) |
| 201 hold ("off"); | |
| 202 endif | |
| 8507 | 203 end_unwind_protect |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
204 |
| 5576 | 205 endif |
| 206 endif | |
| 207 endfunction | |
| 208 | |
| 209 %!demo | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
210 %! % Plot a simple tree plot |
| 5576 | 211 %! treeplot([2 4 2 0 6 4 6]) |
| 212 | |
| 213 %!demo | |
| 214 %! % Plot a simple tree plot defining the edge and node styles | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
215 %! treeplot([2 4 2 0 6 4 6], "b+", "g") |