octave-libtiff: scripts/sparse/treelayout.m annotate

annotate scripts/sparse/treelayout.m @ 30875:5d3faba0342e

doc: Ensure documentation lists output argument when it exists for all m-files. For new users of Octave it is best to show explicit calling forms in the documentation and to show a return argument when it exists. * bp-table.cc, shift.m, accumarray.m, accumdim.m, bincoeff.m, bitcmp.m, bitget.m, bitset.m, blkdiag.m, celldisp.m, cplxpair.m, dblquad.m, flip.m, fliplr.m, flipud.m, idivide.m, int2str.m, interpft.m, logspace.m, num2str.m, polyarea.m, postpad.m, prepad.m, randi.m, repmat.m, rng.m, rot90.m, rotdim.m, structfun.m, triplequad.m, uibuttongroup.m, uicontrol.m, uipanel.m, uipushtool.m, uitoggletool.m, uitoolbar.m, waitforbuttonpress.m, help.m, __additional_help_message__.m, hsv.m, im2double.m, im2frame.m, javachk.m, usejava.m, argnames.m, char.m, formula.m, inline.m, __vectorize__.m, findstr.m, flipdim.m, strmatch.m, vectorize.m, commutation_matrix.m, cond.m, cross.m, duplication_matrix.m, expm.m, orth.m, rank.m, rref.m, trace.m, vech.m, cast.m, compare_versions.m, delete.m, dir.m, fileattrib.m, grabcode.m, gunzip.m, inputname.m, license.m, list_primes.m, ls.m, mexext.m, movefile.m, namelengthmax.m, nargoutchk.m, nthargout.m, substruct.m, swapbytes.m, ver.m, verLessThan.m, what.m, fminunc.m, fsolve.m, fzero.m, optimget.m, __fdjac__.m, matlabroot.m, savepath.m, campos.m, camroll.m, camtarget.m, camup.m, camva.m, camzoom.m, clabel.m, diffuse.m, legend.m, orient.m, rticks.m, specular.m, thetaticks.m, xlim.m, xtickangle.m, xticklabels.m, xticks.m, ylim.m, ytickangle.m, yticklabels.m, yticks.m, zlim.m, ztickangle.m, zticklabels.m, zticks.m, ellipsoid.m, isocolors.m, isonormals.m, stairs.m, surfnorm.m, __actual_axis_position__.m, __pltopt__.m, close.m, graphics_toolkit.m, pan.m, print.m, printd.m, __ghostscript__.m, __gnuplot_print__.m, __opengl_print__.m, rotate3d.m, subplot.m, zoom.m, compan.m, conv.m, poly.m, polyaffine.m, polyder.m, polyint.m, polyout.m, polyreduce.m, polyvalm.m, roots.m, prefdir.m, prefsfile.m, profexplore.m, profexport.m, profshow.m, powerset.m, unique.m, arch_rnd.m, arma_rnd.m, autoreg_matrix.m, bartlett.m, blackman.m, detrend.m, durbinlevinson.m, fftconv.m, fftfilt.m, fftshift.m, fractdiff.m, hamming.m, hanning.m, hurst.m, ifftshift.m, rectangle_lw.m, rectangle_sw.m, triangle_lw.m, sinc.m, sinetone.m, sinewave.m, spectral_adf.m, spectral_xdf.m, spencer.m, ilu.m, __sprand__.m, sprand.m, sprandn.m, sprandsym.m, treelayout.m, beta.m, betainc.m, betaincinv.m, betaln.m, cosint.m, expint.m, factorial.m, gammainc.m, gammaincinv.m, lcm.m, nthroot.m, perms.m, reallog.m, realpow.m, realsqrt.m, sinint.m, hadamard.m, hankel.m, hilb.m, invhilb.m, magic.m, pascal.m, rosser.m, toeplitz.m, vander.m, wilkinson.m, center.m, corr.m, cov.m, discrete_cdf.m, discrete_inv.m, discrete_pdf.m, discrete_rnd.m, empirical_cdf.m, empirical_inv.m, empirical_pdf.m, empirical_rnd.m, kendall.m, kurtosis.m, mad.m, mean.m, meansq.m, median.m, mode.m, moment.m, range.m, ranks.m, run_count.m, skewness.m, spearman.m, statistics.m, std.m, base2dec.m, bin2dec.m, blanks.m, cstrcat.m, deblank.m, dec2base.m, dec2bin.m, dec2hex.m, hex2dec.m, index.m, regexptranslate.m, rindex.m, strcat.m, strjust.m, strtrim.m, strtrunc.m, substr.m, untabify.m, __have_feature__.m, __prog_output_assert__.m, __run_test_suite__.m, example.m, fail.m, asctime.m, calendar.m, ctime.m, date.m, etime.m: Add return arguments to @deftypefn macros where they were missing. Rename variables in functions (particularly generic "retval") to match documentation. Rename some return variables for (hopefully) better clarity (e.g., 'ax' to 'hax' to indicate it is a graphics handle to an axes object).

author	Rik <rik@octave.org>
date	Wed, 30 Mar 2022 20:40:27 -0700
parents	397d29f7135c
children

rev	line source
27923 bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	1 ########################################################################
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	2 ##
30564 796f54d4ddbf update Octave Project Developers copyright for the new year John W. Eaton <jwe@octave.org> parents: 29359 diff changeset	3 ## Copyright (C) 2008-2022 The Octave Project Developers
27918 b442ec6dda5c use centralized file for copyright info for individual contributors John W. Eaton <jwe@octave.org> parents: 26376 diff changeset	4 ##
27923 bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	5 ## See the file COPYRIGHT.md in the top-level directory of this
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	6 ## distribution or <https://octave.org/copyright/>.
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	7 ##
a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	8 ## This file is part of Octave.
a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	9 ##
24534 194eb4bd202b maint: Update punctuation for GPL v3 license text. Rik <rik@octave.org> parents: 23220 diff changeset	10 ## Octave is free software: you can redistribute it and/or modify it
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	11 ## under the terms of the GNU General Public License as published by
24534 194eb4bd202b maint: Update punctuation for GPL v3 license text. Rik <rik@octave.org> parents: 23220 diff changeset	12 ## the Free Software Foundation, either version 3 of the License, or
22755 3a2b891d0b33 maint: Standardize Copyright formatting. Rik <rik@octave.org> parents: 22323 diff changeset	13 ## (at your option) any later version.
8338 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 ## 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	16 ## WITHOUT ANY WARRANTY; without even the implied warranty of
22755 3a2b891d0b33 maint: Standardize Copyright formatting. Rik <rik@octave.org> parents: 22323 diff changeset	17 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
3a2b891d0b33 maint: Standardize Copyright formatting. Rik <rik@octave.org> parents: 22323 diff changeset	18 ## GNU General Public License for more details.
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	19 ##
a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	20 ## 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	21 ## along with Octave; see the file COPYING. If not, see
24534 194eb4bd202b maint: Update punctuation for GPL v3 license text. Rik <rik@octave.org> parents: 23220 diff changeset	22 ## <https://www.gnu.org/licenses/>.
27923 bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	23 ##
bd51beb6205e update formatting of copyright notices John W. Eaton <jwe@octave.org> parents: 27919 diff changeset	24 ########################################################################
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	25
a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	26 ## -- texinfo --
30875 5d3faba0342e doc: Ensure documentation lists output argument when it exists for all m-files. Rik <rik@octave.org> parents: 30603 diff changeset	27 ## @deftypefn {} {[@var{x}, @var{y}] =} treelayout (@var{tree})
5d3faba0342e doc: Ensure documentation lists output argument when it exists for all m-files. Rik <rik@octave.org> parents: 30603 diff changeset	28 ## @deftypefnx {} {[@var{x}, @var{y}] =} treelayout (@var{tree}, @var{permutation})
5d3faba0342e doc: Ensure documentation lists output argument when it exists for all m-files. Rik <rik@octave.org> parents: 30603 diff changeset	29 ## @deftypefnx {} {[@var{x}, @var{y}, @var{h}, @var{s}] =} treelayout (@dots{})
20164 df437a52bcaf doc: Update more docstrings to have one sentence summary as first line. Rik <rik@octave.org> parents: 19833 diff changeset	30 ## 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: 19833 diff changeset	31 ##
df437a52bcaf doc: Update more docstrings to have one sentence summary as first line. Rik <rik@octave.org> parents: 19833 diff changeset	32 ## 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: 19833 diff changeset	33 ##
30875 5d3faba0342e doc: Ensure documentation lists output argument when it exists for all m-files. Rik <rik@octave.org> parents: 30603 diff changeset	34 ## The optional parameter @var{permutation} is a postorder permutation.
20164 df437a52bcaf doc: Update more docstrings to have one sentence summary as first line. Rik <rik@octave.org> parents: 19833 diff changeset	35 ##
df437a52bcaf doc: Update more docstrings to have one sentence summary as first line. Rik <rik@octave.org> parents: 19833 diff changeset	36 ## 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: 19833 diff changeset	37 ## requirements.
12575 d0b799dafede Grammarcheck files for 3.4.1 release. Rik <octave@nomad.inbox5.com> parents: 11587 diff changeset	38 ## @seealso{etreeplot, gplot, treeplot}
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	39 ## @end deftypefn
a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	40
30875 5d3faba0342e doc: Ensure documentation lists output argument when it exists for all m-files. Rik <rik@octave.org> parents: 30603 diff changeset	41 function [x, y, h, s] = treelayout (tree, permutation)
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	42
28789 28de41192f3c Eliminate unneeded verification of nargin, nargout in m-files. Rik <rik@octave.org> parents: 27923 diff changeset	43 if (nargin < 1)
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	44 print_usage ();
11587 c792872f8942 all script files: untabify and strip trailing whitespace John W. Eaton <jwe@octave.org> parents: 11523 diff changeset	45 elseif (! isvector (tree) \|\| rows (tree) != 1 \|\| ! isnumeric (tree)
19833 9fc020886ae9 maint: Clean up m-files to follow Octave coding conventions. Rik <rik@octave.org> parents: 19697 diff changeset	46 \|\| any (tree > length (tree)) \|\| any (tree < 0))
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	47 error ("treelayout: the first input argument must be a vector of predecessors");
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	48 endif
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	49
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	50 ## Make it a row vector.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	51 tree = tree(:)';
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	52
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	53 ## The count of nodes of the graph.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	54 num_nodes = length (tree);
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	55 ## The number of children.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	56 num_children = zeros (1, num_nodes + 1);
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	57
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	58 ## Checking vector of predecessors.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	59 for i = 1 : num_nodes
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	60 if (tree(i) < i)
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	61 ## This part of graph was checked before.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	62 continue;
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	63 endif
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	64
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	65 ## Try to find cicle in this part of graph using modified Floyd's
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	66 ## cycle-finding algorithm.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	67 tortoise = tree(i);
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	68 hare = tree(tortoise);
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	69
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	70 while (tortoise != hare)
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	71 ## End after finding a cicle or reaching a checked part of graph.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	72
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	73 if (hare < i)
10549 95c3e38098bf Untabify .m scripts Rik <code@nomad.inbox5.com> parents: 9051 diff changeset	74 ## This part of graph was checked before.
28917 72d57dbcc305 maint: Add semicolon after break and return keywords. Rik <rik@octave.org> parents: 28789 diff changeset	75 break;
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	76 endif
a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	77
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	78 tortoise = tree(tortoise);
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	79 ## Hare will move faster than tortoise so in cicle hare must
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	80 ## reach tortoise.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	81 hare = tree(tree(hare));
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	82
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	83 endwhile
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	84
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	85 if (tortoise == hare)
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	86 ## If hare reach tortoise we found circle.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	87 error ("treelayout: vector of predecessors has bad format");
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	88 endif
a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	89
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	90 endfor
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	91 ## Vector of predecessors has right format.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	92
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	93 for i = 1:num_nodes
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	94 ## vec_of_child is helping vector which is used to speed up the
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	95 ## choice of descendant nodes.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	96
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	97 num_children(tree(i)+1) = num_children(tree(i)+1) + 1;
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	98 endfor
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	99
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	100 pos = 1;
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	101 start = zeros (1, num_nodes+1);
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	102 xhelp = zeros (1, num_nodes+1);
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	103 stop = zeros (1, num_nodes+1);
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	104 for i = 1 : num_nodes + 1
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	105 start(i) = pos;
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	106 xhelp(i) = pos;
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	107 pos += num_children(i);
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	108 stop(i) = pos;
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	109 endfor
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	110
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	111 if (nargin == 1)
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	112 for i = 1:num_nodes
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	113 vec_of_child(xhelp(tree(i)+1)) = i;
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	114 xhelp(tree(i)+1) = xhelp(tree(i)+1) + 1;
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	115 endfor
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	116 else
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	117 vec_of_child = permutation;
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	118 endif
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	119
22105 3f5f1234c619 main: Fix typos "It's" -> "Its" and "it's" -> "its" (Bug #48508) Andreas Weber <andy.weber.aw@gmail.com> parents: 21758 diff changeset	120 ## The number of "parent" (actual) node (its descendants will be
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	121 ## browse in the next iteration).
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	122 par_number = 0;
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	123
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	124 ## The x-coordinate of the left most descendant of "parent node"
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	125 ## this value is increased in each leaf.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	126 left_most = 0;
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	127
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	128 ## The level of "parent" node (root level is num_nodes).
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	129 level = num_nodes;
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	130
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	131 ## num_nodes - max_ht is the height of this graph.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	132 max_ht = num_nodes;
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	133
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	134 ## Main stack - each item consists of two numbers - the number of
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	135 ## node and the number it's of parent node on the top of stack
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	136 ## there is "parent node".
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	137 stk = [-1, 0];
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	138
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	139 ## Number of vertices s in the top-level separator.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	140 s = 0;
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	141 ## Flag which says if we are in top level separator.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	142 top_level = 1;
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	143 ## The top of the stack.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	144 while (par_number != -1)
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	145 if (start(par_number+1) < stop(par_number+1))
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	146 idx = vec_of_child(start(par_number+1) : stop(par_number+1) - 1);
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	147 else
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	148 idx = zeros (1, 0);
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	149 endif
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	150
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	151 ## Add to idx the vector of parent descendants.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	152 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	153
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	154 ## We are in top level separator when we have one child and the
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	155 ## flag is 1
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	156 if (columns (idx) == 1 && top_level == 1)
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	157 s += 1;
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	158 else
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	159 ## We aren't in top level separator now.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	160 top_level = 0;
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	161 endif
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	162 ## If there is not any descendant of "parent node":
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	163 if (stk(end,2) != par_number)
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	164 left_most += 1;
30875 5d3faba0342e doc: Ensure documentation lists output argument when it exists for all m-files. Rik <rik@octave.org> parents: 30603 diff changeset	165 x_r(par_number) = left_most;
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	166 max_ht = min (max_ht, level);
30603 397d29f7135c shift.m: Deprecate function in favor of circshift for Matlab compatibility. Rik <rik@octave.org> parents: 30564 diff changeset	167 if (length (stk) > 1 && find ((circshift (stk,1) - stk) == 0) > 1
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	168 && stk(end,2) != stk(end-1,2))
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	169 ## Return to the nearest branching the position to return
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	170 ## position is the position on the stack, where should be
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	171 ## started further search (there are two nodes which has the
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	172 ## same parent node).
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	173
30603 397d29f7135c shift.m: Deprecate function in favor of circshift for Matlab compatibility. Rik <rik@octave.org> parents: 30564 diff changeset	174 position = (find ((circshift (stk(:,2), 1) - stk(:,2)) == 0))(end) + 1;
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	175 par_number_vec = stk(position:end,2);
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	176
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	177 ## The vector of removed nodes (the content of stack form
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	178 ## position to end).
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	179
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	180 level += length (par_number_vec);
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	181
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	182 ## The level have to be decreased.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	183
30875 5d3faba0342e doc: Ensure documentation lists output argument when it exists for all m-files. Rik <rik@octave.org> parents: 30603 diff changeset	184 x_r(par_number_vec) = left_most;
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	185 stk(position:end,:) = [];
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	186 endif
a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	187
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	188 ## Remove the next node from "searched branch".
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	189
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	190 stk(end,:) = [];
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	191 ## Choose new "parent node".
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	192 par_number = stk(end,1);
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	193 ## If there is another branch start to search it.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	194 if (par_number != -1)
30875 5d3faba0342e doc: Ensure documentation lists output argument when it exists for all m-files. Rik <rik@octave.org> parents: 30603 diff changeset	195 y(par_number) = level;
5d3faba0342e doc: Ensure documentation lists output argument when it exists for all m-files. Rik <rik@octave.org> parents: 30603 diff changeset	196 x_l(par_number) = left_most + 1;
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	197 endif
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	198 else
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	199
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	200 ## There were descendants of "parent nod" choose the last of
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	201 ## them and go on through it.
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	202 level -= 1;
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	203 par_number = stk(end,1);
30875 5d3faba0342e doc: Ensure documentation lists output argument when it exists for all m-files. Rik <rik@octave.org> parents: 30603 diff changeset	204 y(par_number) = level;
5d3faba0342e doc: Ensure documentation lists output argument when it exists for all m-files. Rik <rik@octave.org> parents: 30603 diff changeset	205 x_l(par_number) = left_most + 1;
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	206 endif
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	207 endwhile
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	208
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	209 ## Calculate the x coordinates (the known values are the position
ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	210 ## of most left and most right descendants).
30875 5d3faba0342e doc: Ensure documentation lists output argument when it exists for all m-files. Rik <rik@octave.org> parents: 30603 diff changeset	211 x = (x_l + x_r) / 2;
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	212
30875 5d3faba0342e doc: Ensure documentation lists output argument when it exists for all m-files. Rik <rik@octave.org> parents: 30603 diff changeset	213 h = num_nodes - max_ht - 1;
21758 ffad2baa90f7 maint: Use newlines to make code more readable. Rik <rik@octave.org> parents: 20852 diff changeset	214
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	215 endfunction
a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	216
14363 f3d52523cde1 Use Octave coding conventions in all m-file %!test blocks Rik <octave@nomad.inbox5.com> parents: 14138 diff changeset	217
13060 85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	218 %!test
11587 c792872f8942 all script files: untabify and strip trailing whitespace John W. Eaton <jwe@octave.org> parents: 11523 diff changeset	219 %! % Compute a simple tree layout
13060 85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	220 %! [x, y, h, s] = treelayout ([0, 1, 2, 2]);
85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	221 %! assert (x, [1.5, 1.5, 2, 1]);
85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	222 %! assert (y, [3, 2, 1, 1]);
85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	223 %! assert (h, 2);
85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	224 %! assert (s, 2);
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	225
13060 85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	226 %!test
8338 a35bf360b919 Add the cgs and treelayout functions Radek Salac <salac.r@gmail.com> parents: diff changeset	227 %! % 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	228 %! [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	229 %! assert (x, [1.5, 1.5, 1, 2]);
85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	230 %! assert (y, [3, 2, 1, 1]);
85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	231 %! assert (h, 2);
85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	232 %! assert (s, 2);
85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	233
85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	234 %!test
85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	235 %! % Compute a simple tree layout with defined postorder permutation
85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	236 %! [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	237 %! assert (x, [0, 0, 0, 1]);
85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	238 %! assert (y, [0, 0, 0, 3]);
85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	239 %! assert (h, 0);
85dd509673e7 codesprint: tests for treelayout John W. Eaton <jwe@octave.org> parents: 12575 diff changeset	240 %! assert (s, 1);

Mercurial > octave-libtiff

annotate scripts/sparse/treelayout.m @ 30875:5d3faba0342e