Mercurial > octave
view scripts/sparse/treelayout.m @ 30564:796f54d4ddbf stable
update Octave Project Developers copyright for the new year
In files that have the "Octave Project Developers" copyright notice,
update for 2021.
In all .txi and .texi files except gpl.txi and gpl.texi in the
doc/liboctave and doc/interpreter directories, change the copyright
to "Octave Project Developers", the same as used for other source
files. Update copyright notices for 2022 (not done since 2019). For
gpl.txi and gpl.texi, change the copyright notice to be "Free Software
Foundation, Inc." and leave the date at 2007 only because this file
only contains the text of the GPL, not anything created by the Octave
Project Developers.
Add Paul Thomas to contributors.in.
author | John W. Eaton <jwe@octave.org> |
---|---|
date | Tue, 28 Dec 2021 18:22:40 -0500 |
parents | 7854d5752dd2 |
children | 397d29f7135c |
line wrap: on
line source
######################################################################## ## ## Copyright (C) 2008-2022 The Octave Project Developers ## ## See the file COPYRIGHT.md in the top-level directory of this ## distribution or <https://octave.org/copyright/>. ## ## This file is part of Octave. ## ## Octave is free software: you can redistribute it and/or modify it ## under the terms of the GNU General Public License as published by ## the Free Software Foundation, either version 3 of the License, or ## (at your option) any later version. ## ## Octave is distributed in the hope that it will be useful, but ## WITHOUT ANY WARRANTY; without even the implied warranty of ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ## GNU General Public License for more details. ## ## You should have received a copy of the GNU General Public License ## along with Octave; see the file COPYING. If not, see ## <https://www.gnu.org/licenses/>. ## ######################################################################## ## -*- texinfo -*- ## @deftypefn {} {} treelayout (@var{tree}) ## @deftypefnx {} {} treelayout (@var{tree}, @var{permutation}) ## treelayout lays out a tree or a forest. ## ## The first argument @var{tree} is a vector of predecessors. ## ## The parameter @var{permutation} is an optional postorder permutation. ## ## The complexity of the algorithm is O(n) in terms of time and memory ## requirements. ## @seealso{etreeplot, gplot, treeplot} ## @end deftypefn function [x_coordinate, y_coordinate, height, s] = ... treelayout (tree, permutation) if (nargin < 1) print_usage (); elseif (! isvector (tree) || rows (tree) != 1 || ! isnumeric (tree) || any (tree > length (tree)) || any (tree < 0)) error ("treelayout: the first input argument must be a vector of predecessors"); endif ## Make it a row vector. tree = tree(:)'; ## The count of nodes of the graph. num_nodes = length (tree); ## The number of children. num_children = zeros (1, num_nodes + 1); ## Checking vector of predecessors. for i = 1 : num_nodes if (tree(i) < i) ## This part of graph was checked before. continue; endif ## Try to find cicle in this part of graph using modified Floyd's ## cycle-finding algorithm. tortoise = tree(i); hare = tree(tortoise); while (tortoise != hare) ## End after finding a cicle or reaching a checked part of graph. if (hare < i) ## This part of graph was checked before. break; endif tortoise = tree(tortoise); ## Hare will move faster than tortoise so in cicle hare must ## reach tortoise. hare = tree(tree(hare)); endwhile if (tortoise == hare) ## If hare reach tortoise we found circle. error ("treelayout: vector of predecessors has bad format"); endif endfor ## Vector of predecessors has right format. for i = 1:num_nodes ## vec_of_child is helping vector which is used to speed up the ## choice of descendant nodes. num_children(tree(i)+1) = num_children(tree(i)+1) + 1; endfor pos = 1; start = zeros (1, num_nodes+1); xhelp = zeros (1, num_nodes+1); stop = zeros (1, num_nodes+1); for i = 1 : num_nodes + 1 start(i) = pos; xhelp(i) = pos; pos += num_children(i); stop(i) = pos; endfor if (nargin == 1) for i = 1:num_nodes vec_of_child(xhelp(tree(i)+1)) = i; xhelp(tree(i)+1) = xhelp(tree(i)+1) + 1; endfor else vec_of_child = permutation; endif ## The number of "parent" (actual) node (its descendants will be ## browse in the next iteration). par_number = 0; ## The x-coordinate of the left most descendant of "parent node" ## this value is increased in each leaf. left_most = 0; ## The level of "parent" node (root level is num_nodes). level = num_nodes; ## num_nodes - max_ht is the height of this graph. max_ht = num_nodes; ## Main stack - each item consists of two numbers - the number of ## node and the number it's of parent node on the top of stack ## there is "parent node". stk = [-1, 0]; ## Number of vertices s in the top-level separator. s = 0; ## Flag which says if we are in top level separator. top_level = 1; ## The top of the stack. while (par_number != -1) if (start(par_number+1) < stop(par_number+1)) idx = vec_of_child(start(par_number+1) : stop(par_number+1) - 1); else idx = zeros (1, 0); endif ## Add to idx the vector of parent descendants. stk = [stk; [idx', ones(fliplr(size(idx))) * par_number]]; ## We are in top level separator when we have one child and the ## flag is 1 if (columns (idx) == 1 && top_level == 1) s += 1; else ## We aren't in top level separator now. top_level = 0; endif ## If there is not any descendant of "parent node": if (stk(end,2) != par_number) left_most += 1; x_coordinate_r(par_number) = left_most; max_ht = min (max_ht, level); if (length (stk) > 1 && find ((shift (stk,1) - stk) == 0) > 1 && stk(end,2) != stk(end-1,2)) ## Return to the nearest branching the position to return ## position is the position on the stack, where should be ## started further search (there are two nodes which has the ## same parent node). position = (find ((shift (stk(:,2), 1) - stk(:,2)) == 0))(end) + 1; par_number_vec = stk(position:end,2); ## The vector of removed nodes (the content of stack form ## position to end). level += length (par_number_vec); ## The level have to be decreased. x_coordinate_r(par_number_vec) = left_most; stk(position:end,:) = []; endif ## Remove the next node from "searched branch". stk(end,:) = []; ## Choose new "parent node". par_number = stk(end,1); ## If there is another branch start to search it. if (par_number != -1) y_coordinate(par_number) = level; x_coordinate_l(par_number) = left_most + 1; endif else ## There were descendants of "parent nod" choose the last of ## them and go on through it. level -= 1; par_number = stk(end,1); y_coordinate(par_number) = level; x_coordinate_l(par_number) = left_most + 1; endif endwhile ## Calculate the x coordinates (the known values are the position ## of most left and most right descendants). x_coordinate = (x_coordinate_l + x_coordinate_r) / 2; height = num_nodes - max_ht - 1; endfunction %!test %! % Compute a simple tree layout %! [x, y, h, s] = treelayout ([0, 1, 2, 2]); %! assert (x, [1.5, 1.5, 2, 1]); %! assert (y, [3, 2, 1, 1]); %! assert (h, 2); %! assert (s, 2); %!test %! % Compute a simple tree layout with defined postorder permutation %! [x, y, h, s] = treelayout ([0, 1, 2, 2], [1, 2, 4, 3]); %! assert (x, [1.5, 1.5, 1, 2]); %! assert (y, [3, 2, 1, 1]); %! assert (h, 2); %! assert (s, 2); %!test %! % Compute a simple tree layout with defined postorder permutation %! [x, y, h, s] = treelayout ([0, 1, 2, 2], [4, 2, 3, 1]); %! assert (x, [0, 0, 0, 1]); %! assert (y, [0, 0, 0, 3]); %! assert (h, 0); %! assert (s, 1);