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