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