Clover icon

Coverage Report

  1. Project Clover database Wed Nov 13 2024 16:21:17 GMT
  2. Package jalview.analysis

File TreeEngine.java

 

Coverage histogram

../../img/srcFileCovDistChart8.png
20% of files have more coverage

Code metrics

26
71
8
1
318
164
26
0.37
8.88
8
3.25

Classes

Class Line # Actions
TreeEngine 30 71 26
0.7428571674.3%
 

Contributing tests

This file is covered by 3 tests. .

Source view

1    /*
2    * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3    * Copyright (C) $$Year-Rel$$ The Jalview Authors
4    *
5    * This file is part of Jalview.
6    *
7    * Jalview is free software: you can redistribute it and/or
8    * modify it under the terms of the GNU General Public License
9    * as published by the Free Software Foundation, either version 3
10    * of the License, or (at your option) any later version.
11    *
12    * Jalview is distributed in the hope that it will be useful, but
13    * WITHOUT ANY WARRANTY; without even the implied warranty
14    * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15    * PURPOSE. See the GNU General Public License for more details.
16    *
17    * You should have received a copy of the GNU General Public License
18    * along with Jalview. If not, see <http://www.gnu.org/licenses/>.
19    * The Jalview Authors are detailed in the 'AUTHORS' file.
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   
 
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    * Calculates and returns r, whatever that is
65    *
66    * @param i
67    * @param j
68    *
69    * @return
70    */
 
71  144 toggle protected double findr(int i, int j)
72    {
73  144 double tmp = 1;
74   
75  7248 for (int k = 0; k < noseqs; k++)
76    {
77  7104 if ((k != i) && (k != j) && (!done.get(k)))
78    {
79  3408 tmp = tmp + distances.getValue(i, k);
80    }
81    }
82   
83  144 if (noClus > 2)
84    {
85  138 tmp = tmp / (noClus - 2);
86    }
87   
88  144 return tmp;
89    }
90   
91    /**
92    * Merges cluster(j) to cluster(i) and recalculates cluster and node distances
93    *
94    * @param i
95    * @param j
96    */
 
97  72 toggle protected void joinClusters(final int i, final int j)
98    {
99  72 double dist = distances.getValue(i, j);
100   
101  72 ri = findr(i, j);
102  72 rj = findr(j, i);
103   
104  72 findClusterDistance(i, j);
105   
106  72 BinaryNode sn = new BinaryNode();
107   
108  72 sn.setLeft((node.elementAt(i)));
109  72 sn.setRight((node.elementAt(j)));
110   
111  72 BinaryNode tmpi = (node.elementAt(i));
112  72 BinaryNode tmpj = (node.elementAt(j));
113   
114  72 findNewDistances(tmpi, tmpj, dist);
115   
116  72 tmpi.setParent(sn);
117  72 tmpj.setParent(sn);
118   
119  72 node.setElementAt(sn, i);
120   
121    /*
122    * move the members of cluster(j) to cluster(i)
123    * and mark cluster j as out of the game
124    */
125  72 clusters.get(i).or(clusters.get(j));
126  72 clusters.get(j).clear();
127  72 done.set(j);
128    }
129   
130    protected abstract void findNewDistances(BinaryNode nodei,
131    BinaryNode nodej, double previousDistance);
132   
133    /**
134    * Calculates and saves the distance between the combination of cluster(i) and
135    * cluster(j) and all other clusters. The form of the calculation depends on
136    * the tree clustering method being used.
137    *
138    * @param i
139    * @param j
140    */
141    protected abstract void findClusterDistance(int i, int j);
142   
143    /**
144    * Finds the node, at or below the given node, with the maximum distance, and
145    * saves the node and the distance value
146    *
147    * @param nd
148    */
 
149  147 toggle protected void findMaxDist(BinaryNode nd)
150    {
151  147 if (nd == null)
152    {
153  0 return;
154    }
155   
156  147 if ((nd.left() == null) && (nd.right() == null))
157    {
158  75 double dist = nd.dist;
159   
160  75 if (dist > maxDistValue)
161    {
162  12 maxdist = nd;
163  12 maxDistValue = dist;
164    }
165    }
166    else
167    {
168  72 findMaxDist((BinaryNode) nd.left());
169  72 findMaxDist((BinaryNode) nd.right());
170    }
171    }
172   
173    /**
174    * Form clusters by grouping sub-clusters, starting from one sequence per
175    * cluster, and finishing when only two clusters remain
176    */
 
177  3 toggle protected void cluster()
178    {
179  72 while (noClus > 2)
180    {
181  69 findMinDistance();
182   
183  69 joinClusters(mini, minj);
184   
185  69 noClus--;
186    }
187   
188  3 int rightChild = done.nextClearBit(0);
189  3 int leftChild = done.nextClearBit(rightChild + 1);
190   
191  3 joinClusters(leftChild, rightChild);
192  3 top = (node.elementAt(leftChild));
193   
194  3 reCount(top);
195  3 findHeight(top);
196  3 findMaxDist(top);
197    }
198   
199    /**
200    * Returns the minimum distance between two clusters, and also sets the
201    * indices of the clusters in fields mini and minj
202    *
203    * @return
204    */
205    protected abstract double findMinDistance();
206   
207    /**
208    * DOCUMENT ME!
209    *
210    * @param nd
211    * DOCUMENT ME!
212    */
 
213  147 toggle protected void _reCount(BinaryNode nd)
214    {
215    // if (_lycount<_lylimit)
216    // {
217    // jalview.bin.Console.errPrintln("Warning: depth of _recount greater than
218    // number of
219    // nodes.");
220    // }
221  147 if (nd == null)
222    {
223  0 return;
224    }
225    // _lycount++;
226   
227  147 if ((nd.left() != null) && (nd.right() != null))
228    {
229   
230  72 _reCount(nd.left());
231  72 _reCount((BinaryNode) nd.right());
232   
233  72 BinaryNode l = nd.left();
234  72 BinaryNode r = nd.right();
235   
236  72 nd.count = l.count + r.count;
237  72 nd.ycount = (l.ycount + r.ycount) / 2;
238    }
239    else
240    {
241  75 nd.count = 1;
242  75 nd.ycount = ycount++;
243    }
244    // _lycount--;
245    }
246   
247    /**
248    * DOCUMENT ME!
249    *
250    * @param nd
251    * DOCUMENT ME!
252    *
253    * @return DOCUMENT ME!
254    */
 
255  0 toggle 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    * DOCUMENT ME!
296    *
297    * @param nd
298    * DOCUMENT ME!
299    */
 
300  3 toggle void reCount(BinaryNode nd)
301    {
302  3 ycount = 0;
303    // _lycount = 0;
304    // _lylimit = this.node.size();
305  3 _reCount(nd);
306    }
307   
308    /**
309    * DOCUMENT ME!
310    *
311    * @return DOCUMENT ME!
312    */
 
313  9 toggle public BinaryNode getTopNode()
314    {
315  9 return top;
316    }
317   
318    }