|
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) |
|
|
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 |
|
5578
|
135 hold ("on"); |
|
5576
|
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 |
|
5578
|
151 hold ("off"); |
|
5576
|
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") |
