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