source: branches/ralph/src/main/java/de/ugoe/cs/autoquest/tasktrees/alignment/pal/tree/NodeUtils.java @ 1612

Last change on this file since 1612 was 1580, checked in by rkrimmel, 10 years ago

Further code cleanup
File size: 13.3 KB
Line 
1// NodeUtils.java
2//
3// (c) 1999-2001 PAL Development Core Team
4//
5// This package may be distributed under the
6// terms of the Lesser GNU General Public License (LGPL)
7
8
9package de.ugoe.cs.autoquest.tasktrees.alignment.pal.tree;
10
11
12import de.ugoe.cs.autoquest.tasktrees.alignment.pal.misc.Identifier;
13
14
15/**
16 * Helper routines for dealing with nodes.
17 *
18 * @version $Id: NodeUtils.java,v 1.19 2002/01/08 02:09:53 alexi Exp $
19 *
20 * @author Alexei Drummond
21 * @author Korbinian Strimmer
22 */
23public class NodeUtils {
24
25        /**
26         * Converts lengths to heights, *without* assuming contemporaneous
27         * tips.
28         */
29        public static void lengths2Heights(Node root) {
30
31                lengths2Heights(root, getGreatestDistance(root));
32        }
33
34        /**
35         * Converts lengths to heights, but maintains tip heights.
36         */
37        public static void lengths2HeightsKeepTips(Node node, boolean useMax) {
38
39                if (!node.isLeaf()) {
40                        for (int i = 0; i < node.getChildCount(); i++) {
41                                lengths2HeightsKeepTips(node.getChild(i), useMax);
42                        }
43
44                        double totalHL = 0.0;
45                        double maxHL = 0.0;
46                        double hl = 0.0;
47                        double maxH = 0.0;
48                        double h = 0.0;
49                        for (int i = 0; i < node.getChildCount(); i++) {
50                                h = node.getChild(i).getNodeHeight();
51                                hl = node.getChild(i).getBranchLength() + h;
52                                if (hl > maxHL) maxHL = hl;
53                                if (h > maxH) maxH = h;
54                                totalHL += hl;
55                        }
56                        if (useMax) {
57                                hl = maxHL; // set parent height to maximum parent height implied by children
58                        } else {
59                                hl = totalHL /  node.getChildCount(); // get mean parent height
60                                if (hl < maxH) hl = maxHL; // if mean parent height is not greater than all children height, fall back on max parent height.
61                        }
62                        node.setNodeHeight(hl); // set new parent height
63
64                        // change lengths in children to reflect changes.
65                        for (int i = 0; i < node.getChildCount(); i++) {
66                                h = node.getChild(i).getNodeHeight();
67                                node.getChild(i).setBranchLength(hl - h);
68                        }
69                }
70        }
71
72
73        /**
74         * sets this nodes height value to newHeight and all children's
75         * height values based on length of branches.
76         */
77        private static void lengths2Heights(Node node, double newHeight) {
78
79                if (!node.isRoot()) {
80                        newHeight -= node.getBranchLength();
81                        node.setNodeHeight(newHeight);
82                } else {
83                        node.setNodeHeight(newHeight);
84                }
85
86                for (int i = 0; i < node.getChildCount(); i++) {
87                        lengths2Heights(node.getChild(i), newHeight);
88                }
89        }
90
91        /**
92         * Exchange field info between two nodes. Specifically
93         * identifiers, branch lengths, node heights and branch length
94         * SEs.
95         */
96        public static void exchangeInfo(Node node1, Node node2) {
97
98                Identifier swaps;
99                double swapd;
100
101                swaps = node1.getIdentifier();
102                node1.setIdentifier(node2.getIdentifier());
103                node2.setIdentifier(swaps);
104
105                swapd = node1.getBranchLength();
106                node1.setBranchLength(node2.getBranchLength());
107                node2.setBranchLength(swapd);
108
109                swapd = node1.getNodeHeight();
110                node1.setNodeHeight(node2.getNodeHeight());
111                node2.setNodeHeight(swapd);
112
113                swapd = node1.getBranchLengthSE();
114                node1.setBranchLengthSE(node2.getBranchLengthSE());
115                node2.setBranchLengthSE(swapd);
116        }
117
118
119
120
121        /**
122         * Get the distance to furthest leaf from this nodes parent.
123         */
124        private static double getGreatestDistance(Node node) {
125
126                double distance = 0.0;
127                if (!node.isLeaf()) {
128                        if (!node.isRoot()) {
129                                distance = node.getBranchLength();
130                        }
131                        double max = getGreatestDistance(node.getChild(0));
132                        double posmax = 0.0;
133                        for (int i = 1; i < node.getChildCount(); i++) {
134                                posmax = getGreatestDistance(node.getChild(i));
135                                if (posmax > max) max = posmax;
136                        }
137                        distance += max;
138
139                                        return distance;
140                } else {
141                                        return node.getBranchLength();
142                }
143        }
144
145        /**
146         * Finds the largest child (in terms of node height).
147         */
148        public static double findLargestChild(Node node) {
149                // find child with largest height
150                double max = node.getChild(0).getNodeHeight();
151                for (int j = 1; j < node.getChildCount(); j++)
152                {
153                        if (node.getChild(j).getNodeHeight() > max)
154                        {
155                                max = node.getChild(j).getNodeHeight();
156                        }
157                }
158                return max;
159        }
160
161        /**
162         * remove child
163         *
164         * @param node child node to be removed
165         */
166        public static void removeChild(Node parent, Node child)
167        {
168                int rm = -1;
169                for (int i = 0; i < parent.getChildCount(); i++)
170                {
171                        if (child == parent.getChild(i))
172                        {
173                                rm = i;
174                                break;
175                        }
176                }
177
178                parent.removeChild(rm);
179        }
180
181        /**
182         * remove internal branch (collapse node with its parent)
183         *
184         * @param node node associated with internal branch
185         */
186        public static void removeBranch(Node node)
187        {
188                if (node.isRoot() || node.isLeaf())
189                {
190                        throw new IllegalArgumentException("INTERNAL NODE REQUIRED (NOT ROOT)");
191                }
192
193                Node parent = node.getParent();
194
195                // add childs of node to parent
196                // (node still contains the link to childs
197                // to allow later restoration)
198                int numChilds = node.getChildCount();
199                for (int i = 0; i < numChilds; i++)
200                {
201                        parent.addChild(node.getChild(i));
202                }
203
204                // remove node from parent
205                // (link to parent is restored and the
206                // position is stored)
207                int rm = -1;
208                for (int i = 0; i < parent.getChildCount(); i++)
209                {
210                        if (node == parent.getChild(i))
211                        {
212                                rm = i;
213                                break;
214                        }
215                }
216                parent.removeChild(rm);
217                node.setParent(parent);
218                node.setNumber(rm);
219        }
220
221        /**
222         * restore internal branch
223         *
224         * @param node node associated with internal branch
225         */
226        public static void restoreBranch(Node node)
227        {
228                if (node.isRoot() || node.isLeaf())
229                {
230                        throw new IllegalArgumentException("INTERNAL NODE REQUIRED (NOT ROOT)");
231                }
232
233                Node parent = node.getParent();
234
235                // remove childs of node from parent and make node their parent
236                int numChilds = node.getChildCount();
237                for (int i = 0; i < numChilds; i++)
238                {
239                        Node c = node.getChild(i);
240                        removeChild(parent, c);
241                        c.setParent(node);
242                }
243
244                // insert node into parent
245                parent.insertChild(node, node.getNumber());
246        }
247
248
249
250        /**
251         * join two childs, introducing a new node/branch in the tree
252         * that replaces the first child
253         *
254         * @param n1 number of first child
255         * @param n2 number of second child
256         */
257        public static void joinChilds(Node node, int n1, int n2) {
258
259                if (n1 == n2) {
260                        throw new IllegalArgumentException("CHILDREN MUST BE DIFFERENT");
261                }
262
263                int c1, c2;
264                if (n2 < n1)
265                {
266                        c1 = n2;
267                        c2 = n1;
268                }
269                else
270                {
271                        c1 = n1;
272                        c2 = n2;
273                }
274
275                Node newNode = NodeFactory.createNode();
276
277                Node child1 = node.getChild(c1);
278                Node child2 = node.getChild(c2);
279
280                node.setChild(c1, newNode);
281                newNode.setParent(node);
282                node.removeChild(c2); // now parent of child2 = null
283
284                newNode.addChild(child1);
285                newNode.addChild(child2);
286        }
287
288        /**
289         * determine preorder successor of this node
290         *
291         * @return next node
292         */
293        public static Node preorderSuccessor(Node node) {
294
295                Node next = null;
296
297                if (node.isLeaf()) {
298                        Node cn = node, ln = null; // Current and last node
299
300                        // Go up
301                        do
302                        {
303                                if (cn.isRoot())
304                                {
305                                        next = cn;
306                                        break;
307                                }
308                                ln = cn;
309                                cn = cn.getParent();
310                        }
311                        while (cn.getChild(cn.getChildCount()-1) == ln);
312
313                        // Determine next node
314                        if (next == null)
315                        {
316                                // Go down one node
317                                for (int i = 0; i < cn.getChildCount()-1; i++)
318                                {
319                                        if (cn.getChild(i) == ln)
320                                        {
321                                                next = cn.getChild(i+1);
322                                                break;
323                                        }
324                                }
325                        }
326                }
327                else
328                {
329                        next = node.getChild(0);
330                }
331
332                return next;
333        }
334
335        /**
336         * determine postorder successor of a node
337         *
338         * @return next node
339         */
340        public static Node postorderSuccessor(Node node) {
341
342                Node cn = null;
343                Node parent = node.getParent();
344
345                if (node.isRoot())
346                {
347                        cn = node;
348                }
349                else
350                {
351
352                        // Go up one node
353                        if (parent.getChild(parent.getChildCount()-1) == node) {
354                                return parent;
355                        }
356                        // Go down one node
357                        for (int i = 0; i < parent.getChildCount()-1; i++)
358                        {
359                                if (parent.getChild(i) == node)
360                                {
361                                        cn = parent.getChild(i+1);
362                                        break;
363                                }
364                        }
365                }
366
367                // Go down until leaf
368                while (cn.getChildCount() > 0)
369                {
370
371                        cn = cn.getChild(0);
372                }
373
374                return cn;
375        }
376
377
378
379
380        /**
381         * Returns the first nodes in this tree that has the
382         * required identifiers.
383         * @return null if none of the identifiers names match nodes in tree, else return array which may have
384         *  null "blanks" for corresponding identifiers that do not match any node in the tree
385         */
386        public static final Node[] findByIdentifier(Node node, String[] identifierNames) {
387                Node[] nodes = new Node[identifierNames.length];
388                boolean foundSomething = false;
389                for(int i = 0 ; i < nodes.length ; i++) {
390                        nodes[i] = findByIdentifier(node,identifierNames[i]);
391                        foundSomething = foundSomething||(nodes[i]!=null);
392                }
393                if(!foundSomething) {
394                        return null;
395                }
396                return nodes;
397        }
398        /**
399         * Returns the first nodes in this tree that has the
400         * required identifiers.
401         */
402        public static final Node[] findByIdentifier(Node node, Identifier[] identifiers) {
403                Node[] nodes = new Node[identifiers.length];
404                for(int i = 0 ; i < nodes.length ; i++) {
405                        nodes[i] = findByIdentifier(node,identifiers[i]);
406                }
407                return nodes;
408        }
409        /**
410         * Returns the first node in this tree that has the
411         * required identifier.
412         */
413        public static final Node findByIdentifier(Node node, Identifier identifier) {
414                return findByIdentifier(node,identifier.getName());
415        }
416        /**
417         * Returns the first node in this tree that has the
418         * required identifier.
419         */
420        public static final Node findByIdentifier(Node node, String identifierName) {
421
422
423                if (node.getIdentifier().getName().equals(identifierName)) {
424                        return node;
425                } else {
426                        Node pos = null;
427                        for (int i = 0; i < node.getChildCount(); i++) {
428                                pos = findByIdentifier(node.getChild(i), identifierName);
429                                if (pos != null) return pos;
430                        }
431               
432                        return pos;
433                }
434        }
435
436        /**
437         * Root tree at this node.
438         */
439        public static Node root(Node node) {
440
441                if (!node.isRoot()) {
442
443                        Node myParent = node.getParent();
444                        removeChild(myParent, node);
445
446                        root(myParent);
447
448                        while (myParent.getChildCount() == 1) {
449                                myParent = myParent.getChild(0);
450                        }
451
452                        node.addChild(myParent);
453                        lengths2Heights(node);
454                }
455                return node;
456        }
457
458        /**
459         * Root the tree above the node with this identifier.
460         */
461        public static Node rootAbove(Identifier id, Node root) {
462                return rootAbove(findByIdentifier(root, id));
463        }
464
465        /**
466         * Root tree above this node;
467         */
468        public static Node rootAbove(Node node) {
469
470                if (!node.isRoot()) {
471
472                        Node root = NodeFactory.createNode();
473
474                        Node myParent = node.getParent();
475                        removeChild(myParent, node);
476
477                        root(myParent);
478                       
479                        while (myParent.getChildCount() == 1) {
480                                myParent = myParent.getChild(0);
481                        }
482
483                        root.addChild(myParent);
484                        root.addChild(node);
485
486                        lengths2Heights(root);
487
488                        return root;
489
490                } else return node;
491        }
492
493        /**
494         * determine distance to root
495         *
496         * @return distance to root
497         */
498        public static double getDistanceToRoot(Node node)
499        {
500                if (node.isRoot())
501                {
502                        return 0.0;
503                }
504                else
505                {
506                        return node.getBranchLength() + getDistanceToRoot(node.getParent());
507                }
508        }
509
510        /**
511         * Return the number of terminal leaves below this node or 1 if this is
512         * a terminal leaf.
513         */
514        public static int getLeafCount(Node node) {
515
516                int count = 0;
517                if (!node.isLeaf()) {
518                        for (int i = 0; i < node.getChildCount(); i++) {
519                                count += getLeafCount(node.getChild(i));
520                        }
521                } else {
522                        count = 1;
523                }
524                return count;
525        }
526        /**
527         * For two nodes in the tree true if the first node is the ancestor of the second
528         *
529         * @param possibleAncestor the node that may be the ancestor of the other node
530         * @param node the node that may have the other node as it's ancestor
531         */
532        public static boolean isAncestor(Node possibleAncestor, Node node) {
533                if(node==possibleAncestor) {
534                        return true;
535                }
536                while(!node.isRoot()){
537                        node = node.getParent();
538                        if(node==possibleAncestor) {
539                                return true;
540                        }
541                }
542                return false;
543        }
544
545        /**
546         * For a set of nodes in the tree returns the common ancestor closest to all nodes (most recent common ancestor)
547         *
548         * @param nodes the nodes to check, is okay if array elements are null!
549         * @returns null if a at least one node is disjoint from the others nodes disjoint
550         */
551        public static Node getFirstCommonAncestor(Node[] nodes) {
552                Node currentCA = nodes[0];
553                for(int i = 1; i < nodes.length ;i++) {
554                        if(currentCA!=null&&nodes[i]!=null) {
555                                currentCA = getFirstCommonAncestor(currentCA,nodes[i]);
556                                if(currentCA==null) {
557                                        return null;
558                                }
559                        }
560                }
561                return currentCA;
562        }
563        /**
564         * For two nodes in the tree returns the common ancestor closest to both nodes (most recent common ancestor)
565         *
566         * @param nodeOne
567         * @param nodeTwo
568         * @returns null if two nodes disjoint (from different trees). May also return either nodeOne or nodeTwo if one node is an ancestor of the other
569         */
570        public static Node getFirstCommonAncestor(Node nodeOne, Node nodeTwo) {
571                if(isAncestor(nodeTwo, nodeOne)) {
572                        return nodeTwo;
573                }
574                if(isAncestor(nodeOne, nodeTwo)) {
575                        return nodeOne;
576                }
577                while(!nodeTwo.isRoot()) {
578                        nodeTwo = nodeTwo.getParent();
579                        if(isAncestor(nodeTwo, nodeOne)) {
580                                return nodeTwo;
581                        }
582                }
583                return null;
584        }
585
586                /** returns number of branches centered around an internal node in an unrooted tree */
587        public static final int getUnrootedBranchCount(Node center) {
588                if (center.isRoot())    {
589                        return center.getChildCount();
590                }
591                else {
592                        return center.getChildCount()+1;
593                }
594        }
595
596        /** Attempts to remove the root of a tree by making it polyficating (as opposed to bificating).
597        */
598        public static final Node getUnrooted(Node root) {
599                if(!root.isRoot()) {
600                        return root; //Already unrooted
601                }
602                Node left = root.getChild(0);
603                Node right = root.getChild(1);
604                /*if(left.getChildCount()==1) {
605                        if(l
606                } */
607                if(left.getChildCount()>1) {
608                        return root(left);
609                }
610                if(right.getChildCount()>1) {
611                        return root(right);
612                }
613                return root; //Can't do much
614        }
615}
Note: See TracBrowser for help on using the repository browser.