/***********************************************************\ | A didactic script - Exact Solution by Branch-and-Bound | | by P.A. Goloboff (2021) | | | | Options: | | | | -v0 make run non-verbose (which saves | | a looot of output) | | | | -v1 make run verbose (=default) | | | | -v2 send no output to screen, save it | | text buffer (for later viewing) | | | | This script does NOT collapse zero-length branches; it | | just stores the trees that are distinct as binary | | It also makes heavy use of TNT's commands for handling | | trees (to make it simpler) | | | | Feel free to modify and use. | | | \***********************************************************/ int bound , nextax , max_internal_node , recursionlevel ; int checked = 0 , verbose = 0 ; void check_all_positions ( void ) { int i , n , thistreelength ; tnt ( "copytree %i;" , recursionlevel ) ; // work on a new copy of tree... ++ recursionlevel ; for ( i = 1 ; i < max_internal_node ; ++ i ) { if ( verbose != 1 ) if ( nextax == 5 ) { // produce a progress report progress ( checked , 105 , "Best %i " , bound ) ; ++ checked ; } if ( i == nextax ) i = root + 1 ; // skip terminal taxa not yet in tree (duh!!) tnt ( "edit ] %i %i %i %i ;" , recursionlevel , root , nextax , i ) ; // insert nextax into tree with TNT's "edit" command thistreelength = length ( recursionlevel ) ; if ( verbose ) { if ( verbose == 1 ) tnt ( "sil-all;" ) ; else tnt ( "sil-buff; " ) ; for ( n = 0 ; n < recursionlevel ; ++ n ) tntprintf ( " " ) ; tntprintf ( "Add %i to %i: %i steps" , nextax , i , thistreelength ) ; if ( thistreelength > bound ) tntprintf ( " (worse than bound=%i; skip)\n" , bound ) ; else { if ( thistreelength < bound && nextax == ntax ) tntprintf ( " (improves current bound!)" ) ; tntprintf ( "\n" ) ; }} if ( thistreelength <= bound ) { if ( nextax == ntax ) { // tree is complete if ( thistreelength < bound ) { // update bound and empty tree-vault bound = thistreelength ; tnt ( "sil=all; tvault -; " ) ; } if ( vtrees < 99 ) { if ( verbose ) { if ( verbose == 1 ) tnt ( "sil-all;" ) ; else tnt ( "sil-buff; " ) ; for ( n = 0 ; n < recursionlevel ; ++ n ) tntprintf ( " " ) ; tntprintf ( " Store as tree %i...\n" , vtrees + 1 ) ; tnt ( "sil=all;" ) ; } tnt ( "sil=all; tvault > %i;" , recursionlevel ) ; }} // just store; no need to check duplicate trees (never produced!) else { // call yourself ++ nextax ; ++ max_internal_node ; check_all_positions () ; -- nextax ; -- max_internal_node ; }} tnt ( "sil=all; pruntax %i / %i;" , recursionlevel , nextax ) ; // prune taxon off the tree with TNT's "pruntax" command } tnt ( " keep %i;" , ntrees ) ; // discard temporary copy of tree -- recursionlevel ; } void main ( int argc , char ** argv ) { if ( argc > 1 ) { if ( !strcmp ( "-v0" , argv[ 1 ] ) ) verbose = 0 ; if ( !strcmp ( "-v1" , argv[ 1 ] ) ) verbose = 1 ; if ( !strcmp ( "-v2" , argv[ 1 ] ) ) verbose = 2 ; } tnt ( "hold 100 / 100 ;" ) ; // make sure we have a tree-vault where to store partial results tnt ( "macro=; report - ; mult = repl 1 hold 1 ;" ) ; // get a quick initial bound bound = length ( 0 ) ; tntprintf ( "INITIAL BOUND: %i\n" , bound ) ; tnt ( "sil=all ; keep 0 ; tread ( 0 ( 1 2 ) ) ;" ) ; // create an initial three-taxon tree recursionlevel = 0 ; nextax = 3 ; max_internal_node = root + 2 ; check_all_positions () ; progress ( 0 , 0 , NULL ) ; // erase progress bar tnt ( "keep 0 ; tvault < . ; sil-all ; report=; " ) ; // get all trees from vault tntprintf ( "Branch-and-bound: Found %i trees of %i steps\n" , Ntrees , bound ) ; }