+ 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 ) {
+ while ( node1 != node2 ) {
+ if ( node1.getId() > node2.getId() ) {
+ node1 = node1.getParent();
+ }
+ else {
+ node2 = node2.getParent();
+ }