binaries/src/clustalo/src/clustal/muscle_tree.h

   1 /* This a mix of tree functions and data-structures from
   2  * Bob Edgar's Muscle (version 3.7) ported to pure C.
   3  *
   4  * Used files: phy.cpp, tree.h, phytofile.cpp and phyfromclust.cpp
   5  *
   6  * Muscle's code is public domain and so is this code here.
   7
   8  * From http://www.drive5.com/muscle/license.htm:
   9  * """
  10  * MUSCLE is public domain software
  11  *
  12  * The MUSCLE software, including object and source code and
  13  * documentation, is hereby donated to the public domain.
  14  *
  15  * Disclaimer of warranty
  16  * THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND,
  17  * EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * """
  20  *
  21  */
  22
  23 /*
  24  *  RCS $Id: muscle_tree.h 230 2011-04-09 15:37:50Z andreas $
  25  */
  26
  27
  28 #ifndef CLUSTALO_MUSCLE_CLUSTALO_TREE_H
  29 #define CLUSTALO_MUSCLE_CLUSTALO_TREE_H
  30
  31 #include <stdio.h>
  32 #include "util.h"
  33
  34 #ifndef uint
  35 /* limit use of uint (see coding_style_guideline.txt) */
  36 typedef unsigned int uint;
  37 #endif
  38
  39 static const uint NULL_NEIGHBOR = UINT_MAX;
  40
  41 /**
  42  * @brief guide-tree structure
  43  *
  44  * @note We kept the original variable names here, to make it easy to
  45  * search through Muscle's source code.
  46  * From phy.cpp:
  47  *    Node has 0 to 3 neighbors:
  48  *    0 neighbors: singleton root
  49  *    1 neighbor:  leaf, neighbor is parent
  50  *    2 neigbors:  non-singleton root
  51  *    3 neighbors: internal node (other than root)
  52  *
  53  *    Minimal rooted tree is single node.
  54  *    Minimal unrooted tree is single edge.
  55  *    Leaf node always has nulls in neighbors 2 and 3, neighbor 1 is parent.
  56  *    When tree is rooted, neighbor 1=parent, 2=left, 3=right.
  57  *
  58  */
  59 typedef struct {
  60     uint m_uNodeCount;/**< number of nodes */
  61     uint m_uCacheCount;/**< reserved memory */
  62
  63     uint *m_uNeighbor1;/**< parent node */
  64     uint *m_uNeighbor2;/**< left node */
  65     uint *m_uNeighbor3;/**< right node */
  66
  67     /* do we have edge lengths info stored (m_dEdgeLength[123]) */
  68     bool *m_bHasEdgeLength1;
  69     bool *m_bHasEdgeLength2;
  70     bool *m_bHasEdgeLength3;
  71
  72     double *m_dEdgeLength1;
  73     double *m_dEdgeLength2;
  74     double *m_dEdgeLength3;
  75
  76 #if USE_HEIGHT
  77     /* unused in our version of the code. we might need it at some
  78      * stage so keep it in here, but disable via USE_HEIGHT throughout
  79      * the code */
  80     double *m_dHeight;
  81     bool *m_bHasHeight;
  82 #endif
  83
  84     /**
  85      * leaf labels.
  86      * index range: 0 -- (m_uNodeCount+1)/2
  87      */
  88     char **m_ptrName;
  89
  90     /**
  91      * node id.
  92      * index range: 0 -- m_uNodeCount
  93      */
  94     uint *m_Ids;
  95
  96     bool m_bRooted; /**< tree is rooted */
  97     uint m_uRootNodeIndex;
  98 } tree_t;
  99
 100
 101 extern void
 102 MuscleTreeCreate(tree_t *tree, uint uLeafCount, uint uRoot, const uint *Left,
 103            const uint  *Right, const float *LeftLength, const float* RightLength,
 104            const uint *LeafIds, char **LeafNames);
 105
 106 extern void
 107 MuscleTreeToFile(FILE *fp, tree_t *tree);
 108
 109 extern int
 110 MuscleTreeFromFile(tree_t *tree, char *ftree);
 111
 112 extern void
 113 FreeMuscleTree(tree_t *tree);
 114
 115 extern void
 116 LogTree(tree_t *tree, FILE *fp);
 117
 118 extern bool
 119 IsRooted(tree_t *tree);
 120
 121 extern uint
 122 GetNodeCount(tree_t *tree);
 123
 124 extern uint
 125 GetLeafCount(tree_t *tree);
 126
 127 extern uint
 128 FirstDepthFirstNode(tree_t *tree);
 129
 130 extern uint
 131 NextDepthFirstNode(uint nodeindex, tree_t *tree);
 132
 133 extern bool
 134 IsLeaf(uint nodeindex, tree_t *tree);
 135
 136 extern void
 137 SetLeafId(tree_t *tree, uint uNodeIndex, uint uId);
 138
 139 extern uint
 140 GetLeafId(uint nodeindex, tree_t *tree);
 141
 142 extern char *
 143 GetLeafName(unsigned uNodeIndex, tree_t *tree);
 144
 145 extern uint
 146 GetLeft(uint nodeindex, tree_t *tree);
 147
 148 extern uint
 149 GetRight(uint nodeindex, tree_t *tree);
 150
 151 extern uint
 152 GetRootNodeIndex(tree_t *tree);
 153
 154 extern bool
 155 IsRoot(uint uNodeIndex, tree_t *tree);
 156
 157 extern uint
 158 GetParent(unsigned uNodeIndex, tree_t *tree);
 159
 160 extern double
 161 GetEdgeLength(uint uNodeIndex1, uint uNodeIndex2, tree_t *tree);
 162
 163 extern uint
 164 LeafIndexToNodeIndex(uint uLeafIndex, tree_t *prTree);
 165
 166 extern void
 167 AppendTree(tree_t *prDstTree,
 168           uint uDstTreeNodeIndex, tree_t *prSrcTree);
 169
 170 extern void
 171 TreeValidate(tree_t *tree);
 172
 173 #endif