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

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

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