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

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

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