Mercurial > octave-nkf
annotate scripts/sparse/treelayout.m @ 20199:df437a52bcaf stable
doc: Update more docstrings to have one sentence summary as first line.
Reviewed miscellaneous, sparse, strings in scripts directory.
* scripts/miscellaneous/bzip2.m, scripts/miscellaneous/citation.m,
scripts/miscellaneous/compare_versions.m, scripts/miscellaneous/computer.m,
scripts/miscellaneous/debug.m, scripts/miscellaneous/dir.m,
scripts/miscellaneous/edit.m, scripts/miscellaneous/error_ids.m,
scripts/miscellaneous/fileattrib.m, scripts/miscellaneous/fullfile.m,
scripts/miscellaneous/genvarname.m, scripts/miscellaneous/gzip.m,
scripts/miscellaneous/mkoctfile.m, scripts/miscellaneous/news.m,
scripts/miscellaneous/open.m, scripts/miscellaneous/parseparams.m,
scripts/miscellaneous/recycle.m, scripts/miscellaneous/run.m,
scripts/miscellaneous/swapbytes.m, scripts/miscellaneous/tar.m,
scripts/miscellaneous/tmpnam.m, scripts/miscellaneous/unpack.m,
scripts/miscellaneous/what.m, scripts/sparse/bicg.m, scripts/sparse/bicgstab.m,
scripts/sparse/cgs.m, scripts/sparse/colperm.m, scripts/sparse/eigs.m,
scripts/sparse/etreeplot.m, scripts/sparse/gmres.m, scripts/sparse/gplot.m,
scripts/sparse/ichol.m, scripts/sparse/ilu.m, scripts/sparse/pcg.m,
scripts/sparse/pcr.m, scripts/sparse/qmr.m, scripts/sparse/spaugment.m,
scripts/sparse/spconvert.m, scripts/sparse/spdiags.m, scripts/sparse/spfun.m,
scripts/sparse/spones.m, scripts/sparse/sprandsym.m, scripts/sparse/spstats.m,
scripts/sparse/spy.m, scripts/sparse/svds.m, scripts/sparse/treelayout.m,
scripts/sparse/treeplot.m, scripts/strings/base2dec.m,
scripts/strings/bin2dec.m, scripts/strings/blanks.m, scripts/strings/cstrcat.m,
scripts/strings/deblank.m, scripts/strings/dec2base.m,
scripts/strings/dec2bin.m, scripts/strings/dec2hex.m,
scripts/strings/findstr.m, scripts/strings/hex2dec.m, scripts/strings/index.m,
scripts/strings/isletter.m, scripts/strings/isstrprop.m,
scripts/strings/mat2str.m, scripts/strings/ostrsplit.m,
scripts/strings/regexptranslate.m, scripts/strings/rindex.m,
scripts/strings/str2num.m, scripts/strings/strcat.m, scripts/strings/strchr.m,
scripts/strings/strjoin.m, scripts/strings/strjust.m,
scripts/strings/strmatch.m, scripts/strings/strsplit.m,
scripts/strings/strtok.m, scripts/strings/strtrim.m,
scripts/strings/strtrunc.m, scripts/strings/substr.m,
scripts/strings/untabify.m, scripts/time/datenum.m:
Update more docstrings to have one sentence summary as first line.
| author | Rik <rik@octave.org> |
|---|---|
| date | Mon, 04 May 2015 14:22:02 -0700 |
| parents | 9fc020886ae9 |
| children |
| rev | line source |
|---|---|
|
19731
4197fc428c7d
maint: Update copyright notices for 2015.
John W. Eaton <jwe@octave.org>
parents:
17744
diff
changeset
|
1 ## Copyright (C) 2008-2015 Ivana Varekova & Radek Salac |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
2 ## |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
3 ## This file is part of Octave. |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
4 ## |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
5 ## Octave is free software; you can redistribute it and/or modify it |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
6 ## under the terms of the GNU General Public License as published by |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
7 ## the Free Software Foundation; either version 3 of the License, or (at |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
8 ## your option) any later version. |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
9 ## |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
10 ## Octave is distributed in the hope that it will be useful, but |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
11 ## WITHOUT ANY WARRANTY; without even the implied warranty of |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
12 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
13 ## General Public License for more details. |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
14 ## |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
15 ## You should have received a copy of the GNU General Public License |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
16 ## along with Octave; see the file COPYING. If not, see |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
17 ## <http://www.gnu.org/licenses/>. |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
18 |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
19 ## -*- texinfo -*- |
|
11469
c776f063fefe
Overhaul m-script files to use common variable name between code and documentation.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
20 ## @deftypefn {Function File} {} treelayout (@var{tree}) |
|
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} {} treelayout (@var{tree}, @var{permutation}) |
|
20199
df437a52bcaf
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19867
diff
changeset
|
22 ## treelayout lays out a tree or a forest. |
|
df437a52bcaf
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19867
diff
changeset
|
23 ## |
|
df437a52bcaf
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19867
diff
changeset
|
24 ## The first argument @var{tree} is a vector of predecessors. |
|
df437a52bcaf
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19867
diff
changeset
|
25 ## |
|
df437a52bcaf
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19867
diff
changeset
|
26 ## The parameter @var{permutation} is an optional postorder permutation. |
|
df437a52bcaf
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19867
diff
changeset
|
27 ## |
|
df437a52bcaf
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19867
diff
changeset
|
28 ## The complexity of the algorithm is O(n) in terms of time and memory |
|
df437a52bcaf
doc: Update more docstrings to have one sentence summary as first line.
Rik <rik@octave.org>
parents:
19867
diff
changeset
|
29 ## requirements. |
|
12575
d0b799dafede
Grammarcheck files for 3.4.1 release.
Rik <octave@nomad.inbox5.com>
parents:
11587
diff
changeset
|
30 ## @seealso{etreeplot, gplot, treeplot} |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
31 ## @end deftypefn |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
32 |
| 8507 | 33 function [x_coordinate, y_coordinate, height, s] = treelayout (tree, permutation) |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
34 if (nargin < 1 || nargin > 2 || nargout > 4) |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
35 print_usage (); |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
36 elseif (! isvector (tree) || rows (tree) != 1 || ! isnumeric (tree) |
|
19867
9fc020886ae9
maint: Clean up m-files to follow Octave coding conventions.
Rik <rik@octave.org>
parents:
19731
diff
changeset
|
37 || any (tree > length (tree)) || any (tree < 0)) |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
38 error ("treelayout: the first input argument must be a vector of predecessors"); |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
39 else |
| 8506 | 40 ## Make it a row vector. |
| 8507 | 41 tree = tree(:)'; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
42 |
| 8506 | 43 ## The count of nodes of the graph. |
| 8507 | 44 num_nodes = length (tree); |
| 8506 | 45 ## The number of children. |
| 8507 | 46 num_children = zeros (1, num_nodes + 1); |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
47 |
| 8506 | 48 ## Checking vector of predecessors. |
| 8507 | 49 for i = 1 : num_nodes |
| 50 if (tree(i) < i) | |
| 10549 | 51 ## This part of graph was checked before. |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
52 continue; |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
53 endif |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
54 |
| 8506 | 55 ## Try to find cicle in this part of graph using modified Floyd's |
| 56 ## cycle-finding algorithm. | |
| 8507 | 57 tortoise = tree(i); |
| 58 hare = tree(tortoise); | |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
59 |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
60 while (tortoise != hare) |
| 10549 | 61 ## End after finding a cicle or reaching a checked part of graph. |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
62 |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
63 if (hare < i) |
| 8506 | 64 ## This part of graph was checked before. |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
65 break |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
66 endif |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
67 |
| 8507 | 68 tortoise = tree(tortoise); |
| 10549 | 69 ## Hare will move faster than tortoise so in cicle hare must |
| 70 ## reach tortoise. | |
| 8507 | 71 hare = tree(tree(hare)); |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
72 |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
73 endwhile |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
74 |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
75 if (tortoise == hare) |
| 10549 | 76 ## If hare reach tortoise we found circle. |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
77 error ("treelayout: vector of predecessors has bad format"); |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
78 endif |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
79 |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
80 endfor |
| 8506 | 81 ## Vector of predecessors has right format. |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
82 |
| 8507 | 83 for i = 1:num_nodes |
| 84 ## vec_of_child is helping vector which is used to speed up the | |
| 8506 | 85 ## choice of descendant nodes. |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
86 |
| 8507 | 87 num_children(tree(i)+1) = num_children(tree(i)+1) + 1; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
88 endfor |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
89 |
| 8507 | 90 pos = 1; |
| 91 start = zeros (1, num_nodes+1); | |
| 92 xhelp = zeros (1, num_nodes+1); | |
| 93 stop = zeros (1, num_nodes+1); | |
| 94 for i = 1 : num_nodes + 1 | |
| 95 start(i) = pos; | |
| 96 xhelp(i) = pos; | |
| 97 pos += num_children(i); | |
| 98 stop(i) = pos; | |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
99 endfor |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
100 |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
101 if (nargin == 1) |
| 8507 | 102 for i = 1:num_nodes |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
103 vec_of_child(xhelp(tree(i)+1)) = i; |
| 8507 | 104 xhelp(tree(i)+1) = xhelp(tree(i)+1) + 1; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
105 endfor |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
106 else |
| 8507 | 107 vec_of_child = permutation; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
108 endif |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
109 |
| 8506 | 110 ## The number of "parent" (actual) node (it's descendants will be |
| 111 ## browse in the next iteration). | |
| 8507 | 112 par_number = 0; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
113 |
| 8506 | 114 ## The x-coordinate of the left most descendant of "parent node" |
| 115 ## this value is increased in each leaf. | |
| 8507 | 116 left_most = 0; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
117 |
| 8507 | 118 ## The level of "parent" node (root level is num_nodes). |
| 119 level = num_nodes; | |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
120 |
| 8507 | 121 ## num_nodes - max_ht is the height of this graph. |
| 122 max_ht = num_nodes; | |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
123 |
| 8506 | 124 ## Main stack - each item consists of two numbers - the number of |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
125 ## node and the number it's of parent node on the top of stack |
| 8506 | 126 ## there is "parent node". |
| 8507 | 127 stk = [-1, 0]; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
128 |
| 8506 | 129 ## Number of vertices s in the top-level separator. |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
130 s = 0; |
| 8506 | 131 ## Flag which says if we are in top level separator. |
| 8507 | 132 top_level = 1; |
| 8506 | 133 ## The top of the stack. |
| 8507 | 134 while (par_number != -1) |
| 135 if (start(par_number+1) < stop(par_number+1)) | |
| 136 idx = vec_of_child(start(par_number+1) : stop(par_number+1) - 1); | |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
137 else |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
138 idx = zeros (1, 0); |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
139 endif |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
140 |
| 8506 | 141 ## Add to idx the vector of parent descendants. |
| 8507 | 142 stk = [stk; [idx', ones(fliplr(size(idx))) * par_number]]; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
143 |
| 8506 | 144 ## We are in top level separator when we have one child and the |
| 145 ## flag is 1 | |
|
14868
5d3a684236b0
maint: Use Octave coding conventions for cuddling parentheses in scripts directory
Rik <octave@nomad.inbox5.com>
parents:
14363
diff
changeset
|
146 if (columns (idx) == 1 && top_level == 1) |
| 8507 | 147 s++; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
148 else |
|
17336
b81b9d079515
Use '##' for comments which stand alone on a line.
Rik <rik@octave.org>
parents:
14868
diff
changeset
|
149 ## We aren't in top level separator now. |
| 8507 | 150 top_level = 0; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
151 endif |
| 8506 | 152 ## If there is not any descendant of "parent node": |
| 8507 | 153 if (stk(end,2) != par_number) |
| 154 left_most++; | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
155 x_coordinate_r(par_number) = left_most; |
| 8507 | 156 max_ht = min (max_ht, level); |
|
14868
5d3a684236b0
maint: Use Octave coding conventions for cuddling parentheses in scripts directory
Rik <octave@nomad.inbox5.com>
parents:
14363
diff
changeset
|
157 if (length (stk) > 1 && find ((shift (stk,1) - stk) == 0) > 1 |
| 10549 | 158 && stk(end,2) != stk(end-1,2)) |
| 159 ## Return to the nearest branching the position to return | |
| 160 ## position is the position on the stack, where should be | |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
161 ## started further search (there are two nodes which has the |
| 8506 | 162 ## same parent node). |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
163 |
| 8507 | 164 position = (find ((shift (stk(:,2), 1) - stk(:,2)) == 0))(end) + 1; |
| 165 par_number_vec = stk(position:end,2); | |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
166 |
| 8506 | 167 ## The vector of removed nodes (the content of stack form |
| 168 ## position to end). | |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
169 |
| 8507 | 170 level += length (par_number_vec); |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
171 |
| 10549 | 172 ## The level have to be decreased. |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
173 |
| 8507 | 174 x_coordinate_r(par_number_vec) = left_most; |
| 175 stk(position:end,:) = []; | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
176 endif |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
177 |
| 8506 | 178 ## Remove the next node from "searched branch". |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
179 |
| 8507 | 180 stk(end,:) = []; |
| 10549 | 181 ## Choose new "parent node". |
| 8507 | 182 par_number = stk(end,1); |
| 10549 | 183 ## If there is another branch start to search it. |
| 184 if (par_number != -1) | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
185 y_coordinate(par_number) = level; |
| 8507 | 186 x_coordinate_l(par_number) = left_most + 1; |
| 10549 | 187 endif |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
188 else |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
189 |
| 8506 | 190 ## There were descendants of "parent nod" choose the last of |
| 191 ## them and go on through it. | |
| 8507 | 192 level--; |
| 193 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
|
194 y_coordinate(par_number) = level; |
| 8507 | 195 x_coordinate_l(par_number) = left_most + 1; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
196 endif |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
197 endwhile |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
198 |
| 8506 | 199 ## Calculate the x coordinates (the known values are the position |
| 200 ## of most left and most right descendants). | |
| 8507 | 201 x_coordinate = (x_coordinate_l + x_coordinate_r) / 2; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
202 |
| 8507 | 203 height = num_nodes - max_ht - 1; |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
204 endif |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
205 endfunction |
|
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
206 |
|
14363
f3d52523cde1
Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents:
14138
diff
changeset
|
207 |
|
13060
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
208 %!test |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
209 %! % Compute a simple tree layout |
|
13060
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
210 %! [x, y, h, s] = treelayout ([0, 1, 2, 2]); |
|
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
211 %! assert (x, [1.5, 1.5, 2, 1]); |
|
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
212 %! assert (y, [3, 2, 1, 1]); |
|
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
213 %! assert (h, 2); |
|
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
214 %! assert (s, 2); |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
215 |
|
13060
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
216 %!test |
|
8338
a35bf360b919
Add the cgs and treelayout functions
Radek Salac <salac.r@gmail.com>
parents:
diff
changeset
|
217 %! % Compute a simple tree layout with defined postorder permutation |
|
13060
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
218 %! [x, y, h, s] = treelayout ([0, 1, 2, 2], [1, 2, 4, 3]); |
|
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
219 %! assert (x, [1.5, 1.5, 1, 2]); |
|
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
220 %! assert (y, [3, 2, 1, 1]); |
|
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
221 %! assert (h, 2); |
|
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
222 %! assert (s, 2); |
|
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
223 |
|
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
224 %!test |
|
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
225 %! % Compute a simple tree layout with defined postorder permutation |
|
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
226 %! [x, y, h, s] = treelayout ([0, 1, 2, 2], [4, 2, 3, 1]); |
|
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
227 %! assert (x, [0, 0, 0, 1]); |
|
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
228 %! assert (y, [0, 0, 0, 3]); |
|
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
229 %! assert (h, 0); |
|
85dd509673e7
codesprint: tests for treelayout
John W. Eaton <jwe@octave.org>
parents:
12575
diff
changeset
|
230 %! assert (s, 1); |
|
14363
f3d52523cde1
Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents:
14138
diff
changeset
|
231 |