2 * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3 * Copyright (C) $$Year-Rel$$ The Jalview Authors
5 * This file is part of Jalview.
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.
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.
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.
21 package jalview.analysis;
23 import java.util.BitSet;
24 import java.util.Vector;
26 import jalview.datamodel.BinaryNode;
27 import jalview.datamodel.SequenceNode;
28 import jalview.math.MatrixI;
30 public abstract class TreeEngine
33 protected Vector<BitSet> clusters;
35 protected BitSet done;
41 protected MatrixI distances;
47 protected Vector<BinaryNode> node;
57 protected BinaryNode top;
64 * Calculates and returns r, whatever that is
71 protected double findr(int i, int j)
75 for (int k = 0; k < noseqs; k++)
77 if ((k != i) && (k != j) && (!done.get(k)))
79 tmp = tmp + distances.getValue(i, k);
85 tmp = tmp / (noClus - 2);
92 * Merges cluster(j) to cluster(i) and recalculates cluster and node distances
97 protected void joinClusters(final int i, final int j)
99 double dist = distances.getValue(i, j);
104 findClusterDistance(i, j);
106 BinaryNode sn = new BinaryNode();
108 sn.setLeft((node.elementAt(i)));
109 sn.setRight((node.elementAt(j)));
111 BinaryNode tmpi = (node.elementAt(i));
112 BinaryNode tmpj = (node.elementAt(j));
114 findNewDistances(tmpi, tmpj, dist);
119 node.setElementAt(sn, i);
122 * move the members of cluster(j) to cluster(i)
123 * and mark cluster j as out of the game
125 clusters.get(i).or(clusters.get(j));
126 clusters.get(j).clear();
130 protected abstract void findNewDistances(BinaryNode nodei,
131 BinaryNode nodej, double previousDistance);
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.
141 protected abstract void findClusterDistance(int i, int j);
144 * Finds the node, at or below the given node, with the maximum distance, and
145 * saves the node and the distance value
149 protected void findMaxDist(BinaryNode nd)
156 if ((nd.left() == null) && (nd.right() == null))
158 double dist = nd.dist;
160 if (dist > maxDistValue)
168 findMaxDist((BinaryNode) nd.left());
169 findMaxDist((BinaryNode) nd.right());
174 * Form clusters by grouping sub-clusters, starting from one sequence per
175 * cluster, and finishing when only two clusters remain
177 protected void cluster()
183 joinClusters(mini, minj);
188 int rightChild = done.nextClearBit(0);
189 int leftChild = done.nextClearBit(rightChild + 1);
191 joinClusters(leftChild, rightChild);
192 top = (node.elementAt(leftChild));
200 * Returns the minimum distance between two clusters, and also sets the
201 * indices of the clusters in fields mini and minj
205 protected abstract double findMinDistance();
213 protected void _reCount(BinaryNode nd)
215 // if (_lycount<_lylimit)
217 // jalview.bin.Console.errPrintln("Warning: depth of _recount greater than
227 if ((nd.left() != null) && (nd.right() != null))
231 _reCount((BinaryNode) nd.right());
233 BinaryNode l = nd.left();
234 BinaryNode r = nd.right();
236 nd.count = l.count + r.count;
237 nd.ycount = (l.ycount + r.ycount) / 2;
242 nd.ycount = ycount++;
253 * @return DOCUMENT ME!
255 double findHeight(BinaryNode nd)
262 if ((nd.left() == null) && (nd.right() == null))
264 nd.height = ((BinaryNode) nd.parent()).height + nd.dist;
266 if (nd.height > maxheight)
277 if (nd.parent() != null)
279 nd.height = ((BinaryNode) nd.parent()).height + nd.dist;
284 nd.height = (float) 0.0;
287 maxheight = findHeight((BinaryNode) (nd.left()));
288 maxheight = findHeight((BinaryNode) (nd.right()));
300 void reCount(BinaryNode nd)
304 // _lylimit = this.node.size();
311 * @return DOCUMENT ME!
313 public BinaryNode getTopNode()