2 // FORESTER -- software libraries and applications
3 // for evolutionary biology research and applications.
5 // Copyright (C) 2008-2009 Christian M. Zmasek
6 // Copyright (C) 2008-2009 Burnham Institute for Medical Research
7 // Copyright (C) 2000-2001 Washington University School of Medicine
8 // and Howard Hughes Medical Institute
11 // This library is free software; you can redistribute it and/or
12 // modify it under the terms of the GNU Lesser General Public
13 // License as published by the Free Software Foundation; either
14 // version 2.1 of the License, or (at your option) any later version.
16 // This library is distributed in the hope that it will be useful,
17 // but WITHOUT ANY WARRANTY; without even the implied warranty of
18 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 // Lesser General Public License for more details.
21 // You should have received a copy of the GNU Lesser General Public
22 // License along with this library; if not, write to the Free Software
23 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
25 // Contact: phylosoft @ gmail . com
26 // WWW: www.phylosoft.org/forester
28 package org.forester.phylogeny;
30 import java.io.IOException;
31 import java.util.ArrayList;
32 import java.util.Arrays;
33 import java.util.Collection;
34 import java.util.HashMap;
35 import java.util.Iterator;
36 import java.util.List;
38 import java.util.NoSuchElementException;
39 import java.util.Vector;
41 import org.forester.io.writers.PhylogenyWriter;
42 import org.forester.phylogeny.data.BranchData;
43 import org.forester.phylogeny.data.Confidence;
44 import org.forester.phylogeny.data.Identifier;
45 import org.forester.phylogeny.data.Sequence;
46 import org.forester.phylogeny.data.SequenceRelation;
47 import org.forester.phylogeny.data.SequenceRelation.SEQUENCE_RELATION_TYPE;
48 import org.forester.phylogeny.iterators.ExternalForwardIterator;
49 import org.forester.phylogeny.iterators.LevelOrderTreeIterator;
50 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
51 import org.forester.phylogeny.iterators.PostorderTreeIterator;
52 import org.forester.phylogeny.iterators.PreorderTreeIterator;
53 import org.forester.util.FailedConditionCheckException;
54 import org.forester.util.ForesterUtil;
56 public class Phylogeny {
58 public final static boolean ALLOW_MULTIPLE_PARENTS_DEFAULT = false;
59 private PhylogenyNode _root;
60 private boolean _rooted;
61 private boolean _allow_multiple_parents;
64 private String _description;
65 private String _distance_unit;
66 private Confidence _confidence;
67 private Identifier _identifier;
68 private boolean _rerootable;
69 private HashMap<Integer, PhylogenyNode> _idhash;
70 private List<PhylogenyNode> _external_nodes_set;
71 private Collection<Sequence> _sequenceRelationQueries;
72 private Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> _relevant_sequence_relation_types;
75 * Default Phylogeny constructor. Constructs an empty Phylogeny.
82 * Adds this Phylogeny to the list of child nodes of PhylogenyNode parent
83 * and sets the parent of this to parent.
86 * the PhylogenyNode to add
88 public void addAsChild( final PhylogenyNode parent ) {
90 throw new IllegalArgumentException( "Attempt to add an empty tree." );
93 throw new IllegalArgumentException( "Attempt to add an unrooted tree." );
95 parent.addAsChild( getRoot() );
96 externalNodesHaveChanged();
99 public void addAsSibling( final PhylogenyNode sibling ) {
101 throw new IllegalArgumentException( "Attempt to add an empty tree." );
104 throw new IllegalArgumentException( "Attempt to add an unrooted tree." );
106 final int sibling_index = sibling.getChildNodeIndex();
107 final PhylogenyNode new_node = new PhylogenyNode();
108 final PhylogenyNode sibling_parent = sibling.getParent();
109 new_node.setChild1( sibling );
110 new_node.setChild2( getRoot() );
111 new_node.setParent( sibling_parent );
112 sibling.setParent( new_node );
113 sibling_parent.setChildNode( sibling_index, new_node );
114 final double new_dist = sibling.getDistanceToParent() == PhylogenyNode.DISTANCE_DEFAULT ? PhylogenyNode.DISTANCE_DEFAULT
115 : sibling.getDistanceToParent() / 2;
116 new_node.setDistanceToParent( new_dist );
117 sibling.setDistanceToParent( new_dist );
118 externalNodesHaveChanged();
122 * This calculates the height of the subtree emanating at n for rooted,
123 * tree-shaped phylogenies
126 * the root-node of a subtree
127 * @return the height of the subtree emanating at n
129 public double calculateSubtreeHeight( final PhylogenyNode n ) {
130 if ( n.isExternal() || n.isCollapse() ) {
131 return ForesterUtil.isLargerOrEqualToZero( n.getDistanceToParent() );
134 double max = -Double.MAX_VALUE;
135 for( int i = 0; i < n.getNumberOfDescendants(); ++i ) {
136 final double l = calculateSubtreeHeight( n.getChildNode( i ) );
141 return max + ForesterUtil.isLargerOrEqualToZero( n.getDistanceToParent() );
146 * Returns a deep copy of this Phylogeny.
148 * (The resulting Phylogeny has its references in the external nodes
149 * corrected, if they are lacking/obsolete in this.)
151 public Phylogeny copy() {
152 return copy( _root );
156 * Returns a shallow copy of this Phylogeny.
158 * (The resulting Phylogeny has its references in the external nodes
159 * corrected, if they are lacking/obsolete in this.)
161 public Phylogeny copyShallow() {
162 return copyShallow( _root );
165 public Phylogeny copyShallow( final PhylogenyNode source ) {
166 final Phylogeny tree = new Phylogeny();
171 tree._rooted = _rooted;
173 tree._description = _description;
175 tree._rerootable = _rerootable;
176 tree._distance_unit = _distance_unit;
177 tree._confidence = _confidence;
178 tree._identifier = _identifier;
179 tree.setAllowMultipleParents( isAllowMultipleParents() );
180 tree._root = PhylogenyMethods.copySubTreeShallow( source );
185 * Returns a deep copy of this Phylogeny.
187 * (The resulting Phylogeny has its references in the external nodes
188 * corrected, if they are lacking/obsolete in this.)
190 public Phylogeny copy( final PhylogenyNode source ) {
191 final Phylogeny tree = new Phylogeny();
196 tree._rooted = _rooted;
197 tree._name = new String( _name );
198 tree._description = new String( _description );
199 tree._type = new String( _type );
200 tree._rerootable = _rerootable;
201 tree._distance_unit = new String( _distance_unit );
202 if ( _confidence != null ) {
203 tree._confidence = ( Confidence ) _confidence.copy();
205 if ( _identifier != null ) {
206 tree._identifier = ( Identifier ) _identifier.copy();
208 tree.setAllowMultipleParents( isAllowMultipleParents() );
209 tree._root = PhylogenyMethods.copySubTree( source );
214 * Need the delete and/or rehash _idhash (not done automatically
215 * to allow client multiple deletions in linear time).
216 * Need to call 'recalculateNumberOfExternalDescendants(boolean)' after this
217 * if tree is to be displayed.
219 * @param remove_us the parent node of the subtree to be deleted
221 public void deleteSubtree( final PhylogenyNode remove_us, final boolean collapse_resulting_node_with_one_desc ) {
225 if ( remove_us.isRoot() ) {
229 if ( !collapse_resulting_node_with_one_desc ) {
230 remove_us.getParent().removeChildNode( remove_us );
233 final PhylogenyNode removed_node = remove_us;
234 final PhylogenyNode p = remove_us.getParent();
236 if ( p.getNumberOfDescendants() == 2 ) {
237 if ( removed_node.isFirstChildNode() ) {
238 setRoot( getRoot().getChildNode( 1 ) );
239 getRoot().setParent( null );
242 setRoot( getRoot().getChildNode( 0 ) );
243 getRoot().setParent( null );
247 p.removeChildNode( removed_node.getChildNodeIndex() );
251 final PhylogenyNode pp = removed_node.getParent().getParent();
252 if ( p.getNumberOfDescendants() == 2 ) {
253 final int pi = p.getChildNodeIndex();
254 if ( removed_node.isFirstChildNode() ) {
255 p.getChildNode( 1 ).setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p
256 .getDistanceToParent(), p.getChildNode( 1 ).getDistanceToParent() ) );
257 pp.setChildNode( pi, p.getChildNode( 1 ) );
260 p.getChildNode( 0 ).setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p
261 .getDistanceToParent(), p.getChildNode( 0 ).getDistanceToParent() ) );
262 pp.setChildNode( pi, p.getChildNode( 0 ) );
266 p.removeChildNode( removed_node.getChildNodeIndex() );
270 remove_us.setParent( null );
272 externalNodesHaveChanged();
275 public void externalNodesHaveChanged() {
276 _external_nodes_set = null;
279 public String[] getAllExternalNodeNames() {
284 final String[] names = new String[ getNumberOfExternalNodes() ];
285 for( final PhylogenyNodeIterator iter = iteratorExternalForward(); iter.hasNext(); ) {
286 names[ i++ ] = new String( iter.next().getName() );
291 public Confidence getConfidence() {
295 public String getDescription() {
299 public String getDistanceUnit() {
300 return _distance_unit;
305 * Warning. The order of the returned nodes is random
306 * -- and hence cannot be relied on.
308 * @return Unordered set of PhylogenyNode
310 public List<PhylogenyNode> getExternalNodes() {
311 if ( _external_nodes_set == null ) {
312 _external_nodes_set = new ArrayList<PhylogenyNode>();
313 for( final PhylogenyNodeIterator it = iteratorPostorder(); it.hasNext(); ) {
314 final PhylogenyNode n = it.next();
315 if ( n.isExternal() ) {
316 _external_nodes_set.add( n );
320 return _external_nodes_set;
324 * Returns the number of duplications of this Phylogeny (int). A return
325 * value of -1 indicates that the number of duplications is unknown.
327 // public int getNumberOfDuplications() {
328 // return _number_of_duplications;
329 // } // getNumberOfDuplications()
331 * Sets the number of duplications of this Phylogeny (int). A value of -1
332 * indicates that the number of duplications is unknown.
335 * set to true for clean NH format
337 // public void setNumberOfDuplications( int i ) {
339 // _number_of_duplications = -1;
342 // _number_of_duplications = i;
344 // } // setNumberOfDuplications( int )
346 * Returns the first external PhylogenyNode.
348 public PhylogenyNode getFirstExternalNode() {
350 throw new FailedConditionCheckException( "attempt to obtain first external node of empty phylogeney" );
352 PhylogenyNode node = getRoot();
353 while ( node.isInternal() ) {
354 node = node.getFirstChildNode();
360 * This calculates the height for rooted, tree-shaped phylogenies. The
361 * height is the longest distance from the root to an external node. Please
362 * note. Child nodes of collapsed nodes are ignored -- which is useful for
363 * display purposes but might be misleading for other applications.
365 * @return the height for rooted, tree-shaped phylogenies
367 public double getHeight() {
371 return calculateSubtreeHeight( getRoot() );
374 public Identifier getIdentifier() {
378 // ---------------------------------------------------------
379 // Modification of Phylogeny topology and Phylogeny appearance
380 // ---------------------------------------------------------
381 private HashMap<Integer, PhylogenyNode> getIdHash() {
386 * Returns the name of this Phylogeny.
388 public String getName() {
393 * Finds the PhylogenyNode of this Phylogeny which has a matching ID number.
394 * Takes O(n) time. After method hashIDs() has been called it runs in
398 * ID number (int) of the PhylogenyNode to find
399 * @return PhylogenyNode with matching ID, null if not found
401 public PhylogenyNode getNode( final int id ) throws NoSuchElementException {
403 throw new NoSuchElementException( "attempt to get node in an empty phylogeny" );
405 if ( _idhash != null ) {
406 return _idhash.get( id );
409 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
410 final PhylogenyNode node = iter.next();
411 if ( node.getId() == id ) {
420 * Returns a PhylogenyNode of this Phylogeny which has a matching name.
421 * Throws an Exception if seqname is not present in this or not unique.
424 * name (String) of PhylogenyNode to find
425 * @return PhylogenyNode with matchin name
427 public PhylogenyNode getNode( final String name ) {
431 final List<PhylogenyNode> nodes = getNodes( name );
432 if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
433 throw new IllegalArgumentException( "node named [" + name + "] not found" );
435 if ( nodes.size() > 1 ) {
436 throw new IllegalArgumentException( "node named [" + name + "] not unique" );
438 return nodes.get( 0 );
442 * Return Node by TaxonomyId Olivier CHABROL :
443 * olivier.chabrol@univ-provence.fr
446 * search taxonomy identifier
448 * sublist node to search
449 * @return List node with the same taxonomy identifier
451 private List<PhylogenyNode> getNodeByTaxonomyID( final String taxonomyID, final List<PhylogenyNode> nodes ) {
452 final List<PhylogenyNode> retour = new ArrayList<PhylogenyNode>();
453 for( final PhylogenyNode node : nodes ) {
454 if ( taxonomyID.equals( PhylogenyMethods.getTaxonomyIdentifier( node ) ) ) {
462 * Returns a List with references to all Nodes of this Phylogeny which have
466 * name (String) of Nodes to find
467 * @return Vector of references to Nodes of this Phylogeny with matching
469 * @see #getNodesWithMatchingSpecies(String)
471 public List<PhylogenyNode> getNodes( final String name ) {
475 final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
476 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
477 final PhylogenyNode n = iter.next();
478 if ( n.getName().equals( name ) ) {
485 public List<PhylogenyNode> getNodesViaSequenceName( final String seq_name ) {
489 final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
490 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
491 final PhylogenyNode n = iter.next();
492 if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getName().equals( seq_name ) ) {
499 public List<PhylogenyNode> getNodesViaTaxonomyCode( final String taxonomy_code ) {
503 final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
504 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
505 final PhylogenyNode n = iter.next();
506 if ( n.getNodeData().isHasTaxonomy()
507 && n.getNodeData().getTaxonomy().getTaxonomyCode().equals( taxonomy_code ) ) {
515 * Returns a Vector with references to all Nodes of this Phylogeny which
516 * have a matching species name.
519 * species name (String) of Nodes to find
520 * @return Vector of references to Nodes of this Phylogeny with matching
522 * @see #getNodes(String)
524 public List<PhylogenyNode> getNodesWithMatchingSpecies( final String specname ) {
528 final List<PhylogenyNode> nodes = new ArrayList<PhylogenyNode>();
529 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
530 final PhylogenyNode n = iter.next();
531 if ( PhylogenyMethods.getSpecies( n ).equals( specname ) ) {
538 public PhylogenyNode getNodeViaSequenceName( final String seq_name ) {
542 final List<PhylogenyNode> nodes = getNodesViaSequenceName( seq_name );
543 if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
544 throw new IllegalArgumentException( "node with sequence named [" + seq_name + "] not found" );
546 if ( nodes.size() > 1 ) {
547 throw new IllegalArgumentException( "node with sequence named [" + seq_name + "] not unique" );
549 return nodes.get( 0 );
552 public PhylogenyNode getNodeViaTaxonomyCode( final String taxonomy_code ) {
556 final List<PhylogenyNode> nodes = getNodesViaTaxonomyCode( taxonomy_code );
557 if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
558 throw new IllegalArgumentException( "node with taxonomy code \"" + taxonomy_code + "\" not found" );
560 if ( nodes.size() > 1 ) {
561 throw new IllegalArgumentException( "node with taxonomy code \"" + taxonomy_code + "\" not unique" );
563 return nodes.get( 0 );
566 public int getNumberOfBranches() {
571 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); iter.next() ) {
581 * Returns the sum of external Nodes of this Phylogeny (int).
583 public int getNumberOfExternalNodes() {
587 return getExternalNodes().size();
591 * Returns all paralogs of the external PhylogenyNode n of this Phylogeny.
592 * paralog are returned as List of node references.
594 * PRECONDITION: This tree must be binary and rooted, and speciation -
595 * duplication need to be assigned for each of its internal Nodes.
597 * Returns null if this Phylogeny is empty or if n is internal.
599 * (Last modified: 11/22/00) Olivier CHABROL :
600 * olivier.chabrol@univ-provence.fr
603 * external PhylogenyNode whose orthologs are to be returned
604 * @return Vector of references to all orthologous Nodes of PhylogenyNode n
605 * of this Phylogeny, null if this Phylogeny is empty or if n is
608 public List<PhylogenyNode> getParalogousNodes( final PhylogenyNode n, final String[] taxonomyCodeRange ) {
609 PhylogenyNode node = n;
610 PhylogenyNode prev = null;
611 final List<PhylogenyNode> v = new ArrayList<PhylogenyNode>();
612 final Map<PhylogenyNode, List<String>> map = new HashMap<PhylogenyNode, List<String>>();
613 getTaxonomyMap( getRoot(), map );
614 if ( !node.isExternal() || isEmpty() ) {
617 final String searchNodeSpeciesId = PhylogenyMethods.getTaxonomyIdentifier( n );
618 if ( !node.isExternal() || isEmpty() ) {
621 List<String> taxIdList = null;
622 final List<String> taxonomyCodeRangeList = Arrays.asList( taxonomyCodeRange );
623 while ( !node.isRoot() ) {
625 node = node.getParent();
626 taxIdList = map.get( node );
627 if ( node.isDuplication() && isContains( taxIdList, taxonomyCodeRangeList ) ) {
628 if ( node.getChildNode1() == prev ) {
629 v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode2()
630 .getAllExternalDescendants() ) );
633 v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode1()
634 .getAllExternalDescendants() ) );
641 public Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> getRelevantSequenceRelationTypes() {
642 if ( _relevant_sequence_relation_types == null ) {
643 _relevant_sequence_relation_types = new Vector<SEQUENCE_RELATION_TYPE>();
645 return _relevant_sequence_relation_types;
649 * Returns the root PhylogenyNode of this Phylogeny.
651 public PhylogenyNode getRoot() {
655 public Collection<Sequence> getSequenceRelationQueries() {
656 return _sequenceRelationQueries;
660 * List all species contains in all leaf under a node Olivier CHABROL :
661 * olivier.chabrol@univ-provence.fr
664 * PhylogenyNode whose sub node species are returned
665 * @return species contains in all leaf under the param node
667 private List<String> getSubNodeTaxonomy( final PhylogenyNode node ) {
668 final List<String> taxonomyList = new ArrayList<String>();
669 final List<PhylogenyNode> childs = node.getAllExternalDescendants();
670 String speciesId = null;
671 for( final PhylogenyNode phylogenyNode : childs ) {
672 // taxId = new Long(phylogenyNode.getTaxonomyID());
673 speciesId = PhylogenyMethods.getTaxonomyIdentifier( phylogenyNode );
674 if ( !taxonomyList.contains( speciesId ) ) {
675 taxonomyList.add( speciesId );
682 * Create a map [<PhylogenyNode, List<String>], the list contains the
683 * species contains in all leaf under phylogeny node Olivier CHABROL :
684 * olivier.chabrol@univ-provence.fr
691 private void getTaxonomyMap( final PhylogenyNode node, final Map<PhylogenyNode, List<String>> map ) {
693 if ( node.isExternal() ) {
696 map.put( node, getSubNodeTaxonomy( node ) );
697 getTaxonomyMap( node.getChildNode1(), map );
698 getTaxonomyMap( node.getChildNode2(), map );
701 public String getType() {
706 * Hashes the ID number of each PhylogenyNode of this Phylogeny to its
707 * corresponding PhylogenyNode, in order to make method getNode( id ) run in
708 * constant time. Important: The user is responsible for calling this method
709 * (again) after this Phylogeny has been changed/created/renumbered.
711 public void hashIDs() {
715 setIdHash( new HashMap<Integer, PhylogenyNode>() );
716 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
717 final PhylogenyNode node = iter.next();
718 getIdHash().put( node.getId(), node );
723 * Deletes this Phylogeny.
736 setAllowMultipleParents( Phylogeny.ALLOW_MULTIPLE_PARENTS_DEFAULT );
739 private boolean isAllowMultipleParents() {
740 return _allow_multiple_parents;
744 * Returns whether this is a completely binary tree (i.e. all internal nodes
748 public boolean isCompletelyBinary() {
752 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
753 final PhylogenyNode node = iter.next();
754 if ( node.isInternal() && ( node.getNumberOfDescendants() != 2 ) ) {
762 * Util method to check if all element of a list is contains in the
763 * rangeList. Olivier CHABROL : olivier.chabrol@univ-provence.fr
768 * the range list to compare
769 * @return <code>true</code> if all param list element are contains in param
770 * rangeList, <code>false</code> otherwise.
772 private boolean isContains( final List<String> list, final List<String> rangeList ) {
773 if ( list.size() > rangeList.size() ) {
777 for( final Iterator<String> iterator = list.iterator(); iterator.hasNext(); ) {
779 if ( !rangeList.contains( l ) ) {
787 * Checks whether a Phylogeny object is deleted (or empty).
789 * @return true if the tree is deleted (or empty), false otherwise
791 public boolean isEmpty() {
792 return ( getRoot() == null );
795 public boolean isRerootable() {
800 * Returns true is this Phylogeny is rooted.
802 public boolean isRooted() {
806 public boolean isTree() {
810 public PhylogenyNodeIterator iteratorExternalForward() {
811 return new ExternalForwardIterator( this );
814 public PhylogenyNodeIterator iteratorLevelOrder() {
815 return new LevelOrderTreeIterator( this );
818 public PhylogenyNodeIterator iteratorPostorder() {
819 return new PostorderTreeIterator( this );
822 public PhylogenyNodeIterator iteratorPreorder() {
823 return new PreorderTreeIterator( this );
827 * Resets the ID numbers of the nodes of this Phylogeny in level order,
828 * starting with start_label (for the root). <br>
829 * WARNING. After this method has been called, node IDs are no longer
832 public void levelOrderReID() {
838 for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); ) {
839 final PhylogenyNode node = it.next();
840 if ( node.isRoot() ) {
841 node.setId( PhylogenyNode.getNodeCount() );
844 node.setId( node.getParent().getId() + 1 );
845 if ( node.getId() > max ) {
850 PhylogenyNode.setNodeCount( max + 1 );
854 * Arranges the order of childern for each node of this Phylogeny in such a
855 * way that either the branch with more children is on top (right) or on
856 * bottom (left), dependent on the value of boolean order.
859 * decides in which direction to order
861 public void orderAppearance( final boolean order ) throws RuntimeException {
863 throw new FailedConditionCheckException( "Attempt to order appearance on phylogeny which is not tree-like." );
868 orderAppearanceHelper( getRoot(), order );
871 // Helper method for "orderAppearance(boolean)".
872 // Traverses this Phylogeny recusively.
873 private void orderAppearanceHelper( final PhylogenyNode n, final boolean order ) {
874 if ( n.isExternal() ) {
878 PhylogenyNode temp = null;
880 if ( ( n.getNumberOfDescendants() == 2 )
881 && ( n.getChildNode1().getNumberOfExternalNodes() != n.getChildNode2().getNumberOfExternalNodes() )
882 && ( ( n.getChildNode1().getNumberOfExternalNodes() < n.getChildNode2().getNumberOfExternalNodes() ) == order ) ) {
883 temp = n.getChildNode1();
884 n.setChild1( n.getChildNode2() );
887 for( int i = 0; i < n.getNumberOfDescendants(); ++i ) {
888 orderAppearanceHelper( n.getChildNode( i ), order );
893 public void preOrderReId() {
898 int i = PhylogenyNode.getNodeCount();
899 for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); ) {
900 it.next().setId( i++ );
902 PhylogenyNode.setNodeCount( i );
906 * Prints descriptions of all external Nodes of this Phylogeny to
909 public void printExtNodes() {
913 for( final PhylogenyNodeIterator iter = iteratorExternalForward(); iter.hasNext(); ) {
914 System.out.println( iter.next() + "\n" );
919 * (Re)counts the number of children for each PhylogenyNode of this
920 * Phylogeny. As an example, this method needs to be called after a
921 * Phylogeny has been reRooted and it is to be displayed.
923 * @param consider_collapsed_nodes
924 * set to true to take into account collapsed nodes (collapsed
925 * nodes have 1 child).
927 public void recalculateNumberOfExternalDescendants( final boolean consider_collapsed_nodes ) {
931 for( final PhylogenyNodeIterator iter = iteratorPostorder(); iter.hasNext(); ) {
932 final PhylogenyNode node = iter.next();
933 if ( node.isExternal() || ( consider_collapsed_nodes && node.isCollapse() ) ) {
934 node.setSumExtNodes( 1 );
938 for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
939 sum += node.getChildNode( i ).getNumberOfExternalNodes();
941 node.setSumExtNodes( sum );
947 * Places the root of this Phylogeny on the parent branch of the
948 * PhylogenyNode with a corresponding ID. The new root is always placed on
949 * the middle of the branch. If the resulting reRooted Phylogeny is to be
950 * used any further, in most cases the following methods have to be called
951 * on the resulting Phylogeny:
953 * <li>recalculateNumberOfExternalDescendants(boolean)
954 * <li>recalculateAndReset()
957 * ID (int) of PhylogenyNode of this Phylogeny
959 public void reRoot( final int id ) {
960 reRoot( getNode( id ) );
964 * Places the root of this Phylogeny on Branch b. The new root is always
965 * placed on the middle of the branch b.
968 public void reRoot( final PhylogenyBranch b ) {
969 final PhylogenyNode n1 = b.getFirstNode();
970 final PhylogenyNode n2 = b.getSecondNode();
971 if ( n1.isExternal() ) {
974 else if ( n2.isExternal() ) {
977 else if ( ( n2 == n1.getChildNode1() ) || ( n2 == n1.getChildNode2() ) ) {
980 else if ( ( n1 == n2.getChildNode1() ) || ( n1 == n2.getChildNode2() ) ) {
983 else if ( ( n1.getParent() != null ) && n1.getParent().isRoot()
984 && ( ( n1.getParent().getChildNode1() == n2 ) || ( n1.getParent().getChildNode2() == n2 ) ) ) {
988 throw new IllegalArgumentException( "reRoot( Branch b ): b is not a branch." );
993 * Places the root of this Phylogeny on the parent branch PhylogenyNode n.
994 * The new root is always placed on the middle of the branch.
996 * If the resulting reRooted Phylogeny is to be used any further, in most
997 * cases the following three methods have to be called on the resulting
1000 * <li>recalculateNumberOfExternalDescendants(boolean) <li>recalculateAndReset()
1003 * (Last modified: 10/01/01)
1006 * PhylogenyNode of this Phylogeny\
1008 public void reRoot( final PhylogenyNode n ) {
1012 public void reRoot( final PhylogenyNode n, final double distance_n_to_parent ) {
1013 if ( isEmpty() || ( getNumberOfExternalNodes() < 2 ) ) {
1020 else if ( n.getParent().isRoot() ) {
1021 if ( ( n.getParent().getNumberOfDescendants() == 2 ) && ( distance_n_to_parent >= 0 ) ) {
1022 final double d = n.getParent().getChildNode1().getDistanceToParent()
1023 + n.getParent().getChildNode2().getDistanceToParent();
1024 PhylogenyNode other;
1025 if ( n.getChildNodeIndex() == 0 ) {
1026 other = n.getParent().getChildNode2();
1029 other = n.getParent().getChildNode1();
1031 n.setDistanceToParent( distance_n_to_parent );
1032 final double dm = d - distance_n_to_parent;
1034 other.setDistanceToParent( dm );
1037 other.setDistanceToParent( 0 );
1040 if ( n.getParent().getNumberOfDescendants() > 2 ) {
1041 final int index = n.getChildNodeIndex();
1042 final double dn = n.getDistanceToParent();
1043 final PhylogenyNode prev_root = getRoot();
1044 prev_root.getDescendants().remove( index );
1045 final PhylogenyNode new_root = new PhylogenyNode();
1046 new_root.setChildNode( 0, n );
1047 new_root.setChildNode( 1, prev_root );
1048 if ( n.getBranchDataDirectly() != null ) {
1049 prev_root.setBranchData( ( BranchData ) n.getBranchDataDirectly().copy() );
1051 setRoot( new_root );
1052 if ( distance_n_to_parent >= 0 ) {
1053 n.setDistanceToParent( distance_n_to_parent );
1054 final double d = dn - distance_n_to_parent;
1056 prev_root.setDistanceToParent( d );
1059 prev_root.setDistanceToParent( 0 );
1064 final double d = dn / 2.0;
1065 n.setDistanceToParent( d );
1066 prev_root.setDistanceToParent( d );
1072 PhylogenyNode a = n;
1073 PhylogenyNode b = null;
1074 PhylogenyNode c = null;
1075 final PhylogenyNode new_root = new PhylogenyNode();
1076 double distance1 = 0.0;
1077 double distance2 = 0.0;
1078 BranchData branch_data_1 = null;
1079 BranchData branch_data_2 = null;
1082 new_root.setChildNode( 0, a );
1083 new_root.setChildNode( 1, b );
1084 distance1 = c.getDistanceToParent();
1085 if ( c.getBranchDataDirectly() != null ) {
1086 branch_data_1 = ( BranchData ) c.getBranchDataDirectly().copy();
1088 c.setDistanceToParent( b.getDistanceToParent() );
1089 if ( b.getBranchDataDirectly() != null ) {
1090 c.setBranchData( ( BranchData ) b.getBranchDataDirectly().copy() );
1092 if ( a.getBranchDataDirectly() != null ) {
1093 b.setBranchData( ( BranchData ) a.getBranchDataDirectly().copy() );
1095 // New root is always placed in the middle of the branch:
1096 if ( a.getDistanceToParent() == PhylogenyNode.DISTANCE_DEFAULT ) {
1097 b.setDistanceToParent( PhylogenyNode.DISTANCE_DEFAULT );
1100 if ( distance_n_to_parent >= 0.0 ) {
1101 final double diff = a.getDistanceToParent() - distance_n_to_parent;
1102 a.setDistanceToParent( distance_n_to_parent );
1103 b.setDistanceToParent( diff >= 0.0 ? diff : 0.0 );
1106 final double d = a.getDistanceToParent() / 2.0;
1107 a.setDistanceToParent( d );
1108 b.setDistanceToParent( d );
1111 b.setChildNodeOnly( a.getChildNodeIndex( b ), c );
1112 // moving to the old root, swapping references:
1113 while ( !c.isRoot() ) {
1117 b.setChildNodeOnly( a.getChildNodeIndex( b ), c );
1119 distance2 = c.getDistanceToParent();
1120 branch_data_2 = c.getBranchDataDirectly();
1121 c.setDistanceToParent( distance1 );
1122 c.setBranchData( branch_data_1 );
1123 distance1 = distance2;
1124 branch_data_1 = branch_data_2;
1126 // removing the old root:
1127 if ( c.getNumberOfDescendants() == 2 ) {
1128 final PhylogenyNode node = c.getChildNode( 1 - b.getChildNodeIndex( c ) );
1129 node.setParent( b );
1130 if ( ( c.getDistanceToParent() == PhylogenyNode.DISTANCE_DEFAULT )
1131 && ( node.getDistanceToParent() == PhylogenyNode.DISTANCE_DEFAULT ) ) {
1132 node.setDistanceToParent( PhylogenyNode.DISTANCE_DEFAULT );
1135 node.setDistanceToParent( ( c.getDistanceToParent() >= 0.0 ? c.getDistanceToParent() : 0.0 )
1136 + ( node.getDistanceToParent() >= 0.0 ? node.getDistanceToParent() : 0.0 ) );
1138 if ( c.getBranchDataDirectly() != null ) {
1139 node.setBranchData( ( BranchData ) c.getBranchDataDirectly().copy() );
1141 for( int i = 0; i < b.getNumberOfDescendants(); ++i ) {
1142 if ( b.getChildNode( i ) == c ) {
1143 b.setChildNodeOnly( i, node );
1150 c.removeChildNode( b.getChildNodeIndex( c ) );
1152 setRoot( new_root );
1157 * Sets all Nodes of this Phylogeny to not-collapsed.
1159 * In most cases methods adjustNodeCount(false) and recalculateAndReset()
1160 * need to be called after this method has been called.
1162 public void setAllNodesToNotCollapse() {
1166 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1167 final PhylogenyNode node = iter.next();
1168 node.setCollapse( false );
1172 private void setAllowMultipleParents( final boolean allow_multiple_parents ) {
1173 _allow_multiple_parents = allow_multiple_parents;
1176 public void setConfidence( final Confidence confidence ) {
1177 _confidence = confidence;
1180 public void setDescription( final String description ) {
1181 _description = description;
1184 public void setDistanceUnit( final String _distance_unit ) {
1185 this._distance_unit = _distance_unit;
1188 public void setIdentifier( final Identifier identifier ) {
1189 _identifier = identifier;
1192 void setIdHash( final HashMap<Integer, PhylogenyNode> idhash ) {
1197 * Sets the indicators of all Nodes of this Phylogeny to 0.
1199 public void setIndicatorsToZero() {
1203 for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1204 iter.next().setIndicator( ( byte ) 0 );
1206 } // setIndicatorsToZero()
1209 * Sets the name of this Phylogeny to s.
1211 public void setName( final String s ) {
1215 public void setRelevantSequenceRelationTypes( final Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> types ) {
1216 _relevant_sequence_relation_types = types;
1219 public void setRerootable( final boolean rerootable ) {
1220 _rerootable = rerootable;
1223 public void setRoot( final PhylogenyNode n ) {
1225 } // setRoot( PhylogenyNode )
1228 * Sets whether this Phylogeny is rooted or not.
1230 public void setRooted( final boolean b ) {
1232 } // setRooted( boolean )
1234 public void setSequenceRelationQueries( final Collection<Sequence> sequencesByName ) {
1235 _sequenceRelationQueries = sequencesByName;
1238 public void setType( final String type ) {
1243 * Swaps the the two childern of a PhylogenyNode node of this Phylogeny.
1245 * (Last modified: 06/13/01)
1248 * a PhylogenyNode of this Phylogeny
1250 public void swapChildren( final PhylogenyNode node ) throws RuntimeException {
1252 throw new FailedConditionCheckException( "Attempt to swap children on phylogeny which is not tree-like." );
1254 if ( isEmpty() || node.isExternal() || ( node.getNumberOfDescendants() < 2 ) ) {
1257 final PhylogenyNode first = node.getFirstChildNode();
1258 for( int i = 1; i < node.getNumberOfDescendants(); ++i ) {
1259 node.setChildNode( i - 1, node.getChildNode( i ) );
1261 node.setChildNode( node.getNumberOfDescendants() - 1, first );
1262 } // swapChildren( PhylogenyNode )
1264 public String toNewHampshire() {
1265 return toNewHampshire( false );
1268 public String toNewHampshire( final boolean simple_nh ) {
1270 return new PhylogenyWriter().toNewHampshire( this, simple_nh, true ).toString();
1272 catch ( final IOException e ) {
1273 throw new Error( "this should not have happend: " + e.getMessage() );
1277 public String toNewHampshireX() {
1279 return new PhylogenyWriter().toNewHampshireX( this ).toString();
1281 catch ( final IOException e ) {
1282 throw new Error( "this should not have happend: " + e.getMessage() );
1286 public String toNexus() {
1288 return new PhylogenyWriter().toNexus( this ).toString();
1290 catch ( final IOException e ) {
1291 throw new Error( "this should not have happend: " + e.getMessage() );
1295 public String toPhyloXML( final int phyloxml_level ) {
1297 return new PhylogenyWriter().toPhyloXML( this, phyloxml_level ).toString();
1299 catch ( final IOException e ) {
1300 throw new Error( "this should not have happend: " + e.getMessage() );
1304 // ---------------------------------------------------------
1305 // Writing of Phylogeny to Strings
1306 // ---------------------------------------------------------
1308 * Converts this Phylogeny to a New Hampshire X (String) representation.
1310 * @return New Hampshire X (String) representation of this
1311 * @see #toNewHampshireX()
1314 public String toString() {
1315 return toNewHampshireX();
1319 * Removes the root PhylogenyNode this Phylogeny.
1321 public void unRoot() throws RuntimeException {
1323 throw new FailedConditionCheckException( "Attempt to unroot a phylogeny which is not tree-like." );
1328 setIndicatorsToZero();
1329 if ( !isRooted() || ( getNumberOfExternalNodes() <= 1 ) ) {