Mercurial > hg > octave-lyh

comparison scripts/sparse/treeplot.m @ 6498:2c85044aa63f

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