Mercurial > hg > octave-nkf

comparison scripts/sparse/treeplot.m @ 8507:cadc73247d65

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
style fixes
author John W. Eaton <jwe@octave.org>
date Tue, 13 Jan 2009 14:08:36 -0500
parents a1dbe9d80eee
children eb63fbe60fab
comparison
equal deleted inserted replaced
8506:bc982528de11 8507:cadc73247d65
15 ## You should have received a copy of the GNU General Public License 15 ## You should have received a copy of the GNU General Public License
16 ## along with Octave; see the file COPYING. If not, see 16 ## along with Octave; see the file COPYING. If not, see
17 ## <http://www.gnu.org/licenses/>. 17 ## <http://www.gnu.org/licenses/>.
18 18
19 ## -*- texinfo -*- 19 ## -*- texinfo -*-
20 ## @deftypefn {Function File} {} treeplot (@var{Tree}) 20 ## @deftypefn {Function File} {} treeplot (@var{tree})
21 ## @deftypefnx {Function File} {} treeplot (@var{Tree}, @var{LineStyle}, @var{EdgeStyle}) 21 ## @deftypefnx {Function File} {} treeplot (@var{tree}, @var{line_style}, @var{edge_style})
22 ## Produces a graph of tree or forest. The first argument is vector of 22 ## Produces a graph of tree or forest. The first argument is vector of
23 ## predecessors, optional parameters @var{LineStyle} and @var{EdgeStyle} 23 ## predecessors, optional parameters @var{line_style} and @var{edge_style}
24 ## define the output style. The complexity of the algorithm is O(n) in 24 ## define the output style. The complexity of the algorithm is O(n) in
25 ## terms of is time and memory requirements. 25 ## terms of is time and memory requirements.
26 ## @seealso{etreeplot, gplot} 26 ## @seealso{etreeplot, gplot}
27 ## @end deftypefn 27 ## @end deftypefn
28 28
29 function treeplot (Tree, NodeS, EdgeS) 29 function treeplot (tree, node_s, edge_s)
30 30
31 if (nargin < 1 || nargin > 3 || nargout > 0) 31 if (nargin < 1 || nargin > 3 || nargout > 0)
32 print_usage (); 32 print_usage ();
33 else 33 else
34 if (! ismatrix (Tree) || rows (Tree) != 1 || ! isnumeric (Tree) 34 if (! ismatrix (tree) || rows (tree) != 1 || ! isnumeric (tree)
35 || ! isvector (Tree) || any (Tree > length (Tree))) 35 || ! isvector (tree) || any (tree > length (tree)))
36 error ("treeplot: the first input argument must be a vector of predecessors"); 36 error ("treeplot: the first input argument must be a vector of predecessors");
37 else 37 else
38 ## the inicialization of node end edge style 38 ## The initialization of node end edge style.
39 NodeStyle = "k*"; 39 node_style = "k*";
40 EdgeStyle = "r"; 40 edge_style = "r";
41 if (nargin > 2) 41 if (nargin > 2)
42 EdgeStyle = EdgeS; 42 edge_style = edge_s;
43 if (nargin > 1) 43 if (nargin > 1)
44 if (length (findstr (NodeS, "*")) == 0 44 if (length (findstr (node_s, "*")) == 0
45 && length (findstr (NodeS, "+")) == 0 45 && length (findstr (node_s, "+")) == 0
46 && length (findstr (NodeS, "x")) == 0) 46 && length (findstr (node_s, "x")) == 0)
47 NodeStyle = [NodeS, "o"]; 47 node_style = [node_s, "o"];
48 else 48 else
49 NodeStyle = NodeS; 49 node_style = node_s;
50 endif 50 endif
51 endif 51 endif
52 endif 52 endif
53 53
54 Tree = Tree(:)'; ## make it a row vector 54 ## Make it a row vector.
55 NodNumber = length (Tree); ## the count of nodes of the graph 55 tree = tree(:)';
56 ChildNumber = zeros (1, NodNumber+1); ## the number of childrens 56
57 ## The count of nodes of the graph.
58 num_nodes = length (tree);
59
60 ## The number of children.
61 num_children = zeros (1, num_nodes+1);
57 62
58 for i = 1:NodNumber 63 for i = 1:num_nodes
59 ## VecOfChild is helping vector which is used to speed up the 64 ## VEC_OF_CHILD is helping vector which is used to speed up the
60 ## choose of descendant nodes 65 ## choose of descendant nodes.
61 66
62 ChildNumber(Tree(i)+1) = ChildNumber(Tree(i)+1) + 1; 67 num_children(tree(i)+1) = num_children(tree(i)+1) + 1;
63 endfor 68 endfor
64 Pos = 1; 69 pos = 1;
65 for i = 1:NodNumber+1 70 start = zeros (1, num_nodes+1);
66 Start(i) = Pos; 71 xhelp = zeros (1, num_nodes+1);
67 Help(i) = Pos; 72 stop = zeros (1, num_nodes+1);
68 Pos += ChildNumber(i); 73 for i = 1:num_nodes+1
69 Stop(i) = Pos; 74 start(i) = pos;
75 xhelp(i) = pos;
76 pos += num_children(i);
77 stop(i) = pos;
70 endfor 78 endfor
71 for i = 1:NodNumber 79 for i = 1:num_nodes
72 VecOfChild(Help(Tree(i)+1)) = i; 80 vec_of_child(xhelp(tree(i)+1)) = i;
73 Help(Tree(i)+1) = Help(Tree(i)+1)+1; 81 xhelp(tree(i)+1) = xhelp(tree(i)+1)+1;
74 endfor 82 endfor
75 83
76 ## the number of "parent" (actual) node (it's descendants will be 84 ## The number of "parent" (actual) node (it's descendants will be
77 ## browse in the next iteration) 85 ## browse in the next iteration).
78 ParNumber = 0; 86 par_number = 0;
79 87
80 ## the x-coordinate of the left most descendant of "parent node" 88 ## The x-coordinate of the left most descendant of "parent node"
81 ## this value is increased in each leaf 89 ## this value is increased in each leaf.
82 LeftMost = 0; 90 left_most = 0;
83 91
84 ## the level of "parent" node (root level is NodNumber) 92 ## The level of "parent" node (root level is num_nodes).
85 Level = NodNumber; 93 level = num_nodes;
86 94
87 ## NodNumber - Max is the height of this graph 95 ## Num_nodes - max_ht is the height of this graph.
88 Max = NodNumber; 96 max_ht = num_nodes;
89 97
90 ## main stack - each item consists of two numbers - the number of 98 ## 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 99 ## node and the number it's of parent node on the top of stack
92 ## there is "parent node" 100 ## there is "parent node".
93 St = [-1,0]; 101 stk = [-1, 0];
94 102
95 ## stack which is use to draw the graph edge (it have to be 103 ## Stack which is use to draw the graph edge (it have to be
96 ## uninterupted line) 104 ## uninterupted line).
97 Skelet = 0; 105 skelet = 0;
98 106
99 ## the top of the stack 107 ## The top of the stack.
100 while (ParNumber != -1) 108 while (par_number != -1)
101 if (Start(ParNumber+1) < Stop(ParNumber+1)) 109 if (start(par_number+1) < stop(par_number+1))
102 idx = VecOfChild(Start(ParNumber+1):Stop(ParNumber+1)-1); 110 idx = vec_of_child(start(par_number+1):stop(par_number+1)-1);
103 else 111 else
104 idx = zeros (1, 0); 112 idx = zeros (1, 0);
105 endif 113 endif
106 ## add to idx the vector of parent descendants 114 ## Add to idx the vector of parent descendants.
107 St = [St ; [idx', ones(fliplr(size(idx)))*ParNumber]]; 115 stk = [stk; [idx', ones(fliplr(size(idx)))*par_number]];
108 ## add to stack the records relevant to parent descandant s 116 ## Add to stack the records relevant to parent descandant s.
109 if (ParNumber != 0) 117 if (par_number != 0)
110 Skelet = [Skelet; ([ones(size(idx))*ParNumber; idx])(:)]; 118 skelet = [skelet; ([ones(size(idx))*par_number; idx])(:)];
111 endif 119 endif
112 120
113 ## if there is not any descendant of "parent node": 121 ## If there is not any descendant of "parent node":
114 if (St(end,2) != ParNumber) 122 if (stk(end,2) != par_number)
115 LeftMost = LeftMost + 1; 123 left_most++;
116 XCoordinateR(ParNumber) = LeftMost; 124 x_coordinate_r(par_number) = left_most;
117 Max = min (Max, Level); 125 max_ht = min (max_ht, level);
118 if ((length(St)>1) && (find((shift(St,1)-St) == 0) >1) 126 if (length(stk) > 1 && find ((shift(stk,1)-stk) == 0) > 1
119 && St(end,2) != St(end-1,2)) 127 && stk(end,2) != stk(end-1,2))
120 ## return to the nearest branching the position to return 128 ## Return to the nearest branching the position to return
121 ## position is the position on the stack, where should be 129 ## position is the position on the stack, where should be
122 ## started further search (there are two nodes which has the 130 ## started further search (there are two nodes which has the
123 ## same parent node) 131 ## same parent node).
124 Position = (find((shift(St(:,2),1)-St(:,2)) == 0))(end)+1; 132 position = (find ((shift(stk(:,2),1)-stk(:,2)) == 0))(end) + 1;
125 ParNumberVec = St(Position:end,2); 133 par_number_vec = stk(position:end,2);
126 ## the vector of removed nodes (the content of stack form 134 ## The vector of removed nodes (the content of stack form
127 ## position to end) 135 ## position to end).
128 Skelet = [Skelet; flipud(ParNumberVec)]; 136 skelet = [skelet; flipud(par_number_vec)];
129 Level = Level + length(ParNumberVec); 137 level += length (par_number_vec);
130 ## the level have to be decreased 138 ## The level have to be decreased.
131 XCoordinateR(ParNumberVec) = LeftMost; 139 x_coordinate_r(par_number_vec) = left_most;
132 St(Position:end,:) = []; 140 stk(position:end,:) = [];
133 endif 141 endif
134 ## remove the next node from "searched branch" 142 ## Remove the next node from "searched branch".
135 St(end,:) = []; 143 stk(end,:) = [];
136 ## choose new "parent node" 144 ## Choose new "parent node".
137 ParNumber = St(end,1); 145 par_number = stk(end,1);
138 ## if there is another branch start to search it 146 ## If there is another branch start to search it.
139 if (ParNumber != -1) 147 if (par_number != -1)
140 Skelet = [Skelet ; St(end,2); ParNumber]; 148 skelet = [skelet; stk(end,2); par_number];
141 YCoordinate(ParNumber) = Level; 149 y_coordinate(par_number) = level;
142 XCoordinateL(ParNumber) = LeftMost + 1; 150 x_coordinate_l(par_number) = left_most + 1;
143 endif 151 endif
144 else 152 else
145 ## there were descendants of "parent nod" choose the last of 153 ## There were descendants of "parent nod" choose the last of
146 ## them and go on through it 154 ## them and go on through it.
147 Level--; 155 level--;
148 ParNumber = St(end,1); 156 par_number = stk(end,1);
149 YCoordinate(ParNumber) = Level; 157 y_coordinate(par_number) = level;
150 XCoordinateL(ParNumber) = LeftMost+1; 158 x_coordinate_l(par_number) = left_most + 1;
151 endif 159 endif
152 endwhile 160 endwhile
153 161
154 ## calculate the x coordinates (the known values are the position 162 ## Calculate the x coordinates (the known values are the position
155 ## of most left and most right descendants) 163 ## of most left and most right descendants).
156 XCoordinate = (XCoordinateL + XCoordinateR) / 2; 164 x_coordinate = (x_coordinate_l + x_coordinate_r) / 2;
157 165
158 hold ("on"); 166 ## FIXME -- we should probably stuff all the arguments into a cell
159 167 ## array and make a single call to plot here so we can avoid
160 ## plot grah nodes 168 ## setting the hold state...
161 plot (XCoordinate,YCoordinate,NodeStyle); 169
162 170 hold_is_on = ishold ();
163 ## helping command - usable for plotting edges 171 unwind_protect
164 Skelet = [Skelet; 0]; 172 hold ("on");
165 173
166 ## draw graph edges 174 ## Plot grah nodes.
167 idx = find (Skelet == 0); 175 plot (x_coordinate, y_coordinate, node_style);
168 176
169 ## plot each tree component in one loop 177 ## Helping command - usable for plotting edges
170 for i = 2:length(idx) 178 skelet = [skelet; 0];
171 ## tree component start 179
172 istart = idx(i-1) + 1; 180 ## Draw graph edges.
173 ## tree component end 181 idx = find (skelet == 0);
174 istop = idx(i) - 1; 182
175 if (istop - istart < 1) 183 ## Plot each tree component in one loop.
176 continue; 184 for i = 2:length(idx)
177 endif 185 ## Tree component start.
178 plot (XCoordinate(Skelet(istart:istop)), 186 istart = idx(i-1) + 1;
179 YCoordinate(Skelet(istart:istop)), EdgeStyle) 187 ## Tree component end.
180 endfor 188 istop = idx(i) - 1;
181 189 if (istop - istart < 1)
182 ## set axis and graph size 190 continue;
183 axis ([0.5, LeftMost+0.5, Max-0.5, NodNumber-0.5], "nolabel"); 191 endif
184 192 plot (x_coordinate(skelet(istart:istop)),
185 hold ("off"); 193 y_coordinate(skelet(istart:istop)), edge_style)
194 endfor
195
196 ## Set axis and graph size.
197 axis ([0.5, left_most+0.5, max_ht-0.5, num_nodes-0.5], "nolabel");
198
199 unwind_protect_cleanup
200 if (! hold_is_on)
201 hold ("off");
202 endif
203 end_unwind_protect
186 204
187 endif 205 endif
188 endif 206 endif
189 endfunction 207 endfunction
190 208