Mercurial > hg > octave-lyh

comparison scripts/sparse/treeplot.m @ 5576:7e008607a86e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[project @ 2005-12-13 19:05:54 by jwe]
author jwe
date Tue, 13 Dec 2005 19:05:55 +0000
parents
children 591e9accd44c
comparison
equal deleted inserted replaced
5575:9b4d9dbe88f7 5576:7e008607a86e
1 ## Copyright (C) 2005 Ivana Varekova
2 ##
3 ## This program is free software; you can redistribute it and/or modify
4 ## it under the terms of the GNU General Public License as published by
5 ## the Free Software Foundation; either version 2 of the License, or
6 ## (at your option) any later version.
7 ##
8 ## This program is distributed in the hope that it will be useful,
9 ## but WITHOUT ANY WARRANTY; without even the implied warranty of
10 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 ## GNU General Public License for more details.
12 ##
13 ## You should have received a copy of the GNU General Public License
14 ## along with this program; if not, write to the Free Software
15 ## Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
16 ## 02110-1301 USA
17
18 ## -*- texinfo -*-
19 ## @deftypefn {Function File} {} treeplot (@var{Tree})
20 ## @deftypefnx {Function File} {} treeplot (@var{Tree}, @var{LineStyle}, @var{EdgeStyle})
21 ## Produces a graph of tree or forest. The first argument is vector of
22 ## predecessors, optional parametres @var{LineStyle} and @var{EdgeStyle}
23 ## define the output style. The complexity of the algorithm is O(n) in
24 ## terms of is time and memory requirements.
25 ## @end deftypefn
26 ## @seealso{etreeplot,gplot}
27
28 function treeplot (Tree, NodeS, EdgeS)
29
30 if (nargin < 1 || nargin > 3 || nargout > 0)
31 error ("treeplot: wrong number of input/output arguments");
32 else
33 if (!ismatrix(Tree) || size(Tree)(1) != 1 || !isnumeric(Tree)
34 || !isvector(Tree) || any(Tree>length (Tree)))
35 error ("treeplot: the first input argument must be a vector of predecessors");
36 else
37
38 NodeStyle = "0*;;"; ## the inicialization of node end edge style
39 EdgeStyle = "1;;";
40 if (nargin > 2)
41 EdgeStyle = EdgeS;
42 if (nargin > 1)
43 if ((length(findstr(NodeS,"*")) == 0)
44 && (length(findstr(NodeS,"+")) == 0)
45 && (length(findstr(NodeS,"x")) == 0) )
46 NodeStyle = [NodeS,"o"];
47 else
48 NodeStyle = NodeS;
49 endif
50 endif
51 endif
52
53 Tree = Tree(:)'; ## make it a row vector
54 NodNumber = length (Tree); ## the count of nodes of the graph
55 ChildNumber = zeros (1,NodNumber+1); ## the number of childrens
56
57 for i = 1:(NodNumber) ## VecOfChild is helping vector which is used to speed up the
58 ## choose of descendant nodes
59
60 ChildNumber(Tree(i)+1) = ChildNumber(Tree(i)+1) + 1;
61 endfor
62 Pos = 1;
63 for i = 1:(NodNumber+1)
64 Start(i) = Pos;
65 Help(i) = Pos;
66 Pos = Pos + ChildNumber(i);
67 Stop(i) = Pos;
68 endfor
69 for i = 1:NodNumber
70 VecOfChild(Help(Tree(i)+1)) = i;
71 Help(Tree(i)+1)=Help(Tree(i)+1)+1;
72 endfor ## VecOfChild is helping vector which is used to speed up the
73 ## choose of descendant nodes
74
75 ParNumber = 0; ## the number of "parent" (actual) node (it's descendants will
76 ## be browse in the next iteration)
77 LeftMost = 0; ## the x-coordinate of the left most descendant of "parent node"
78 ## this value is increased in each leaf
79 Level = NodNumber; ## the level of "parent" node (root level is NodNumber)
80 Max = NodNumber; ## NodNumber - Max is the height of this graph
81 St = [-1,0]; ## main stack - each item consists of two numbers - the number of node and
82 ## the number it's of parent node
83 ## on the top of stack there is "parent node"
84 Skelet = 0; ## stack which is use to draw the graph edge (it
85 ## have to be uninterupted line)
86 while (ParNumber!=-1) ## the top of the stack
87 if (Start(ParNumber+1) < Stop(ParNumber+1))
88 idx = VecOfChild(Start(ParNumber+1):Stop(ParNumber+1)-1);
89 else
90 idx = zeros(1,0);
91 endif ## add to idx the vector of parent descendants
92 St = [St ; [idx', ones(fliplr(size(idx)))*ParNumber]];
93 ## add to stack the records relevant to parent descandant s
94 if (ParNumber != 0)
95 Skelet = [Skelet ; ([ones(size(idx))*ParNumber; idx])(:)];
96 endif
97 if (St(end,2) != ParNumber) ## if there is not any descendant of "parent node":
98 LeftMost = LeftMost + 1;
99 XCoordinateR(ParNumber) = LeftMost;
100 Max = min (Max, Level);
101 if ((length(St)>1) && (find((shift(St,1)-St) == 0) >1) && St(end,2) != St(end-1,2))
102 ## return to the nearest branching
103 Position = (find((shift(St(:,2),1)-St(:,2)) == 0))(end)+1; ## the position to return
104 ## position is the position on the stack, where should be started
105 ## further search (there are two nodes which has the same parent node)
106 ParNumberVec = St(Position:end,2);
107 ## the vector of removed nodes (the content of stack form position to end)
108 Skelet = [Skelet; flipud(ParNumberVec)];
109 Level = Level + length(ParNumberVec);
110 ## the level have to be decreased
111 XCoordinateR(ParNumberVec) = LeftMost;
112 St(Position:end,:) = [];
113 endif
114 St(end,:) = []; ## remove the next node from "searched branch"
115 ParNumber = St(end,1); ## choose new "parent node"
116 if (ParNumber != -1) ## if there is another branch start to search it
117 Skelet = [Skelet ; St(end,2); ParNumber];
118 YCoordinate(ParNumber) = Level;
119 XCoordinateL(ParNumber) = LeftMost + 1;
120 endif
121 else ## there were descendants of "parent nod"
122 Level = Level - 1; ## choose the last of them and go on through it
123 ParNumber = St(end,1);
124 YCoordinate(ParNumber) = Level;
125 XCoordinateL(ParNumber) = LeftMost+1;
126 endif
127 endwhile
128
129 XCoordinate = (XCoordinateL + XCoordinateR) / 2; ## calculate the x coordinates
130 ## (the known values are the position of most left and most right descendants)
131
132 axis ([0.5 LeftMost+0.5 Max-0.5 NodNumber-0.5], "nolabel"); ## set axis and graph size
133
134 plot (XCoordinate,YCoordinate,NodeStyle); ## plot grah nodes
135 hold on;
136
137 Skelet = [Skelet; 0]; ## helping command - usable for plotting edges
138
139 idx = find (Skelet == 0); ## draw graph edges
140
141 for i = 2:length(idx) ## plot each tree component in one loop
142 istart = idx(i-1) + 1; ## tree component start
143 istop = idx(i) - 1; ## tree component end
144 if (istop - istart < 1)
145 continue;
146 endif
147 plot (XCoordinate(Skelet(istart:istop)),
148 YCoordinate(Skelet(istart:istop)), EdgeStyle)
149 endfor
150
151 hold off;
152
153 endif
154 endif
155 St;
156 Skelet;
157 endfunction
158
159 %!demo
160 %! % Plot a simple tree plot
161 %! treeplot([2 4 2 0 6 4 6])
162
163 %!demo
164 %! % Plot a simple tree plot defining the edge and node styles
165 %! treeplot([2 4 2 0 6 4 6], "b+", "g")