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 // System.err.println("Warning: depth of _recount greater than number of
226 if ((nd.left() != null) && (nd.right() != null))
230 _reCount((BinaryNode) nd.right());
232 BinaryNode l = nd.left();
233 BinaryNode r = nd.right();
235 nd.count = l.count + r.count;
236 nd.ycount = (l.ycount + r.ycount) / 2;
241 nd.ycount = ycount++;
252 * @return DOCUMENT ME!
254 double findHeight(BinaryNode nd)
261 if ((nd.left() == null) && (nd.right() == null))
263 nd.height = ((BinaryNode) nd.parent()).height + nd.dist;
265 if (nd.height > maxheight)
276 if (nd.parent() != null)
278 nd.height = ((BinaryNode) nd.parent()).height + nd.dist;
283 nd.height = (float) 0.0;
286 maxheight = findHeight((BinaryNode) (nd.left()));
287 maxheight = findHeight((BinaryNode) (nd.right()));
299 void reCount(BinaryNode nd)
303 // _lylimit = this.node.size();
310 * @return DOCUMENT ME!
312 public BinaryNode getTopNode()