1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|
5 |
|
|
6 |
|
|
7 |
|
|
8 |
|
|
9 |
|
|
10 |
|
|
11 |
|
|
12 |
|
|
13 |
|
|
14 |
|
|
15 |
|
|
16 |
|
|
17 |
|
|
18 |
|
|
19 |
|
|
20 |
|
|
21 |
|
package jalview.analysis; |
22 |
|
|
23 |
|
import java.util.BitSet; |
24 |
|
import java.util.Vector; |
25 |
|
|
26 |
|
import jalview.datamodel.BinaryNode; |
27 |
|
import jalview.datamodel.SequenceNode; |
28 |
|
import jalview.math.MatrixI; |
29 |
|
|
|
|
| 74.3% |
Uncovered Elements: 27 (105) |
Complexity: 26 |
Complexity Density: 0.37 |
|
30 |
|
public abstract class TreeEngine |
31 |
|
{ |
32 |
|
|
33 |
|
protected Vector<BitSet> clusters; |
34 |
|
|
35 |
|
protected BitSet done; |
36 |
|
|
37 |
|
protected int noseqs; |
38 |
|
|
39 |
|
protected int noClus; |
40 |
|
|
41 |
|
protected MatrixI distances; |
42 |
|
|
43 |
|
protected double ri; |
44 |
|
|
45 |
|
protected double rj; |
46 |
|
|
47 |
|
protected Vector<BinaryNode> node; |
48 |
|
|
49 |
|
BinaryNode maxdist; |
50 |
|
|
51 |
|
double maxDistValue; |
52 |
|
|
53 |
|
protected int mini; |
54 |
|
|
55 |
|
protected int minj; |
56 |
|
|
57 |
|
protected BinaryNode top; |
58 |
|
|
59 |
|
protected int ycount; |
60 |
|
|
61 |
|
double maxheight; |
62 |
|
|
63 |
|
|
64 |
|
|
65 |
|
|
66 |
|
@param |
67 |
|
@param |
68 |
|
|
69 |
|
@return |
70 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (13) |
Complexity: 6 |
Complexity Density: 0.86 |
|
71 |
124 |
protected double findr(int i, int j)... |
72 |
|
{ |
73 |
124 |
double tmp = 1; |
74 |
|
|
75 |
7008 |
for (int k = 0; k < noseqs; k++) |
76 |
|
{ |
77 |
6884 |
if ((k != i) && (k != j) && (!done.get(k))) |
78 |
|
{ |
79 |
3318 |
tmp = tmp + distances.getValue(i, k); |
80 |
|
} |
81 |
|
} |
82 |
|
|
83 |
124 |
if (noClus > 2) |
84 |
|
{ |
85 |
120 |
tmp = tmp / (noClus - 2); |
86 |
|
} |
87 |
|
|
88 |
124 |
return tmp; |
89 |
|
} |
90 |
|
|
91 |
|
|
92 |
|
|
93 |
|
|
94 |
|
@param |
95 |
|
@param |
96 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (16) |
Complexity: 1 |
Complexity Density: 0.06 |
|
97 |
62 |
protected void joinClusters(final int i, final int j)... |
98 |
|
{ |
99 |
62 |
double dist = distances.getValue(i, j); |
100 |
|
|
101 |
62 |
ri = findr(i, j); |
102 |
62 |
rj = findr(j, i); |
103 |
|
|
104 |
62 |
findClusterDistance(i, j); |
105 |
|
|
106 |
62 |
BinaryNode sn = new BinaryNode(); |
107 |
|
|
108 |
62 |
sn.setLeft((node.elementAt(i))); |
109 |
62 |
sn.setRight((node.elementAt(j))); |
110 |
|
|
111 |
62 |
BinaryNode tmpi = (node.elementAt(i)); |
112 |
62 |
BinaryNode tmpj = (node.elementAt(j)); |
113 |
|
|
114 |
62 |
findNewDistances(tmpi, tmpj, dist); |
115 |
|
|
116 |
62 |
tmpi.setParent(sn); |
117 |
62 |
tmpj.setParent(sn); |
118 |
|
|
119 |
62 |
node.setElementAt(sn, i); |
120 |
|
|
121 |
|
|
122 |
|
|
123 |
|
|
124 |
|
|
125 |
62 |
clusters.get(i).or(clusters.get(j)); |
126 |
62 |
clusters.get(j).clear(); |
127 |
62 |
done.set(j); |
128 |
|
} |
129 |
|
|
130 |
|
protected abstract void findNewDistances(BinaryNode nodei, |
131 |
|
BinaryNode nodej, double previousDistance); |
132 |
|
|
133 |
|
|
134 |
|
|
135 |
|
|
136 |
|
|
137 |
|
|
138 |
|
@param |
139 |
|
@param |
140 |
|
|
141 |
|
protected abstract void findClusterDistance(int i, int j); |
142 |
|
|
143 |
|
|
144 |
|
|
145 |
|
|
146 |
|
|
147 |
|
@param |
148 |
|
|
|
|
| 86.7% |
Uncovered Elements: 2 (15) |
Complexity: 5 |
Complexity Density: 0.56 |
|
149 |
126 |
protected void findMaxDist(BinaryNode nd)... |
150 |
|
{ |
151 |
126 |
if (nd == null) |
152 |
|
{ |
153 |
0 |
return; |
154 |
|
} |
155 |
|
|
156 |
126 |
if ((nd.left() == null) && (nd.right() == null)) |
157 |
|
{ |
158 |
64 |
double dist = nd.dist; |
159 |
|
|
160 |
64 |
if (dist > maxDistValue) |
161 |
|
{ |
162 |
10 |
maxdist = nd; |
163 |
10 |
maxDistValue = dist; |
164 |
|
} |
165 |
|
} |
166 |
|
else |
167 |
|
{ |
168 |
62 |
findMaxDist((BinaryNode) nd.left()); |
169 |
62 |
findMaxDist((BinaryNode) nd.right()); |
170 |
|
} |
171 |
|
} |
172 |
|
|
173 |
|
|
174 |
|
|
175 |
|
|
176 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (13) |
Complexity: 2 |
Complexity Density: 0.18 |
|
177 |
2 |
protected void cluster()... |
178 |
|
{ |
179 |
62 |
while (noClus > 2) |
180 |
|
{ |
181 |
60 |
findMinDistance(); |
182 |
|
|
183 |
60 |
joinClusters(mini, minj); |
184 |
|
|
185 |
60 |
noClus--; |
186 |
|
} |
187 |
|
|
188 |
2 |
int rightChild = done.nextClearBit(0); |
189 |
2 |
int leftChild = done.nextClearBit(rightChild + 1); |
190 |
|
|
191 |
2 |
joinClusters(leftChild, rightChild); |
192 |
2 |
top = (node.elementAt(leftChild)); |
193 |
|
|
194 |
2 |
reCount(top); |
195 |
2 |
findHeight(top); |
196 |
2 |
findMaxDist(top); |
197 |
|
} |
198 |
|
|
199 |
|
|
200 |
|
|
201 |
|
|
202 |
|
|
203 |
|
@return |
204 |
|
|
205 |
|
protected abstract double findMinDistance(); |
206 |
|
|
207 |
|
|
208 |
|
|
209 |
|
|
210 |
|
@param |
211 |
|
|
212 |
|
|
|
|
| 86.7% |
Uncovered Elements: 2 (15) |
Complexity: 4 |
Complexity Density: 0.36 |
|
213 |
126 |
protected void _reCount(BinaryNode nd)... |
214 |
|
{ |
215 |
|
|
216 |
|
|
217 |
|
|
218 |
|
|
219 |
|
|
220 |
|
|
221 |
126 |
if (nd == null) |
222 |
|
{ |
223 |
0 |
return; |
224 |
|
} |
225 |
|
|
226 |
|
|
227 |
126 |
if ((nd.left() != null) && (nd.right() != null)) |
228 |
|
{ |
229 |
|
|
230 |
62 |
_reCount(nd.left()); |
231 |
62 |
_reCount((BinaryNode) nd.right()); |
232 |
|
|
233 |
62 |
BinaryNode l = nd.left(); |
234 |
62 |
BinaryNode r = nd.right(); |
235 |
|
|
236 |
62 |
nd.count = l.count + r.count; |
237 |
62 |
nd.ycount = (l.ycount + r.ycount) / 2; |
238 |
|
} |
239 |
|
else |
240 |
|
{ |
241 |
64 |
nd.count = 1; |
242 |
64 |
nd.ycount = ycount++; |
243 |
|
} |
244 |
|
|
245 |
|
} |
246 |
|
|
247 |
|
|
248 |
|
|
249 |
|
|
250 |
|
@param |
251 |
|
|
252 |
|
|
253 |
|
@return |
254 |
|
|
|
|
| 0% |
Uncovered Elements: 22 (22) |
Complexity: 6 |
Complexity Density: 0.43 |
|
255 |
0 |
double findHeight(BinaryNode nd)... |
256 |
|
{ |
257 |
0 |
if (nd == null) |
258 |
|
{ |
259 |
0 |
return maxheight; |
260 |
|
} |
261 |
|
|
262 |
0 |
if ((nd.left() == null) && (nd.right() == null)) |
263 |
|
{ |
264 |
0 |
nd.height = ((BinaryNode) nd.parent()).height + nd.dist; |
265 |
|
|
266 |
0 |
if (nd.height > maxheight) |
267 |
|
{ |
268 |
0 |
return nd.height; |
269 |
|
} |
270 |
|
else |
271 |
|
{ |
272 |
0 |
return maxheight; |
273 |
|
} |
274 |
|
} |
275 |
|
else |
276 |
|
{ |
277 |
0 |
if (nd.parent() != null) |
278 |
|
{ |
279 |
0 |
nd.height = ((BinaryNode) nd.parent()).height + nd.dist; |
280 |
|
} |
281 |
|
else |
282 |
|
{ |
283 |
0 |
maxheight = 0; |
284 |
0 |
nd.height = (float) 0.0; |
285 |
|
} |
286 |
|
|
287 |
0 |
maxheight = findHeight((BinaryNode) (nd.left())); |
288 |
0 |
maxheight = findHeight((BinaryNode) (nd.right())); |
289 |
|
} |
290 |
|
|
291 |
0 |
return maxheight; |
292 |
|
} |
293 |
|
|
294 |
|
|
295 |
|
|
296 |
|
|
297 |
|
@param |
298 |
|
|
299 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (2) |
Complexity: 1 |
Complexity Density: 0.5 |
|
300 |
2 |
void reCount(BinaryNode nd)... |
301 |
|
{ |
302 |
2 |
ycount = 0; |
303 |
|
|
304 |
|
|
305 |
2 |
_reCount(nd); |
306 |
|
} |
307 |
|
|
308 |
|
|
309 |
|
|
310 |
|
|
311 |
|
@return |
312 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (1) |
Complexity: 1 |
Complexity Density: 1 |
|
313 |
6 |
public BinaryNode getTopNode()... |
314 |
|
{ |
315 |
6 |
return top; |
316 |
|
} |
317 |
|
|
318 |
|
} |