forester/java/src/org/forester/phylogeny/Phylogeny.java

   1 // $Id:
   2 // FORESTER -- software libraries and applications
   3 // for evolutionary biology research and applications.
   4 //
   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
   9 // All rights reserved
  10 //
  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.
  15 //
  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.
  20 //
  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
  24 //
  25 // Contact: phylosoft @ gmail . com
  26 // WWW: www.phylosoft.org/forester
  27
  28 package org.forester.phylogeny;
  29
  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;
  37 import java.util.Map;
  38 import java.util.NoSuchElementException;
  39 import java.util.Vector;
  40
  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;
  55
  56 public class Phylogeny {
  57
  58     public final static boolean                                 ALLOW_MULTIPLE_PARENTS_DEFAULT = false;
  59     private PhylogenyNode                                       _root;
  60     private boolean                                             _rooted;
  61     private boolean                                             _allow_multiple_parents;
  62     private String                                              _name;
  63     private String                                              _type;
  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;
  73
  74     /**
  75      * Default Phylogeny constructor. Constructs an empty Phylogeny.
  76      */
  77     public Phylogeny() {
  78         init();
  79     }
  80
  81     /**
  82      * Adds this Phylogeny to the list of child nodes of PhylogenyNode parent
  83      * and sets the parent of this to parent.
  84      *
  85      * @param n
  86      *            the PhylogenyNode to add
  87      */
  88     public void addAsChild( final PhylogenyNode parent ) {
  89         if ( isEmpty() ) {
  90             throw new IllegalArgumentException( "Attempt to add an empty tree." );
  91         }
  92         if ( !isRooted() ) {
  93             throw new IllegalArgumentException( "Attempt to add an unrooted tree." );
  94         }
  95         parent.addAsChild( getRoot() );
  96         externalNodesHaveChanged();
  97     }
  98
  99     public void addAsSibling( final PhylogenyNode sibling ) {
 100         if ( isEmpty() ) {
 101             throw new IllegalArgumentException( "Attempt to add an empty tree." );
 102         }
 103         if ( !isRooted() ) {
 104             throw new IllegalArgumentException( "Attempt to add an unrooted tree." );
 105         }
 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();
 119     }
 120
 121     /**
 122      * This calculates the height of the subtree emanating at n for rooted,
 123      * tree-shaped phylogenies
 124      *
 125      * @param n
 126      *            the root-node of a subtree
 127      * @return the height of the subtree emanating at n
 128      */
 129     public double calculateSubtreeHeight( final PhylogenyNode n ) {
 130         if ( n.isExternal() || n.isCollapse() ) {
 131             return ForesterUtil.isLargerOrEqualToZero( n.getDistanceToParent() );
 132         }
 133         else {
 134             double max = -Double.MAX_VALUE;
 135             for( int i = 0; i < n.getNumberOfDescendants(); ++i ) {
 136                 final double l = calculateSubtreeHeight( n.getChildNode( i ) );
 137                 if ( l > max ) {
 138                     max = l;
 139                 }
 140             }
 141             return max + ForesterUtil.isLargerOrEqualToZero( n.getDistanceToParent() );
 142         }
 143     }
 144
 145     /**
 146      * Returns a deep copy of this Phylogeny.
 147      * <p>
 148      * (The resulting Phylogeny has its references in the external nodes
 149      * corrected, if they are lacking/obsolete in this.)
 150      */
 151     public Phylogeny copy() {
 152         return copy( _root );
 153     }
 154
 155     /**
 156      * Returns a shallow copy of this Phylogeny.
 157      * <p>
 158      * (The resulting Phylogeny has its references in the external nodes
 159      * corrected, if they are lacking/obsolete in this.)
 160      */
 161     public Phylogeny copyShallow() {
 162         return copyShallow( _root );
 163     }
 164
 165     public Phylogeny copyShallow( final PhylogenyNode source ) {
 166         final Phylogeny tree = new Phylogeny();
 167         if ( isEmpty() ) {
 168             tree.init();
 169             return tree;
 170         }
 171         tree._rooted = _rooted;
 172         tree._name = _name;
 173         tree._description = _description;
 174         tree._type = _type;
 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 );
 181         return tree;
 182     }
 183
 184     /**
 185      * Returns a deep copy of this Phylogeny.
 186      * <p>
 187      * (The resulting Phylogeny has its references in the external nodes
 188      * corrected, if they are lacking/obsolete in this.)
 189      */
 190     public Phylogeny copy( final PhylogenyNode source ) {
 191         final Phylogeny tree = new Phylogeny();
 192         if ( isEmpty() ) {
 193             tree.init();
 194             return tree;
 195         }
 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();
 204         }
 205         if ( _identifier != null ) {
 206             tree._identifier = ( Identifier ) _identifier.copy();
 207         }
 208         tree.setAllowMultipleParents( isAllowMultipleParents() );
 209         tree._root = PhylogenyMethods.copySubTree( source );
 210         return tree;
 211     }
 212
 213     /**
 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.
 218      *
 219      * @param remove_us the parent node of the subtree to be deleted
 220      */
 221     public void deleteSubtree( final PhylogenyNode remove_us, final boolean collapse_resulting_node_with_one_desc ) {
 222         if ( isEmpty() ) {
 223             return;
 224         }
 225         if ( remove_us.isRoot() ) {
 226             init();
 227             return;
 228         }
 229         if ( !collapse_resulting_node_with_one_desc ) {
 230             remove_us.getParent().removeChildNode( remove_us );
 231         }
 232         else {
 233             final PhylogenyNode removed_node = remove_us;
 234             final PhylogenyNode p = remove_us.getParent();
 235             if ( p.isRoot() ) {
 236                 if ( p.getNumberOfDescendants() == 2 ) {
 237                     if ( removed_node.isFirstChildNode() ) {
 238                         setRoot( getRoot().getChildNode( 1 ) );
 239                         getRoot().setParent( null );
 240                     }
 241                     else {
 242                         setRoot( getRoot().getChildNode( 0 ) );
 243                         getRoot().setParent( null );
 244                     }
 245                 }
 246                 else {
 247                     p.removeChildNode( removed_node.getChildNodeIndex() );
 248                 }
 249             }
 250             else {
 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 ) );
 258                     }
 259                     else {
 260                         p.getChildNode( 0 ).setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p
 261                                 .getDistanceToParent(), p.getChildNode( 0 ).getDistanceToParent() ) );
 262                         pp.setChildNode( pi, p.getChildNode( 0 ) );
 263                     }
 264                 }
 265                 else {
 266                     p.removeChildNode( removed_node.getChildNodeIndex() );
 267                 }
 268             }
 269         }
 270         remove_us.setParent( null );
 271         setIdHash( null );
 272         externalNodesHaveChanged();
 273     }
 274
 275     public void externalNodesHaveChanged() {
 276         _external_nodes_set = null;
 277     }
 278
 279     public String[] getAllExternalNodeNames() {
 280         int i = 0;
 281         if ( isEmpty() ) {
 282             return null;
 283         }
 284         final String[] names = new String[ getNumberOfExternalNodes() ];
 285         for( final PhylogenyNodeIterator iter = iteratorExternalForward(); iter.hasNext(); ) {
 286             names[ i++ ] = new String( iter.next().getName() );
 287         }
 288         return names;
 289     }
 290
 291     public Confidence getConfidence() {
 292         return _confidence;
 293     }
 294
 295     public String getDescription() {
 296         return _description;
 297     }
 298
 299     public String getDistanceUnit() {
 300         return _distance_unit;
 301     }
 302
 303     /**
 304      *
 305      * Warning. The order of the returned nodes is random
 306      * -- and hence cannot be relied on.
 307      *
 308      * @return Unordered set of PhylogenyNode
 309      */
 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 );
 317                 }
 318             }
 319         }
 320         return _external_nodes_set;
 321     }
 322
 323     /**
 324      * Returns the number of duplications of this Phylogeny (int). A return
 325      * value of -1 indicates that the number of duplications is unknown.
 326      */
 327     // public int getNumberOfDuplications() {
 328     // return _number_of_duplications;
 329     // } // getNumberOfDuplications()
 330     /**
 331      * Sets the number of duplications of this Phylogeny (int). A value of -1
 332      * indicates that the number of duplications is unknown.
 333      *
 334      * @param clean_nh
 335      *            set to true for clean NH format
 336      */
 337     // public void setNumberOfDuplications( int i ) {
 338     // if ( i < 0 ) {
 339     // _number_of_duplications = -1;
 340     // }
 341     // else {
 342     // _number_of_duplications = i;
 343     // }
 344     // } // setNumberOfDuplications( int )
 345     /**
 346      * Returns the first external PhylogenyNode.
 347      */
 348     public PhylogenyNode getFirstExternalNode() {
 349         if ( isEmpty() ) {
 350             throw new FailedConditionCheckException( "attempt to obtain first external node of empty phylogeney" );
 351         }
 352         PhylogenyNode node = getRoot();
 353         while ( node.isInternal() ) {
 354             node = node.getFirstChildNode();
 355         }
 356         return node;
 357     }
 358
 359     /**
 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.
 364      *
 365      * @return the height for rooted, tree-shaped phylogenies
 366      */
 367     public double getHeight() {
 368         if ( isEmpty() ) {
 369             return 0.0;
 370         }
 371         return calculateSubtreeHeight( getRoot() );
 372     }
 373
 374     public Identifier getIdentifier() {
 375         return _identifier;
 376     }
 377
 378     // ---------------------------------------------------------
 379     // Modification of Phylogeny topology and Phylogeny appearance
 380     // ---------------------------------------------------------
 381     private HashMap<Integer, PhylogenyNode> getIdHash() {
 382         return _idhash;
 383     }
 384
 385     /**
 386      * Returns the name of this Phylogeny.
 387      */
 388     public String getName() {
 389         return _name;
 390     }
 391
 392     /**
 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
 395      * constant time.
 396      *
 397      * @param id
 398      *            ID number (int) of the PhylogenyNode to find
 399      * @return PhylogenyNode with matching ID, null if not found
 400      */
 401     public PhylogenyNode getNode( final int id ) throws NoSuchElementException {
 402         if ( isEmpty() ) {
 403             throw new NoSuchElementException( "attempt to get node in an empty phylogeny" );
 404         }
 405         if ( _idhash != null ) {
 406             return _idhash.get( id );
 407         }
 408         else {
 409             for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 410                 final PhylogenyNode node = iter.next();
 411                 if ( node.getId() == id ) {
 412                     return node;
 413                 }
 414             }
 415         }
 416         return null;
 417     }
 418
 419     /**
 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.
 422      *
 423      * @param name
 424      *            name (String) of PhylogenyNode to find
 425      * @return PhylogenyNode with matchin name
 426      */
 427     public PhylogenyNode getNode( final String name ) {
 428         if ( isEmpty() ) {
 429             return null;
 430         }
 431         final List<PhylogenyNode> nodes = getNodes( name );
 432         if ( ( nodes == null ) || ( nodes.size() < 1 ) ) {
 433             throw new IllegalArgumentException( "node named [" + name + "] not found" );
 434         }
 435         if ( nodes.size() > 1 ) {
 436             throw new IllegalArgumentException( "node named [" + name + "] not unique" );
 437         }
 438         return nodes.get( 0 );
 439     }
 440
 441     /**
 442      * Return Node by TaxonomyId Olivier CHABROL :
 443      * olivier.chabrol@univ-provence.fr
 444      *
 445      * @param taxonomyID
 446      *            search taxonomy identifier
 447      * @param nodes
 448      *            sublist node to search
 449      * @return List node with the same taxonomy identifier
 450      */
 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 ) ) ) {
 455                 retour.add( node );
 456             }
 457         }
 458         return retour;
 459     }
 460
 461     /**
 462      * Returns a List with references to all Nodes of this Phylogeny which have
 463      * a matching name.
 464      *
 465      * @param name
 466      *            name (String) of Nodes to find
 467      * @return Vector of references to Nodes of this Phylogeny with matching
 468      *         names
 469      * @see #getNodesWithMatchingSpecies(String)
 470      */
 471     public List<PhylogenyNode> getNodes( final String name ) {
 472         if ( isEmpty() ) {
 473             return null;
 474         }
 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 ) ) {
 479                 nodes.add( n );
 480             }
 481         }
 482         return nodes;
 483     }
 484
 485     public List<PhylogenyNode> getNodesViaSequenceName( final String seq_name ) {
 486         if ( isEmpty() ) {
 487             return null;
 488         }
 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 ) ) {
 493                 nodes.add( n );
 494             }
 495         }
 496         return nodes;
 497     }
 498
 499     public List<PhylogenyNode> getNodesViaTaxonomyCode( final String taxonomy_code ) {
 500         if ( isEmpty() ) {
 501             return null;
 502         }
 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 ) ) {
 508                 nodes.add( n );
 509             }
 510         }
 511         return nodes;
 512     }
 513
 514     /**
 515      * Returns a Vector with references to all Nodes of this Phylogeny which
 516      * have a matching species name.
 517      *
 518      * @param specname
 519      *            species name (String) of Nodes to find
 520      * @return Vector of references to Nodes of this Phylogeny with matching
 521      *         species names.
 522      * @see #getNodes(String)
 523      */
 524     public List<PhylogenyNode> getNodesWithMatchingSpecies( final String specname ) {
 525         if ( isEmpty() ) {
 526             return null;
 527         }
 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 ) ) {
 532                 nodes.add( n );
 533             }
 534         }
 535         return nodes;
 536     }
 537
 538     public PhylogenyNode getNodeViaSequenceName( final String seq_name ) {
 539         if ( isEmpty() ) {
 540             return null;
 541         }
 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" );
 545         }
 546         if ( nodes.size() > 1 ) {
 547             throw new IllegalArgumentException( "node with sequence named [" + seq_name + "] not unique" );
 548         }
 549         return nodes.get( 0 );
 550     }
 551
 552     public PhylogenyNode getNodeViaTaxonomyCode( final String taxonomy_code ) {
 553         if ( isEmpty() ) {
 554             return null;
 555         }
 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" );
 559         }
 560         if ( nodes.size() > 1 ) {
 561             throw new IllegalArgumentException( "node with taxonomy code \"" + taxonomy_code + "\" not unique" );
 562         }
 563         return nodes.get( 0 );
 564     }
 565
 566     /**
 567      * This is time-inefficient since it runs a iterator each time it is called.
 568      *
 569      */
 570     public int getNodeCount() {
 571         if ( isEmpty() ) {
 572             return 0;
 573         }
 574         int c = 0;
 575         for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); it.next() ) {
 576             ++c;
 577         }
 578         return c;
 579     }
 580
 581     public int getNumberOfBranches() {
 582         if ( isEmpty() ) {
 583             return 0;
 584         }
 585         int c = 0;
 586         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); iter.next() ) {
 587             ++c;
 588         }
 589         if ( !isRooted() ) {
 590             --c;
 591         }
 592         return c;
 593     }
 594
 595     /**
 596      * Returns the sum of external Nodes of this Phylogeny (int).
 597      */
 598     public int getNumberOfExternalNodes() {
 599         if ( isEmpty() ) {
 600             return 0;
 601         }
 602         return getExternalNodes().size();
 603     }
 604
 605     /**
 606      * Returns all paralogs of the external PhylogenyNode n of this Phylogeny.
 607      * paralog are returned as List of node references.
 608      * <p>
 609      * PRECONDITION: This tree must be binary and rooted, and speciation -
 610      * duplication need to be assigned for each of its internal Nodes.
 611      * <p>
 612      * Returns null if this Phylogeny is empty or if n is internal.
 613      * <p>
 614      * (Last modified: 11/22/00) Olivier CHABROL :
 615      * olivier.chabrol@univ-provence.fr
 616      *
 617      * @param n
 618      *            external PhylogenyNode whose orthologs are to be returned
 619      * @return Vector of references to all orthologous Nodes of PhylogenyNode n
 620      *         of this Phylogeny, null if this Phylogeny is empty or if n is
 621      *         internal
 622      */
 623     public List<PhylogenyNode> getParalogousNodes( final PhylogenyNode n, final String[] taxonomyCodeRange ) {
 624         PhylogenyNode node = n;
 625         PhylogenyNode prev = null;
 626         final List<PhylogenyNode> v = new ArrayList<PhylogenyNode>();
 627         final Map<PhylogenyNode, List<String>> map = new HashMap<PhylogenyNode, List<String>>();
 628         getTaxonomyMap( getRoot(), map );
 629         if ( !node.isExternal() || isEmpty() ) {
 630             return null;
 631         }
 632         final String searchNodeSpeciesId = PhylogenyMethods.getTaxonomyIdentifier( n );
 633         if ( !node.isExternal() || isEmpty() ) {
 634             return null;
 635         }
 636         List<String> taxIdList = null;
 637         final List<String> taxonomyCodeRangeList = Arrays.asList( taxonomyCodeRange );
 638         while ( !node.isRoot() ) {
 639             prev = node;
 640             node = node.getParent();
 641             taxIdList = map.get( node );
 642             if ( node.isDuplication() && isContains( taxIdList, taxonomyCodeRangeList ) ) {
 643                 if ( node.getChildNode1() == prev ) {
 644                     v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode2()
 645                             .getAllExternalDescendants() ) );
 646                 }
 647                 else {
 648                     v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode1()
 649                             .getAllExternalDescendants() ) );
 650                 }
 651             }
 652         }
 653         return v;
 654     }
 655
 656     public Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> getRelevantSequenceRelationTypes() {
 657         if ( _relevant_sequence_relation_types == null ) {
 658             _relevant_sequence_relation_types = new Vector<SEQUENCE_RELATION_TYPE>();
 659         }
 660         return _relevant_sequence_relation_types;
 661     }
 662
 663     /**
 664      * Returns the root PhylogenyNode of this Phylogeny.
 665      */
 666     public PhylogenyNode getRoot() {
 667         return _root;
 668     }
 669
 670     public Collection<Sequence> getSequenceRelationQueries() {
 671         return _sequenceRelationQueries;
 672     }
 673
 674     /**
 675      * List all species contains in all leaf under a node Olivier CHABROL :
 676      * olivier.chabrol@univ-provence.fr
 677      *
 678      * @param node
 679      *            PhylogenyNode whose sub node species are returned
 680      * @return species contains in all leaf under the param node
 681      */
 682     private List<String> getSubNodeTaxonomy( final PhylogenyNode node ) {
 683         final List<String> taxonomyList = new ArrayList<String>();
 684         final List<PhylogenyNode> childs = node.getAllExternalDescendants();
 685         String speciesId = null;
 686         for( final PhylogenyNode phylogenyNode : childs ) {
 687             // taxId = new Long(phylogenyNode.getTaxonomyID());
 688             speciesId = PhylogenyMethods.getTaxonomyIdentifier( phylogenyNode );
 689             if ( !taxonomyList.contains( speciesId ) ) {
 690                 taxonomyList.add( speciesId );
 691             }
 692         }
 693         return taxonomyList;
 694     }
 695
 696     /**
 697      * Create a map [<PhylogenyNode, List<String>], the list contains the
 698      * species contains in all leaf under phylogeny node Olivier CHABROL :
 699      * olivier.chabrol@univ-provence.fr
 700      *
 701      * @param node
 702      *            the tree root node
 703      * @param map
 704      *            map to fill
 705      */
 706     private void getTaxonomyMap( final PhylogenyNode node, final Map<PhylogenyNode, List<String>> map ) {
 707         // node is leaf
 708         if ( node.isExternal() ) {
 709             return;
 710         }
 711         map.put( node, getSubNodeTaxonomy( node ) );
 712         getTaxonomyMap( node.getChildNode1(), map );
 713         getTaxonomyMap( node.getChildNode2(), map );
 714     }
 715
 716     public String getType() {
 717         return _type;
 718     }
 719
 720     /**
 721      * Hashes the ID number of each PhylogenyNode of this Phylogeny to its
 722      * corresponding PhylogenyNode, in order to make method getNode( id ) run in
 723      * constant time. Important: The user is responsible for calling this method
 724      * (again) after this Phylogeny has been changed/created/renumbered.
 725      */
 726     public void hashIDs() {
 727         if ( isEmpty() ) {
 728             return;
 729         }
 730         setIdHash( new HashMap<Integer, PhylogenyNode>() );
 731         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 732             final PhylogenyNode node = iter.next();
 733             getIdHash().put( node.getId(), node );
 734         }
 735     }
 736
 737     /**
 738      * Deletes this Phylogeny.
 739      */
 740     public void init() {
 741         _root = null;
 742         _rooted = false;
 743         _name = "";
 744         _description = "";
 745         _type = "";
 746         _distance_unit = "";
 747         _idhash = null;
 748         _confidence = null;
 749         _identifier = null;
 750         _rerootable = true;
 751         setAllowMultipleParents( Phylogeny.ALLOW_MULTIPLE_PARENTS_DEFAULT );
 752     }
 753
 754     private boolean isAllowMultipleParents() {
 755         return _allow_multiple_parents;
 756     }
 757
 758     /**
 759      * Returns whether this is a completely binary tree (i.e. all internal nodes
 760      * are bifurcations).
 761      *
 762      */
 763     public boolean isCompletelyBinary() {
 764         if ( isEmpty() ) {
 765             return false;
 766         }
 767         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
 768             final PhylogenyNode node = iter.next();
 769             if ( node.isInternal() && ( node.getNumberOfDescendants() != 2 ) ) {
 770                 return false;
 771             }
 772         }
 773         return true;
 774     }
 775
 776     /**
 777      * Util method to check if all element of a list is contains in the
 778      * rangeList. Olivier CHABROL : olivier.chabrol@univ-provence.fr
 779      *
 780      * @param list
 781      *            list to be check
 782      * @param rangeList
 783      *            the range list to compare
 784      * @return <code>true</code> if all param list element are contains in param
 785      *         rangeList, <code>false</code> otherwise.
 786      */
 787     private boolean isContains( final List<String> list, final List<String> rangeList ) {
 788         if ( list.size() > rangeList.size() ) {
 789             return false;
 790         }
 791         String l = null;
 792         for( final Iterator<String> iterator = list.iterator(); iterator.hasNext(); ) {
 793             l = iterator.next();
 794             if ( !rangeList.contains( l ) ) {
 795                 return false;
 796             }
 797         }
 798         return true;
 799     }
 800
 801     /**
 802      * Checks whether a Phylogeny object is deleted (or empty).
 803      *
 804      * @return true if the tree is deleted (or empty), false otherwise
 805      */
 806     public boolean isEmpty() {
 807         return ( getRoot() == null );
 808     }
 809
 810     public boolean isRerootable() {
 811         return _rerootable;
 812     }
 813
 814     /**
 815      * Returns true is this Phylogeny is rooted.
 816      */
 817     public boolean isRooted() {
 818         return _rooted;
 819     } // isRooted()
 820
 821     public boolean isTree() {
 822         return true;
 823     }
 824
 825     public PhylogenyNodeIterator iteratorExternalForward() {
 826         return new ExternalForwardIterator( this );
 827     }
 828
 829     public PhylogenyNodeIterator iteratorLevelOrder() {
 830         return new LevelOrderTreeIterator( this );
 831     }
 832
 833     public PhylogenyNodeIterator iteratorPostorder() {
 834         return new PostorderTreeIterator( this );
 835     }
 836
 837     public PhylogenyNodeIterator iteratorPreorder() {
 838         return new PreorderTreeIterator( this );
 839     }
 840
 841     /**
 842      * Resets the ID numbers of the nodes of this Phylogeny in level order,
 843      * starting with start_label (for the root). <br>
 844      * WARNING. After this method has been called, node IDs are no longer
 845      * unique.
 846      */
 847     public void levelOrderReID() {
 848         if ( isEmpty() ) {
 849             return;
 850         }
 851         _idhash = null;
 852         int max = 0;
 853         for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); ) {
 854             final PhylogenyNode node = it.next();
 855             if ( node.isRoot() ) {
 856                 node.setId( PhylogenyNode.getNodeCount() );
 857             }
 858             else {
 859                 node.setId( node.getParent().getId() + 1 );
 860                 if ( node.getId() > max ) {
 861                     max = node.getId();
 862                 }
 863             }
 864         }
 865         PhylogenyNode.setNodeCount( max + 1 );
 866     }
 867
 868     /**
 869      * Arranges the order of childern for each node of this Phylogeny in such a
 870      * way that either the branch with more children is on top (right) or on
 871      * bottom (left), dependent on the value of boolean order.
 872      *
 873      * @param order
 874      *            decides in which direction to order
 875      */
 876     public void orderAppearance( final boolean order ) throws RuntimeException {
 877         if ( !isTree() ) {
 878             throw new FailedConditionCheckException( "Attempt to order appearance on phylogeny which is not tree-like." );
 879         }
 880         if ( isEmpty() ) {
 881             return;
 882         }
 883         orderAppearanceHelper( getRoot(), order );
 884     }
 885
 886     // Helper method for "orderAppearance(boolean)".
 887     // Traverses this Phylogeny recusively.
 888     private void orderAppearanceHelper( final PhylogenyNode n, final boolean order ) {
 889         if ( n.isExternal() ) {
 890             return;
 891         }
 892         else {
 893             PhylogenyNode temp = null;
 894             // FIXME
 895             if ( ( n.getNumberOfDescendants() == 2 )
 896                     && ( n.getChildNode1().getNumberOfExternalNodes() != n.getChildNode2().getNumberOfExternalNodes() )
 897                     && ( ( n.getChildNode1().getNumberOfExternalNodes() < n.getChildNode2().getNumberOfExternalNodes() ) == order ) ) {
 898                 temp = n.getChildNode1();
 899                 n.setChild1( n.getChildNode2() );
 900                 n.setChild2( temp );
 901             }
 902             for( int i = 0; i < n.getNumberOfDescendants(); ++i ) {
 903                 orderAppearanceHelper( n.getChildNode( i ), order );
 904             }
 905         }
 906     }
 907
 908     public void preOrderReId() {
 909         if ( isEmpty() ) {
 910             return;
 911         }
 912         setIdHash( null );
 913         int i = PhylogenyNode.getNodeCount();
 914         for( final PhylogenyNodeIterator it = iteratorPreorder(); it.hasNext(); ) {
 915             it.next().setId( i++ );
 916         }
 917         PhylogenyNode.setNodeCount( i );
 918     }
 919
 920     /**
 921      * Prints descriptions of all external Nodes of this Phylogeny to
 922      * System.out.
 923      */
 924     public void printExtNodes() {
 925         if ( isEmpty() ) {
 926             return;
 927         }
 928         for( final PhylogenyNodeIterator iter = iteratorExternalForward(); iter.hasNext(); ) {
 929             System.out.println( iter.next() + "\n" );
 930         }
 931     }
 932
 933     /**
 934      * (Re)counts the number of children for each PhylogenyNode of this
 935      * Phylogeny. As an example, this method needs to be called after a
 936      * Phylogeny has been reRooted and it is to be displayed.
 937      *
 938      * @param consider_collapsed_nodes
 939      *            set to true to take into account collapsed nodes (collapsed
 940      *            nodes have 1 child).
 941      */
 942     public void recalculateNumberOfExternalDescendants( final boolean consider_collapsed_nodes ) {
 943         if ( isEmpty() ) {
 944             return;
 945         }
 946         for( final PhylogenyNodeIterator iter = iteratorPostorder(); iter.hasNext(); ) {
 947             final PhylogenyNode node = iter.next();
 948             if ( node.isExternal() || ( consider_collapsed_nodes && node.isCollapse() ) ) {
 949                 node.setSumExtNodes( 1 );
 950             }
 951             else {
 952                 int sum = 0;
 953                 for( int i = 0; i < node.getNumberOfDescendants(); ++i ) {
 954                     sum += node.getChildNode( i ).getNumberOfExternalNodes();
 955                 }
 956                 node.setSumExtNodes( sum );
 957             }
 958         }
 959     }
 960
 961     /**
 962      * Places the root of this Phylogeny on the parent branch of the
 963      * PhylogenyNode with a corresponding ID. The new root is always placed on
 964      * the middle of the branch. If the resulting reRooted Phylogeny is to be
 965      * used any further, in most cases the following methods have to be called
 966      * on the resulting Phylogeny:
 967      * <p>
 968      * <li>recalculateNumberOfExternalDescendants(boolean)
 969      * <li>recalculateAndReset()
 970      *
 971      * @param id
 972      *            ID (int) of PhylogenyNode of this Phylogeny
 973      */
 974     public void reRoot( final int id ) {
 975         reRoot( getNode( id ) );
 976     }
 977
 978     /**
 979      * Places the root of this Phylogeny on Branch b. The new root is always
 980      * placed on the middle of the branch b.
 981      *
 982      */
 983     public void reRoot( final PhylogenyBranch b ) {
 984         final PhylogenyNode n1 = b.getFirstNode();
 985         final PhylogenyNode n2 = b.getSecondNode();
 986         if ( n1.isExternal() ) {
 987             reRoot( n1 );
 988         }
 989         else if ( n2.isExternal() ) {
 990             reRoot( n2 );
 991         }
 992         else if ( ( n2 == n1.getChildNode1() ) || ( n2 == n1.getChildNode2() ) ) {
 993             reRoot( n2 );
 994         }
 995         else if ( ( n1 == n2.getChildNode1() ) || ( n1 == n2.getChildNode2() ) ) {
 996             reRoot( n1 );
 997         }
 998         else if ( ( n1.getParent() != null ) && n1.getParent().isRoot()
 999                 && ( ( n1.getParent().getChildNode1() == n2 ) || ( n1.getParent().getChildNode2() == n2 ) ) ) {
1000             reRoot( n1 );
1001         }
1002         else {
1003             throw new IllegalArgumentException( "reRoot( Branch b ): b is not a branch." );
1004         }
1005     }
1006
1007     /**
1008      * Places the root of this Phylogeny on the parent branch PhylogenyNode n.
1009      * The new root is always placed on the middle of the branch.
1010      * <p>
1011      * If the resulting reRooted Phylogeny is to be used any further, in most
1012      * cases the following three methods have to be called on the resulting
1013      * Phylogeny:
1014      * <ul>
1015      * <li>recalculateNumberOfExternalDescendants(boolean) <li>recalculateAndReset()
1016      * </ul>
1017      * <p>
1018      * (Last modified: 10/01/01)
1019      *
1020      * @param n
1021      *            PhylogenyNode of this Phylogeny\
1022      */
1023     public void reRoot( final PhylogenyNode n ) {
1024         reRoot( n, -1 );
1025     }
1026
1027     public void reRoot( final PhylogenyNode n, final double distance_n_to_parent ) {
1028         if ( isEmpty() || ( getNumberOfExternalNodes() < 2 ) ) {
1029             return;
1030         }
1031         setRooted( true );
1032         if ( n.isRoot() ) {
1033             return;
1034         }
1035         else if ( n.getParent().isRoot() ) {
1036             if ( ( n.getParent().getNumberOfDescendants() == 2 ) && ( distance_n_to_parent >= 0 ) ) {
1037                 final double d = n.getParent().getChildNode1().getDistanceToParent()
1038                         + n.getParent().getChildNode2().getDistanceToParent();
1039                 PhylogenyNode other;
1040                 if ( n.getChildNodeIndex() == 0 ) {
1041                     other = n.getParent().getChildNode2();
1042                 }
1043                 else {
1044                     other = n.getParent().getChildNode1();
1045                 }
1046                 n.setDistanceToParent( distance_n_to_parent );
1047                 final double dm = d - distance_n_to_parent;
1048                 if ( dm >= 0 ) {
1049                     other.setDistanceToParent( dm );
1050                 }
1051                 else {
1052                     other.setDistanceToParent( 0 );
1053                 }
1054             }
1055             if ( n.getParent().getNumberOfDescendants() > 2 ) {
1056                 final int index = n.getChildNodeIndex();
1057                 final double dn = n.getDistanceToParent();
1058                 final PhylogenyNode prev_root = getRoot();
1059                 prev_root.getDescendants().remove( index );
1060                 final PhylogenyNode new_root = new PhylogenyNode();
1061                 new_root.setChildNode( 0, n );
1062                 new_root.setChildNode( 1, prev_root );
1063                 if ( n.getBranchDataDirectly() != null ) {
1064                     prev_root.setBranchData( ( BranchData ) n.getBranchDataDirectly().copy() );
1065                 }
1066                 setRoot( new_root );
1067                 if ( distance_n_to_parent >= 0 ) {
1068                     n.setDistanceToParent( distance_n_to_parent );
1069                     final double d = dn - distance_n_to_parent;
1070                     if ( d >= 0 ) {
1071                         prev_root.setDistanceToParent( d );
1072                     }
1073                     else {
1074                         prev_root.setDistanceToParent( 0 );
1075                     }
1076                 }
1077                 else {
1078                     if ( dn >= 0 ) {
1079                         final double d = dn / 2.0;
1080                         n.setDistanceToParent( d );
1081                         prev_root.setDistanceToParent( d );
1082                     }
1083                 }
1084             }
1085         }
1086         else {
1087             PhylogenyNode a = n;
1088             PhylogenyNode b = null;
1089             PhylogenyNode c = null;
1090             final PhylogenyNode new_root = new PhylogenyNode();
1091             double distance1 = 0.0;
1092             double distance2 = 0.0;
1093             BranchData branch_data_1 = null;
1094             BranchData branch_data_2 = null;
1095             b = a.getParent();
1096             c = b.getParent();
1097             new_root.setChildNode( 0, a );
1098             new_root.setChildNode( 1, b );
1099             distance1 = c.getDistanceToParent();
1100             if ( c.getBranchDataDirectly() != null ) {
1101                 branch_data_1 = ( BranchData ) c.getBranchDataDirectly().copy();
1102             }
1103             c.setDistanceToParent( b.getDistanceToParent() );
1104             if ( b.getBranchDataDirectly() != null ) {
1105                 c.setBranchData( ( BranchData ) b.getBranchDataDirectly().copy() );
1106             }
1107             if ( a.getBranchDataDirectly() != null ) {
1108                 b.setBranchData( ( BranchData ) a.getBranchDataDirectly().copy() );
1109             }
1110             // New root is always placed in the middle of the branch:
1111             if ( a.getDistanceToParent() == PhylogenyNode.DISTANCE_DEFAULT ) {
1112                 b.setDistanceToParent( PhylogenyNode.DISTANCE_DEFAULT );
1113             }
1114             else {
1115                 if ( distance_n_to_parent >= 0.0 ) {
1116                     final double diff = a.getDistanceToParent() - distance_n_to_parent;
1117                     a.setDistanceToParent( distance_n_to_parent );
1118                     b.setDistanceToParent( diff >= 0.0 ? diff : 0.0 );
1119                 }
1120                 else {
1121                     final double d = a.getDistanceToParent() / 2.0;
1122                     a.setDistanceToParent( d );
1123                     b.setDistanceToParent( d );
1124                 }
1125             }
1126             b.setChildNodeOnly( a.getChildNodeIndex( b ), c );
1127             // moving to the old root, swapping references:
1128             while ( !c.isRoot() ) {
1129                 a = b;
1130                 b = c;
1131                 c = c.getParent();
1132                 b.setChildNodeOnly( a.getChildNodeIndex( b ), c );
1133                 b.setParent( a );
1134                 distance2 = c.getDistanceToParent();
1135                 branch_data_2 = c.getBranchDataDirectly();
1136                 c.setDistanceToParent( distance1 );
1137                 c.setBranchData( branch_data_1 );
1138                 distance1 = distance2;
1139                 branch_data_1 = branch_data_2;
1140             }
1141             // removing the old root:
1142             if ( c.getNumberOfDescendants() == 2 ) {
1143                 final PhylogenyNode node = c.getChildNode( 1 - b.getChildNodeIndex( c ) );
1144                 node.setParent( b );
1145                 if ( ( c.getDistanceToParent() == PhylogenyNode.DISTANCE_DEFAULT )
1146                         && ( node.getDistanceToParent() == PhylogenyNode.DISTANCE_DEFAULT ) ) {
1147                     node.setDistanceToParent( PhylogenyNode.DISTANCE_DEFAULT );
1148                 }
1149                 else {
1150                     node.setDistanceToParent( ( c.getDistanceToParent() >= 0.0 ? c.getDistanceToParent() : 0.0 )
1151                             + ( node.getDistanceToParent() >= 0.0 ? node.getDistanceToParent() : 0.0 ) );
1152                 }
1153                 if ( c.getBranchDataDirectly() != null ) {
1154                     node.setBranchData( ( BranchData ) c.getBranchDataDirectly().copy() );
1155                 }
1156                 for( int i = 0; i < b.getNumberOfDescendants(); ++i ) {
1157                     if ( b.getChildNode( i ) == c ) {
1158                         b.setChildNodeOnly( i, node );
1159                         break;
1160                     }
1161                 }
1162             }
1163             else {
1164                 c.setParent( b );
1165                 c.removeChildNode( b.getChildNodeIndex( c ) );
1166             }
1167             setRoot( new_root );
1168         }
1169     }
1170
1171     /**
1172      * Sets all Nodes of this Phylogeny to not-collapsed.
1173      * <p>
1174      * In most cases methods adjustNodeCount(false) and recalculateAndReset()
1175      * need to be called after this method has been called.
1176      */
1177     public void setAllNodesToNotCollapse() {
1178         if ( isEmpty() ) {
1179             return;
1180         }
1181         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1182             final PhylogenyNode node = iter.next();
1183             node.setCollapse( false );
1184         }
1185     }
1186
1187     private void setAllowMultipleParents( final boolean allow_multiple_parents ) {
1188         _allow_multiple_parents = allow_multiple_parents;
1189     }
1190
1191     public void setConfidence( final Confidence confidence ) {
1192         _confidence = confidence;
1193     }
1194
1195     public void setDescription( final String description ) {
1196         _description = description;
1197     }
1198
1199     public void setDistanceUnit( final String _distance_unit ) {
1200         this._distance_unit = _distance_unit;
1201     }
1202
1203     public void setIdentifier( final Identifier identifier ) {
1204         _identifier = identifier;
1205     }
1206
1207     void setIdHash( final HashMap<Integer, PhylogenyNode> idhash ) {
1208         _idhash = idhash;
1209     }
1210
1211     /**
1212      * Sets the indicators of all Nodes of this Phylogeny to 0.
1213      */
1214     public void setIndicatorsToZero() {
1215         if ( isEmpty() ) {
1216             return;
1217         }
1218         for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) {
1219             iter.next().setIndicator( ( byte ) 0 );
1220         }
1221     } // setIndicatorsToZero()
1222
1223     /**
1224      * Sets the name of this Phylogeny to s.
1225      */
1226     public void setName( final String s ) {
1227         _name = s;
1228     }
1229
1230     public void setRelevantSequenceRelationTypes( final Collection<SequenceRelation.SEQUENCE_RELATION_TYPE> types ) {
1231         _relevant_sequence_relation_types = types;
1232     }
1233
1234     public void setRerootable( final boolean rerootable ) {
1235         _rerootable = rerootable;
1236     }
1237
1238     public void setRoot( final PhylogenyNode n ) {
1239         _root = n;
1240     } // setRoot( PhylogenyNode )
1241
1242     /**
1243      * Sets whether this Phylogeny is rooted or not.
1244      */
1245     public void setRooted( final boolean b ) {
1246         _rooted = b;
1247     } // setRooted( boolean )
1248
1249     public void setSequenceRelationQueries( final Collection<Sequence> sequencesByName ) {
1250         _sequenceRelationQueries = sequencesByName;
1251     }
1252
1253     public void setType( final String type ) {
1254         _type = type;
1255     }
1256
1257     /**
1258      * Swaps the the two childern of a PhylogenyNode node of this Phylogeny.
1259      * <p>
1260      * (Last modified: 06/13/01)
1261      *
1262      * @param node
1263      *            a PhylogenyNode of this Phylogeny
1264      */
1265     public void swapChildren( final PhylogenyNode node ) throws RuntimeException {
1266         if ( !isTree() ) {
1267             throw new FailedConditionCheckException( "Attempt to swap children on phylogeny which is not tree-like." );
1268         }
1269         if ( isEmpty() || node.isExternal() || ( node.getNumberOfDescendants() < 2 ) ) {
1270             return;
1271         }
1272         final PhylogenyNode first = node.getFirstChildNode();
1273         for( int i = 1; i < node.getNumberOfDescendants(); ++i ) {
1274             node.setChildNode( i - 1, node.getChildNode( i ) );
1275         }
1276         node.setChildNode( node.getNumberOfDescendants() - 1, first );
1277     } // swapChildren( PhylogenyNode )
1278
1279     public String toNewHampshire() {
1280         return toNewHampshire( false );
1281     }
1282
1283     public String toNewHampshire( final boolean simple_nh ) {
1284         try {
1285             return new PhylogenyWriter().toNewHampshire( this, simple_nh, true ).toString();
1286         }
1287         catch ( final IOException e ) {
1288             throw new Error( "this should not have happend: " + e.getMessage() );
1289         }
1290     }
1291
1292     public String toNewHampshireX() {
1293         try {
1294             return new PhylogenyWriter().toNewHampshireX( this ).toString();
1295         }
1296         catch ( final IOException e ) {
1297             throw new Error( "this should not have happend: " + e.getMessage() );
1298         }
1299     }
1300
1301     public String toNexus() {
1302         try {
1303             return new PhylogenyWriter().toNexus( this ).toString();
1304         }
1305         catch ( final IOException e ) {
1306             throw new Error( "this should not have happend: " + e.getMessage() );
1307         }
1308     }
1309
1310     public String toPhyloXML( final int phyloxml_level ) {
1311         try {
1312             return new PhylogenyWriter().toPhyloXML( this, phyloxml_level ).toString();
1313         }
1314         catch ( final IOException e ) {
1315             throw new Error( "this should not have happend: " + e.getMessage() );
1316         }
1317     }
1318
1319     // ---------------------------------------------------------
1320     // Writing of Phylogeny to Strings
1321     // ---------------------------------------------------------
1322     /**
1323      * Converts this Phylogeny to a New Hampshire X (String) representation.
1324      *
1325      * @return New Hampshire X (String) representation of this
1326      * @see #toNewHampshireX()
1327      */
1328     @Override
1329     public String toString() {
1330         return toNewHampshireX();
1331     }
1332
1333     /**
1334      * Removes the root PhylogenyNode this Phylogeny.
1335      */
1336     public void unRoot() throws RuntimeException {
1337         if ( !isTree() ) {
1338             throw new FailedConditionCheckException( "Attempt to unroot a phylogeny which is not tree-like." );
1339         }
1340         if ( isEmpty() ) {
1341             return;
1342         }
1343         setIndicatorsToZero();
1344         if ( !isRooted() || ( getNumberOfExternalNodes() <= 1 ) ) {
1345             return;
1346         }
1347         setRooted( false );
1348         return;
1349     } // unRoot()
1350 }