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