forester/java/src/org/forester/evoinference/TestPhylogenyReconstruction.java

   1 // $Id:
   2 // $
   3 //
   4 // FORESTER -- software libraries and applications
   5 // for evolutionary biology research and applications.
   6 //
   7 // Copyright (C) 2008-2009 Christian M. Zmasek
   8 // Copyright (C) 2008-2009 Burnham Institute for Medical Research
   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.evoinference;
  29
  30 import java.io.File;
  31 import java.io.FileInputStream;
  32 import java.io.StringWriter;
  33 import java.util.Date;
  34 import java.util.List;
  35
  36 import org.forester.evoinference.distance.NeighborJoining;
  37 import org.forester.evoinference.distance.NeighborJoiningF;
  38 import org.forester.evoinference.distance.NeighborJoiningX;
  39 import org.forester.evoinference.distance.PairwiseDistanceCalculator;
  40 import org.forester.evoinference.matrix.character.BasicCharacterStateMatrix;
  41 import org.forester.evoinference.matrix.character.CharacterStateMatrix;
  42 import org.forester.evoinference.matrix.character.CharacterStateMatrix.BinaryStates;
  43 import org.forester.evoinference.matrix.character.CharacterStateMatrix.GainLossStates;
  44 import org.forester.evoinference.matrix.distance.BasicSymmetricalDistanceMatrix;
  45 import org.forester.evoinference.matrix.distance.DistanceMatrix;
  46 import org.forester.evoinference.parsimony.DolloParsimony;
  47 import org.forester.evoinference.parsimony.FitchParsimony;
  48 import org.forester.io.parsers.GeneralMsaParser;
  49 import org.forester.io.parsers.SymmetricalDistanceMatrixParser;
  50 import org.forester.io.parsers.nhx.NHXParser;
  51 import org.forester.msa.Msa;
  52 import org.forester.phylogeny.Phylogeny;
  53 import org.forester.phylogeny.factories.ParserBasedPhylogenyFactory;
  54 import org.forester.phylogeny.factories.PhylogenyFactory;
  55 import org.forester.util.ForesterUtil;
  56
  57 public class TestPhylogenyReconstruction {
  58
  59     private final static double ZERO_DIFF = 1.0E-9;
  60
  61     public static boolean isEqual( final double a, final double b ) {
  62         return ( ( Math.abs( a - b ) ) < ZERO_DIFF );
  63     }
  64
  65     public static boolean isUnequal( final double a, final double b ) {
  66         return !isEqual( a, b );
  67     }
  68
  69     public static void main( final String[] args ) {
  70         if ( testNeighborJoining() ) {
  71             System.out.println( "OK." );
  72         }
  73         else {
  74             System.out.println( "failed." );
  75         }
  76         timeNeighborJoining();
  77     }
  78
  79     public static boolean test( final File test_dir ) {
  80         System.out.print( "  Basic symmetrical distance matrix: " );
  81         if ( !testBasicSymmetricalDistanceMatrix() ) {
  82             System.out.println( "failed." );
  83             return false;
  84         }
  85         System.out.println( "OK." );
  86         System.out.print( "  Basic character state matrix: " );
  87         if ( !testBasicCharacterStateMatrix() ) {
  88             System.out.println( "failed." );
  89             return false;
  90         }
  91         System.out.println( "OK." );
  92         System.out.print( "  Symmetrical distance matrix parser: " );
  93         if ( !testSymmetricalDistanceMatrixParser() ) {
  94             System.out.println( "failed." );
  95             return false;
  96         }
  97         System.out.println( "OK." );
  98         System.out.print( "  Distance Calculation: " );
  99         if ( !testDistanceCalculationMethods( test_dir ) ) {
 100             System.out.println( "failed." );
 101             return false;
 102         }
 103         System.out.println( "OK." );
 104         System.out.print( "  Neighbor Joining: " );
 105         if ( !testNeighborJoining() ) {
 106             System.out.println( "failed." );
 107             return false;
 108         }
 109         System.out.println( "OK." );
 110         System.out.print( "  Dollo Parsimony: " );
 111         if ( !testDolloParsimony() ) {
 112             System.out.println( "failed." );
 113             return false;
 114         }
 115         System.out.println( "OK." );
 116         System.out.print( "  Dollo Parsimony on non binary trees: " );
 117         if ( !testDolloParsimonyOnNonBinaryTree() ) {
 118             System.out.println( "failed." );
 119             return false;
 120         }
 121         System.out.println( "OK." );
 122         System.out.print( "  Fitch Parsimony: " );
 123         if ( !testFitchParsimony() ) {
 124             System.out.println( "failed." );
 125             return false;
 126         }
 127         System.out.println( "OK." );
 128         return true;
 129     }
 130
 131     private static boolean testDistanceCalculationMethods( final File test_dir ) {
 132         try {
 133             final Msa msa0 = GeneralMsaParser.parse( new FileInputStream( test_dir + ForesterUtil.FILE_SEPARATOR
 134                     + "bcl.aln" ) );
 135             final BasicSymmetricalDistanceMatrix pwd0 = PairwiseDistanceCalculator.calcKimuraDistances( msa0 );
 136             if ( pwd0.getSize() != 120 ) {
 137                 return false;
 138             }
 139             for( int i = 0; i < pwd0.getSize(); ++i ) {
 140                 if ( !isEqual( pwd0.getValue( i, i ), 0.0 ) ) {
 141                     return false;
 142                 }
 143             }
 144         }
 145         catch ( final Exception e ) {
 146             e.printStackTrace( System.out );
 147             return false;
 148         }
 149         return true;
 150     }
 151
 152     private static boolean testBasicCharacterStateMatrix() {
 153         try {
 154             final CharacterStateMatrix<String> matrix_0 = new BasicCharacterStateMatrix<String>( 4, 8 );
 155             final CharacterStateMatrix<String> matrix_00 = new BasicCharacterStateMatrix<String>( 4, 8 );
 156             matrix_0.setIdentifier( 0, "A" );
 157             matrix_0.setIdentifier( 1, "B" );
 158             matrix_0.setIdentifier( 2, "C" );
 159             matrix_0.setIdentifier( 3, "D" );
 160             matrix_0.setCharacter( 0, "0" );
 161             matrix_0.setCharacter( 1, "1" );
 162             matrix_0.setCharacter( 2, "2" );
 163             matrix_0.setCharacter( 3, "3" );
 164             matrix_0.setCharacter( 4, "4" );
 165             matrix_0.setCharacter( 5, "5" );
 166             matrix_0.setCharacter( 6, "6" );
 167             matrix_0.setCharacter( 7, "7" );
 168             matrix_00.setIdentifier( 0, "A" );
 169             matrix_00.setIdentifier( 1, "B" );
 170             matrix_00.setIdentifier( 2, "C" );
 171             matrix_00.setIdentifier( 3, "D" );
 172             matrix_00.setCharacter( 3, "3" );
 173             matrix_00.setCharacter( 4, "4" );
 174             if ( !matrix_0.getCharacter( 1 ).equals( "1" ) ) {
 175                 return false;
 176             }
 177             if ( !matrix_0.getIdentifier( 0 ).equals( "A" ) ) {
 178                 return false;
 179             }
 180             matrix_0.setState( 0, 0, "00" );
 181             matrix_00.setState( 0, 0, "00" );
 182             if ( !matrix_0.getState( 0, 0 ).equals( "00" ) ) {
 183                 return false;
 184             }
 185             matrix_0.setState( 0, 1, "01" );
 186             matrix_00.setState( 0, 1, "01" );
 187             if ( !matrix_0.getState( 0, 1 ).equals( "01" ) ) {
 188                 return false;
 189             }
 190             matrix_0.setState( 1, 1, "11" );
 191             matrix_00.setState( 1, 1, "11" );
 192             if ( !matrix_0.getState( 1, 1 ).equals( "11" ) ) {
 193                 return false;
 194             }
 195             matrix_0.setState( 1, 0, "10" );
 196             matrix_00.setState( 1, 0, "10" );
 197             if ( !matrix_0.getState( 1, 0 ).equals( "10" ) ) {
 198                 return false;
 199             }
 200             matrix_0.setState( 1, 2, "12" );
 201             matrix_00.setState( 1, 2, "12" );
 202             if ( !matrix_0.getState( 1, 2 ).equals( "12" ) ) {
 203                 return false;
 204             }
 205             matrix_0.setState( 3, 7, "37" );
 206             matrix_00.setState( 3, 7, "37" );
 207             if ( !matrix_0.getState( 3, 7 ).equals( "37" ) ) {
 208                 return false;
 209             }
 210             matrix_0.setState( 2, 6, "26" );
 211             matrix_00.setState( 2, 6, "26" );
 212             if ( !matrix_0.getState( 2, 6 ).equals( "26" ) ) {
 213                 return false;
 214             }
 215             matrix_0.setState( "D", "3", "33" );
 216             matrix_00.setState( "D", "3", "33" );
 217             if ( !matrix_0.getState( 3, 3 ).equals( "33" ) ) {
 218                 return false;
 219             }
 220             if ( !matrix_0.getState( "D", "3" ).equals( "33" ) ) {
 221                 return false;
 222             }
 223             matrix_0.setState( "C", "4", "24" );
 224             matrix_00.setState( "C", "4", "24" );
 225             if ( !matrix_0.getState( 2, 4 ).equals( "24" ) ) {
 226                 return false;
 227             }
 228             if ( !matrix_0.getState( "C", "4" ).equals( "24" ) ) {
 229                 return false;
 230             }
 231             if ( matrix_0.isEmpty() ) {
 232                 return false;
 233             }
 234             if ( matrix_0.getNumberOfIdentifiers() != 4 ) {
 235                 return false;
 236             }
 237             if ( matrix_0.getNumberOfCharacters() != 8 ) {
 238                 return false;
 239             }
 240             if ( !matrix_0.equals( matrix_0 ) ) {
 241                 return false;
 242             }
 243             if ( !matrix_0.equals( matrix_00 ) ) {
 244                 return false;
 245             }
 246             matrix_00.setState( "C", "4", "123" );
 247             if ( matrix_0.equals( matrix_00 ) ) {
 248                 return false;
 249             }
 250             final Integer[][] ints = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
 251             final CharacterStateMatrix<Integer> matrix_000 = new BasicCharacterStateMatrix<Integer>( ints );
 252             matrix_000.toString();
 253             if ( matrix_000.getNumberOfCharacters() != 4 ) {
 254                 return false;
 255             }
 256             if ( matrix_000.getNumberOfIdentifiers() != 3 ) {
 257                 return false;
 258             }
 259             if ( matrix_000.getState( 0, 1 ) != 2 ) {
 260                 return false;
 261             }
 262             if ( matrix_000.getState( 2, 3 ) != 12 ) {
 263                 return false;
 264             }
 265             final Integer[][] ints0 = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
 266             final CharacterStateMatrix<Integer> matrix_0000 = new BasicCharacterStateMatrix<Integer>( ints0 );
 267             if ( !matrix_000.equals( matrix_0000 ) ) {
 268                 return false;
 269             }
 270             final Integer[][] ints00 = { { 1, 2, 3, -4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
 271             final CharacterStateMatrix<Integer> matrix_00000 = new BasicCharacterStateMatrix<Integer>( ints00 );
 272             if ( matrix_000.equals( matrix_00000 ) ) {
 273                 return false;
 274             }
 275             final CharacterStateMatrix<String> clone0 = matrix_0.copy();
 276             final CharacterStateMatrix<String> clone00 = matrix_00.copy();
 277             if ( !clone0.equals( matrix_0 ) ) {
 278                 return false;
 279             }
 280             if ( !clone00.equals( matrix_00 ) ) {
 281                 return false;
 282             }
 283             if ( clone00.equals( clone0 ) ) {
 284                 return false;
 285             }
 286             final CharacterStateMatrix<String> pivot0 = matrix_0.pivot();
 287             final CharacterStateMatrix<String> pivot00 = matrix_00.pivot();
 288             if ( !pivot0.getState( 1, 0 ).equals( "01" ) ) {
 289                 return false;
 290             }
 291             if ( !pivot0.getState( 6, 2 ).equals( "26" ) ) {
 292                 return false;
 293             }
 294             if ( !matrix_0.getState( 2, 6 ).equals( "26" ) ) {
 295                 return false;
 296             }
 297             final CharacterStateMatrix<String> pivotpivot00 = pivot00.pivot();
 298             if ( !pivotpivot00.equals( matrix_00 ) ) {
 299                 return false;
 300             }
 301             final CharacterStateMatrix<BinaryStates> nex = new BasicCharacterStateMatrix<BinaryStates>( 4, 3 );
 302             nex.setIdentifier( 0, "amphioxus" );
 303             nex.setIdentifier( 1, "sponge" );
 304             nex.setIdentifier( 2, "sea_anemone" );
 305             nex.setIdentifier( 3, "cobra" );
 306             nex.setCharacter( 0, "notch" );
 307             nex.setCharacter( 1, "homeobox" );
 308             nex.setCharacter( 2, "wnt" );
 309             nex.setState( 0, 0, BinaryStates.ABSENT );
 310             nex.setState( 0, 1, BinaryStates.ABSENT );
 311             nex.setState( 0, 2, BinaryStates.ABSENT );
 312             nex.setState( 1, 0, BinaryStates.PRESENT );
 313             nex.setState( 1, 1, BinaryStates.PRESENT );
 314             nex.setState( 1, 2, BinaryStates.ABSENT );
 315             nex.setState( 2, 0, BinaryStates.PRESENT );
 316             nex.setState( 2, 1, BinaryStates.PRESENT );
 317             nex.setState( 2, 2, BinaryStates.PRESENT );
 318             nex.setState( 3, 0, BinaryStates.PRESENT );
 319             nex.setState( 3, 1, BinaryStates.ABSENT );
 320             nex.setState( 3, 2, BinaryStates.ABSENT );
 321             StringWriter w = new StringWriter();
 322             nex.toWriter( w, CharacterStateMatrix.Format.NEXUS_BINARY );
 323             //System.out.println( w.getBuffer().toString() );
 324             w = new StringWriter();
 325             nex.pivot().toWriter( w, CharacterStateMatrix.Format.NEXUS_BINARY );
 326             //System.out.println( w.getBuffer().toString() );
 327         }
 328         catch ( final Exception e ) {
 329             e.printStackTrace( System.out );
 330             return false;
 331         }
 332         return true;
 333     }
 334
 335     private static boolean testBasicSymmetricalDistanceMatrix() {
 336         try {
 337             final DistanceMatrix matrix_0 = new BasicSymmetricalDistanceMatrix( 4 );
 338             matrix_0.setIdentifier( 0, "A" );
 339             matrix_0.setIdentifier( 1, "B" );
 340             matrix_0.setIdentifier( 2, "C" );
 341             matrix_0.setIdentifier( 3, "0123456789012" );
 342             matrix_0.setValue( 1, 0, 0.00001 );
 343             matrix_0.setValue( 0, 2, 0.0000009 );
 344             matrix_0.setValue( 3, 0, 3.0 );
 345             matrix_0.setValue( 1, 2, 4.0 );
 346             matrix_0.setValue( 3, 1, 5.0 );
 347             matrix_0.setValue( 2, 3, 6.0 );
 348             if ( !matrix_0.getIdentifier( 0 ).equals( "A" ) ) {
 349                 return false;
 350             }
 351             if ( !matrix_0.getIdentifier( 1 ).equals( "B" ) ) {
 352                 return false;
 353             }
 354             if ( !matrix_0.getIdentifier( 2 ).equals( "C" ) ) {
 355                 return false;
 356             }
 357             if ( !matrix_0.getIdentifier( 3 ).equals( "0123456789012" ) ) {
 358                 return false;
 359             }
 360             if ( matrix_0.getSize() != 4 ) {
 361                 return false;
 362             }
 363             if ( !isEqual( matrix_0.getValue( 0, 0 ), 0.0 ) ) {
 364                 return false;
 365             }
 366             if ( !isEqual( matrix_0.getValue( 3, 3 ), 0.0 ) ) {
 367                 return false;
 368             }
 369             if ( !isEqual( matrix_0.getValue( 0, 1 ), 0.00001 ) ) {
 370                 return false;
 371             }
 372             if ( !isEqual( matrix_0.getValue( 0, 2 ), 0.0000009 ) ) {
 373                 return false;
 374             }
 375             if ( !isEqual( matrix_0.getValue( 0, 3 ), 3 ) ) {
 376                 return false;
 377             }
 378             if ( !isEqual( matrix_0.getValue( 1, 0 ), 0.00001 ) ) {
 379                 return false;
 380             }
 381             if ( !isEqual( matrix_0.getValue( 1, 2 ), 4 ) ) {
 382                 return false;
 383             }
 384             if ( !isEqual( matrix_0.getValue( 1, 3 ), 5 ) ) {
 385                 return false;
 386             }
 387             if ( !isEqual( matrix_0.getValue( 2, 0 ), 0.0000009 ) ) {
 388                 return false;
 389             }
 390             if ( !isEqual( matrix_0.getValue( 2, 1 ), 4 ) ) {
 391                 return false;
 392             }
 393             if ( !isEqual( matrix_0.getValue( 2, 3 ), 6 ) ) {
 394                 return false;
 395             }
 396             if ( !isEqual( matrix_0.getValue( 3, 0 ), 3 ) ) {
 397                 return false;
 398             }
 399             if ( !isEqual( matrix_0.getValue( 3, 1 ), 5 ) ) {
 400                 return false;
 401             }
 402             if ( !isEqual( matrix_0.getValue( 3, 2 ), 6 ) ) {
 403                 return false;
 404             }
 405             final StringBuffer matrix_0_phylip = new StringBuffer();
 406             matrix_0_phylip.append( "    4" );
 407             matrix_0_phylip.append( ForesterUtil.LINE_SEPARATOR );
 408             matrix_0_phylip.append( "A           0.000000  0.000010  0.000001  3.000000" );
 409             matrix_0_phylip.append( ForesterUtil.LINE_SEPARATOR );
 410             matrix_0_phylip.append( "B           0.000010  0.000000  4.000000  5.000000" );
 411             matrix_0_phylip.append( ForesterUtil.LINE_SEPARATOR );
 412             matrix_0_phylip.append( "C           0.000001  4.000000  0.000000  6.000000" );
 413             matrix_0_phylip.append( ForesterUtil.LINE_SEPARATOR );
 414             matrix_0_phylip.append( "0123456789  3.000000  5.000000  6.000000  0.000000" );
 415             if ( !matrix_0_phylip.toString()
 416                     .equals( matrix_0.toStringBuffer( DistanceMatrix.Format.PHYLIP ).toString() ) ) {
 417                 return false;
 418             }
 419         }
 420         catch ( final Exception e ) {
 421             e.printStackTrace( System.out );
 422             return false;
 423         }
 424         return true;
 425     }
 426
 427     private static boolean testDolloParsimony() {
 428         try {
 429             final BinaryStates PRESENT = BinaryStates.PRESENT;
 430             final BinaryStates ABSENT = BinaryStates.ABSENT;
 431             final GainLossStates UNCHANGED_PRESENT = GainLossStates.UNCHANGED_PRESENT;
 432             final DolloParsimony dollo1 = DolloParsimony.createInstance();
 433             final PhylogenyFactory factory1 = ParserBasedPhylogenyFactory.getInstance();
 434             final String p1_str = "((((((a,b)ab,c)ac,d)ad,(e,f)ef)af,(g,h)gh)ah,i)r";
 435             final Phylogeny p1 = factory1.create( p1_str, new NHXParser() )[ 0 ];
 436             CharacterStateMatrix<CharacterStateMatrix.BinaryStates> m1 = new BasicCharacterStateMatrix<CharacterStateMatrix.BinaryStates>( 9,
 437                                                                                                                                            1 );
 438             m1.setIdentifier( 0, "a" );
 439             m1.setIdentifier( 1, "b" );
 440             m1.setIdentifier( 2, "c" );
 441             m1.setIdentifier( 3, "d" );
 442             m1.setIdentifier( 4, "e" );
 443             m1.setIdentifier( 5, "f" );
 444             m1.setIdentifier( 6, "g" );
 445             m1.setIdentifier( 7, "h" );
 446             m1.setIdentifier( 8, "i" );
 447             m1.setCharacter( 0, "0" );
 448             m1.setState( "a", "0", PRESENT );
 449             m1.setState( "b", "0", ABSENT );
 450             m1.setState( "c", "0", PRESENT );
 451             m1.setState( "d", "0", ABSENT );
 452             m1.setState( "e", "0", ABSENT );
 453             m1.setState( "f", "0", ABSENT );
 454             m1.setState( "g", "0", ABSENT );
 455             m1.setState( "h", "0", ABSENT );
 456             m1.setState( "i", "0", ABSENT );
 457             dollo1.execute( p1, m1 );
 458             if ( dollo1.getTotalGains() != 1 ) {
 459                 return false;
 460             }
 461             if ( dollo1.getTotalLosses() != 1 ) {
 462                 return false;
 463             }
 464             if ( dollo1.getTotalUnchanged() != 15 ) {
 465                 return false;
 466             }
 467             m1.setState( "b", "0", PRESENT );
 468             dollo1.execute( p1, m1 );
 469             if ( dollo1.getTotalGains() != 1 ) {
 470                 return false;
 471             }
 472             if ( dollo1.getTotalLosses() != 0 ) {
 473                 return false;
 474             }
 475             if ( dollo1.getTotalUnchanged() != 16 ) {
 476                 return false;
 477             }
 478             m1.setState( "b", "0", ABSENT );
 479             m1.setState( "e", "0", PRESENT );
 480             dollo1.execute( p1, m1 );
 481             if ( dollo1.getTotalGains() != 1 ) {
 482                 return false;
 483             }
 484             if ( dollo1.getTotalLosses() != 3 ) {
 485                 return false;
 486             }
 487             if ( dollo1.getTotalUnchanged() != 13 ) {
 488                 return false;
 489             }
 490             m1.setState( "a", "0", ABSENT );
 491             m1.setState( "c", "0", ABSENT );
 492             m1.setState( "g", "0", PRESENT );
 493             dollo1.setReturnInternalStates( true );
 494             dollo1.setReturnGainLossMatrix( true );
 495             dollo1.execute( p1, m1 );
 496             if ( dollo1.getTotalGains() != 1 ) {
 497                 return false;
 498             }
 499             if ( dollo1.getTotalLosses() != 3 ) {
 500                 return false;
 501             }
 502             if ( dollo1.getTotalUnchanged() != 13 ) {
 503                 return false;
 504             }
 505             final DolloParsimony dollo2 = DolloParsimony.createInstance();
 506             final PhylogenyFactory factory2 = ParserBasedPhylogenyFactory.getInstance();
 507             final String p2_str = "((((((a,b)ab,c)ac,d)ad,(e,f)ef)af,(g,h,i)gi)ai,((j,k,l)jl,(m,n,o)mo,(p,q,r)pr)jr)root";
 508             final Phylogeny p2 = factory2.create( p2_str, new NHXParser() )[ 0 ];
 509             final CharacterStateMatrix<CharacterStateMatrix.BinaryStates> m2 = new BasicCharacterStateMatrix<CharacterStateMatrix.BinaryStates>( 18,
 510                                                                                                                                                  4 );
 511             m2.setIdentifier( 0, "a" );
 512             m2.setIdentifier( 1, "b" );
 513             m2.setIdentifier( 2, "c" );
 514             m2.setIdentifier( 3, "d" );
 515             m2.setIdentifier( 4, "e" );
 516             m2.setIdentifier( 5, "f" );
 517             m2.setIdentifier( 6, "g" );
 518             m2.setIdentifier( 7, "h" );
 519             m2.setIdentifier( 8, "i" );
 520             m2.setIdentifier( 9, "j" );
 521             m2.setIdentifier( 10, "k" );
 522             m2.setIdentifier( 11, "l" );
 523             m2.setIdentifier( 12, "m" );
 524             m2.setIdentifier( 13, "n" );
 525             m2.setIdentifier( 14, "o" );
 526             m2.setIdentifier( 15, "p" );
 527             m2.setIdentifier( 16, "q" );
 528             m2.setIdentifier( 17, "r" );
 529             m2.setCharacter( 0, "0" );
 530             m2.setCharacter( 1, "1" );
 531             m2.setCharacter( 2, "2" );
 532             m2.setCharacter( 3, "3" );
 533             m2.setState( "a", "0", PRESENT );
 534             m2.setState( "b", "0", ABSENT );
 535             m2.setState( "c", "0", PRESENT );
 536             m2.setState( "d", "0", ABSENT );
 537             m2.setState( "e", "0", ABSENT );
 538             m2.setState( "f", "0", ABSENT );
 539             m2.setState( "g", "0", ABSENT );
 540             m2.setState( "h", "0", ABSENT );
 541             m2.setState( "i", "0", ABSENT );
 542             m2.setState( "j", "0", ABSENT );
 543             m2.setState( "k", "0", ABSENT );
 544             m2.setState( "l", "0", ABSENT );
 545             m2.setState( "m", "0", ABSENT );
 546             m2.setState( "n", "0", ABSENT );
 547             m2.setState( "o", "0", ABSENT );
 548             m2.setState( "p", "0", ABSENT );
 549             m2.setState( "q", "0", ABSENT );
 550             m2.setState( "r", "0", ABSENT );
 551             m2.setState( "a", "1", PRESENT );
 552             m2.setState( "b", "1", ABSENT );
 553             m2.setState( "c", "1", PRESENT );
 554             m2.setState( "d", "1", ABSENT );
 555             m2.setState( "e", "1", ABSENT );
 556             m2.setState( "f", "1", ABSENT );
 557             m2.setState( "g", "1", PRESENT );
 558             m2.setState( "h", "1", ABSENT );
 559             m2.setState( "i", "1", ABSENT );
 560             m2.setState( "j", "1", PRESENT );
 561             m2.setState( "k", "1", ABSENT );
 562             m2.setState( "l", "1", ABSENT );
 563             m2.setState( "m", "1", PRESENT );
 564             m2.setState( "n", "1", ABSENT );
 565             m2.setState( "o", "1", ABSENT );
 566             m2.setState( "p", "1", ABSENT );
 567             m2.setState( "q", "1", ABSENT );
 568             m2.setState( "r", "1", ABSENT );
 569             m2.setState( "a", "2", ABSENT );
 570             m2.setState( "b", "2", ABSENT );
 571             m2.setState( "c", "2", ABSENT );
 572             m2.setState( "d", "2", ABSENT );
 573             m2.setState( "e", "2", ABSENT );
 574             m2.setState( "f", "2", ABSENT );
 575             m2.setState( "g", "2", ABSENT );
 576             m2.setState( "h", "2", ABSENT );
 577             m2.setState( "i", "2", ABSENT );
 578             m2.setState( "j", "2", PRESENT );
 579             m2.setState( "k", "2", ABSENT );
 580             m2.setState( "l", "2", ABSENT );
 581             m2.setState( "m", "2", PRESENT );
 582             m2.setState( "n", "2", ABSENT );
 583             m2.setState( "o", "2", ABSENT );
 584             m2.setState( "p", "2", PRESENT );
 585             m2.setState( "q", "2", ABSENT );
 586             m2.setState( "r", "2", ABSENT );
 587             m2.setState( "a", "3", ABSENT );
 588             m2.setState( "b", "3", ABSENT );
 589             m2.setState( "c", "3", PRESENT );
 590             m2.setState( "d", "3", ABSENT );
 591             m2.setState( "e", "3", ABSENT );
 592             m2.setState( "f", "3", ABSENT );
 593             m2.setState( "g", "3", PRESENT );
 594             m2.setState( "h", "3", ABSENT );
 595             m2.setState( "i", "3", ABSENT );
 596             m2.setState( "j", "3", ABSENT );
 597             m2.setState( "k", "3", ABSENT );
 598             m2.setState( "l", "3", ABSENT );
 599             m2.setState( "m", "3", ABSENT );
 600             m2.setState( "n", "3", ABSENT );
 601             m2.setState( "o", "3", ABSENT );
 602             m2.setState( "p", "3", ABSENT );
 603             m2.setState( "q", "3", ABSENT );
 604             m2.setState( "r", "3", ABSENT );
 605             dollo2.setReturnInternalStates( true );
 606             dollo2.setReturnGainLossMatrix( true );
 607             dollo2.execute( p2, m2 );
 608             final CharacterStateMatrix<BinaryStates> i_m = dollo2.getInternalStatesMatrix();
 609             final CharacterStateMatrix<GainLossStates> gl_m = dollo2.getGainLossMatrix();
 610             if ( dollo2.getTotalGains() != 3 ) {
 611                 return false;
 612             }
 613             if ( dollo2.getTotalLosses() != 22 ) {
 614                 return false;
 615             }
 616             if ( dollo2.getTotalUnchanged() != 95 ) {
 617                 return false;
 618             }
 619             if ( i_m.getState( "ab", "0" ) != PRESENT ) {
 620                 return false;
 621             }
 622             if ( i_m.getState( "ac", "0" ) != PRESENT ) {
 623                 return false;
 624             }
 625             if ( i_m.getState( "ad", "0" ) != ABSENT ) {
 626                 return false;
 627             }
 628             if ( i_m.getState( "af", "0" ) != ABSENT ) {
 629                 return false;
 630             }
 631             if ( i_m.getState( "ef", "0" ) != ABSENT ) {
 632                 return false;
 633             }
 634             if ( i_m.getState( "ai", "0" ) != ABSENT ) {
 635                 return false;
 636             }
 637             if ( i_m.getState( "gi", "0" ) != ABSENT ) {
 638                 return false;
 639             }
 640             if ( i_m.getState( "jl", "0" ) != ABSENT ) {
 641                 return false;
 642             }
 643             if ( i_m.getState( "mo", "0" ) != ABSENT ) {
 644                 return false;
 645             }
 646             if ( i_m.getState( "pr", "0" ) != ABSENT ) {
 647                 return false;
 648             }
 649             if ( i_m.getState( "jr", "0" ) != ABSENT ) {
 650                 return false;
 651             }
 652             if ( i_m.getState( "root", "0" ) != ABSENT ) {
 653                 return false;
 654             }
 655             if ( i_m.getState( "ab", "1" ) != PRESENT ) {
 656                 return false;
 657             }
 658             if ( i_m.getState( "ac", "1" ) != PRESENT ) {
 659                 return false;
 660             }
 661             if ( i_m.getState( "ad", "1" ) != PRESENT ) {
 662                 return false;
 663             }
 664             if ( i_m.getState( "af", "1" ) != PRESENT ) {
 665                 return false;
 666             }
 667             if ( i_m.getState( "ef", "1" ) != ABSENT ) {
 668                 return false;
 669             }
 670             if ( i_m.getState( "ai", "1" ) != PRESENT ) {
 671                 return false;
 672             }
 673             if ( i_m.getState( "gi", "1" ) != PRESENT ) {
 674                 return false;
 675             }
 676             if ( i_m.getState( "jl", "1" ) != PRESENT ) {
 677                 return false;
 678             }
 679             if ( i_m.getState( "mo", "1" ) != PRESENT ) {
 680                 return false;
 681             }
 682             if ( i_m.getState( "pr", "1" ) != ABSENT ) {
 683                 return false;
 684             }
 685             if ( i_m.getState( "jr", "1" ) != PRESENT ) {
 686                 return false;
 687             }
 688             if ( i_m.getState( "root", "1" ) != PRESENT ) {
 689                 return false;
 690             }
 691             if ( i_m.getState( "ab", "2" ) != ABSENT ) {
 692                 return false;
 693             }
 694             if ( i_m.getState( "ac", "2" ) != ABSENT ) {
 695                 return false;
 696             }
 697             if ( i_m.getState( "ad", "2" ) != ABSENT ) {
 698                 return false;
 699             }
 700             if ( i_m.getState( "af", "2" ) != ABSENT ) {
 701                 return false;
 702             }
 703             if ( i_m.getState( "ef", "2" ) != ABSENT ) {
 704                 return false;
 705             }
 706             if ( i_m.getState( "ai", "2" ) != ABSENT ) {
 707                 return false;
 708             }
 709             if ( i_m.getState( "gi", "2" ) != ABSENT ) {
 710                 return false;
 711             }
 712             if ( i_m.getState( "jl", "2" ) != PRESENT ) {
 713                 return false;
 714             }
 715             if ( i_m.getState( "mo", "2" ) != PRESENT ) {
 716                 return false;
 717             }
 718             if ( i_m.getState( "pr", "2" ) != PRESENT ) {
 719                 return false;
 720             }
 721             if ( i_m.getState( "jr", "2" ) != PRESENT ) {
 722                 return false;
 723             }
 724             if ( i_m.getState( "root", "2" ) != ABSENT ) {
 725                 return false;
 726             }
 727             if ( i_m.getState( "ab", "3" ) != ABSENT ) {
 728                 return false;
 729             }
 730             if ( i_m.getState( "ac", "3" ) != PRESENT ) {
 731                 return false;
 732             }
 733             if ( i_m.getState( "ad", "3" ) != PRESENT ) {
 734                 return false;
 735             }
 736             if ( i_m.getState( "af", "3" ) != PRESENT ) {
 737                 return false;
 738             }
 739             if ( i_m.getState( "ef", "3" ) != ABSENT ) {
 740                 return false;
 741             }
 742             if ( i_m.getState( "ai", "3" ) != PRESENT ) {
 743                 return false;
 744             }
 745             if ( i_m.getState( "gi", "3" ) != PRESENT ) {
 746                 return false;
 747             }
 748             if ( i_m.getState( "jl", "3" ) != ABSENT ) {
 749                 return false;
 750             }
 751             if ( i_m.getState( "mo", "3" ) != ABSENT ) {
 752                 return false;
 753             }
 754             if ( i_m.getState( "pr", "3" ) != ABSENT ) {
 755                 return false;
 756             }
 757             if ( i_m.getState( "jr", "3" ) != ABSENT ) {
 758                 return false;
 759             }
 760             if ( i_m.getState( "root", "3" ) != ABSENT ) {
 761                 return false;
 762             }
 763             if ( gl_m.getState( "a", "0" ) != UNCHANGED_PRESENT ) {
 764                 return false;
 765             }
 766             final DolloParsimony dollo9 = DolloParsimony.createInstance();
 767             final PhylogenyFactory factory9 = ParserBasedPhylogenyFactory.getInstance();
 768             final String p9_str = "((((((a,b)ab,c)ac,d)ad,(e,f)ef)af,(g,h)gh)ah,i)r";
 769             final Phylogeny p9 = factory9.create( p9_str, new NHXParser() )[ 0 ];
 770             m1 = new BasicCharacterStateMatrix<CharacterStateMatrix.BinaryStates>( 9, 3 );
 771             m1.setIdentifier( 0, "a" );
 772             m1.setIdentifier( 1, "b" );
 773             m1.setIdentifier( 2, "c" );
 774             m1.setIdentifier( 3, "d" );
 775             m1.setIdentifier( 4, "e" );
 776             m1.setIdentifier( 5, "f" );
 777             m1.setIdentifier( 6, "g" );
 778             m1.setIdentifier( 7, "h" );
 779             m1.setIdentifier( 8, "i" );
 780             m1.setState( 0, 0, PRESENT );
 781             m1.setState( 1, 0, ABSENT );
 782             m1.setState( 2, 0, PRESENT );
 783             m1.setState( 3, 0, ABSENT );
 784             m1.setState( 4, 0, ABSENT );
 785             m1.setState( 5, 0, ABSENT );
 786             m1.setState( 6, 0, ABSENT );
 787             m1.setState( 7, 0, ABSENT );
 788             m1.setState( 8, 0, ABSENT );
 789             m1.setState( 0, 1, PRESENT );
 790             m1.setState( 1, 1, PRESENT );
 791             m1.setState( 2, 1, PRESENT );
 792             m1.setState( 3, 1, PRESENT );
 793             m1.setState( 4, 1, ABSENT );
 794             m1.setState( 5, 1, ABSENT );
 795             m1.setState( 6, 1, ABSENT );
 796             m1.setState( 7, 1, ABSENT );
 797             m1.setState( 8, 1, ABSENT );
 798             m1.setState( 0, 2, PRESENT );
 799             m1.setState( 1, 2, ABSENT );
 800             m1.setState( 2, 2, ABSENT );
 801             m1.setState( 3, 2, ABSENT );
 802             m1.setState( 4, 2, ABSENT );
 803             m1.setState( 5, 2, ABSENT );
 804             m1.setState( 6, 2, ABSENT );
 805             m1.setState( 7, 2, PRESENT );
 806             m1.setState( 8, 2, ABSENT );
 807             dollo9.execute( p9, m1 );
 808             if ( dollo9.getTotalGains() != 3 ) {
 809                 return false;
 810             }
 811             if ( dollo9.getTotalLosses() != 6 ) {
 812                 return false;
 813             }
 814             final DolloParsimony dollo10 = DolloParsimony.createInstance();
 815             final PhylogenyFactory factory10 = ParserBasedPhylogenyFactory.getInstance();
 816             final String p10_str = "((((((a,b)ab,c)ac,d)ad,(e,f)ef)af,(g,h)gh)ah,i)r";
 817             final Phylogeny p10 = factory10.create( p10_str, new NHXParser() )[ 0 ];
 818             final CharacterStateMatrix<CharacterStateMatrix.BinaryStates> m10 = new BasicCharacterStateMatrix<CharacterStateMatrix.BinaryStates>( 9,
 819                                                                                                                                                   1 );
 820             m10.setIdentifier( 0, "a" );
 821             m10.setIdentifier( 1, "b" );
 822             m10.setIdentifier( 2, "c" );
 823             m10.setIdentifier( 3, "d" );
 824             m10.setIdentifier( 4, "e" );
 825             m10.setIdentifier( 5, "f" );
 826             m10.setIdentifier( 6, "g" );
 827             m10.setIdentifier( 7, "h" );
 828             m10.setIdentifier( 8, "i" );
 829             m10.setState( 0, 0, PRESENT );
 830             m10.setState( 1, 0, ABSENT );
 831             m10.setState( 2, 0, PRESENT );
 832             m10.setState( 3, 0, ABSENT );
 833             m10.setState( 4, 0, ABSENT );
 834             m10.setState( 5, 0, ABSENT );
 835             m10.setState( 6, 0, ABSENT );
 836             m10.setState( 7, 0, ABSENT );
 837             m10.setState( 8, 0, ABSENT );
 838             dollo10.execute( p10, m10 );
 839             if ( dollo10.getTotalGains() != 1 ) {
 840                 return false;
 841             }
 842             if ( dollo10.getTotalLosses() != 1 ) {
 843                 return false;
 844             }
 845         }
 846         catch ( final Exception e ) {
 847             e.printStackTrace( System.out );
 848             return false;
 849         }
 850         return true;
 851     }
 852
 853     private static boolean testDolloParsimonyOnNonBinaryTree() {
 854         try {
 855             final BinaryStates PRESENT = BinaryStates.PRESENT;
 856             final BinaryStates ABSENT = BinaryStates.ABSENT;
 857             final DolloParsimony dollo1 = DolloParsimony.createInstance();
 858             final PhylogenyFactory factory1 = ParserBasedPhylogenyFactory.getInstance();
 859             final String p1_str = "((((((a,b,y)aby,c)ac,d)ad,(e,f)ef)af,(g,h)gh)ah,i)r";
 860             final Phylogeny p1 = factory1.create( p1_str, new NHXParser() )[ 0 ];
 861             final CharacterStateMatrix<CharacterStateMatrix.BinaryStates> m1 = new BasicCharacterStateMatrix<CharacterStateMatrix.BinaryStates>( 10,
 862                                                                                                                                                  1 );
 863             m1.setIdentifier( 0, "a" );
 864             m1.setIdentifier( 1, "b" );
 865             m1.setIdentifier( 2, "y" );
 866             m1.setIdentifier( 3, "c" );
 867             m1.setIdentifier( 4, "d" );
 868             m1.setIdentifier( 5, "e" );
 869             m1.setIdentifier( 6, "f" );
 870             m1.setIdentifier( 7, "g" );
 871             m1.setIdentifier( 8, "h" );
 872             m1.setIdentifier( 9, "i" );
 873             m1.setCharacter( 0, "0" );
 874             m1.setState( "a", "0", PRESENT );
 875             m1.setState( "b", "0", ABSENT );
 876             m1.setState( "y", "0", PRESENT );
 877             m1.setState( "c", "0", PRESENT );
 878             m1.setState( "d", "0", ABSENT );
 879             m1.setState( "e", "0", ABSENT );
 880             m1.setState( "f", "0", ABSENT );
 881             m1.setState( "g", "0", ABSENT );
 882             m1.setState( "h", "0", ABSENT );
 883             m1.setState( "i", "0", ABSENT );
 884             dollo1.execute( p1, m1 );
 885             if ( dollo1.getTotalGains() != 1 ) {
 886                 return false;
 887             }
 888             if ( dollo1.getTotalLosses() != 1 ) {
 889                 return false;
 890             }
 891             if ( dollo1.getTotalUnchanged() != 16 ) {
 892                 return false;
 893             }
 894             m1.setState( "b", "0", PRESENT );
 895             dollo1.execute( p1, m1 );
 896             if ( dollo1.getTotalGains() != 1 ) {
 897                 return false;
 898             }
 899             if ( dollo1.getTotalLosses() != 0 ) {
 900                 return false;
 901             }
 902             if ( dollo1.getTotalUnchanged() != 17 ) {
 903                 return false;
 904             }
 905             m1.setState( "a", "0", ABSENT );
 906             m1.setState( "b", "0", ABSENT );
 907             dollo1.execute( p1, m1 );
 908             if ( dollo1.getTotalGains() != 1 ) {
 909                 return false;
 910             }
 911             if ( dollo1.getTotalLosses() != 2 ) {
 912                 return false;
 913             }
 914             if ( dollo1.getTotalUnchanged() != 15 ) {
 915                 return false;
 916             }
 917             m1.setState( "y", "0", ABSENT );
 918             dollo1.execute( p1, m1 );
 919             if ( dollo1.getTotalGains() != 1 ) {
 920                 return false;
 921             }
 922             if ( dollo1.getTotalLosses() != 0 ) {
 923                 return false;
 924             }
 925             if ( dollo1.getTotalUnchanged() != 17 ) {
 926                 return false;
 927             }
 928             final DolloParsimony dollo2 = DolloParsimony.createInstance();
 929             final PhylogenyFactory factory2 = ParserBasedPhylogenyFactory.getInstance();
 930             final String p2_str = "((((((a,b,y)aby,c,d)cad,e,f)af,(g,h)gh)ah,i))r";
 931             final Phylogeny p2 = factory2.create( p2_str, new NHXParser() )[ 0 ];
 932             final CharacterStateMatrix<CharacterStateMatrix.BinaryStates> m2 = new BasicCharacterStateMatrix<CharacterStateMatrix.BinaryStates>( 10,
 933                                                                                                                                                  1 );
 934             m2.setIdentifier( 0, "a" );
 935             m2.setIdentifier( 1, "b" );
 936             m2.setIdentifier( 2, "y" );
 937             m2.setIdentifier( 3, "c" );
 938             m2.setIdentifier( 4, "d" );
 939             m2.setIdentifier( 5, "e" );
 940             m2.setIdentifier( 6, "f" );
 941             m2.setIdentifier( 7, "g" );
 942             m2.setIdentifier( 8, "h" );
 943             m2.setIdentifier( 9, "i" );
 944             m2.setCharacter( 0, "0" );
 945             m2.setState( "a", "0", PRESENT );
 946             m2.setState( "b", "0", ABSENT );
 947             m2.setState( "y", "0", PRESENT );
 948             m2.setState( "c", "0", PRESENT );
 949             m2.setState( "d", "0", ABSENT );
 950             m2.setState( "e", "0", ABSENT );
 951             m2.setState( "f", "0", ABSENT );
 952             m2.setState( "g", "0", ABSENT );
 953             m2.setState( "h", "0", ABSENT );
 954             m2.setState( "i", "0", ABSENT );
 955             dollo2.setReturnInternalStates( true );
 956             dollo2.execute( p2, m2 );
 957             CharacterStateMatrix<BinaryStates> i_m2 = dollo2.getInternalStatesMatrix();
 958             if ( i_m2.getState( "aby", "0" ) != PRESENT ) {
 959                 return false;
 960             }
 961             if ( i_m2.getState( "cad", "0" ) != PRESENT ) {
 962                 return false;
 963             }
 964             if ( i_m2.getState( "af", "0" ) != ABSENT ) {
 965                 return false;
 966             }
 967             if ( i_m2.getState( "gh", "0" ) != ABSENT ) {
 968                 return false;
 969             }
 970             if ( i_m2.getState( "ah", "0" ) != ABSENT ) {
 971                 return false;
 972             }
 973             if ( i_m2.getState( "r", "0" ) != ABSENT ) {
 974                 return false;
 975             }
 976             if ( dollo2.getTotalGains() != 1 ) {
 977                 return false;
 978             }
 979             if ( dollo2.getTotalLosses() != 2 ) {
 980                 return false;
 981             }
 982             if ( dollo2.getTotalUnchanged() != 14 ) {
 983                 return false;
 984             }
 985             m2.setState( "b", "0", PRESENT );
 986             dollo2.execute( p2, m2 );
 987             if ( dollo2.getTotalGains() != 1 ) {
 988                 return false;
 989             }
 990             if ( dollo2.getTotalLosses() != 1 ) {
 991                 return false;
 992             }
 993             if ( dollo2.getTotalUnchanged() != 15 ) {
 994                 return false;
 995             }
 996             m2.setState( "a", "0", ABSENT );
 997             m2.setState( "b", "0", ABSENT );
 998             dollo2.execute( p2, m2 );
 999             if ( dollo2.getTotalGains() != 1 ) {
1000                 return false;
1001             }
1002             if ( dollo2.getTotalLosses() != 3 ) {
1003                 return false;
1004             }
1005             if ( dollo2.getTotalUnchanged() != 13 ) {
1006                 return false;
1007             }
1008             m2.setState( "y", "0", ABSENT );
1009             dollo2.execute( p2, m2 );
1010             if ( dollo2.getTotalGains() != 1 ) {
1011                 return false;
1012             }
1013             if ( dollo2.getTotalLosses() != 0 ) {
1014                 return false;
1015             }
1016             if ( dollo2.getTotalUnchanged() != 16 ) {
1017                 return false;
1018             }
1019             m2.setState( "c", "0", ABSENT );
1020             dollo2.execute( p2, m2 );
1021             if ( dollo2.getTotalGains() != 0 ) {
1022                 return false;
1023             }
1024             if ( dollo2.getTotalLosses() != 0 ) {
1025                 return false;
1026             }
1027             if ( dollo2.getTotalUnchanged() != 17 ) {
1028                 return false;
1029             }
1030             m2.setState( "y", "0", PRESENT );
1031             m2.setState( "e", "0", PRESENT );
1032             dollo2.execute( p2, m2 );
1033             if ( dollo2.getTotalGains() != 1 ) {
1034                 return false;
1035             }
1036             if ( dollo2.getTotalLosses() != 5 ) {
1037                 return false;
1038             }
1039             if ( dollo2.getTotalUnchanged() != 11 ) {
1040                 return false;
1041             }
1042             i_m2 = dollo2.getInternalStatesMatrix();
1043             if ( i_m2.getState( "aby", "0" ) != PRESENT ) {
1044                 return false;
1045             }
1046             if ( i_m2.getState( "cad", "0" ) != PRESENT ) {
1047                 return false;
1048             }
1049             if ( i_m2.getState( "af", "0" ) != PRESENT ) {
1050                 return false;
1051             }
1052             if ( i_m2.getState( "gh", "0" ) != ABSENT ) {
1053                 return false;
1054             }
1055             if ( i_m2.getState( "ah", "0" ) != ABSENT ) {
1056                 return false;
1057             }
1058             if ( i_m2.getState( "r", "0" ) != ABSENT ) {
1059                 return false;
1060             }
1061         }
1062         catch ( final Exception e ) {
1063             e.printStackTrace( System.out );
1064             return false;
1065         }
1066         return true;
1067     }
1068
1069     private static boolean testFitchParsimony() {
1070         try {
1071             final BinaryStates PRESENT = BinaryStates.PRESENT;
1072             final BinaryStates ABSENT = BinaryStates.ABSENT;
1073             final GainLossStates GAIN = GainLossStates.GAIN;
1074             final GainLossStates LOSS = GainLossStates.LOSS;
1075             final GainLossStates UNCHANGED_PRESENT = GainLossStates.UNCHANGED_PRESENT;
1076             final GainLossStates UNCHANGED_ABSENT = GainLossStates.UNCHANGED_ABSENT;
1077             final FitchParsimony<String> fitch1 = new FitchParsimony<String>();
1078             final PhylogenyFactory factory1 = ParserBasedPhylogenyFactory.getInstance();
1079             final String p1_str = "((((((a,b)ab,c)ac,d)ad,(e,f)ef)af,(g,h,i)gi)ai,((j,k,l)jl,(m,n,o)mo,(p,q,r)pr)jr)root";
1080             final Phylogeny p1 = factory1.create( p1_str, new NHXParser() )[ 0 ];
1081             final CharacterStateMatrix<String> m1 = new BasicCharacterStateMatrix<String>( 18, 1 );
1082             m1.setIdentifier( 0, "a" );
1083             m1.setIdentifier( 1, "b" );
1084             m1.setIdentifier( 2, "c" );
1085             m1.setIdentifier( 3, "d" );
1086             m1.setIdentifier( 4, "e" );
1087             m1.setIdentifier( 5, "f" );
1088             m1.setIdentifier( 6, "g" );
1089             m1.setIdentifier( 7, "h" );
1090             m1.setIdentifier( 8, "i" );
1091             m1.setIdentifier( 9, "j" );
1092             m1.setIdentifier( 10, "k" );
1093             m1.setIdentifier( 11, "l" );
1094             m1.setIdentifier( 12, "m" );
1095             m1.setIdentifier( 13, "n" );
1096             m1.setIdentifier( 14, "o" );
1097             m1.setIdentifier( 15, "p" );
1098             m1.setIdentifier( 16, "q" );
1099             m1.setIdentifier( 17, "r" );
1100             m1.setCharacter( 0, "0" );
1101             m1.setState( "a", "0", "A" );
1102             m1.setState( "b", "0", "A" );
1103             m1.setState( "c", "0", "B" );
1104             m1.setState( "d", "0", "C" );
1105             m1.setState( "e", "0", "D" );
1106             m1.setState( "f", "0", "A" );
1107             m1.setState( "g", "0", "A" );
1108             m1.setState( "h", "0", "B" );
1109             m1.setState( "i", "0", "C" );
1110             m1.setState( "j", "0", "A" );
1111             m1.setState( "k", "0", "B" );
1112             m1.setState( "l", "0", "C" );
1113             m1.setState( "m", "0", "B" );
1114             m1.setState( "n", "0", "B" );
1115             m1.setState( "o", "0", "B" );
1116             m1.setState( "p", "0", "A" );
1117             m1.setState( "q", "0", "C" );
1118             m1.setState( "r", "0", "D" );
1119             fitch1.setReturnInternalStates( true );
1120             fitch1.setReturnGainLossMatrix( false );
1121             fitch1.setRandomize( false );
1122             fitch1.execute( p1, m1 );
1123             final CharacterStateMatrix<String> i_m = fitch1.getInternalStatesMatrix();
1124             final CharacterStateMatrix<List<String>> i_m_all = fitch1.getInternalStatesMatrixPriorToTraceback();
1125             if ( fitch1.getCost() != 10 ) {
1126                 return false;
1127             }
1128             if ( !i_m.getState( "ab", "0" ).equals( "A" ) ) {
1129                 return false;
1130             }
1131             if ( !i_m.getState( "ac", "0" ).equals( "A" ) ) {
1132                 return false;
1133             }
1134             if ( !i_m.getState( "ad", "0" ).equals( "A" ) ) {
1135                 return false;
1136             }
1137             if ( !i_m.getState( "ef", "0" ).equals( "A" ) ) {
1138                 return false;
1139             }
1140             if ( !i_m.getState( "ai", "0" ).equals( "A" ) ) {
1141                 return false;
1142             }
1143             if ( !i_m.getState( "gi", "0" ).equals( "A" ) ) {
1144                 return false;
1145             }
1146             if ( !i_m.getState( "jl", "0" ).equals( "A" ) ) {
1147                 return false;
1148             }
1149             if ( !i_m.getState( "mo", "0" ).equals( "B" ) ) {
1150                 return false;
1151             }
1152             if ( !i_m.getState( "pr", "0" ).equals( "A" ) ) {
1153                 return false;
1154             }
1155             if ( i_m_all.getState( "ab", "0" ).size() != 1 ) {
1156                 return false;
1157             }
1158             if ( !i_m_all.getState( "ab", "0" ).contains( "A" ) ) {
1159                 return false;
1160             }
1161             if ( i_m_all.getState( "ac", "0" ).size() != 2 ) {
1162                 return false;
1163             }
1164             if ( !i_m_all.getState( "ac", "0" ).contains( "A" ) ) {
1165                 return false;
1166             }
1167             if ( !i_m_all.getState( "ac", "0" ).contains( "B" ) ) {
1168                 return false;
1169             }
1170             if ( i_m_all.getState( "ad", "0" ).size() != 3 ) {
1171                 return false;
1172             }
1173             if ( !i_m_all.getState( "ad", "0" ).contains( "A" ) ) {
1174                 return false;
1175             }
1176             if ( !i_m_all.getState( "ad", "0" ).contains( "B" ) ) {
1177                 return false;
1178             }
1179             if ( !i_m_all.getState( "ad", "0" ).contains( "C" ) ) {
1180                 return false;
1181             }
1182             if ( i_m_all.getState( "af", "0" ).size() != 1 ) {
1183                 return false;
1184             }
1185             if ( !i_m_all.getState( "af", "0" ).contains( "A" ) ) {
1186                 return false;
1187             }
1188             if ( i_m_all.getState( "ef", "0" ).size() != 2 ) {
1189                 return false;
1190             }
1191             if ( !i_m_all.getState( "ef", "0" ).contains( "A" ) ) {
1192                 return false;
1193             }
1194             if ( !i_m_all.getState( "ef", "0" ).contains( "D" ) ) {
1195                 return false;
1196             }
1197             if ( i_m_all.getState( "gi", "0" ).size() != 3 ) {
1198                 return false;
1199             }
1200             if ( !i_m_all.getState( "gi", "0" ).contains( "A" ) ) {
1201                 return false;
1202             }
1203             if ( !i_m_all.getState( "gi", "0" ).contains( "B" ) ) {
1204                 return false;
1205             }
1206             if ( !i_m_all.getState( "gi", "0" ).contains( "C" ) ) {
1207                 return false;
1208             }
1209             if ( i_m_all.getState( "ai", "0" ).size() != 1 ) {
1210                 return false;
1211             }
1212             if ( !i_m_all.getState( "ai", "0" ).contains( "A" ) ) {
1213                 return false;
1214             }
1215             if ( i_m_all.getState( "jl", "0" ).size() != 3 ) {
1216                 return false;
1217             }
1218             if ( !i_m_all.getState( "jl", "0" ).contains( "A" ) ) {
1219                 return false;
1220             }
1221             if ( !i_m_all.getState( "jl", "0" ).contains( "B" ) ) {
1222                 return false;
1223             }
1224             if ( !i_m_all.getState( "jl", "0" ).contains( "C" ) ) {
1225                 return false;
1226             }
1227             if ( i_m_all.getState( "mo", "0" ).size() != 1 ) {
1228                 return false;
1229             }
1230             if ( !i_m_all.getState( "mo", "0" ).contains( "B" ) ) {
1231                 return false;
1232             }
1233             if ( i_m_all.getState( "pr", "0" ).size() != 3 ) {
1234                 return false;
1235             }
1236             if ( !i_m_all.getState( "pr", "0" ).contains( "A" ) ) {
1237                 return false;
1238             }
1239             if ( !i_m_all.getState( "pr", "0" ).contains( "C" ) ) {
1240                 return false;
1241             }
1242             if ( !i_m_all.getState( "pr", "0" ).contains( "D" ) ) {
1243                 return false;
1244             }
1245             if ( i_m_all.getState( "jr", "0" ).size() != 4 ) {
1246                 return false;
1247             }
1248             if ( !i_m_all.getState( "jr", "0" ).contains( "A" ) ) {
1249                 return false;
1250             }
1251             if ( !i_m_all.getState( "jr", "0" ).contains( "B" ) ) {
1252                 return false;
1253             }
1254             if ( !i_m_all.getState( "jr", "0" ).contains( "C" ) ) {
1255                 return false;
1256             }
1257             if ( !i_m_all.getState( "jr", "0" ).contains( "D" ) ) {
1258                 return false;
1259             }
1260             final FitchParsimony<String> fitch2 = new FitchParsimony<String>();
1261             final PhylogenyFactory factory2 = ParserBasedPhylogenyFactory.getInstance();
1262             final String p2_str = "((a,b)ab,(c,(d,e)de)cde)r";
1263             final Phylogeny p2 = factory2.create( p2_str, new NHXParser() )[ 0 ];
1264             final CharacterStateMatrix<String> m2 = new BasicCharacterStateMatrix<String>( 5, 1 );
1265             m2.setIdentifier( 0, "a" );
1266             m2.setIdentifier( 1, "b" );
1267             m2.setIdentifier( 2, "c" );
1268             m2.setIdentifier( 3, "d" );
1269             m2.setIdentifier( 4, "e" );
1270             m2.setCharacter( 0, "0" );
1271             m2.setState( "a", "0", "C" );
1272             m2.setState( "b", "0", "A" );
1273             m2.setState( "c", "0", "C" );
1274             m2.setState( "d", "0", "A" );
1275             m2.setState( "e", "0", "G" );
1276             fitch2.setReturnInternalStates( true );
1277             fitch2.setReturnGainLossMatrix( false );
1278             fitch2.execute( p2, m2 );
1279             final CharacterStateMatrix<String> i_m2 = fitch2.getInternalStatesMatrix();
1280             final CharacterStateMatrix<List<String>> i_m_all2 = fitch2.getInternalStatesMatrixPriorToTraceback();
1281             if ( fitch2.getCost() != 3 ) {
1282                 return false;
1283             }
1284             if ( !i_m2.getState( "ab", "0" ).equals( "A" ) ) {
1285                 return false;
1286             }
1287             if ( !i_m2.getState( "de", "0" ).equals( "A" ) ) {
1288                 return false;
1289             }
1290             if ( !i_m2.getState( "cde", "0" ).equals( "A" ) ) {
1291                 return false;
1292             }
1293             if ( !i_m2.getState( "r", "0" ).equals( "A" ) ) {
1294                 return false;
1295             }
1296             if ( i_m_all2.getState( "cde", "0" ).size() != 3 ) {
1297                 return false;
1298             }
1299             if ( !i_m_all2.getState( "cde", "0" ).contains( "A" ) ) {
1300                 return false;
1301             }
1302             if ( !i_m_all2.getState( "cde", "0" ).contains( "C" ) ) {
1303                 return false;
1304             }
1305             if ( !i_m_all2.getState( "cde", "0" ).contains( "G" ) ) {
1306                 return false;
1307             }
1308             if ( i_m_all2.getState( "ab", "0" ).size() != 2 ) {
1309                 return false;
1310             }
1311             if ( !i_m_all2.getState( "ab", "0" ).contains( "A" ) ) {
1312                 return false;
1313             }
1314             if ( !i_m_all2.getState( "ab", "0" ).contains( "C" ) ) {
1315                 return false;
1316             }
1317             fitch2.setReturnInternalStates( true );
1318             fitch2.setReturnGainLossMatrix( false );
1319             fitch2.setUseLast( true );
1320             fitch2.execute( p2, m2 );
1321             final CharacterStateMatrix<String> i_m21 = fitch2.getInternalStatesMatrix();
1322             final CharacterStateMatrix<List<String>> i_m_all21 = fitch2.getInternalStatesMatrixPriorToTraceback();
1323             if ( fitch2.getCost() != 3 ) {
1324                 return false;
1325             }
1326             if ( !i_m21.getState( "ab", "0" ).equals( "C" ) ) {
1327                 return false;
1328             }
1329             if ( !i_m21.getState( "de", "0" ).equals( "G" ) ) {
1330                 return false;
1331             }
1332             if ( !i_m21.getState( "cde", "0" ).equals( "C" ) ) {
1333                 return false;
1334             }
1335             if ( !i_m21.getState( "r", "0" ).equals( "C" ) ) {
1336                 return false;
1337             }
1338             if ( i_m_all21.getState( "cde", "0" ).size() != 3 ) {
1339                 return false;
1340             }
1341             if ( !i_m_all21.getState( "cde", "0" ).contains( "A" ) ) {
1342                 return false;
1343             }
1344             if ( !i_m_all21.getState( "cde", "0" ).contains( "C" ) ) {
1345                 return false;
1346             }
1347             if ( !i_m_all21.getState( "cde", "0" ).contains( "G" ) ) {
1348                 return false;
1349             }
1350             final FitchParsimony<String> fitch3 = new FitchParsimony<String>();
1351             final PhylogenyFactory factory3 = ParserBasedPhylogenyFactory.getInstance();
1352             final String p3_str = "(((a,b)ab,((c,d)cd,e)cde)abcde,f)r";
1353             final Phylogeny p3 = factory3.create( p3_str, new NHXParser() )[ 0 ];
1354             final CharacterStateMatrix<String> m3 = new BasicCharacterStateMatrix<String>( 6, 1 );
1355             m3.setIdentifier( 0, "a" );
1356             m3.setIdentifier( 1, "b" );
1357             m3.setIdentifier( 2, "c" );
1358             m3.setIdentifier( 3, "d" );
1359             m3.setIdentifier( 4, "e" );
1360             m3.setIdentifier( 5, "f" );
1361             m3.setCharacter( 0, "0" );
1362             m3.setState( "a", "0", "C" );
1363             m3.setState( "b", "0", "U" );
1364             m3.setState( "c", "0", "G" );
1365             m3.setState( "d", "0", "U" );
1366             m3.setState( "e", "0", "A" );
1367             m3.setState( "f", "0", "A" );
1368             fitch3.setReturnInternalStates( true );
1369             fitch3.setReturnGainLossMatrix( false );
1370             fitch3.execute( p3, m3 );
1371             final CharacterStateMatrix<String> i_m3 = fitch3.getInternalStatesMatrix();
1372             final CharacterStateMatrix<List<String>> i_m_all3 = fitch3.getInternalStatesMatrixPriorToTraceback();
1373             if ( fitch3.getCost() != 4 ) {
1374                 return false;
1375             }
1376             if ( !i_m3.getState( "ab", "0" ).equals( "U" ) ) {
1377                 return false;
1378             }
1379             if ( !i_m3.getState( "cd", "0" ).equals( "U" ) ) {
1380                 return false;
1381             }
1382             if ( !i_m3.getState( "cde", "0" ).equals( "U" ) ) {
1383                 return false;
1384             }
1385             if ( !i_m3.getState( "abcde", "0" ).equals( "U" ) ) {
1386                 return false;
1387             }
1388             if ( !i_m3.getState( "r", "0" ).equals( "A" ) ) {
1389                 return false;
1390             }
1391             if ( i_m_all3.getState( "cde", "0" ).size() != 3 ) {
1392                 return false;
1393             }
1394             if ( !i_m_all3.getState( "cde", "0" ).contains( "A" ) ) {
1395                 return false;
1396             }
1397             if ( !i_m_all3.getState( "cde", "0" ).contains( "G" ) ) {
1398                 return false;
1399             }
1400             if ( !i_m_all3.getState( "cde", "0" ).contains( "U" ) ) {
1401                 return false;
1402             }
1403             if ( i_m_all3.getState( "ab", "0" ).size() != 2 ) {
1404                 return false;
1405             }
1406             if ( !i_m_all3.getState( "ab", "0" ).contains( "C" ) ) {
1407                 return false;
1408             }
1409             if ( !i_m_all3.getState( "ab", "0" ).contains( "U" ) ) {
1410                 return false;
1411             }
1412             if ( i_m_all3.getState( "cd", "0" ).size() != 2 ) {
1413                 return false;
1414             }
1415             if ( !i_m_all3.getState( "cd", "0" ).contains( "G" ) ) {
1416                 return false;
1417             }
1418             if ( !i_m_all3.getState( "cd", "0" ).contains( "U" ) ) {
1419                 return false;
1420             }
1421             if ( i_m_all3.getState( "abcde", "0" ).size() != 1 ) {
1422                 return false;
1423             }
1424             if ( !i_m_all3.getState( "abcde", "0" ).contains( "U" ) ) {
1425                 return false;
1426             }
1427             if ( i_m_all3.getState( "r", "0" ).size() != 2 ) {
1428                 return false;
1429             }
1430             if ( !i_m_all3.getState( "r", "0" ).contains( "A" ) ) {
1431                 return false;
1432             }
1433             if ( !i_m_all3.getState( "r", "0" ).contains( "U" ) ) {
1434                 return false;
1435             }
1436             final FitchParsimony<BinaryStates> fitch4 = new FitchParsimony<BinaryStates>();
1437             final PhylogenyFactory factory4 = ParserBasedPhylogenyFactory.getInstance();
1438             final String p4_str = "(((a,b)ab,((c,d)cd,e)cde)abcde,f)r";
1439             final Phylogeny p4 = factory4.create( p4_str, new NHXParser() )[ 0 ];
1440             final CharacterStateMatrix<BinaryStates> m4 = new BasicCharacterStateMatrix<BinaryStates>( 6, 1 );
1441             m4.setIdentifier( 0, "a" );
1442             m4.setIdentifier( 1, "b" );
1443             m4.setIdentifier( 2, "c" );
1444             m4.setIdentifier( 3, "d" );
1445             m4.setIdentifier( 4, "e" );
1446             m4.setIdentifier( 5, "f" );
1447             m4.setCharacter( 0, "0" );
1448             m4.setState( "a", "0", PRESENT );
1449             m4.setState( "b", "0", ABSENT );
1450             m4.setState( "c", "0", PRESENT );
1451             m4.setState( "d", "0", PRESENT );
1452             m4.setState( "e", "0", ABSENT );
1453             m4.setState( "f", "0", ABSENT );
1454             fitch4.setReturnInternalStates( true );
1455             fitch4.setReturnGainLossMatrix( true );
1456             fitch4.execute( p4, m4 );
1457             final CharacterStateMatrix<GainLossStates> gl_m_4 = fitch4.getGainLossMatrix();
1458             if ( fitch4.getCost() != 2 ) {
1459                 return false;
1460             }
1461             if ( fitch4.getTotalLosses() != 0 ) {
1462                 return false;
1463             }
1464             if ( fitch4.getTotalGains() != 2 ) {
1465                 return false;
1466             }
1467             if ( fitch4.getTotalUnchanged() != 9 ) {
1468                 return false;
1469             }
1470             if ( gl_m_4.getState( "a", "0" ) != GAIN ) {
1471                 return false;
1472             }
1473             if ( gl_m_4.getState( "b", "0" ) != UNCHANGED_ABSENT ) {
1474                 return false;
1475             }
1476             if ( gl_m_4.getState( "ab", "0" ) != UNCHANGED_ABSENT ) {
1477                 return false;
1478             }
1479             if ( gl_m_4.getState( "cd", "0" ) != GAIN ) {
1480                 return false;
1481             }
1482             if ( gl_m_4.getState( "r", "0" ) != UNCHANGED_ABSENT ) {
1483                 return false;
1484             }
1485             final FitchParsimony<BinaryStates> fitch5 = new FitchParsimony<BinaryStates>();
1486             final PhylogenyFactory factory5 = ParserBasedPhylogenyFactory.getInstance();
1487             final String p5_str = "(((a,b)ab,((c,d)cd,e)cde)abcde,f)r";
1488             final Phylogeny p5 = factory5.create( p5_str, new NHXParser() )[ 0 ];
1489             final CharacterStateMatrix<BinaryStates> m5 = new BasicCharacterStateMatrix<BinaryStates>( 6, 1 );
1490             m5.setIdentifier( 0, "a" );
1491             m5.setIdentifier( 1, "b" );
1492             m5.setIdentifier( 2, "c" );
1493             m5.setIdentifier( 3, "d" );
1494             m5.setIdentifier( 4, "e" );
1495             m5.setIdentifier( 5, "f" );
1496             m5.setCharacter( 0, "0" );
1497             m5.setState( "a", "0", PRESENT );
1498             m5.setState( "b", "0", ABSENT );
1499             m5.setState( "c", "0", PRESENT );
1500             m5.setState( "d", "0", ABSENT );
1501             m5.setState( "e", "0", PRESENT );
1502             m5.setState( "f", "0", ABSENT );
1503             fitch5.setReturnInternalStates( true );
1504             fitch5.setReturnGainLossMatrix( true );
1505             fitch5.execute( p5, m5 );
1506             final CharacterStateMatrix<GainLossStates> gl_m_5 = fitch5.getGainLossMatrix();
1507             if ( fitch5.getCost() != 3 ) {
1508                 return false;
1509             }
1510             if ( fitch5.getTotalLosses() != 2 ) {
1511                 return false;
1512             }
1513             if ( fitch5.getTotalGains() != 1 ) {
1514                 return false;
1515             }
1516             if ( fitch5.getTotalUnchanged() != 8 ) {
1517                 return false;
1518             }
1519             if ( gl_m_5.getState( "abcde", "0" ) != GAIN ) {
1520                 return false;
1521             }
1522             if ( gl_m_5.getState( "a", "0" ) != UNCHANGED_PRESENT ) {
1523                 return false;
1524             }
1525             if ( gl_m_5.getState( "b", "0" ) != LOSS ) {
1526                 return false;
1527             }
1528             if ( gl_m_5.getState( "d", "0" ) != LOSS ) {
1529                 return false;
1530             }
1531             if ( gl_m_5.getState( "r", "0" ) != UNCHANGED_ABSENT ) {
1532                 return false;
1533             }
1534             final FitchParsimony<BinaryStates> fitch6 = new FitchParsimony<BinaryStates>();
1535             final PhylogenyFactory factory6 = ParserBasedPhylogenyFactory.getInstance();
1536             final String p6_str = "(((a,b)ab,((c,d)cd,e)cde)abcde,f)r";
1537             final Phylogeny p6 = factory6.create( p6_str, new NHXParser() )[ 0 ];
1538             final CharacterStateMatrix<BinaryStates> m6 = new BasicCharacterStateMatrix<BinaryStates>( 6, 1 );
1539             m6.setIdentifier( 0, "a" );
1540             m6.setIdentifier( 1, "b" );
1541             m6.setIdentifier( 2, "c" );
1542             m6.setIdentifier( 3, "d" );
1543             m6.setIdentifier( 4, "e" );
1544             m6.setIdentifier( 5, "f" );
1545             m6.setCharacter( 0, "0" );
1546             m6.setState( "a", "0", PRESENT );
1547             m6.setState( "b", "0", ABSENT );
1548             m6.setState( "c", "0", PRESENT );
1549             m6.setState( "d", "0", PRESENT );
1550             m6.setState( "e", "0", ABSENT );
1551             m6.setState( "f", "0", PRESENT );
1552             fitch6.setReturnInternalStates( true );
1553             fitch6.setReturnGainLossMatrix( true );
1554             fitch6.execute( p6, m6 );
1555             final CharacterStateMatrix<GainLossStates> gl_m_6 = fitch6.getGainLossMatrix();
1556             if ( fitch6.getCost() != 2 ) {
1557                 return false;
1558             }
1559             if ( fitch6.getTotalLosses() != 2 ) {
1560                 return false;
1561             }
1562             if ( fitch6.getTotalGains() != 0 ) {
1563                 return false;
1564             }
1565             if ( fitch6.getTotalUnchanged() != 9 ) {
1566                 return false;
1567             }
1568             if ( gl_m_6.getState( "abcde", "0" ) != UNCHANGED_PRESENT ) {
1569                 return false;
1570             }
1571             if ( gl_m_6.getState( "r", "0" ) != UNCHANGED_PRESENT ) {
1572                 return false;
1573             }
1574             if ( gl_m_6.getState( "b", "0" ) != LOSS ) {
1575                 return false;
1576             }
1577             if ( gl_m_6.getState( "e", "0" ) != LOSS ) {
1578                 return false;
1579             }
1580             final FitchParsimony<BinaryStates> fitch7 = new FitchParsimony<BinaryStates>();
1581             final PhylogenyFactory factory7 = ParserBasedPhylogenyFactory.getInstance();
1582             final String p7_str = "(((a,b)ab,(c,d)cd)abcd,((e,f)ef,(g,h)gh)efgh)r";
1583             final Phylogeny p7 = factory7.create( p7_str, new NHXParser() )[ 0 ];
1584             final CharacterStateMatrix<BinaryStates> m7 = new BasicCharacterStateMatrix<BinaryStates>( 8, 1 );
1585             m7.setIdentifier( 0, "a" );
1586             m7.setIdentifier( 1, "b" );
1587             m7.setIdentifier( 2, "c" );
1588             m7.setIdentifier( 3, "d" );
1589             m7.setIdentifier( 4, "e" );
1590             m7.setIdentifier( 5, "f" );
1591             m7.setIdentifier( 6, "g" );
1592             m7.setIdentifier( 7, "h" );
1593             m7.setCharacter( 0, "0" );
1594             m7.setState( "a", "0", PRESENT );
1595             m7.setState( "b", "0", ABSENT );
1596             m7.setState( "c", "0", PRESENT );
1597             m7.setState( "d", "0", ABSENT );
1598             m7.setState( "e", "0", PRESENT );
1599             m7.setState( "f", "0", ABSENT );
1600             m7.setState( "g", "0", PRESENT );
1601             m7.setState( "h", "0", ABSENT );
1602             fitch7.setReturnInternalStates( true );
1603             fitch7.setReturnGainLossMatrix( true );
1604             fitch7.execute( p7, m7 );
1605             final CharacterStateMatrix<GainLossStates> gl_m_7 = fitch7.getGainLossMatrix();
1606             if ( fitch7.getCost() != 4 ) {
1607                 return false;
1608             }
1609             if ( fitch7.getTotalLosses() != 0 ) {
1610                 return false;
1611             }
1612             if ( fitch7.getTotalGains() != 4 ) {
1613                 return false;
1614             }
1615             if ( fitch7.getTotalUnchanged() != 11 ) {
1616                 return false;
1617             }
1618             if ( gl_m_7.getState( "a", "0" ) != GAIN ) {
1619                 return false;
1620             }
1621             if ( gl_m_7.getState( "c", "0" ) != GAIN ) {
1622                 return false;
1623             }
1624             if ( gl_m_7.getState( "e", "0" ) != GAIN ) {
1625                 return false;
1626             }
1627             if ( gl_m_7.getState( "g", "0" ) != GAIN ) {
1628                 return false;
1629             }
1630             if ( gl_m_7.getState( "r", "0" ) != UNCHANGED_ABSENT ) {
1631                 return false;
1632             }
1633             fitch7.setReturnInternalStates( true );
1634             fitch7.setReturnGainLossMatrix( true );
1635             fitch7.setUseLast( true );
1636             fitch7.execute( p7, m7 );
1637             final CharacterStateMatrix<GainLossStates> gl_m_71 = fitch7.getGainLossMatrix();
1638             if ( fitch7.getCost() != 4 ) {
1639                 return false;
1640             }
1641             if ( fitch7.getTotalLosses() != 4 ) {
1642                 return false;
1643             }
1644             if ( fitch7.getTotalGains() != 0 ) {
1645                 return false;
1646             }
1647             if ( fitch7.getTotalUnchanged() != 11 ) {
1648                 return false;
1649             }
1650             if ( gl_m_71.getState( "b", "0" ) != LOSS ) {
1651                 return false;
1652             }
1653             if ( gl_m_71.getState( "d", "0" ) != LOSS ) {
1654                 return false;
1655             }
1656             if ( gl_m_71.getState( "f", "0" ) != LOSS ) {
1657                 return false;
1658             }
1659             if ( gl_m_71.getState( "h", "0" ) != LOSS ) {
1660                 return false;
1661             }
1662             if ( gl_m_71.getState( "r", "0" ) != UNCHANGED_PRESENT ) {
1663                 return false;
1664             }
1665             final FitchParsimony<BinaryStates> fitch8 = new FitchParsimony<BinaryStates>();
1666             final PhylogenyFactory factory8 = ParserBasedPhylogenyFactory.getInstance();
1667             final String p8_str = "(((a,b)ab,(c,d)cd)abcd,((e,f)ef,(g,h)gh)efgh)r";
1668             final Phylogeny p8 = factory8.create( p8_str, new NHXParser() )[ 0 ];
1669             final CharacterStateMatrix<BinaryStates> m8 = new BasicCharacterStateMatrix<BinaryStates>( 8, 1 );
1670             m8.setIdentifier( 0, "a" );
1671             m8.setIdentifier( 1, "b" );
1672             m8.setIdentifier( 2, "c" );
1673             m8.setIdentifier( 3, "d" );
1674             m8.setIdentifier( 4, "e" );
1675             m8.setIdentifier( 5, "f" );
1676             m8.setIdentifier( 6, "g" );
1677             m8.setIdentifier( 7, "h" );
1678             m8.setCharacter( 0, "0" );
1679             m8.setState( "a", "0", PRESENT );
1680             m8.setState( "b", "0", PRESENT );
1681             m8.setState( "c", "0", PRESENT );
1682             m8.setState( "d", "0", ABSENT );
1683             m8.setState( "e", "0", ABSENT );
1684             m8.setState( "f", "0", ABSENT );
1685             m8.setState( "g", "0", ABSENT );
1686             m8.setState( "h", "0", ABSENT );
1687             fitch8.setReturnInternalStates( true );
1688             fitch8.setReturnGainLossMatrix( true );
1689             fitch8.execute( p8, m8 );
1690             final CharacterStateMatrix<GainLossStates> gl_m_8 = fitch8.getGainLossMatrix();
1691             if ( fitch8.getCost() != 2 ) {
1692                 return false;
1693             }
1694             if ( fitch8.getTotalLosses() != 1 ) {
1695                 return false;
1696             }
1697             if ( fitch8.getTotalGains() != 1 ) {
1698                 return false;
1699             }
1700             if ( fitch8.getTotalUnchanged() != 13 ) {
1701                 return false;
1702             }
1703             if ( gl_m_8.getState( "d", "0" ) != LOSS ) {
1704                 return false;
1705             }
1706             if ( gl_m_8.getState( "abcd", "0" ) != GAIN ) {
1707                 return false;
1708             }
1709             final FitchParsimony<BinaryStates> fitch9 = new FitchParsimony<BinaryStates>();
1710             final PhylogenyFactory factory9 = ParserBasedPhylogenyFactory.getInstance();
1711             final String p9_str = "(((a,b)ab,c)abc,d)abcd";
1712             final Phylogeny p9 = factory9.create( p9_str, new NHXParser() )[ 0 ];
1713             final CharacterStateMatrix<BinaryStates> m9 = new BasicCharacterStateMatrix<BinaryStates>( 4, 1 );
1714             m9.setIdentifier( 0, "a" );
1715             m9.setIdentifier( 1, "b" );
1716             m9.setIdentifier( 2, "c" );
1717             m9.setIdentifier( 3, "d" );
1718             m9.setCharacter( 0, "0" );
1719             m9.setState( "a", "0", PRESENT );
1720             m9.setState( "b", "0", ABSENT );
1721             m9.setState( "c", "0", PRESENT );
1722             m9.setState( "d", "0", ABSENT );
1723             fitch9.setReturnInternalStates( true );
1724             fitch9.setReturnGainLossMatrix( true );
1725             fitch9.setUseLast( false );
1726             fitch9.execute( p9, m9 );
1727             final CharacterStateMatrix<GainLossStates> gl_m_9a = fitch9.getGainLossMatrix();
1728             if ( fitch9.getCost() != 2 ) {
1729                 return false;
1730             }
1731             if ( fitch9.getTotalLosses() != 1 ) {
1732                 return false;
1733             }
1734             if ( fitch9.getTotalGains() != 1 ) {
1735                 return false;
1736             }
1737             if ( fitch9.getTotalUnchanged() != 5 ) {
1738                 return false;
1739             }
1740             if ( gl_m_9a.getState( "a", "0" ) != UNCHANGED_PRESENT ) {
1741                 return false;
1742             }
1743             if ( gl_m_9a.getState( "b", "0" ) != LOSS ) {
1744                 return false;
1745             }
1746             if ( gl_m_9a.getState( "c", "0" ) != UNCHANGED_PRESENT ) {
1747                 return false;
1748             }
1749             if ( gl_m_9a.getState( "d", "0" ) != UNCHANGED_ABSENT ) {
1750                 return false;
1751             }
1752             if ( gl_m_9a.getState( "ab", "0" ) != UNCHANGED_PRESENT ) {
1753                 return false;
1754             }
1755             if ( gl_m_9a.getState( "abc", "0" ) != GAIN ) {
1756                 return false;
1757             }
1758             if ( gl_m_9a.getState( "abcd", "0" ) != UNCHANGED_ABSENT ) {
1759                 return false;
1760             }
1761             fitch9.setUseLast( true );
1762             fitch9.execute( p9, m9 );
1763             final CharacterStateMatrix<GainLossStates> gl_m_9b = fitch9.getGainLossMatrix();
1764             if ( fitch9.getCost() != 2 ) {
1765                 return false;
1766             }
1767             if ( fitch9.getTotalLosses() != 2 ) {
1768                 return false;
1769             }
1770             if ( fitch9.getTotalGains() != 0 ) {
1771                 return false;
1772             }
1773             if ( fitch9.getTotalUnchanged() != 5 ) {
1774                 return false;
1775             }
1776             if ( gl_m_9b.getState( "a", "0" ) != UNCHANGED_PRESENT ) {
1777                 return false;
1778             }
1779             if ( gl_m_9b.getState( "b", "0" ) != LOSS ) {
1780                 return false;
1781             }
1782             if ( gl_m_9b.getState( "c", "0" ) != UNCHANGED_PRESENT ) {
1783                 return false;
1784             }
1785             if ( gl_m_9b.getState( "d", "0" ) != LOSS ) {
1786                 return false;
1787             }
1788             if ( gl_m_9b.getState( "ab", "0" ) != UNCHANGED_PRESENT ) {
1789                 return false;
1790             }
1791             if ( gl_m_9b.getState( "abc", "0" ) != UNCHANGED_PRESENT ) {
1792                 return false;
1793             }
1794             if ( gl_m_9b.getState( "abcd", "0" ) != UNCHANGED_PRESENT ) {
1795                 return false;
1796             }
1797             fitch9.setUseLast( false );
1798             fitch9.setRandomize( true );
1799             fitch9.setRandomNumberSeed( 8722445 );
1800             fitch9.execute( p9, m9 );
1801             fitch9.getGainLossMatrix();
1802             if ( fitch9.getCost() != 2 ) {
1803                 return false;
1804             }
1805             if ( fitch9.getTotalLosses() != 1 ) {
1806                 return false;
1807             }
1808             if ( fitch9.getTotalGains() != 1 ) {
1809                 return false;
1810             }
1811             if ( fitch9.getTotalUnchanged() != 5 ) {
1812                 return false;
1813             }
1814             final FitchParsimony<BinaryStates> fitch10 = new FitchParsimony<BinaryStates>();
1815             final PhylogenyFactory factory10 = ParserBasedPhylogenyFactory.getInstance();
1816             final String p10_str = "((((a,b)ab,c)abc,d)abcd,e)abcde";
1817             final Phylogeny p10 = factory10.create( p10_str, new NHXParser() )[ 0 ];
1818             final CharacterStateMatrix<BinaryStates> m10 = new BasicCharacterStateMatrix<BinaryStates>( 5, 1 );
1819             m10.setIdentifier( 0, "a" );
1820             m10.setIdentifier( 1, "b" );
1821             m10.setIdentifier( 2, "c" );
1822             m10.setIdentifier( 3, "d" );
1823             m10.setIdentifier( 4, "e" );
1824             m10.setCharacter( 0, "0" );
1825             m10.setState( "a", "0", PRESENT );
1826             m10.setState( "b", "0", ABSENT );
1827             m10.setState( "c", "0", ABSENT );
1828             m10.setState( "d", "0", PRESENT );
1829             m10.setState( "e", "0", ABSENT );
1830             fitch10.setReturnInternalStates( true );
1831             fitch10.setReturnGainLossMatrix( true );
1832             fitch10.setUseLast( false );
1833             fitch10.execute( p10, m10 );
1834             final CharacterStateMatrix<GainLossStates> gl_m_10a = fitch10.getGainLossMatrix();
1835             if ( fitch10.getCost() != 2 ) {
1836                 return false;
1837             }
1838             if ( fitch10.getTotalLosses() != 0 ) {
1839                 return false;
1840             }
1841             if ( fitch10.getTotalGains() != 2 ) {
1842                 return false;
1843             }
1844             if ( fitch10.getTotalUnchanged() != 7 ) {
1845                 return false;
1846             }
1847             if ( gl_m_10a.getState( "a", "0" ) != GAIN ) {
1848                 return false;
1849             }
1850             if ( gl_m_10a.getState( "b", "0" ) != UNCHANGED_ABSENT ) {
1851                 return false;
1852             }
1853             if ( gl_m_10a.getState( "c", "0" ) != UNCHANGED_ABSENT ) {
1854                 return false;
1855             }
1856             if ( gl_m_10a.getState( "d", "0" ) != GAIN ) {
1857                 return false;
1858             }
1859             if ( gl_m_10a.getState( "e", "0" ) != UNCHANGED_ABSENT ) {
1860                 return false;
1861             }
1862             if ( gl_m_10a.getState( "ab", "0" ) != UNCHANGED_ABSENT ) {
1863                 return false;
1864             }
1865             if ( gl_m_10a.getState( "abc", "0" ) != UNCHANGED_ABSENT ) {
1866                 return false;
1867             }
1868             if ( gl_m_10a.getState( "abcd", "0" ) != UNCHANGED_ABSENT ) {
1869                 return false;
1870             }
1871             if ( gl_m_10a.getState( "abcde", "0" ) != UNCHANGED_ABSENT ) {
1872                 return false;
1873             }
1874             fitch10.setUseLast( true );
1875             fitch10.execute( p10, m10 );
1876             final CharacterStateMatrix<GainLossStates> gl_m_10b = fitch10.getGainLossMatrix();
1877             if ( fitch10.getCost() != 2 ) {
1878                 return false;
1879             }
1880             if ( fitch10.getTotalLosses() != 0 ) {
1881                 return false;
1882             }
1883             if ( fitch10.getTotalGains() != 2 ) {
1884                 return false;
1885             }
1886             if ( fitch10.getTotalUnchanged() != 7 ) {
1887                 return false;
1888             }
1889             if ( gl_m_10b.getState( "a", "0" ) != GAIN ) {
1890                 return false;
1891             }
1892             if ( gl_m_10b.getState( "b", "0" ) != UNCHANGED_ABSENT ) {
1893                 return false;
1894             }
1895             if ( gl_m_10b.getState( "c", "0" ) != UNCHANGED_ABSENT ) {
1896                 return false;
1897             }
1898             if ( gl_m_10b.getState( "d", "0" ) != GAIN ) {
1899                 return false;
1900             }
1901             if ( gl_m_10b.getState( "e", "0" ) != UNCHANGED_ABSENT ) {
1902                 return false;
1903             }
1904             if ( gl_m_10b.getState( "ab", "0" ) != UNCHANGED_ABSENT ) {
1905                 return false;
1906             }
1907             if ( gl_m_10b.getState( "abc", "0" ) != UNCHANGED_ABSENT ) {
1908                 return false;
1909             }
1910             if ( gl_m_10b.getState( "abcd", "0" ) != UNCHANGED_ABSENT ) {
1911                 return false;
1912             }
1913             if ( gl_m_10b.getState( "abcde", "0" ) != UNCHANGED_ABSENT ) {
1914                 return false;
1915             }
1916         }
1917         catch ( final Exception e ) {
1918             e.printStackTrace( System.out );
1919             return false;
1920         }
1921         return true;
1922     }
1923
1924     private static boolean testNeighborJoining() {
1925         try {
1926             final NeighborJoiningF njf = NeighborJoiningF.createInstance();
1927             final BasicSymmetricalDistanceMatrix m0f = new BasicSymmetricalDistanceMatrix( 4 );
1928             m0f.setIdentifier( 0, "A" );
1929             m0f.setIdentifier( 1, "B" );
1930             m0f.setIdentifier( 2, "C" );
1931             m0f.setIdentifier( 3, "D" );
1932             m0f.setRow( "5 ", 1 );
1933             m0f.setRow( "3 6 ", 2 );
1934             m0f.setRow( "7.5 10.5 5.5", 3 );
1935             final Phylogeny p0f = njf.execute( m0f );
1936             p0f.reRoot( p0f.getNode( "D" ) );
1937             if ( isUnequal( p0f.getNode( "A" ).getDistanceToParent(), 1 ) ) {
1938                 return false;
1939             }
1940             if ( isUnequal( p0f.getNode( "B" ).getDistanceToParent(), 4 ) ) {
1941                 return false;
1942             }
1943             if ( isUnequal( p0f.getNode( "C" ).getDistanceToParent(), 0.5 ) ) {
1944                 return false;
1945             }
1946             if ( isUnequal( p0f.getNode( "D" ).getDistanceToParent(), 2.5 ) ) {
1947                 return false;
1948             }
1949             if ( isUnequal( p0f.getNode( "A" ).getParent().getDistanceToParent(), 1.5 ) ) {
1950                 return false;
1951             }
1952             if ( isUnequal( p0f.getNode( "A" ).getParent().getParent().getDistanceToParent(), 2.5 ) ) {
1953                 return false;
1954             }
1955             //
1956             NeighborJoining nj = NeighborJoining.createInstance();
1957             final BasicSymmetricalDistanceMatrix m0 = new BasicSymmetricalDistanceMatrix( 4 );
1958             m0.setIdentifier( 0, "A" );
1959             m0.setIdentifier( 1, "B" );
1960             m0.setIdentifier( 2, "C" );
1961             m0.setIdentifier( 3, "D" );
1962             m0.setRow( "5 ", 1 );
1963             m0.setRow( "3 6 ", 2 );
1964             m0.setRow( "7.5 10.5 5.5", 3 );
1965             final Phylogeny p0 = nj.execute( m0 );
1966             p0.reRoot( p0.getNode( "D" ) );
1967             if ( isUnequal( p0.getNode( "A" ).getDistanceToParent(), 1 ) ) {
1968                 return false;
1969             }
1970             if ( isUnequal( p0.getNode( "B" ).getDistanceToParent(), 4 ) ) {
1971                 return false;
1972             }
1973             if ( isUnequal( p0.getNode( "C" ).getDistanceToParent(), 0.5 ) ) {
1974                 return false;
1975             }
1976             if ( isUnequal( p0.getNode( "D" ).getDistanceToParent(), 2.5 ) ) {
1977                 return false;
1978             }
1979             if ( isUnequal( p0.getNode( "A" ).getParent().getDistanceToParent(), 1.5 ) ) {
1980                 return false;
1981             }
1982             if ( isUnequal( p0.getNode( "A" ).getParent().getParent().getDistanceToParent(), 2.5 ) ) {
1983                 return false;
1984             }
1985             nj = NeighborJoining.createInstance();
1986             final BasicSymmetricalDistanceMatrix m00 = new BasicSymmetricalDistanceMatrix( 4 );
1987             m00.setIdentifier( 0, "A" );
1988             m00.setIdentifier( 1, "B" );
1989             m00.setIdentifier( 2, "C" );
1990             m00.setIdentifier( 3, "D" );
1991             m00.setRow( "2.01 ", 1 );
1992             m00.setRow( "3 3.01 ", 2 );
1993             m00.setRow( "3.01 3.02 1.01", 3 );
1994             final Phylogeny p00 = nj.execute( m00 );
1995             p00.reRoot( p00.getNode( "D" ) );
1996             if ( isUnequal( p00.getNode( "A" ).getDistanceToParent(), 1 ) ) {
1997                 return false;
1998             }
1999             if ( isUnequal( p00.getNode( "B" ).getDistanceToParent(), 1.01 ) ) {
2000                 return false;
2001             }
2002             if ( isUnequal( p00.getNode( "C" ).getDistanceToParent(), 0.5 ) ) {
2003                 return false;
2004             }
2005             if ( isUnequal( p00.getNode( "D" ).getDistanceToParent(), 0.255 ) ) {
2006                 return false;
2007             }
2008             if ( isUnequal( p00.getNode( "A" ).getParent().getDistanceToParent(), 1.5 ) ) {
2009                 return false;
2010             }
2011             if ( isUnequal( p00.getNode( "A" ).getParent().getParent().getDistanceToParent(), 0.255 ) ) {
2012                 return false;
2013             }
2014             BasicSymmetricalDistanceMatrix m = new BasicSymmetricalDistanceMatrix( 6 );
2015             m.setRow( "5", 1 );
2016             m.setRow( "4 7", 2 );
2017             m.setRow( "7 10 7", 3 );
2018             m.setRow( "6 9 6 5", 4 );
2019             m.setRow( "8 11 8 9 8", 5 );
2020             m.setIdentifier( 0, "A" );
2021             m.setIdentifier( 1, "B" );
2022             m.setIdentifier( 2, "C" );
2023             m.setIdentifier( 3, "D" );
2024             m.setIdentifier( 4, "E" );
2025             m.setIdentifier( 5, "F" );
2026             nj = NeighborJoining.createInstance();
2027             final Phylogeny p1 = nj.execute( m );
2028             p1.reRoot( p1.getNode( "F" ) );
2029             if ( isUnequal( p1.getNode( "A" ).getDistanceToParent(), 1 ) ) {
2030                 return false;
2031             }
2032             if ( isUnequal( p1.getNode( "B" ).getDistanceToParent(), 4 ) ) {
2033                 return false;
2034             }
2035             if ( isUnequal( p1.getNode( "C" ).getDistanceToParent(), 2 ) ) {
2036                 return false;
2037             }
2038             if ( isUnequal( p1.getNode( "D" ).getDistanceToParent(), 3 ) ) {
2039                 return false;
2040             }
2041             if ( isUnequal( p1.getNode( "E" ).getDistanceToParent(), 2 ) ) {
2042                 return false;
2043             }
2044             if ( isUnequal( p1.getNode( "F" ).getDistanceToParent(), 2.5 ) ) {
2045                 return false;
2046             }
2047             if ( isUnequal( p1.getNode( "A" ).getParent().getDistanceToParent(), 1 ) ) {
2048                 return false;
2049             }
2050             if ( isUnequal( p1.getNode( "A" ).getParent().getParent().getDistanceToParent(), 1 ) ) {
2051                 return false;
2052             }
2053             if ( isUnequal( p1.getNode( "A" ).getParent().getParent().getParent().getDistanceToParent(), 2.5 ) ) {
2054                 return false;
2055             }
2056             if ( isUnequal( p1.getNode( "B" ).getParent().getDistanceToParent(), 1 ) ) {
2057                 return false;
2058             }
2059             if ( isUnequal( p1.getNode( "D" ).getParent().getDistanceToParent(), 1 ) ) {
2060                 return false;
2061             }
2062             if ( isUnequal( p1.getNode( "E" ).getParent().getDistanceToParent(), 1 ) ) {
2063                 return false;
2064             }
2065             m = new BasicSymmetricalDistanceMatrix( 7 );
2066             m.setIdentifier( 0, "Bovine" );
2067             m.setIdentifier( 1, "Mouse" );
2068             m.setIdentifier( 2, "Gibbon" );
2069             m.setIdentifier( 3, "Orang" );
2070             m.setIdentifier( 4, "Gorilla" );
2071             m.setIdentifier( 5, "Chimp" );
2072             m.setIdentifier( 6, "Human" );
2073             m.setRow( "0.00000 1.68660 1.71980 1.66060 1.52430 1.60430 1.59050", 0 );
2074             m.setRow( "1.68660 0.00000 1.52320 1.48410 1.44650 1.43890 1.46290", 1 );
2075             m.setRow( "1.71980 1.52320 0.00000 0.71150 0.59580 0.61790 0.55830", 2 );
2076             m.setRow( "1.66060 1.48410 0.71150 0.00000 0.46310 0.50610 0.47100", 3 );
2077             m.setRow( "1.52430 1.44650 0.59580 0.46310 0.00000 0.34840 0.30830", 4 );
2078             m.setRow( "1.60430 1.43890 0.61790 0.50610 0.34840 0.00000 0.26920", 5 );
2079             m.setRow( "1.59050 1.46290 0.55830 0.47100 0.30830 0.26920 0.00000", 6 );
2080             nj = NeighborJoining.createInstance( false, 6 );
2081             final Phylogeny p2 = nj.execute( m );
2082             p2.reRoot( p2.getNode( "Bovine" ) );
2083             if ( isUnequal( p2.getNode( "Chimp" ).getDistanceToParent(), 0.151675 ) ) {
2084                 return false;
2085             }
2086             if ( isUnequal( p2.getNode( "Human" ).getDistanceToParent(), 0.117525 ) ) {
2087                 return false;
2088             }
2089             if ( isUnequal( p2.getNode( "Gorilla" ).getDistanceToParent(), 0.153932 ) ) {
2090                 return false;
2091             }
2092             if ( isUnequal( p2.getNode( "Orang" ).getDistanceToParent(), 0.284694 ) ) {
2093                 return false;
2094             }
2095             if ( isUnequal( p2.getNode( "Gibbon" ).getDistanceToParent(), 0.357931 ) ) {
2096                 return false;
2097             }
2098             if ( isUnequal( p2.getNode( "Mouse" ).getDistanceToParent(), 0.76891 ) ) {
2099                 return false;
2100             }
2101             if ( isUnequal( p2.getNode( "Bovine" ).getDistanceToParent(), 0.458845 ) ) {
2102                 return false;
2103             }
2104             if ( isUnequal( p2.getNode( "Chimp" ).getParent().getDistanceToParent(), 0.039819 ) ) {
2105                 return false;
2106             }
2107             if ( isUnequal( p2.getNode( "Human" ).getParent().getDistanceToParent(), 0.039819 ) ) {
2108                 return false;
2109             }
2110             if ( isUnequal( p2.getNode( "Chimp" ).getParent().getParent().getDistanceToParent(), 0.026956 ) ) {
2111                 return false;
2112             }
2113             if ( isUnequal( p2.getNode( "Chimp" ).getParent().getParent().getParent().getDistanceToParent(), 0.046481 ) ) {
2114                 return false;
2115             }
2116             if ( isUnequal( p2.getNode( "Chimp" ).getParent().getParent().getParent().getParent().getDistanceToParent(),
2117                             0.420269 ) ) {
2118                 return false;
2119             }
2120             if ( isUnequal( p2.getNode( "Chimp" ).getParent().getParent().getParent().getParent().getParent()
2121                     .getDistanceToParent(), 0.458845 ) ) {
2122                 return false;
2123             }
2124             m = new BasicSymmetricalDistanceMatrix( 4 );
2125             m.setIdentifier( 0, "A" );
2126             m.setIdentifier( 1, "B" );
2127             m.setIdentifier( 2, "C" );
2128             m.setIdentifier( 3, "D" );
2129             m.setRow( "0.00 0.95 0.17 0.98", 0 );
2130             m.setRow( "0.95 0.00 1.02 1.83", 1 );
2131             m.setRow( "0.17 1.02 0.00 1.01", 2 );
2132             m.setRow( "0.98 1.83 1.01 0.00", 3 );
2133             final Phylogeny p3 = nj.execute( m );
2134             p3.reRoot( p3.getNode( "C" ) );
2135             if ( isUnequal( p3.getNode( "A" ).getDistanceToParent(), 0.05 ) ) {
2136                 return false;
2137             }
2138             if ( isUnequal( p3.getNode( "B" ).getDistanceToParent(), 0.90 ) ) {
2139                 return false;
2140             }
2141             if ( !isEqual( p3.getNode( "C" ).getDistanceToParent(), 0.05 ) ) {
2142                 return false;
2143             }
2144             if ( !isEqual( p3.getNode( "D" ).getDistanceToParent(), 0.91 ) ) {
2145                 return false;
2146             }
2147             if ( isUnequal( p3.getNode( "A" ).getParent().getDistanceToParent(), 0.02 ) ) {
2148                 return false;
2149             }
2150             if ( isUnequal( p3.getNode( "A" ).getParent().getParent().getDistanceToParent(), 0.05 ) ) {
2151                 return false;
2152             }
2153             //if ( TIME ) {
2154             //    timeNeighborJoining();
2155             //}
2156         }
2157         catch ( final Exception e ) {
2158             e.printStackTrace( System.out );
2159             return false;
2160         }
2161         return true;
2162     }
2163
2164     private static boolean testSymmetricalDistanceMatrixParser() {
2165         try {
2166             final String l = ForesterUtil.getLineSeparator();
2167             StringBuffer source = new StringBuffer();
2168             source.append( " 4" + l );
2169             source.append( "A 0 0 0 0" + l );
2170             source.append( "B 1 0 0 0" + l );
2171             source.append( "C 2 4 0 0" + l );
2172             source.append( "D 3 5 6 0" + l );
2173             source.append( l );
2174             source.append( " 4" + l );
2175             source.append( "A 0   11  12  13" + l );
2176             source.append( "B 11  0   14  15" + l );
2177             source.append( "C 12  14  0   16" + l );
2178             source.append( "D 13  15  16  0" + l );
2179             source.append( l );
2180             source.append( l );
2181             source.append( "     " + l );
2182             source.append( " 4" + l );
2183             source.append( " A        0     " + l );
2184             source.append( " B            21 0" + l );
2185             source.append( " C            22 24    0  " + l );
2186             source.append( " # 2 222 2 2 " + l );
2187             source.append( " D            23 25 26 0" + l );
2188             source.append( l );
2189             source.append( l );
2190             source.append( "     " + l );
2191             final SymmetricalDistanceMatrixParser p0 = SymmetricalDistanceMatrixParser.createInstance();
2192             final DistanceMatrix[] ma0 = p0.parse( source.toString() );
2193             if ( ma0.length != 3 ) {
2194                 return false;
2195             }
2196             if ( !isEqual( ma0[ 0 ].getValue( 0, 0 ), 0 ) ) {
2197                 return false;
2198             }
2199             if ( !isEqual( ma0[ 0 ].getValue( 1, 0 ), 1 ) ) {
2200                 return false;
2201             }
2202             if ( !isEqual( ma0[ 0 ].getValue( 2, 0 ), 2 ) ) {
2203                 return false;
2204             }
2205             if ( !isEqual( ma0[ 0 ].getValue( 3, 0 ), 3 ) ) {
2206                 return false;
2207             }
2208             if ( !isEqual( ma0[ 0 ].getValue( 0, 1 ), 1 ) ) {
2209                 return false;
2210             }
2211             if ( !isEqual( ma0[ 0 ].getValue( 1, 1 ), 0 ) ) {
2212                 return false;
2213             }
2214             if ( !isEqual( ma0[ 0 ].getValue( 2, 1 ), 4 ) ) {
2215                 return false;
2216             }
2217             if ( !isEqual( ma0[ 0 ].getValue( 3, 1 ), 5 ) ) {
2218                 return false;
2219             }
2220             if ( !isEqual( ma0[ 1 ].getValue( 0, 0 ), 0 ) ) {
2221                 return false;
2222             }
2223             if ( !isEqual( ma0[ 1 ].getValue( 1, 0 ), 11 ) ) {
2224                 return false;
2225             }
2226             if ( !isEqual( ma0[ 1 ].getValue( 2, 0 ), 12 ) ) {
2227                 return false;
2228             }
2229             if ( !isEqual( ma0[ 1 ].getValue( 3, 0 ), 13 ) ) {
2230                 return false;
2231             }
2232             if ( !isEqual( ma0[ 1 ].getValue( 0, 1 ), 11 ) ) {
2233                 return false;
2234             }
2235             if ( !isEqual( ma0[ 1 ].getValue( 1, 1 ), 0 ) ) {
2236                 return false;
2237             }
2238             if ( !isEqual( ma0[ 1 ].getValue( 2, 1 ), 14 ) ) {
2239                 return false;
2240             }
2241             if ( !isEqual( ma0[ 1 ].getValue( 3, 1 ), 15 ) ) {
2242                 return false;
2243             }
2244             if ( !isEqual( ma0[ 2 ].getValue( 0, 0 ), 0 ) ) {
2245                 return false;
2246             }
2247             if ( !isEqual( ma0[ 2 ].getValue( 1, 0 ), 21 ) ) {
2248                 return false;
2249             }
2250             if ( !isEqual( ma0[ 2 ].getValue( 2, 0 ), 22 ) ) {
2251                 return false;
2252             }
2253             if ( !isEqual( ma0[ 2 ].getValue( 3, 0 ), 23 ) ) {
2254                 return false;
2255             }
2256             if ( !isEqual( ma0[ 2 ].getValue( 0, 1 ), 21 ) ) {
2257                 return false;
2258             }
2259             if ( !isEqual( ma0[ 2 ].getValue( 1, 1 ), 0 ) ) {
2260                 return false;
2261             }
2262             if ( !isEqual( ma0[ 2 ].getValue( 2, 1 ), 24 ) ) {
2263                 return false;
2264             }
2265             if ( !isEqual( ma0[ 2 ].getValue( 3, 1 ), 25 ) ) {
2266                 return false;
2267             }
2268             source = new StringBuffer();
2269             source.append( "A 0 0 0 0" + l );
2270             source.append( "B 1 0 0 0" + l );
2271             source.append( "C 2 4 0 0" + l );
2272             source.append( "D 3 5 6 0" + l );
2273             source.append( " " + l );
2274             source.append( "A 0   11  12  13" + l );
2275             source.append( "B 11  0   14  15" + l );
2276             source.append( "C 12  14  0   16" + l );
2277             source.append( "D 13  15  16  0" + l );
2278             source.append( l );
2279             source.append( " A        0     " + l );
2280             source.append( " B            21 0" + l );
2281             source.append( " C            22 24    0  " + l );
2282             source.append( " # 2 222 2 2 " + l );
2283             source.append( " D            23 25 26 0" + l );
2284             final DistanceMatrix[] ma1 = p0.parse( source.toString() );
2285             if ( ma1.length != 3 ) {
2286                 return false;
2287             }
2288             if ( !isEqual( ma1[ 0 ].getValue( 0, 0 ), 0 ) ) {
2289                 return false;
2290             }
2291             if ( !isEqual( ma1[ 0 ].getValue( 1, 0 ), 1 ) ) {
2292                 return false;
2293             }
2294             if ( !isEqual( ma1[ 0 ].getValue( 2, 0 ), 2 ) ) {
2295                 return false;
2296             }
2297             if ( !isEqual( ma1[ 0 ].getValue( 3, 0 ), 3 ) ) {
2298                 return false;
2299             }
2300             if ( !isEqual( ma1[ 0 ].getValue( 0, 1 ), 1 ) ) {
2301                 return false;
2302             }
2303             if ( !isEqual( ma1[ 0 ].getValue( 1, 1 ), 0 ) ) {
2304                 return false;
2305             }
2306             if ( !isEqual( ma1[ 0 ].getValue( 2, 1 ), 4 ) ) {
2307                 return false;
2308             }
2309             if ( !isEqual( ma1[ 0 ].getValue( 3, 1 ), 5 ) ) {
2310                 return false;
2311             }
2312             if ( !isEqual( ma1[ 1 ].getValue( 0, 0 ), 0 ) ) {
2313                 return false;
2314             }
2315             if ( !isEqual( ma1[ 1 ].getValue( 1, 0 ), 11 ) ) {
2316                 return false;
2317             }
2318             if ( !isEqual( ma1[ 1 ].getValue( 2, 0 ), 12 ) ) {
2319                 return false;
2320             }
2321             if ( !isEqual( ma1[ 1 ].getValue( 3, 0 ), 13 ) ) {
2322                 return false;
2323             }
2324             if ( !isEqual( ma1[ 1 ].getValue( 0, 1 ), 11 ) ) {
2325                 return false;
2326             }
2327             if ( !isEqual( ma1[ 1 ].getValue( 1, 1 ), 0 ) ) {
2328                 return false;
2329             }
2330             if ( !isEqual( ma1[ 1 ].getValue( 2, 1 ), 14 ) ) {
2331                 return false;
2332             }
2333             if ( !isEqual( ma1[ 1 ].getValue( 3, 1 ), 15 ) ) {
2334                 return false;
2335             }
2336             if ( !isEqual( ma1[ 2 ].getValue( 0, 0 ), 0 ) ) {
2337                 return false;
2338             }
2339             if ( !isEqual( ma1[ 2 ].getValue( 1, 0 ), 21 ) ) {
2340                 return false;
2341             }
2342             if ( !isEqual( ma1[ 2 ].getValue( 2, 0 ), 22 ) ) {
2343                 return false;
2344             }
2345             if ( !isEqual( ma1[ 2 ].getValue( 3, 0 ), 23 ) ) {
2346                 return false;
2347             }
2348             if ( !isEqual( ma1[ 2 ].getValue( 0, 1 ), 21 ) ) {
2349                 return false;
2350             }
2351             if ( !isEqual( ma1[ 2 ].getValue( 1, 1 ), 0 ) ) {
2352                 return false;
2353             }
2354             if ( !isEqual( ma1[ 2 ].getValue( 2, 1 ), 24 ) ) {
2355                 return false;
2356             }
2357             if ( !isEqual( ma1[ 2 ].getValue( 3, 1 ), 25 ) ) {
2358                 return false;
2359             }
2360             source = new StringBuffer();
2361             source.append( "A 0" + l );
2362             source.append( "B 10 0" + l );
2363             final DistanceMatrix[] ma2 = p0.parse( source.toString() );
2364             if ( ma2.length != 1 ) {
2365                 return false;
2366             }
2367             if ( !isEqual( ma2[ 0 ].getValue( 0, 1 ), 10 ) ) {
2368                 return false;
2369             }
2370             source = new StringBuffer();
2371             source.append( " " + l );
2372             source.append( "#" + l );
2373             final DistanceMatrix[] ma3 = p0.parse( source.toString() );
2374             if ( ma3.length != 0 ) {
2375                 return false;
2376             }
2377             source = new StringBuffer();
2378             source.append( " " + l );
2379             source.append( "A 0   11  12  13" + l );
2380             source.append( "B     0   14  15" + l );
2381             source.append( "C         0   16" + l );
2382             source.append( "D              0" + l );
2383             source.append( l );
2384             source.append( "A 0 21  22  23" + l );
2385             source.append( "B 0 24  25" + l );
2386             source.append( "C 0 26" + l );
2387             source.append( "D 0" + l );
2388             p0.setInputMatrixType( SymmetricalDistanceMatrixParser.InputMatrixType.UPPER_TRIANGLE );
2389             final DistanceMatrix[] ma4 = p0.parse( source );
2390             if ( ma4.length != 2 ) {
2391                 return false;
2392             }
2393             if ( !isEqual( ma4[ 0 ].getValue( 0, 0 ), 0 ) ) {
2394                 return false;
2395             }
2396             if ( !isEqual( ma4[ 0 ].getValue( 1, 0 ), 11 ) ) {
2397                 return false;
2398             }
2399             if ( !isEqual( ma4[ 0 ].getValue( 2, 0 ), 12 ) ) {
2400                 return false;
2401             }
2402             if ( !isEqual( ma4[ 0 ].getValue( 3, 0 ), 13 ) ) {
2403                 return false;
2404             }
2405             if ( !isEqual( ma4[ 0 ].getValue( 0, 1 ), 11 ) ) {
2406                 return false;
2407             }
2408             if ( !isEqual( ma4[ 0 ].getValue( 1, 1 ), 0 ) ) {
2409                 return false;
2410             }
2411             if ( !isEqual( ma4[ 0 ].getValue( 2, 1 ), 14 ) ) {
2412                 return false;
2413             }
2414             if ( !isEqual( ma4[ 0 ].getValue( 3, 1 ), 15 ) ) {
2415                 return false;
2416             }
2417             if ( !isEqual( ma4[ 0 ].getValue( 0, 2 ), 12 ) ) {
2418                 return false;
2419             }
2420             if ( !isEqual( ma4[ 0 ].getValue( 1, 2 ), 14 ) ) {
2421                 return false;
2422             }
2423             if ( !isEqual( ma4[ 0 ].getValue( 2, 2 ), 0 ) ) {
2424                 return false;
2425             }
2426             if ( !isEqual( ma4[ 0 ].getValue( 3, 2 ), 16 ) ) {
2427                 return false;
2428             }
2429             if ( !isEqual( ma4[ 0 ].getValue( 0, 3 ), 13 ) ) {
2430                 return false;
2431             }
2432             if ( !isEqual( ma4[ 0 ].getValue( 1, 3 ), 15 ) ) {
2433                 return false;
2434             }
2435             if ( !isEqual( ma4[ 0 ].getValue( 2, 3 ), 16 ) ) {
2436                 return false;
2437             }
2438             if ( !isEqual( ma4[ 0 ].getValue( 3, 3 ), 0 ) ) {
2439                 return false;
2440             }
2441             source = new StringBuffer();
2442             source.append( " 4 " + l );
2443             source.append( "A 0   11  12  13" + l );
2444             source.append( "B     0   14  15" + l );
2445             source.append( "C         0   16" + l );
2446             source.append( "D              0" + l );
2447             source.append( " 4" + l );
2448             source.append( "A 0 21  22  23" + l );
2449             source.append( "B 0 24  25" + l );
2450             source.append( "C 0 26" + l );
2451             source.append( "D 0" + l );
2452             source.append( "     " + l );
2453             source.append( " 4" + l );
2454             source.append( "A 0 21  22  23" + l );
2455             source.append( "B 0 24  25" + l );
2456             source.append( "C 0 26" + l );
2457             source.append( "D 0" + l );
2458             source.append( l );
2459             source.append( "A 0 21  22  23" + l );
2460             source.append( "B 0 24  25" + l );
2461             source.append( "C 0 26" + l );
2462             source.append( "D 0" + l );
2463             p0.setInputMatrixType( SymmetricalDistanceMatrixParser.InputMatrixType.UPPER_TRIANGLE );
2464             final DistanceMatrix[] ma5 = p0.parse( source );
2465             if ( ma5.length != 4 ) {
2466                 return false;
2467             }
2468             if ( !isEqual( ma5[ 0 ].getValue( 0, 0 ), 0 ) ) {
2469                 return false;
2470             }
2471             if ( !isEqual( ma5[ 0 ].getValue( 1, 0 ), 11 ) ) {
2472                 return false;
2473             }
2474             if ( !isEqual( ma5[ 0 ].getValue( 2, 0 ), 12 ) ) {
2475                 return false;
2476             }
2477             if ( !isEqual( ma5[ 0 ].getValue( 3, 0 ), 13 ) ) {
2478                 return false;
2479             }
2480             if ( !isEqual( ma5[ 0 ].getValue( 0, 1 ), 11 ) ) {
2481                 return false;
2482             }
2483             if ( !isEqual( ma5[ 0 ].getValue( 1, 1 ), 0 ) ) {
2484                 return false;
2485             }
2486             if ( !isEqual( ma5[ 0 ].getValue( 2, 1 ), 14 ) ) {
2487                 return false;
2488             }
2489             if ( !isEqual( ma5[ 0 ].getValue( 3, 1 ), 15 ) ) {
2490                 return false;
2491             }
2492             if ( !isEqual( ma5[ 0 ].getValue( 0, 2 ), 12 ) ) {
2493                 return false;
2494             }
2495             if ( !isEqual( ma5[ 0 ].getValue( 1, 2 ), 14 ) ) {
2496                 return false;
2497             }
2498             if ( !isEqual( ma5[ 0 ].getValue( 2, 2 ), 0 ) ) {
2499                 return false;
2500             }
2501             if ( !isEqual( ma5[ 0 ].getValue( 3, 2 ), 16 ) ) {
2502                 return false;
2503             }
2504             if ( !isEqual( ma5[ 0 ].getValue( 0, 3 ), 13 ) ) {
2505                 return false;
2506             }
2507             if ( !isEqual( ma5[ 0 ].getValue( 1, 3 ), 15 ) ) {
2508                 return false;
2509             }
2510             if ( !isEqual( ma5[ 0 ].getValue( 2, 3 ), 16 ) ) {
2511                 return false;
2512             }
2513             if ( !isEqual( ma5[ 0 ].getValue( 3, 3 ), 0 ) ) {
2514                 return false;
2515             }
2516         }
2517         catch ( final Exception e ) {
2518             e.printStackTrace( System.out );
2519             return false;
2520         }
2521         return true;
2522     }
2523
2524     private static void timeNeighborJoining() {
2525         final NeighborJoiningF njf = NeighborJoiningF.createInstance();
2526         for( int n = 3; n <= 10; ++n ) {
2527             final int x = ( int ) Math.pow( 2, n );
2528             final BasicSymmetricalDistanceMatrix mt = new BasicSymmetricalDistanceMatrix( x );
2529             mt.randomize( new Date().getTime() );
2530             //  for( int i = 0; i < mt.getSize(); i++ ) {
2531             //      mt.setIdentifier( i, i + "i" );
2532             //  }
2533             //  System.out.println( mt.toStringBuffer( Format.PHYLIP ) );
2534             final long start_time = new Date().getTime();
2535             njf.execute( mt );
2536             System.out.println( "Size: " + x + " -> " + ( new Date().getTime() - start_time ) + "ms" );
2537         }
2538         final NeighborJoining nj = NeighborJoining.createInstance();
2539         for( int n = 3; n <= 10; ++n ) {
2540             final int x = ( int ) Math.pow( 2, n );
2541             final BasicSymmetricalDistanceMatrix mt = new BasicSymmetricalDistanceMatrix( x );
2542             mt.randomize( new Date().getTime() );
2543             //  for( int i = 0; i < mt.getSize(); i++ ) {
2544             //      mt.setIdentifier( i, i + "i" );
2545             //  }
2546             //  System.out.println( mt.toStringBuffer( Format.PHYLIP ) );
2547             final long start_time = new Date().getTime();
2548             nj.execute( mt );
2549             System.out.println( "Size: " + x + " -> " + ( new Date().getTime() - start_time ) + "ms" );
2550         }
2551         final NeighborJoiningX njx = NeighborJoiningX.createInstance();
2552         for( int n = 3; n <= 10; ++n ) {
2553             final int x = ( int ) Math.pow( 2, n );
2554             final BasicSymmetricalDistanceMatrix mt = new BasicSymmetricalDistanceMatrix( x );
2555             mt.randomize( new Date().getTime() );
2556             //  for( int i = 0; i < mt.getSize(); i++ ) {
2557             //      mt.setIdentifier( i, i + "i" );
2558             //  }
2559             //  System.out.println( mt.toStringBuffer( Format.PHYLIP ) );
2560             final long start_time = new Date().getTime();
2561             njx.execute( mt );
2562             System.out.println( "Size: " + x + " -> " + ( new Date().getTime() - start_time ) + "ms" );
2563         }
2564     }
2565 }