- public PhylogenyNode obtainLCA( final PhylogenyNode node1, final PhylogenyNode node2 ) {
- _temp_hash_set.clear();
- PhylogenyNode n1 = node1;
- PhylogenyNode n2 = node2;
- _temp_hash_set.add( n1.getId() );
- while ( !n1.isRoot() ) {
- n1 = n1.getParent();
- _temp_hash_set.add( n1.getId() );
+ public final static PhylogenyNode calculateLCA( PhylogenyNode node1, PhylogenyNode node2 ) {
+ if ( node1 == null ) {
+ throw new IllegalArgumentException( "first argument (node) is null" );
+ }
+ if ( node2 == null ) {
+ throw new IllegalArgumentException( "second argument (node) is null" );
+ }
+ if ( node1 == node2 ) {
+ return node1;
+ }
+ if ( ( node1.getParent() == node2.getParent() ) ) {
+ return node1.getParent();
+ }
+ int depth1 = node1.calculateDepth();
+ int depth2 = node2.calculateDepth();
+ while ( ( depth1 > -1 ) && ( depth2 > -1 ) ) {
+ if ( depth1 > depth2 ) {
+ node1 = node1.getParent();
+ depth1--;
+ }
+ else if ( depth2 > depth1 ) {
+ node2 = node2.getParent();
+ depth2--;
+ }
+ else {
+ if ( node1 == node2 ) {
+ return node1;
+ }
+ node1 = node1.getParent();
+ node2 = node2.getParent();
+ depth1--;
+ depth2--;
+ }
+ }
+ throw new IllegalArgumentException( "illegal attempt to calculate LCA of two nodes which do not share a common root" );
+ }
+
+ public static final void preOrderReId( final Phylogeny phy ) {
+ if ( phy.isEmpty() ) {
+ return;
+ }
+ phy.setIdToNodeMap( null );
+ int i = PhylogenyNode.getNodeCount();
+ for( final PhylogenyNodeIterator it = phy.iteratorPreorder(); it.hasNext(); ) {
+ it.next().setId( i++ );
+ }
+ PhylogenyNode.setNodeCount( i );
+ }
+
+ /**
+ * Returns the LCA of PhylogenyNodes node1 and node2.
+ * Precondition: ids are in pre-order (or level-order).
+ *
+ *
+ * @param node1
+ * @param node2
+ * @return LCA of node1 and node2
+ */
+ public final static PhylogenyNode calculateLCAonTreeWithIdsInPreOrder( PhylogenyNode node1, PhylogenyNode node2 ) {
+ if ( node1 == null ) {
+ throw new IllegalArgumentException( "first argument (node) is null" );