X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=forester%2Fjava%2Fsrc%2Forg%2Fforester%2Fphylogeny%2FPhylogeny.java;h=379a9338d23cf21eb5e833a6004319f29befaf0e;hb=c0439ed8b088887ffea2faf11bc7897333287cb3;hp=115e88512c60745e05b464c1193695de332419ec;hpb=c956545c704f53df5c8711ede20e786641bfc7be;p=jalview.git diff --git a/forester/java/src/org/forester/phylogeny/Phylogeny.java b/forester/java/src/org/forester/phylogeny/Phylogeny.java index 115e885..379a933 100644 --- a/forester/java/src/org/forester/phylogeny/Phylogeny.java +++ b/forester/java/src/org/forester/phylogeny/Phylogeny.java @@ -56,7 +56,6 @@ import org.forester.phylogeny.iterators.PhylogenyNodeIterator; import org.forester.phylogeny.iterators.PostorderTreeIterator; import org.forester.phylogeny.iterators.PreorderTreeIterator; import org.forester.util.FailedConditionCheckException; -import org.forester.util.ForesterUtil; public class Phylogeny { @@ -86,7 +85,7 @@ public class Phylogeny { /** * Adds this Phylogeny to the list of child nodes of PhylogenyNode parent * and sets the parent of this to parent. - * + * * @param n * the PhylogenyNode to add */ @@ -116,8 +115,8 @@ public class Phylogeny { new_node.setParent( sibling_parent ); sibling.setParent( new_node ); sibling_parent.setChildNode( sibling_index, new_node ); - final double new_dist = sibling.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ? PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT - : sibling.getDistanceToParent() / 2; + final double new_dist = sibling.getDistanceToParent() == PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT + ? PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT : sibling.getDistanceToParent() / 2; new_node.setDistanceToParent( new_dist ); sibling.setDistanceToParent( new_dist ); externalNodesHaveChanged(); @@ -126,24 +125,24 @@ public class Phylogeny { /** * This calculates the height of the subtree emanating at n for rooted, * tree-shaped phylogenies - * + * * @param n * the root-node of a subtree * @return the height of the subtree emanating at n */ - public double calculateSubtreeHeight( final PhylogenyNode n ) { - if ( n.isExternal() || n.isCollapse() ) { - return ForesterUtil.isLargerOrEqualToZero( n.getDistanceToParent() ); + public double calculateSubtreeHeight( final PhylogenyNode n, final boolean take_collapse_into_account ) { + if ( n.isExternal() || ( take_collapse_into_account && n.isCollapse() ) ) { + return n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0; } else { double max = -Double.MAX_VALUE; for( int i = 0; i < n.getNumberOfDescendants(); ++i ) { - final double l = calculateSubtreeHeight( n.getChildNode( i ) ); + final double l = calculateSubtreeHeight( n.getChildNode( i ), take_collapse_into_account ); if ( l > max ) { max = l; } } - return max + ForesterUtil.isLargerOrEqualToZero( n.getDistanceToParent() ); + return max + ( n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0 ); } } @@ -222,9 +221,9 @@ public class Phylogeny { /** * Need to call clearHashIdToNodeMap() afterwards (not done automatically * to allow client multiple deletions in linear time). - * Need to call 'recalculateNumberOfExternalDescendants(boolean)' after this + * Need to call 'recalculateNumberOfExternalDescendants(boolean)' after this * if tree is to be displayed. - * + * * @param remove_us the parent node of the subtree to be deleted */ public void deleteSubtree( final PhylogenyNode remove_us, final boolean collapse_resulting_node_with_one_desc ) { @@ -260,13 +259,17 @@ public class Phylogeny { if ( p.getNumberOfDescendants() == 2 ) { final int pi = p.getChildNodeIndex(); if ( removed_node.isFirstChildNode() ) { - p.getChildNode( 1 ).setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p - .getDistanceToParent(), p.getChildNode( 1 ).getDistanceToParent() ) ); + p.getChildNode( 1 ) + .setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p.getDistanceToParent(), + p.getChildNode( 1 ) + .getDistanceToParent() ) ); pp.setChildNode( pi, p.getChildNode( 1 ) ); } else { - p.getChildNode( 0 ).setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p - .getDistanceToParent(), p.getChildNode( 0 ).getDistanceToParent() ) ); + p.getChildNode( 0 ) + .setDistanceToParent( PhylogenyMethods.addPhylogenyDistances( p.getDistanceToParent(), + p.getChildNode( 0 ) + .getDistanceToParent() ) ); pp.setChildNode( pi, p.getChildNode( 0 ) ); } } @@ -313,15 +316,15 @@ public class Phylogeny { } /** - * + * * Warning. The order of the returned nodes is random * -- and hence cannot be relied on. - * + * * @return Unordered set of PhylogenyNode */ public List getExternalNodes() { if ( _external_nodes_set == null ) { - _external_nodes_set = new ArrayList(); + _external_nodes_set = new ArrayList<>(); for( final PhylogenyNodeIterator it = iteratorPostorder(); it.hasNext(); ) { final PhylogenyNode n = it.next(); if ( n.isExternal() ) { @@ -333,28 +336,6 @@ public class Phylogeny { } /** - * Returns the number of duplications of this Phylogeny (int). A return - * value of -1 indicates that the number of duplications is unknown. - */ - // public int getNumberOfDuplications() { - // return _number_of_duplications; - // } // getNumberOfDuplications() - /** - * Sets the number of duplications of this Phylogeny (int). A value of -1 - * indicates that the number of duplications is unknown. - * - * @param clean_nh - * set to true for clean NH format - */ - // public void setNumberOfDuplications( int i ) { - // if ( i < 0 ) { - // _number_of_duplications = -1; - // } - // else { - // _number_of_duplications = i; - // } - // } // setNumberOfDuplications( int ) - /** * Returns the first external PhylogenyNode. */ public PhylogenyNode getFirstExternalNode() { @@ -370,17 +351,15 @@ public class Phylogeny { /** * This calculates the height for rooted, tree-shaped phylogenies. The - * height is the longest distance from the root to an external node. Please - * note. Child nodes of collapsed nodes are ignored -- which is useful for - * display purposes but might be misleading for other applications. - * + * height is the longest distance from the root to an external node. + * * @return the height for rooted, tree-shaped phylogenies */ - public double getHeight() { + public double calculateHeight( final boolean take_collapse_into_account ) { if ( isEmpty() ) { return 0.0; } - return calculateSubtreeHeight( getRoot() ); + return calculateSubtreeHeight( getRoot(), take_collapse_into_account ); } public Identifier getIdentifier() { @@ -411,7 +390,7 @@ public class Phylogeny { /** * Returns a PhylogenyNode of this Phylogeny which has a matching name. * Throws an Exception if seqname is not present in this or not unique. - * + * * @param name * name (String) of PhylogenyNode to find * @return PhylogenyNode with matchin name @@ -432,7 +411,7 @@ public class Phylogeny { /** * This is time-inefficient since it runs a iterator each time it is called. - * + * */ public int getNodeCount() { if ( isEmpty() ) { @@ -448,7 +427,7 @@ public class Phylogeny { /** * Returns a List with references to all Nodes of this Phylogeny which have * a matching name. - * + * * @param name * name (String) of Nodes to find * @return Vector of references to Nodes of this Phylogeny with matching @@ -459,7 +438,7 @@ public class Phylogeny { if ( isEmpty() ) { return null; } - final List nodes = new ArrayList(); + final List nodes = new ArrayList<>(); for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { final PhylogenyNode n = iter.next(); if ( n.getName().equals( name ) ) { @@ -473,7 +452,7 @@ public class Phylogeny { if ( isEmpty() ) { return null; } - final List nodes = new ArrayList(); + final List nodes = new ArrayList<>(); for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { final PhylogenyNode n = iter.next(); if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getName().equals( seq_name ) ) { @@ -487,7 +466,7 @@ public class Phylogeny { if ( isEmpty() ) { return null; } - final List nodes = new ArrayList(); + final List nodes = new ArrayList<>(); for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { final PhylogenyNode n = iter.next(); if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getSymbol().equals( seq_name ) ) { @@ -501,7 +480,7 @@ public class Phylogeny { if ( isEmpty() ) { return null; } - final List nodes = new ArrayList(); + final List nodes = new ArrayList<>(); for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { final PhylogenyNode n = iter.next(); if ( n.getNodeData().isHasSequence() && n.getNodeData().getSequence().getGeneName().equals( seq_name ) ) { @@ -515,7 +494,7 @@ public class Phylogeny { if ( isEmpty() ) { return null; } - final List nodes = new ArrayList(); + final List nodes = new ArrayList<>(); for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { final PhylogenyNode n = iter.next(); if ( n.getNodeData().isHasTaxonomy() @@ -529,7 +508,7 @@ public class Phylogeny { /** * Returns a Vector with references to all Nodes of this Phylogeny which * have a matching species name. - * + * * @param specname * species name (String) of Nodes to find * @return Vector of references to Nodes of this Phylogeny with matching @@ -540,7 +519,7 @@ public class Phylogeny { if ( isEmpty() ) { return null; } - final List nodes = new ArrayList(); + final List nodes = new ArrayList<>(); for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { final PhylogenyNode n = iter.next(); if ( PhylogenyMethods.getSpecies( n ).equals( specname ) ) { @@ -629,7 +608,7 @@ public class Phylogeny { *

* (Last modified: 11/22/00) Olivier CHABROL : * olivier.chabrol@univ-provence.fr - * + * * @param n * external PhylogenyNode whose orthologs are to be returned * @return Vector of references to all orthologous Nodes of PhylogenyNode n @@ -639,8 +618,8 @@ public class Phylogeny { public List getParalogousNodes( final PhylogenyNode n, final String[] taxonomyCodeRange ) { PhylogenyNode node = n; PhylogenyNode prev = null; - final List v = new ArrayList(); - final Map> map = new HashMap>(); + final List v = new ArrayList<>(); + final Map> map = new HashMap<>(); getTaxonomyMap( getRoot(), map ); if ( !node.isExternal() || isEmpty() ) { return null; @@ -657,12 +636,12 @@ public class Phylogeny { taxIdList = map.get( node ); if ( node.isDuplication() && isContains( taxIdList, taxonomyCodeRangeList ) ) { if ( node.getChildNode1() == prev ) { - v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode2() - .getAllExternalDescendants() ) ); + v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, + node.getChildNode2().getAllExternalDescendants() ) ); } else { - v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, node.getChildNode1() - .getAllExternalDescendants() ) ); + v.addAll( getNodeByTaxonomyID( searchNodeSpeciesId, + node.getChildNode1().getAllExternalDescendants() ) ); } } } @@ -671,7 +650,7 @@ public class Phylogeny { public Collection getRelevantSequenceRelationTypes() { if ( _relevant_sequence_relation_types == null ) { - _relevant_sequence_relation_types = new Vector(); + _relevant_sequence_relation_types = new Vector<>(); } return _relevant_sequence_relation_types; } @@ -711,7 +690,7 @@ public class Phylogeny { /** * Returns whether this is a completely binary tree (i.e. all internal nodes * are bifurcations). - * + * */ public boolean isCompletelyBinary() { if ( isEmpty() ) { @@ -726,9 +705,30 @@ public class Phylogeny { return true; } + public boolean isCompletelyBinaryAllow3ChildrenAtRoot() { + if ( isEmpty() ) { + return false; + } + for( final PhylogenyNodeIterator iter = iteratorPreorder(); iter.hasNext(); ) { + final PhylogenyNode node = iter.next(); + if ( node.isRoot() ) { + if ( node.isInternal() + && ( ( node.getNumberOfDescendants() != 2 ) && ( node.getNumberOfDescendants() != 3 ) ) ) { + return false; + } + } + else { + if ( node.isInternal() && ( node.getNumberOfDescendants() != 2 ) ) { + return false; + } + } + } + return true; + } + /** * Checks whether a Phylogeny object is deleted (or empty). - * + * * @return true if the tree is deleted (or empty), false otherwise */ public boolean isEmpty() { @@ -770,7 +770,7 @@ public class Phylogeny { * Resets the ID numbers of the nodes of this Phylogeny in level order, * starting with start_label (for the root).
* WARNING. After this method has been called, node IDs are no longer - * unique. + * unique. */ public void levelOrderReID() { if ( isEmpty() ) { @@ -810,7 +810,7 @@ public class Phylogeny { * (Re)counts the number of children for each PhylogenyNode of this * Phylogeny. As an example, this method needs to be called after a * Phylogeny has been reRooted and it is to be displayed. - * + * * @param consider_collapsed_nodes * set to true to take into account collapsed nodes (collapsed * nodes have 1 child). @@ -843,7 +843,7 @@ public class Phylogeny { *

*

  • recalculateNumberOfExternalDescendants(boolean) *
  • recalculateAndReset() - * + * * @param id * ID (int) of PhylogenyNode of this Phylogeny */ @@ -863,7 +863,7 @@ public class Phylogeny { * *

    * (Last modified: 10/01/01) - * + * * @param n * PhylogenyNode of this Phylogeny\ */ @@ -1087,7 +1087,7 @@ public class Phylogeny { */ public void setRooted( final boolean b ) { _rooted = b; - } // setRooted( boolean ) + } public void setSequenceRelationQueries( final Collection sequencesByName ) { _sequenceRelationQueries = sequencesByName; @@ -1146,7 +1146,7 @@ public class Phylogeny { // --------------------------------------------------------- /** * Converts this Phylogeny to a New Hampshire X (String) representation. - * + * * @return New Hampshire X (String) representation of this * @see #toNewHampshireX() */ @@ -1180,7 +1180,7 @@ public class Phylogeny { /** * Return Node by TaxonomyId Olivier CHABROL : * olivier.chabrol@univ-provence.fr - * + * * @param taxonomyID * search taxonomy identifier * @param nodes @@ -1188,7 +1188,7 @@ public class Phylogeny { * @return List node with the same taxonomy identifier */ private List getNodeByTaxonomyID( final String taxonomyID, final List nodes ) { - final List retour = new ArrayList(); + final List retour = new ArrayList<>(); for( final PhylogenyNode node : nodes ) { if ( taxonomyID.equals( PhylogenyMethods.getTaxonomyIdentifier( node ) ) ) { retour.add( node ); @@ -1200,13 +1200,13 @@ public class Phylogeny { /** * List all species contains in all leaf under a node Olivier CHABROL : * olivier.chabrol@univ-provence.fr - * + * * @param node * PhylogenyNode whose sub node species are returned * @return species contains in all leaf under the param node */ private List getSubNodeTaxonomy( final PhylogenyNode node ) { - final List taxonomyList = new ArrayList(); + final List taxonomyList = new ArrayList<>(); final List childs = node.getAllExternalDescendants(); String speciesId = null; for( final PhylogenyNode phylogenyNode : childs ) { @@ -1223,7 +1223,7 @@ public class Phylogeny { * Create a map [], the list contains the * species contains in all leaf under phylogeny node Olivier CHABROL : * olivier.chabrol@univ-provence.fr - * + * * @param node * the tree root node * @param map @@ -1246,7 +1246,7 @@ public class Phylogeny { /** * Util method to check if all element of a list is contains in the * rangeList. Olivier CHABROL : olivier.chabrol@univ-provence.fr - * + * * @param list * list to be check * @param rangeList