source: trunk/GDE/MUSCLE/src/tree.h

Last change on this file was 10390, checked in by aboeckma, 11 years ago

added muscle sourcles amd makefile
File size: 9.3 KB
Line 
1#ifndef tree_h
2#define tree_h
3
4#include <limits.h>
5
6class Clust;
7
8const unsigned NULL_NEIGHBOR = UINT_MAX;
9
10enum NEWICK_TOKEN_TYPE
11        {
12        NTT_Unknown,
13
14// Returned from Tree::GetToken:
15        NTT_Lparen,
16        NTT_Rparen,
17        NTT_Colon,
18        NTT_Comma,
19        NTT_Semicolon,
20        NTT_String,
21
22// Following are never returned from Tree::GetToken:
23        NTT_SingleQuotedString,
24        NTT_DoubleQuotedString,
25        NTT_Comment
26        };
27
28class Tree
29        {
30public:
31        Tree()
32                {
33                m_uNodeCount = 0;
34                m_uCacheCount = 0;
35                m_uNeighbor1 = 0;
36                m_uNeighbor2 = 0;
37                m_uNeighbor3 = 0;
38                m_dEdgeLength1 = 0;
39                m_dEdgeLength2 = 0;
40                m_dEdgeLength3 = 0;
41                m_dHeight = 0;
42                m_bHasEdgeLength1 = 0;
43                m_bHasEdgeLength2 = 0;
44                m_bHasEdgeLength3 = 0;
45                m_bHasHeight = 0;
46                m_ptrName = 0;
47                m_Ids = 0;
48                }
49        virtual ~Tree()
50                {
51                Clear();
52                }
53
54        void Clear()
55                {
56                for (unsigned n = 0; n < m_uNodeCount; ++n)
57                        free(m_ptrName[n]);
58
59                m_uNodeCount = 0;
60                m_uCacheCount = 0;
61
62                delete[] m_uNeighbor1;
63                delete[] m_uNeighbor2;
64                delete[] m_uNeighbor3;
65                delete[] m_dEdgeLength1;
66                delete[] m_dEdgeLength2;
67                delete[] m_dEdgeLength3;
68                delete[] m_bHasEdgeLength1;
69                delete[] m_bHasEdgeLength2;
70                delete[] m_bHasEdgeLength3;
71                delete[] m_ptrName;
72                delete[] m_Ids;
73                delete[] m_bHasHeight;
74                delete[] m_dHeight;
75
76                m_uNeighbor1 = 0;
77                m_uNeighbor2 = 0;
78                m_uNeighbor3 = 0;
79                m_dEdgeLength1 = 0;
80                m_dEdgeLength2 = 0;
81                m_dEdgeLength3 = 0;
82                m_ptrName = 0;
83                m_Ids = 0;
84                m_uRootNodeIndex = 0;
85                m_bHasHeight = 0;
86                m_dHeight = 0;
87
88                m_bRooted = false;
89                }
90
91// Creation and manipulation
92        void CreateRooted();
93        void CreateUnrooted(double dEdgeLength);
94
95        void FromFile(TextFile &File);
96        void FromClust(Clust &C);
97
98        void Copy(const Tree &tree);
99
100        void Create(unsigned uLeafCount, unsigned uRoot, const unsigned Left[],
101          const unsigned Right[], const float LeftLength[], const float RightLength[],
102          const unsigned LeafIds[], char *LeafNames[]);
103        unsigned AppendBranch(unsigned uExistingNodeIndex);
104        void SetLeafName(unsigned uNodeIndex, const char *ptrName);
105        void SetLeafId(unsigned uNodeIndex, unsigned uId);
106        void SetEdgeLength(unsigned uNodeIndex1, unsigned uNodeIndex2,
107          double dLength);
108
109        void RootUnrootedTree(unsigned uNodeIndex1, unsigned uNodeIndex2);
110        void RootUnrootedTree(ROOT Method);
111        void UnrootByDeletingRoot();
112
113// Saving to file
114        void ToFile(TextFile &File) const;
115
116// Accessor functions
117        unsigned GetNodeCount() const
118                {
119                return m_uNodeCount;
120                }
121
122        unsigned GetLeafCount() const
123                {
124                if (m_bRooted)
125                        {
126                        assert(m_uNodeCount%2 == 1);
127                        return (m_uNodeCount + 1)/2;
128                        }
129                else
130                        {
131                        assert(m_uNodeCount%2 == 0);
132                        return (m_uNodeCount + 2)/2;
133                        }
134                }
135
136        unsigned GetNeighbor(unsigned uNodeIndex, unsigned uNeighborSubscript) const;
137
138        unsigned GetNeighbor1(unsigned uNodeIndex) const
139                {
140                assert(uNodeIndex < m_uNodeCount);
141                return m_uNeighbor1[uNodeIndex];
142                }
143
144        unsigned GetNeighbor2(unsigned uNodeIndex) const
145                {
146                assert(uNodeIndex < m_uNodeCount);
147                return m_uNeighbor2[uNodeIndex];
148                }
149
150        unsigned GetNeighbor3(unsigned uNodeIndex) const
151                {
152                assert(uNodeIndex < m_uNodeCount);
153                return m_uNeighbor3[uNodeIndex];
154                }
155
156        unsigned GetParent(unsigned uNodeIndex) const
157                {
158                assert(m_bRooted && uNodeIndex < m_uNodeCount);
159                return m_uNeighbor1[uNodeIndex];
160                }
161
162        bool IsRooted() const
163                {
164                return m_bRooted;
165                }
166
167        unsigned GetLeft(unsigned uNodeIndex) const
168                {
169                assert(m_bRooted && uNodeIndex < m_uNodeCount);
170                return m_uNeighbor2[uNodeIndex];
171                }
172
173        unsigned GetRight(unsigned uNodeIndex) const
174                {
175                assert(m_bRooted && uNodeIndex < m_uNodeCount);
176                return m_uNeighbor3[uNodeIndex];
177                }
178
179        const char *GetName(unsigned uNodeIndex) const
180                {
181                assert(uNodeIndex < m_uNodeCount);
182                return m_ptrName[uNodeIndex];
183                }
184
185        unsigned GetRootNodeIndex() const
186                {
187                assert(m_bRooted);
188                return m_uRootNodeIndex;
189                }
190
191        unsigned GetNeighborCount(unsigned uNodeIndex) const
192                {
193                const unsigned n1 = m_uNeighbor1[uNodeIndex];
194                const unsigned n2 = m_uNeighbor2[uNodeIndex];
195                const unsigned n3 = m_uNeighbor3[uNodeIndex];
196                return (NULL_NEIGHBOR != n1) + (NULL_NEIGHBOR != n2) + (NULL_NEIGHBOR != n3);
197                }
198
199        bool IsLeaf(unsigned uNodeIndex) const
200                {
201                assert(uNodeIndex < m_uNodeCount);
202                if (1 == m_uNodeCount)
203                        return true;
204                return 1 == GetNeighborCount(uNodeIndex);
205                }
206
207        bool IsRoot(unsigned uNodeIndex) const
208                {
209                return IsRooted() && m_uRootNodeIndex == uNodeIndex;
210                }
211
212        unsigned GetLeafId(unsigned uNodeIndex) const;
213        unsigned GetLeafNodeIndex(const char *ptrName) const;
214        bool IsEdge(unsigned uNodeIndex1, unsigned uNodeIndex2) const;
215        bool HasEdgeLength(unsigned uNodeIndex1, unsigned uNodeIndex2) const;
216        double GetEdgeLength(unsigned uNodeIndex1, unsigned uNodeIndex2) const;
217        const char *GetLeafName(unsigned uNodeIndex) const;
218        unsigned GetNeighborSubscript(unsigned uNodeIndex, unsigned uNeighborIndex) const;
219        double GetNodeHeight(unsigned uNodeIndex) const;
220
221// Depth-first traversal
222        unsigned FirstDepthFirstNode() const;
223        unsigned NextDepthFirstNode(unsigned uNodeIndex) const;
224
225        unsigned FirstDepthFirstNodeR() const;
226        unsigned NextDepthFirstNodeR(unsigned uNodeIndex) const;
227
228// Equivalent of GetLeft/Right in unrooted tree, works in rooted tree too.
229        unsigned GetFirstNeighbor(unsigned uNodeIndex, unsigned uNeighborIndex) const;
230        unsigned GetSecondNeighbor(unsigned uNodeIndex, unsigned uNeighborIndex) const;
231
232// Getting parent node in unrooted tree defined iff leaf
233        unsigned GetLeafParent(unsigned uNodeIndex) const;
234
235// Misc
236        const char *NTTStr(NEWICK_TOKEN_TYPE NTT) const;
237        void FindCenterByLongestSpan(unsigned *ptrNodeIndex1,
238          unsigned *ptrNodeIndex2) const;
239        void PruneTree(const Tree &tree, unsigned Subfams[],
240          unsigned uSubfamCount);
241        unsigned LeafIndexToNodeIndex(unsigned uLeafIndex) const;
242
243// Debugging & trouble-shooting support
244        void Validate() const;
245        void ValidateNode(unsigned uNodeIndex) const;
246        void AssertAreNeighbors(unsigned uNodeIndex1, unsigned uNodeIndex2) const;
247        void LogMe() const;
248
249private:
250        unsigned UnrootFromFile();
251        NEWICK_TOKEN_TYPE GetTokenVerbose(TextFile &File, char szToken[],
252          unsigned uBytes) const
253                {
254                NEWICK_TOKEN_TYPE NTT = GetToken(File, szToken, uBytes);
255                Log("GetToken %10.10s  %s\n", NTTStr(NTT), szToken);
256                return NTT;
257                }
258
259        void InitCache(unsigned uCacheCount);
260        void ExpandCache();
261        NEWICK_TOKEN_TYPE GetToken(TextFile &File, char szToken[], unsigned uBytes) const;
262        bool GetGroupFromFile(TextFile &File, unsigned uNodeIndex, double *ptrdEdgeLength);
263        unsigned GetLeafCountUnrooted(unsigned uNodeIndex1, unsigned uNodeIndex2,
264          double *ptrdTotalDistance) const;
265        void ToFileNodeRooted(TextFile &File, unsigned uNodeIndex) const;
266        void ToFileNodeUnrooted(TextFile &File, unsigned uNodeIndex, unsigned uParent) const;
267        void OrientParent(unsigned uNodeIndex, unsigned uParentNodeIndex);
268        double FromClustNode(const Clust &C, unsigned uClustNodeIndex, unsigned uPhyNodeIndex);
269        unsigned GetAnyNonLeafNode() const;
270
271// Yuck. Data is made public for the convenience of Tree::Copy.
272// There has to be a better way.
273public:
274        unsigned m_uNodeCount;
275        unsigned m_uCacheCount;
276        unsigned *m_uNeighbor1;
277        unsigned *m_uNeighbor2;
278        unsigned *m_uNeighbor3;
279        double *m_dEdgeLength1;
280        double *m_dEdgeLength2;
281        double *m_dEdgeLength3;
282        double *m_dHeight;
283        bool *m_bHasEdgeLength1;
284        bool *m_bHasEdgeLength2;
285        bool *m_bHasEdgeLength3;
286        bool *m_bHasHeight;
287        unsigned *m_Ids;
288        char **m_ptrName;
289        bool m_bRooted;
290        unsigned m_uRootNodeIndex;
291        };
292
293struct PhyEnumEdgeState
294        {
295        PhyEnumEdgeState()
296                {
297                m_bInit = false;
298                m_uNodeIndex1 = NULL_NEIGHBOR;
299                m_uNodeIndex2 = NULL_NEIGHBOR;
300                }
301        bool m_bInit;
302        unsigned m_uNodeIndex1;
303        unsigned m_uNodeIndex2;
304        };
305
306const unsigned NODE_CHANGED = (unsigned) (~0);
307
308extern bool PhyEnumBiParts(const Tree &tree, PhyEnumEdgeState &ES,
309  unsigned Leaves1[], unsigned *ptruCount1,
310  unsigned Leaves2[], unsigned *ptruCount2);
311extern bool PhyEnumBiPartsR(const Tree &tree, PhyEnumEdgeState &ES,
312  unsigned Leaves1[], unsigned *ptruCount1,
313  unsigned Leaves2[], unsigned *ptruCount2);
314extern void ClusterByHeight(const Tree &tree, double dMaxHeight, unsigned Subtrees[],
315  unsigned *ptruSubtreeCount);
316void ClusterBySubfamCount(const Tree &tree, unsigned uSubfamCount,
317  unsigned Subfams[], unsigned *ptruSubfamCount);
318void GetLeaves(const Tree &tree, unsigned uNodeIndex, unsigned Leaves[],
319  unsigned *ptruLeafCount);
320void GetLeavesExcluding(const Tree &tree, unsigned uNodeIndex,
321  unsigned uExclude, unsigned Leaves[], unsigned *ptruCount);
322void GetInternalNodesInHeightOrder(const Tree &tree, unsigned NodeIndexes[]);
323void ApplyMinEdgeLength(Tree &tree, double dMinEdgeLength);
324void LeafIndexesToLeafNames(const Tree &tree, const unsigned Leaves[], unsigned uCount,
325 char *Names[]);
326void LeafIndexesToIds(const Tree &tree, const unsigned Leaves[], unsigned uCount,
327 unsigned Ids[]);
328void MSASeqSubset(const MSA &msaIn, char *Names[], unsigned uSeqCount,
329  MSA &msaOut);
330void DiffTrees(const Tree &Tree1, const Tree &Tree2, Tree &Diffs,
331  unsigned IdToDiffsLeafNodeIndex[]);
332void DiffTreesE(const Tree &NewTree, const Tree &OldTree,
333  unsigned NewNodeIndexToOldNodeIndex[]);
334void FindRoot(const Tree &tree, unsigned *ptruNode1, unsigned *ptruNode2,
335  double *ptrdLength1, double *ptrdLength2,
336  ROOT RootMethod);
337void FixRoot(Tree &tree, ROOT RootMethod);
338
339#endif // tree_h
Note: See TracBrowser for help on using the repository browser.