|
5576
|
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. |
|
5642
|
25 ## @seealso{etreeplot, gplot} |
|
5576
|
26 ## @end deftypefn |
|
|
27 |
|
|
28 function treeplot (Tree, NodeS, EdgeS) |
|
|
29 |
|
|
30 if (nargin < 1 || nargin > 3 || nargout > 0) |
|
6498
|
31 print_usage (); |
|
5576
|
32 else |
|
6498
|
33 if (! ismatrix (Tree) || rows (Tree) != 1 || ! isnumeric (Tree) |
|
|
34 || ! isvector (Tree) || any (Tree > length (Tree))) |
|
5576
|
35 error ("treeplot: the first input argument must be a vector of predecessors"); |
|
6498
|
36 else |
|
|
37 ## the inicialization of node end edge style |
|
|
38 NodeStyle = "0*;;"; |
|
5576
|
39 EdgeStyle = "1;;"; |
|
|
40 if (nargin > 2) |
|
|
41 EdgeStyle = EdgeS; |
|
|
42 if (nargin > 1) |
|
6498
|
43 if (length (findstr (NodeS, "*")) == 0 |
|
|
44 && length (findstr (NodeS, "+")) == 0 |
|
|
45 && length (findstr (NodeS, "x")) == 0) |
|
|
46 NodeStyle = [NodeS, "o"]; |
|
5576
|
47 else |
|
|
48 NodeStyle = NodeS; |
|
|
49 endif |
|
|
50 endif |
|
|
51 endif |
|
6498
|
52 |
|
5576
|
53 Tree = Tree(:)'; ## make it a row vector |
|
|
54 NodNumber = length (Tree); ## the count of nodes of the graph |
|
6498
|
55 ChildNumber = zeros (1, NodNumber+1); ## the number of childrens |
|
5576
|
56 |
|
6498
|
57 for i = 1:NodNumber |
|
|
58 ## VecOfChild is helping vector which is used to speed up the |
|
|
59 ## choose of descendant nodes |
|
5576
|
60 |
|
|
61 ChildNumber(Tree(i)+1) = ChildNumber(Tree(i)+1) + 1; |
|
|
62 endfor |
|
|
63 Pos = 1; |
|
6498
|
64 for i = 1:NodNumber+1 |
|
5576
|
65 Start(i) = Pos; |
|
|
66 Help(i) = Pos; |
|
6498
|
67 Pos += ChildNumber(i); |
|
5576
|
68 Stop(i) = Pos; |
|
|
69 endfor |
|
|
70 for i = 1:NodNumber |
|
|
71 VecOfChild(Help(Tree(i)+1)) = i; |
|
6498
|
72 Help(Tree(i)+1) = Help(Tree(i)+1)+1; |
|
|
73 endfor |
|
|
74 |
|
|
75 ## the number of "parent" (actual) node (it's descendants will be |
|
|
76 ## browse in the next iteration) |
|
|
77 ParNumber = 0; |
|
|
78 |
|
|
79 ## the x-coordinate of the left most descendant of "parent node" |
|
|
80 ## this value is increased in each leaf |
|
|
81 LeftMost = 0; |
|
|
82 |
|
|
83 ## the level of "parent" node (root level is NodNumber) |
|
|
84 Level = NodNumber; |
|
|
85 |
|
|
86 ## NodNumber - Max is the height of this graph |
|
|
87 Max = NodNumber; |
|
|
88 |
|
|
89 ## main stack - each item consists of two numbers - the number of |
|
|
90 ## node and the number it's of parent node on the top of stack |
|
|
91 ## there is "parent node" |
|
|
92 St = [-1,0]; |
|
|
93 |
|
|
94 ## stack which is use to draw the graph edge (it have to be |
|
|
95 ## uninterupted line) |
|
|
96 Skelet = 0; |
|
|
97 |
|
|
98 ## the top of the stack |
|
|
99 while (ParNumber != -1) |
|
5576
|
100 if (Start(ParNumber+1) < Stop(ParNumber+1)) |
|
|
101 idx = VecOfChild(Start(ParNumber+1):Stop(ParNumber+1)-1); |
|
|
102 else |
|
6498
|
103 idx = zeros (1, 0); |
|
|
104 endif |
|
|
105 ## add to idx the vector of parent descendants |
|
5576
|
106 St = [St ; [idx', ones(fliplr(size(idx)))*ParNumber]]; |
|
6498
|
107 ## add to stack the records relevant to parent descandant s |
|
5576
|
108 if (ParNumber != 0) |
|
6498
|
109 Skelet = [Skelet; ([ones(size(idx))*ParNumber; idx])(:)]; |
|
5576
|
110 endif |
|
6498
|
111 |
|
|
112 ## if there is not any descendant of "parent node": |
|
|
113 if (St(end,2) != ParNumber) |
|
5576
|
114 LeftMost = LeftMost + 1; |
|
|
115 XCoordinateR(ParNumber) = LeftMost; |
|
|
116 Max = min (Max, Level); |
|
6498
|
117 if ((length(St)>1) && (find((shift(St,1)-St) == 0) >1) |
|
|
118 && St(end,2) != St(end-1,2)) |
|
|
119 ## return to the nearest branching the position to return |
|
|
120 ## position is the position on the stack, where should be |
|
|
121 ## started further search (there are two nodes which has the |
|
|
122 ## same parent node) |
|
|
123 Position = (find((shift(St(:,2),1)-St(:,2)) == 0))(end)+1; |
|
5576
|
124 ParNumberVec = St(Position:end,2); |
|
6498
|
125 ## the vector of removed nodes (the content of stack form |
|
|
126 ## position to end) |
|
5576
|
127 Skelet = [Skelet; flipud(ParNumberVec)]; |
|
|
128 Level = Level + length(ParNumberVec); |
|
6498
|
129 ## the level have to be decreased |
|
5576
|
130 XCoordinateR(ParNumberVec) = LeftMost; |
|
|
131 St(Position:end,:) = []; |
|
|
132 endif |
|
6498
|
133 ## remove the next node from "searched branch" |
|
|
134 St(end,:) = []; |
|
|
135 ## choose new "parent node" |
|
|
136 ParNumber = St(end,1); |
|
|
137 ## if there is another branch start to search it |
|
|
138 if (ParNumber != -1) |
|
5576
|
139 Skelet = [Skelet ; St(end,2); ParNumber]; |
|
|
140 YCoordinate(ParNumber) = Level; |
|
|
141 XCoordinateL(ParNumber) = LeftMost + 1; |
|
|
142 endif |
|
6498
|
143 else |
|
|
144 ## there were descendants of "parent nod" choose the last of |
|
|
145 ## them and go on through it |
|
|
146 Level--; |
|
5576
|
147 ParNumber = St(end,1); |
|
|
148 YCoordinate(ParNumber) = Level; |
|
|
149 XCoordinateL(ParNumber) = LeftMost+1; |
|
|
150 endif |
|
|
151 endwhile |
|
|
152 |
|
6498
|
153 ## calculate the x coordinates (the known values are the position |
|
|
154 ## of most left and most right descendants) |
|
|
155 XCoordinate = (XCoordinateL + XCoordinateR) / 2; |
|
5576
|
156 |
|
5578
|
157 hold ("on"); |
|
6498
|
158 |
|
|
159 ## plot grah nodes |
|
|
160 plot (XCoordinate,YCoordinate,NodeStyle); |
|
5576
|
161 |
|
6498
|
162 ## helping command - usable for plotting edges |
|
|
163 Skelet = [Skelet; 0]; |
|
5576
|
164 |
|
6498
|
165 ## draw graph edges |
|
|
166 idx = find (Skelet == 0); |
|
5576
|
167 |
|
6498
|
168 ## plot each tree component in one loop |
|
|
169 for i = 2:length(idx) |
|
|
170 ## tree component start |
|
|
171 istart = idx(i-1) + 1; |
|
|
172 ## tree component end |
|
|
173 istop = idx(i) - 1; |
|
5576
|
174 if (istop - istart < 1) |
|
|
175 continue; |
|
|
176 endif |
|
|
177 plot (XCoordinate(Skelet(istart:istop)), |
|
|
178 YCoordinate(Skelet(istart:istop)), EdgeStyle) |
|
|
179 endfor |
|
|
180 |
|
6498
|
181 ## set axis and graph size |
|
|
182 axis ([0.5, LeftMost+0.5, Max-0.5, NodNumber-0.5], "nolabel"); |
|
|
183 |
|
5578
|
184 hold ("off"); |
|
5576
|
185 |
|
|
186 endif |
|
|
187 endif |
|
|
188 endfunction |
|
|
189 |
|
|
190 %!demo |
|
|
191 %! % Plot a simple tree plot |
|
|
192 %! treeplot([2 4 2 0 6 4 6]) |
|
|
193 |
|
|
194 %!demo |
|
|
195 %! % Plot a simple tree plot defining the edge and node styles |
|
|
196 %! treeplot([2 4 2 0 6 4 6], "b+", "g") |
