X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;ds=sidebyside;f=octave_packages%2Fm%2Fsparse%2Ftreelayout.m;fp=octave_packages%2Fm%2Fsparse%2Ftreelayout.m;h=fbe0d0ac1ca10175fac1ae13997a483f40337173;hb=1c0469ada9531828709108a4882a751d2816994a;hp=0000000000000000000000000000000000000000;hpb=63de9f36673d49121015e3695f2c336ea92bc278;p=CreaPhase.git diff --git a/octave_packages/m/sparse/treelayout.m b/octave_packages/m/sparse/treelayout.m new file mode 100644 index 0000000..fbe0d0a --- /dev/null +++ b/octave_packages/m/sparse/treelayout.m @@ -0,0 +1,227 @@ +## Copyright (C) 2008-2012 Ivana Varekova & Radek Salac +## +## 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 +## . + +## -*- texinfo -*- +## @deftypefn {Function File} {} treelayout (@var{tree}) +## @deftypefnx {Function File} {} treelayout (@var{tree}, @var{permutation}) +## treelayout lays out a tree or a forest. The first argument @var{tree} is a +## vector of +## predecessors, optional 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 || nargin > 2 || nargout > 4) + 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"); + else + ## 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 (it's 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++; + 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++; + 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--; + 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; + endif +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);