pstep-recursive.h 6.63 KB
Newer Older
Andreas Tille's avatar
Andreas Tille committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160
/*
 *   pstep-recursive.h
 *
 *
 * Part of TREE-PUZZLE 5.2 (July 2004)
 *
 * (c) 2003-2004 by Heiko A. Schmidt, Korbinian Strimmer, and Arndt von Haeseler
 * (c) 1999-2003 by Heiko A. Schmidt, Korbinian Strimmer,
 *                  M. Vingron, and Arndt von Haeseler
 * (c) 1995-1999 by Korbinian Strimmer and Arndt von Haeseler
 *
 * All parts of the source except where indicated are distributed under
 * the GNU public licence.  See http://www.opensource.org for details.
 *
 * ($Id$)
 *
 */


#ifndef PSTEP_ORIG_H
#define PSTEP_ORIG_H

#include<stdio.h>
#include<stdlib.h>
#include"puzzle.h"
#include"util.h"
/* #include"newpstep.h" */

#ifndef ONEEDGE
#	define ONEEDGE ONEEDGE_ORIG
#endif /* ! ONEEDGE_DEFINED */

/* tree structure */
typedef struct oneedge_orig {
       	/* pointer to other three edges */
       	struct oneedge_orig *up;
       	struct oneedge_orig *downleft;
       	struct oneedge_orig *downright;
       	int numedge;    /* number of edge (index) */
       	uli edgeinfo;   /* value of this edge (penalty) */
       	int *edgemap;   /* pointer to the local edgemap array */
} ONEEDGE_ORIG;


/*****************************************************************************/
/* internal functions for representing and building puzzling step trees      */
/*****************************************************************************/

/* initialize tree with the following starting configuration
 *
 *                2
 *         0  +------- C(=2)
 * A(=0) -----+
 *            +------- B(=1)
 *                1
 *
 *
 *               A(=0)
 *               [up       =NULL]
 *               [downleft =1]
 *               [downright=2]
 *
 *                    o
 *                    |
 *                    |
 *      +-------------+--------------+
 *      |                            |
 *      |                            |
 *      o                            o
 *
 *   C(=1)                        B(=2)
 *   [up       =0]                [up       =0]
 *   [downleft =NULL]             [downleft =NULL]
 *   [downright=NULL]             [downright=NULL]
 *
 *   nextedge = 3
 *   nextleaf = 3
 *   and set according edge maps
 *
 */
void inittree_orig(ONEEDGE_ORIG **edge,	/* out: new array of edges          */
                   int     **edgeofleaf,/* out: array of external edge ptrs */
                   int       Maxspc, 	/* in:  Number of species (n)       */
                   int       Maxbrnch, 	/* in:  Number of branches (2n-3)   */
                   int      *nextedge, 	/* out: next free edge index (=3)   */
                   int      *nextleaf);	/* out: next free leaf index (=3)   */

/* add next leaf on the specified edge */
void addnextleaf_orig(int      dockedge,	/* insert here         */
                      ONEEDGE_ORIG *edge, 	/* edge array          */
                      int     *edgeofleaf, 	/* ext. edge idx array */
                      int      Maxspc, 		/* No. of species      */
                      int      Maxbrnch, 	/* No. of branches     */
                      int     *nextedge, 	/* next free edge idx  */
                      int     *nextleaf);	/* next free leaf idx  */

/* free memory (to be called after inittree) */
void freetree_orig(ONEEDGE_ORIG *edge,		/* edge array          */
                   int     *edgeofleaf, 	/* ext. edge idx array */
                   int      Maxspc);		/* No. of species      */

/* writes OTU sitting on edge ed */
void writeOTU_orig(FILE    *outfp, 		/* output file          */
                   int      ed, 		/* edge to subtree      */
                   ONEEDGE_ORIG *edge, 		/* edge array           */
                   int     *edgeofleaf, 	/* ext. edge idx array  */
                   int      nextedge, 		/* next free edge idx   */
                   int      nextleaf,		/* next free leaf idx   */
                   int     *column,		/* current screen depth */
                   int     *trueID);		/* species permutation  */

/* write tree */
void writetree_orig(FILE   *outfp,		/* output file          */
                   ONEEDGE_ORIG *edge, 		/* edge array           */
                   int     *edgeofleaf, 	/* ext. edge idx array  */
                   int      nextedge, 		/* next free edge idx   */
                   int      nextleaf,		/* next free leaf idx   */
                   int     *trueID);		/* species permutation  */

/* clear all edgeinfos */
void resetedgeinfo_orig(ONEEDGE_ORIG *edge, 	/* edge array           */
                        int      nextedge);	/* next free edge idx   */

/* increment all edgeinfo between leaf A and B */
void incrementedgeinfo_orig(int      A, 	/* start leaf of penalty path */
                            int      B,		/* start leaf of penalty path */
                            ONEEDGE_ORIG *edge,	  /* edge array           */
                            int     *edgeofleaf); /* ext. edge idx array  */

/* checks which edge has the lowest edgeinfo
   if there are several edges with the same lowest edgeinfo,
   one of them will be selected randomly */
void minimumedgeinfo_orig(ONEEDGE_ORIG *edge, 	/* edge array           */
                          int     *edgeofleaf, 	/* ext. edge idx array  */
                          int      nextedge,	/* next free edge idx   */ 
                          int      nextleaf,	/* next free leaf idx   */
                          int     *minedge, 	/* minimum edge set     */
                          uli     *mininfo); 	/* minumum penalty      */

/*****************************************************************************/
/* global functions for representing and building puzzling step trees        */
/*****************************************************************************/

/* perform one single puzzling step to produce one intermediate tree */
void onepstep(                         /* PStep (intermediate) tree topol: */
         ONEEDGE_ORIG **edge,          /*   out: new array of edges        */
         int     **edgeofleaf,         /*   out: array of extern edge ptrs */
         unsigned char *quartettopols, /* in: quartetblock with all topols */
         int       Maxspc,             /* in: Number of species (n)        */
         ivector   permutation);       /* in: species permutation (trueID) */

/* perform Numtrial single puzzling steps constructing Numtrial intermediate */
/* trees, sort each of them and extract splits for consensus step            */
void allpstep(uli       Numtrial,         /* in: no. psteps to perform       */
              unsigned char *quartetinfo, /* in: quartetblock with all topols*/
              int       Maxspc,           /* in: Number of species (n)       */
              int       fixedorder_optn); /* in: 'fixed' anchored RNG (debug)*/

#endif /* PSTEP_ORIG_H */