1 /* This a mix of tree functions and data-structures from
2 * Bob Edgar's Muscle (version 3.7) ported to pure C.
4 * Used files: phy.cpp, tree.h, phytofile.cpp and phyfromclust.cpp
6 * Muscle's code is public domain and so is this code here.
8 * From http://www.drive5.com/muscle/license.htm:
10 * MUSCLE is public domain software
12 * The MUSCLE software, including object and source code and
13 * documentation, is hereby donated to the public domain.
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
24 * RCS $Id: muscle_tree.h 230 2011-04-09 15:37:50Z andreas $
28 #ifndef CLUSTALO_MUSCLE_CLUSTALO_TREE_H
29 #define CLUSTALO_MUSCLE_CLUSTALO_TREE_H
35 /* limit use of uint (see coding_style_guideline.txt) */
36 typedef unsigned int uint;
39 static const uint NULL_NEIGHBOR = UINT_MAX;
42 * @brief guide-tree structure
44 * @note We kept the original variable names here, to make it easy to
45 * search through Muscle's source code.
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)
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.
60 uint m_uNodeCount;/**< number of nodes */
61 uint m_uCacheCount;/**< reserved memory */
63 uint *m_uNeighbor1;/**< parent node */
64 uint *m_uNeighbor2;/**< left node */
65 uint *m_uNeighbor3;/**< right node */
67 /* do we have edge lengths info stored (m_dEdgeLength[123]) */
68 bool *m_bHasEdgeLength1;
69 bool *m_bHasEdgeLength2;
70 bool *m_bHasEdgeLength3;
72 double *m_dEdgeLength1;
73 double *m_dEdgeLength2;
74 double *m_dEdgeLength3;
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
86 * index range: 0 -- (m_uNodeCount+1)/2
92 * index range: 0 -- m_uNodeCount
96 bool m_bRooted; /**< tree is rooted */
97 uint m_uRootNodeIndex;
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);
107 MuscleTreeToFile(FILE *fp, tree_t *tree);
110 MuscleTreeFromFile(tree_t *tree, char *ftree);
113 FreeMuscleTree(tree_t *tree);
116 LogTree(tree_t *tree, FILE *fp);
119 IsRooted(tree_t *tree);
122 GetNodeCount(tree_t *tree);
125 GetLeafCount(tree_t *tree);
128 FirstDepthFirstNode(tree_t *tree);
131 NextDepthFirstNode(uint nodeindex, tree_t *tree);
134 IsLeaf(uint nodeindex, tree_t *tree);
137 SetLeafId(tree_t *tree, uint uNodeIndex, uint uId);
140 GetLeafId(uint nodeindex, tree_t *tree);
143 GetLeafName(unsigned uNodeIndex, tree_t *tree);
146 GetLeft(uint nodeindex, tree_t *tree);
149 GetRight(uint nodeindex, tree_t *tree);
152 GetRootNodeIndex(tree_t *tree);
155 IsRoot(uint uNodeIndex, tree_t *tree);
158 GetParent(unsigned uNodeIndex, tree_t *tree);
161 GetEdgeLength(uint uNodeIndex1, uint uNodeIndex2, tree_t *tree);
164 LeafIndexToNodeIndex(uint uLeafIndex, tree_t *prTree);
167 AppendTree(tree_t *prDstTree,
168 uint uDstTreeNodeIndex, tree_t *prSrcTree);
171 TreeValidate(tree_t *tree);