+++ /dev/null
-#include "muscle.h"\r
-#include "tree.h"\r
-#include <math.h>\r
-\r
-#define TRACE 0\r
-\r
-/***\r
-Node has 0 to 3 neighbors:\r
- 0 neighbors: singleton root\r
- 1 neighbor: leaf, neighbor is parent\r
- 2 neigbors: non-singleton root\r
- 3 neighbors: internal node (other than root)\r
-\r
-Minimal rooted tree is single node.\r
-Minimal unrooted tree is single edge.\r
-Leaf node always has nulls in neighbors 2 and 3, neighbor 1 is parent.\r
-When tree is rooted, neighbor 1=parent, 2=left, 3=right.\r
-***/\r
-\r
-void Tree::AssertAreNeighbors(unsigned uNodeIndex1, unsigned uNodeIndex2) const\r
- {\r
- if (uNodeIndex1 >= m_uNodeCount || uNodeIndex2 >= m_uNodeCount)\r
- Quit("AssertAreNeighbors(%u,%u), are %u nodes",\r
- uNodeIndex1, uNodeIndex2, m_uNodeCount);\r
-\r
- if (m_uNeighbor1[uNodeIndex1] != uNodeIndex2 &&\r
- m_uNeighbor2[uNodeIndex1] != uNodeIndex2 &&\r
- m_uNeighbor3[uNodeIndex1] != uNodeIndex2)\r
- {\r
- LogMe();\r
- Quit("AssertAreNeighbors(%u,%u) failed", uNodeIndex1, uNodeIndex2);\r
- }\r
-\r
- if (m_uNeighbor1[uNodeIndex2] != uNodeIndex1 &&\r
- m_uNeighbor2[uNodeIndex2] != uNodeIndex1 &&\r
- m_uNeighbor3[uNodeIndex2] != uNodeIndex1)\r
- {\r
- LogMe();\r
- Quit("AssertAreNeighbors(%u,%u) failed", uNodeIndex1, uNodeIndex2);\r
- }\r
-\r
- bool Has12 = HasEdgeLength(uNodeIndex1, uNodeIndex2);\r
- bool Has21 = HasEdgeLength(uNodeIndex2, uNodeIndex1);\r
- if (Has12 != Has21)\r
- {\r
- HasEdgeLength(uNodeIndex1, uNodeIndex2);\r
- HasEdgeLength(uNodeIndex2, uNodeIndex1);\r
- LogMe();\r
- Log("HasEdgeLength(%u, %u)=%c HasEdgeLength(%u, %u)=%c\n",\r
- uNodeIndex1,\r
- uNodeIndex2,\r
- Has12 ? 'T' : 'F',\r
- uNodeIndex2,\r
- uNodeIndex1,\r
- Has21 ? 'T' : 'F');\r
-\r
- Quit("Tree::AssertAreNeighbors, HasEdgeLength not symmetric");\r
- }\r
-\r
- if (Has12)\r
- {\r
- double d12 = GetEdgeLength(uNodeIndex1, uNodeIndex2);\r
- double d21 = GetEdgeLength(uNodeIndex2, uNodeIndex1);\r
- if (d12 != d21)\r
- {\r
- LogMe();\r
- Quit("Tree::AssertAreNeighbors, Edge length disagrees %u-%u=%.3g, %u-%u=%.3g",\r
- uNodeIndex1, uNodeIndex2, d12,\r
- uNodeIndex2, uNodeIndex1, d21);\r
- }\r
- }\r
- }\r
-\r
-void Tree::ValidateNode(unsigned uNodeIndex) const\r
- {\r
- if (uNodeIndex >= m_uNodeCount)\r
- Quit("ValidateNode(%u), %u nodes", uNodeIndex, m_uNodeCount);\r
-\r
- const unsigned uNeighborCount = GetNeighborCount(uNodeIndex);\r
-\r
- if (2 == uNeighborCount)\r
- {\r
- if (!m_bRooted)\r
- {\r
- LogMe();\r
- Quit("Tree::ValidateNode: Node %u has two neighbors, tree is not rooted",\r
- uNodeIndex);\r
- }\r
- if (uNodeIndex != m_uRootNodeIndex)\r
- {\r
- LogMe();\r
- Quit("Tree::ValidateNode: Node %u has two neighbors, but not root node=%u",\r
- uNodeIndex, m_uRootNodeIndex);\r
- }\r
- }\r
-\r
- const unsigned n1 = m_uNeighbor1[uNodeIndex];\r
- const unsigned n2 = m_uNeighbor2[uNodeIndex];\r
- const unsigned n3 = m_uNeighbor3[uNodeIndex];\r
-\r
- if (NULL_NEIGHBOR == n2 && NULL_NEIGHBOR != n3)\r
- {\r
- LogMe();\r
- Quit("Tree::ValidateNode, n2=null, n3!=null", uNodeIndex);\r
- }\r
- if (NULL_NEIGHBOR == n3 && NULL_NEIGHBOR != n2)\r
- {\r
- LogMe();\r
- Quit("Tree::ValidateNode, n3=null, n2!=null", uNodeIndex);\r
- }\r
-\r
- if (n1 != NULL_NEIGHBOR)\r
- AssertAreNeighbors(uNodeIndex, n1);\r
- if (n2 != NULL_NEIGHBOR)\r
- AssertAreNeighbors(uNodeIndex, n2);\r
- if (n3 != NULL_NEIGHBOR)\r
- AssertAreNeighbors(uNodeIndex, n3);\r
-\r
- if (n1 != NULL_NEIGHBOR && (n1 == n2 || n1 == n3))\r
- {\r
- LogMe();\r
- Quit("Tree::ValidateNode, duplicate neighbors in node %u", uNodeIndex);\r
- }\r
- if (n2 != NULL_NEIGHBOR && (n2 == n1 || n2 == n3))\r
- {\r
- LogMe();\r
- Quit("Tree::ValidateNode, duplicate neighbors in node %u", uNodeIndex);\r
- }\r
- if (n3 != NULL_NEIGHBOR && (n3 == n1 || n3 == n2))\r
- {\r
- LogMe();\r
- Quit("Tree::ValidateNode, duplicate neighbors in node %u", uNodeIndex);\r
- }\r
-\r
- if (IsRooted())\r
- {\r
- if (NULL_NEIGHBOR == GetParent(uNodeIndex))\r
- {\r
- if (uNodeIndex != m_uRootNodeIndex)\r
- {\r
- LogMe();\r
- Quit("Tree::ValiateNode(%u), no parent", uNodeIndex);\r
- }\r
- }\r
- else if (GetLeft(GetParent(uNodeIndex)) != uNodeIndex &&\r
- GetRight(GetParent(uNodeIndex)) != uNodeIndex)\r
- {\r
- LogMe();\r
- Quit("Tree::ValidateNode(%u), parent / child mismatch", uNodeIndex);\r
- }\r
- }\r
- }\r
-\r
-void Tree::Validate() const\r
- {\r
- for (unsigned uNodeIndex = 0; uNodeIndex < m_uNodeCount; ++uNodeIndex)\r
- ValidateNode(uNodeIndex);\r
- }\r
-\r
-bool Tree::IsEdge(unsigned uNodeIndex1, unsigned uNodeIndex2) const\r
- {\r
- assert(uNodeIndex1 < m_uNodeCount && uNodeIndex2 < m_uNodeCount);\r
-\r
- return m_uNeighbor1[uNodeIndex1] == uNodeIndex2 ||\r
- m_uNeighbor2[uNodeIndex1] == uNodeIndex2 ||\r
- m_uNeighbor3[uNodeIndex1] == uNodeIndex2;\r
- }\r
-\r
-double Tree::GetEdgeLength(unsigned uNodeIndex1, unsigned uNodeIndex2) const\r
- {\r
- assert(uNodeIndex1 < m_uNodeCount && uNodeIndex2 < m_uNodeCount);\r
- if (!HasEdgeLength(uNodeIndex1, uNodeIndex2))\r
- {\r
- LogMe();\r
- Quit("Missing edge length in tree %u-%u", uNodeIndex1, uNodeIndex2);\r
- }\r
-\r
- if (m_uNeighbor1[uNodeIndex1] == uNodeIndex2)\r
- return m_dEdgeLength1[uNodeIndex1];\r
- else if (m_uNeighbor2[uNodeIndex1] == uNodeIndex2)\r
- return m_dEdgeLength2[uNodeIndex1];\r
- assert(m_uNeighbor3[uNodeIndex1] == uNodeIndex2);\r
- return m_dEdgeLength3[uNodeIndex1];\r
- }\r
-\r
-void Tree::ExpandCache()\r
- {\r
- const unsigned uNodeCount = 100;\r
- unsigned uNewCacheCount = m_uCacheCount + uNodeCount;\r
- unsigned *uNewNeighbor1 = new unsigned[uNewCacheCount];\r
- unsigned *uNewNeighbor2 = new unsigned[uNewCacheCount];\r
- unsigned *uNewNeighbor3 = new unsigned[uNewCacheCount];\r
-\r
- unsigned *uNewIds = new unsigned[uNewCacheCount];\r
- memset(uNewIds, 0xff, uNewCacheCount*sizeof(unsigned));\r
-\r
- double *dNewEdgeLength1 = new double[uNewCacheCount];\r
- double *dNewEdgeLength2 = new double[uNewCacheCount];\r
- double *dNewEdgeLength3 = new double[uNewCacheCount];\r
- double *dNewHeight = new double[uNewCacheCount];\r
-\r
- bool *bNewHasEdgeLength1 = new bool[uNewCacheCount];\r
- bool *bNewHasEdgeLength2 = new bool[uNewCacheCount];\r
- bool *bNewHasEdgeLength3 = new bool[uNewCacheCount];\r
- bool *bNewHasHeight = new bool[uNewCacheCount];\r
-\r
- char **ptrNewName = new char *[uNewCacheCount];\r
- memset(ptrNewName, 0, uNewCacheCount*sizeof(char *));\r
-\r
- if (m_uCacheCount > 0)\r
- {\r
- const unsigned uUnsignedBytes = m_uCacheCount*sizeof(unsigned);\r
- memcpy(uNewNeighbor1, m_uNeighbor1, uUnsignedBytes);\r
- memcpy(uNewNeighbor2, m_uNeighbor2, uUnsignedBytes);\r
- memcpy(uNewNeighbor3, m_uNeighbor3, uUnsignedBytes);\r
-\r
- memcpy(uNewIds, m_Ids, uUnsignedBytes);\r
-\r
- const unsigned uEdgeBytes = m_uCacheCount*sizeof(double);\r
- memcpy(dNewEdgeLength1, m_dEdgeLength1, uEdgeBytes);\r
- memcpy(dNewEdgeLength2, m_dEdgeLength2, uEdgeBytes);\r
- memcpy(dNewEdgeLength3, m_dEdgeLength3, uEdgeBytes);\r
- memcpy(dNewHeight, m_dHeight, uEdgeBytes);\r
-\r
- const unsigned uBoolBytes = m_uCacheCount*sizeof(bool);\r
- memcpy(bNewHasEdgeLength1, m_bHasEdgeLength1, uBoolBytes);\r
- memcpy(bNewHasEdgeLength2, m_bHasEdgeLength2, uBoolBytes);\r
- memcpy(bNewHasEdgeLength3, m_bHasEdgeLength3, uBoolBytes);\r
- memcpy(bNewHasHeight, m_bHasHeight, uBoolBytes);\r
-\r
- const unsigned uNameBytes = m_uCacheCount*sizeof(char *);\r
- memcpy(ptrNewName, m_ptrName, uNameBytes);\r
-\r
- delete[] m_uNeighbor1;\r
- delete[] m_uNeighbor2;\r
- delete[] m_uNeighbor3;\r
-\r
- delete[] m_Ids;\r
-\r
- delete[] m_dEdgeLength1;\r
- delete[] m_dEdgeLength2;\r
- delete[] m_dEdgeLength3;\r
-\r
- delete[] m_bHasEdgeLength1;\r
- delete[] m_bHasEdgeLength2;\r
- delete[] m_bHasEdgeLength3;\r
- delete[] m_bHasHeight;\r
-\r
- delete[] m_ptrName;\r
- }\r
- m_uCacheCount = uNewCacheCount;\r
- m_uNeighbor1 = uNewNeighbor1;\r
- m_uNeighbor2 = uNewNeighbor2;\r
- m_uNeighbor3 = uNewNeighbor3;\r
- m_Ids = uNewIds;\r
- m_dEdgeLength1 = dNewEdgeLength1;\r
- m_dEdgeLength2 = dNewEdgeLength2;\r
- m_dEdgeLength3 = dNewEdgeLength3;\r
- m_dHeight = dNewHeight;\r
- m_bHasEdgeLength1 = bNewHasEdgeLength1;\r
- m_bHasEdgeLength2 = bNewHasEdgeLength2;\r
- m_bHasEdgeLength3 = bNewHasEdgeLength3;\r
- m_bHasHeight = bNewHasHeight;\r
- m_ptrName = ptrNewName;\r
- }\r
-\r
-// Creates tree with single node, no edges.\r
-// Root node always has index 0.\r
-void Tree::CreateRooted()\r
- {\r
- Clear();\r
- ExpandCache();\r
- m_uNodeCount = 1;\r
-\r
- m_uNeighbor1[0] = NULL_NEIGHBOR;\r
- m_uNeighbor2[0] = NULL_NEIGHBOR;\r
- m_uNeighbor3[0] = NULL_NEIGHBOR;\r
-\r
- m_bHasEdgeLength1[0] = false;\r
- m_bHasEdgeLength2[0] = false;\r
- m_bHasEdgeLength3[0] = false;\r
- m_bHasHeight[0] = false;\r
-\r
- m_uRootNodeIndex = 0;\r
- m_bRooted = true;\r
-\r
-#if DEBUG\r
- Validate();\r
-#endif\r
- }\r
-\r
-// Creates unrooted tree with single edge.\r
-// Nodes for that edge are always 0 and 1.\r
-void Tree::CreateUnrooted(double dEdgeLength)\r
- {\r
- Clear();\r
- ExpandCache();\r
-\r
- m_uNeighbor1[0] = 1;\r
- m_uNeighbor2[0] = NULL_NEIGHBOR;\r
- m_uNeighbor3[0] = NULL_NEIGHBOR;\r
-\r
- m_uNeighbor1[1] = 0;\r
- m_uNeighbor2[1] = NULL_NEIGHBOR;\r
- m_uNeighbor3[1] = NULL_NEIGHBOR;\r
-\r
- m_dEdgeLength1[0] = dEdgeLength;\r
- m_dEdgeLength1[1] = dEdgeLength;\r
-\r
- m_bHasEdgeLength1[0] = true;\r
- m_bHasEdgeLength1[1] = true;\r
-\r
- m_bRooted = false;\r
-\r
-#if DEBUG\r
- Validate();\r
-#endif\r
- }\r
-\r
-void Tree::SetLeafName(unsigned uNodeIndex, const char *ptrName)\r
- {\r
- assert(uNodeIndex < m_uNodeCount);\r
- assert(IsLeaf(uNodeIndex));\r
- free(m_ptrName[uNodeIndex]);\r
- m_ptrName[uNodeIndex] = strsave(ptrName);\r
- }\r
-\r
-void Tree::SetLeafId(unsigned uNodeIndex, unsigned uId)\r
- {\r
- assert(uNodeIndex < m_uNodeCount);\r
- assert(IsLeaf(uNodeIndex));\r
- m_Ids[uNodeIndex] = uId;\r
- }\r
-\r
-const char *Tree::GetLeafName(unsigned uNodeIndex) const\r
- {\r
- assert(uNodeIndex < m_uNodeCount);\r
- assert(IsLeaf(uNodeIndex));\r
- return m_ptrName[uNodeIndex];\r
- }\r
-\r
-unsigned Tree::GetLeafId(unsigned uNodeIndex) const\r
- {\r
- assert(uNodeIndex < m_uNodeCount);\r
- assert(IsLeaf(uNodeIndex));\r
- return m_Ids[uNodeIndex];\r
- }\r
-\r
-// Append a new branch.\r
-// This adds two new nodes and joins them to an existing leaf node.\r
-// Return value is k, new nodes have indexes k and k+1 respectively.\r
-unsigned Tree::AppendBranch(unsigned uExistingLeafIndex)\r
- {\r
- if (0 == m_uNodeCount)\r
- Quit("Tree::AppendBranch: tree has not been created");\r
-\r
-#if DEBUG\r
- assert(uExistingLeafIndex < m_uNodeCount);\r
- if (!IsLeaf(uExistingLeafIndex))\r
- {\r
- LogMe();\r
- Quit("AppendBranch(%u): not leaf", uExistingLeafIndex);\r
- }\r
-#endif\r
-\r
- if (m_uNodeCount >= m_uCacheCount - 2)\r
- ExpandCache();\r
-\r
- const unsigned uNewLeaf1 = m_uNodeCount;\r
- const unsigned uNewLeaf2 = m_uNodeCount + 1;\r
-\r
- m_uNodeCount += 2;\r
-\r
- assert(m_uNeighbor2[uExistingLeafIndex] == NULL_NEIGHBOR);\r
- assert(m_uNeighbor3[uExistingLeafIndex] == NULL_NEIGHBOR);\r
-\r
- m_uNeighbor2[uExistingLeafIndex] = uNewLeaf1;\r
- m_uNeighbor3[uExistingLeafIndex] = uNewLeaf2;\r
-\r
- m_uNeighbor1[uNewLeaf1] = uExistingLeafIndex;\r
- m_uNeighbor1[uNewLeaf2] = uExistingLeafIndex;\r
-\r
- m_uNeighbor2[uNewLeaf1] = NULL_NEIGHBOR;\r
- m_uNeighbor2[uNewLeaf2] = NULL_NEIGHBOR;\r
-\r
- m_uNeighbor3[uNewLeaf1] = NULL_NEIGHBOR;\r
- m_uNeighbor3[uNewLeaf2] = NULL_NEIGHBOR;\r
-\r
- m_dEdgeLength2[uExistingLeafIndex] = 0;\r
- m_dEdgeLength3[uExistingLeafIndex] = 0;\r
-\r
- m_dEdgeLength1[uNewLeaf1] = 0;\r
- m_dEdgeLength2[uNewLeaf1] = 0;\r
- m_dEdgeLength3[uNewLeaf1] = 0;\r
-\r
- m_dEdgeLength1[uNewLeaf2] = 0;\r
- m_dEdgeLength2[uNewLeaf2] = 0;\r
- m_dEdgeLength3[uNewLeaf2] = 0;\r
-\r
- m_bHasEdgeLength1[uNewLeaf1] = false;\r
- m_bHasEdgeLength2[uNewLeaf1] = false;\r
- m_bHasEdgeLength3[uNewLeaf1] = false;\r
-\r
- m_bHasEdgeLength1[uNewLeaf2] = false;\r
- m_bHasEdgeLength2[uNewLeaf2] = false;\r
- m_bHasEdgeLength3[uNewLeaf2] = false;\r
-\r
- m_bHasHeight[uNewLeaf1] = false;\r
- m_bHasHeight[uNewLeaf2] = false;\r
-\r
- m_Ids[uNewLeaf1] = uInsane;\r
- m_Ids[uNewLeaf2] = uInsane;\r
- return uNewLeaf1;\r
- }\r
-\r
-void Tree::LogMe() const\r
- {\r
- Log("Tree::LogMe %u nodes, ", m_uNodeCount);\r
-\r
- if (IsRooted())\r
- {\r
- Log("rooted.\n");\r
- Log("\n");\r
- Log("Index Parnt LengthP Left LengthL Right LengthR Id Name\n");\r
- Log("----- ----- ------- ---- ------- ----- ------- ----- ----\n");\r
- }\r
- else\r
- {\r
- Log("unrooted.\n");\r
- Log("\n");\r
- Log("Index Nbr_1 Length1 Nbr_2 Length2 Nbr_3 Length3 Id Name\n");\r
- Log("----- ----- ------- ----- ------- ----- ------- ----- ----\n");\r
- }\r
-\r
- for (unsigned uNodeIndex = 0; uNodeIndex < m_uNodeCount; ++uNodeIndex)\r
- {\r
- Log("%5u ", uNodeIndex);\r
- const unsigned n1 = m_uNeighbor1[uNodeIndex];\r
- const unsigned n2 = m_uNeighbor2[uNodeIndex];\r
- const unsigned n3 = m_uNeighbor3[uNodeIndex];\r
- if (NULL_NEIGHBOR != n1)\r
- {\r
- Log("%5u ", n1);\r
- if (m_bHasEdgeLength1[uNodeIndex])\r
- Log("%7.4f ", m_dEdgeLength1[uNodeIndex]);\r
- else\r
- Log(" * ");\r
- }\r
- else\r
- Log(" ");\r
-\r
- if (NULL_NEIGHBOR != n2)\r
- {\r
- Log("%5u ", n2);\r
- if (m_bHasEdgeLength2[uNodeIndex])\r
- Log("%7.4f ", m_dEdgeLength2[uNodeIndex]);\r
- else\r
- Log(" * ");\r
- }\r
- else\r
- Log(" ");\r
-\r
- if (NULL_NEIGHBOR != n3)\r
- {\r
- Log("%5u ", n3);\r
- if (m_bHasEdgeLength3[uNodeIndex])\r
- Log("%7.4f ", m_dEdgeLength3[uNodeIndex]);\r
- else\r
- Log(" * ");\r
- }\r
- else\r
- Log(" ");\r
-\r
- if (m_Ids != 0 && IsLeaf(uNodeIndex))\r
- {\r
- unsigned uId = m_Ids[uNodeIndex];\r
- if (uId == uInsane)\r
- Log(" *");\r
- else\r
- Log("%5u", uId);\r
- }\r
- else\r
- Log(" ");\r
-\r
- if (m_bRooted && uNodeIndex == m_uRootNodeIndex)\r
- Log(" [ROOT] ");\r
- const char *ptrName = m_ptrName[uNodeIndex];\r
- if (ptrName != 0)\r
- Log(" %s", ptrName);\r
- Log("\n");\r
- }\r
- }\r
-\r
-void Tree::SetEdgeLength(unsigned uNodeIndex1, unsigned uNodeIndex2,\r
- double dLength)\r
- {\r
- assert(uNodeIndex1 < m_uNodeCount && uNodeIndex2 < m_uNodeCount);\r
- assert(IsEdge(uNodeIndex1, uNodeIndex2));\r
-\r
- if (m_uNeighbor1[uNodeIndex1] == uNodeIndex2)\r
- {\r
- m_dEdgeLength1[uNodeIndex1] = dLength;\r
- m_bHasEdgeLength1[uNodeIndex1] = true;\r
- }\r
- else if (m_uNeighbor2[uNodeIndex1] == uNodeIndex2)\r
- {\r
- m_dEdgeLength2[uNodeIndex1] = dLength;\r
- m_bHasEdgeLength2[uNodeIndex1] = true;\r
-\r
- }\r
- else\r
- {\r
- assert(m_uNeighbor3[uNodeIndex1] == uNodeIndex2);\r
- m_dEdgeLength3[uNodeIndex1] = dLength;\r
- m_bHasEdgeLength3[uNodeIndex1] = true;\r
- }\r
-\r
- if (m_uNeighbor1[uNodeIndex2] == uNodeIndex1)\r
- {\r
- m_dEdgeLength1[uNodeIndex2] = dLength;\r
- m_bHasEdgeLength1[uNodeIndex2] = true;\r
- }\r
- else if (m_uNeighbor2[uNodeIndex2] == uNodeIndex1)\r
- {\r
- m_dEdgeLength2[uNodeIndex2] = dLength;\r
- m_bHasEdgeLength2[uNodeIndex2] = true;\r
- }\r
- else\r
- {\r
- assert(m_uNeighbor3[uNodeIndex2] == uNodeIndex1);\r
- m_dEdgeLength3[uNodeIndex2] = dLength;\r
- m_bHasEdgeLength3[uNodeIndex2] = true;\r
- }\r
- }\r
-\r
-unsigned Tree::UnrootFromFile()\r
- {\r
-#if TRACE\r
- Log("Before unroot:\n");\r
- LogMe();\r
-#endif\r
-\r
- if (!m_bRooted)\r
- Quit("Tree::Unroot, not rooted");\r
-\r
-// Convention: root node is always node zero\r
- assert(IsRoot(0));\r
- assert(NULL_NEIGHBOR == m_uNeighbor1[0]);\r
-\r
- const unsigned uThirdNode = m_uNodeCount++;\r
-\r
- m_uNeighbor1[0] = uThirdNode;\r
- m_uNeighbor1[uThirdNode] = 0;\r
-\r
- m_uNeighbor2[uThirdNode] = NULL_NEIGHBOR;\r
- m_uNeighbor3[uThirdNode] = NULL_NEIGHBOR;\r
-\r
- m_dEdgeLength1[0] = 0;\r
- m_dEdgeLength1[uThirdNode] = 0;\r
- m_bHasEdgeLength1[uThirdNode] = true;\r
-\r
- m_bRooted = false;\r
-\r
-#if TRACE\r
- Log("After unroot:\n");\r
- LogMe();\r
-#endif\r
-\r
- return uThirdNode;\r
- }\r
-\r
-// In an unrooted tree, equivalent of GetLeft/Right is \r
-// GetFirst/SecondNeighbor.\r
-// uNeighborIndex must be a known neighbor of uNodeIndex.\r
-// This is the way to find the other two neighbor nodes of\r
-// an internal node.\r
-// The labeling as "First" and "Second" neighbor is arbitrary.\r
-// Calling these functions on a leaf returns NULL_NEIGHBOR, as\r
-// for GetLeft/Right.\r
-unsigned Tree::GetFirstNeighbor(unsigned uNodeIndex, unsigned uNeighborIndex) const\r
- {\r
- assert(uNodeIndex < m_uNodeCount);\r
- assert(uNeighborIndex < m_uNodeCount);\r
- assert(IsEdge(uNodeIndex, uNeighborIndex));\r
-\r
- for (unsigned n = 0; n < 3; ++n)\r
- {\r
- unsigned uNeighbor = GetNeighbor(uNodeIndex, n);\r
- if (NULL_NEIGHBOR != uNeighbor && uNeighborIndex != uNeighbor)\r
- return uNeighbor;\r
- }\r
- return NULL_NEIGHBOR;\r
- }\r
-\r
-unsigned Tree::GetSecondNeighbor(unsigned uNodeIndex, unsigned uNeighborIndex) const\r
- {\r
- assert(uNodeIndex < m_uNodeCount);\r
- assert(uNeighborIndex < m_uNodeCount);\r
- assert(IsEdge(uNodeIndex, uNeighborIndex));\r
-\r
- bool bFoundOne = false;\r
- for (unsigned n = 0; n < 3; ++n)\r
- {\r
- unsigned uNeighbor = GetNeighbor(uNodeIndex, n);\r
- if (NULL_NEIGHBOR != uNeighbor && uNeighborIndex != uNeighbor)\r
- {\r
- if (bFoundOne)\r
- return uNeighbor;\r
- else\r
- bFoundOne = true;\r
- }\r
- }\r
- return NULL_NEIGHBOR;\r
- }\r
-\r
-// Compute the number of leaves in the sub-tree defined by an edge\r
-// in an unrooted tree. Conceptually, the tree is cut at this edge,\r
-// and uNodeIndex2 considered the root of the sub-tree.\r
-unsigned Tree::GetLeafCountUnrooted(unsigned uNodeIndex1, unsigned uNodeIndex2,\r
- double *ptrdTotalDistance) const\r
- {\r
- assert(!IsRooted());\r
-\r
- if (IsLeaf(uNodeIndex2))\r
- {\r
- *ptrdTotalDistance = GetEdgeLength(uNodeIndex1, uNodeIndex2);\r
- return 1;\r
- }\r
-\r
-// Recurse down the rooted sub-tree defined by cutting the edge\r
-// and considering uNodeIndex2 as the root.\r
- const unsigned uLeft = GetFirstNeighbor(uNodeIndex2, uNodeIndex1);\r
- const unsigned uRight = GetSecondNeighbor(uNodeIndex2, uNodeIndex1);\r
-\r
- double dLeftDistance;\r
- double dRightDistance;\r
-\r
- const unsigned uLeftCount = GetLeafCountUnrooted(uNodeIndex2, uLeft,\r
- &dLeftDistance);\r
- const unsigned uRightCount = GetLeafCountUnrooted(uNodeIndex2, uRight,\r
- &dRightDistance);\r
-\r
- *ptrdTotalDistance = dLeftDistance + dRightDistance;\r
- return uLeftCount + uRightCount;\r
- }\r
-\r
-void Tree::RootUnrootedTree(ROOT Method)\r
- {\r
- assert(!IsRooted());\r
-#if TRACE\r
- Log("Tree::RootUnrootedTree, before:");\r
- LogMe();\r
-#endif\r
-\r
- unsigned uNode1;\r
- unsigned uNode2;\r
- double dLength1;\r
- double dLength2;\r
- FindRoot(*this, &uNode1, &uNode2, &dLength1, &dLength2, Method);\r
-\r
- if (m_uNodeCount == m_uCacheCount)\r
- ExpandCache();\r
- m_uRootNodeIndex = m_uNodeCount++;\r
-\r
- double dEdgeLength = GetEdgeLength(uNode1, uNode2);\r
-\r
- m_uNeighbor1[m_uRootNodeIndex] = NULL_NEIGHBOR;\r
- m_uNeighbor2[m_uRootNodeIndex] = uNode1;\r
- m_uNeighbor3[m_uRootNodeIndex] = uNode2;\r
-\r
- if (m_uNeighbor1[uNode1] == uNode2)\r
- m_uNeighbor1[uNode1] = m_uRootNodeIndex;\r
- else if (m_uNeighbor2[uNode1] == uNode2)\r
- m_uNeighbor2[uNode1] = m_uRootNodeIndex;\r
- else\r
- {\r
- assert(m_uNeighbor3[uNode1] == uNode2);\r
- m_uNeighbor3[uNode1] = m_uRootNodeIndex;\r
- }\r
-\r
- if (m_uNeighbor1[uNode2] == uNode1)\r
- m_uNeighbor1[uNode2] = m_uRootNodeIndex;\r
- else if (m_uNeighbor2[uNode2] == uNode1)\r
- m_uNeighbor2[uNode2] = m_uRootNodeIndex;\r
- else\r
- {\r
- assert(m_uNeighbor3[uNode2] == uNode1);\r
- m_uNeighbor3[uNode2] = m_uRootNodeIndex;\r
- }\r
-\r
- OrientParent(uNode1, m_uRootNodeIndex);\r
- OrientParent(uNode2, m_uRootNodeIndex);\r
-\r
- SetEdgeLength(m_uRootNodeIndex, uNode1, dLength1);\r
- SetEdgeLength(m_uRootNodeIndex, uNode2, dLength2);\r
-\r
- m_bHasHeight[m_uRootNodeIndex] = false;\r
-\r
- m_ptrName[m_uRootNodeIndex] = 0;\r
-\r
- m_bRooted = true;\r
-\r
-#if TRACE\r
- Log("\nPhy::RootUnrootedTree, after:");\r
- LogMe();\r
-#endif\r
-\r
- Validate();\r
- }\r
-\r
-bool Tree::HasEdgeLength(unsigned uNodeIndex1, unsigned uNodeIndex2) const\r
- {\r
- assert(uNodeIndex1 < m_uNodeCount);\r
- assert(uNodeIndex2 < m_uNodeCount);\r
- assert(IsEdge(uNodeIndex1, uNodeIndex2));\r
-\r
- if (m_uNeighbor1[uNodeIndex1] == uNodeIndex2)\r
- return m_bHasEdgeLength1[uNodeIndex1];\r
- else if (m_uNeighbor2[uNodeIndex1] == uNodeIndex2)\r
- return m_bHasEdgeLength2[uNodeIndex1];\r
- assert(m_uNeighbor3[uNodeIndex1] == uNodeIndex2);\r
- return m_bHasEdgeLength3[uNodeIndex1];\r
- }\r
-\r
-void Tree::OrientParent(unsigned uNodeIndex, unsigned uParentNodeIndex)\r
- {\r
- if (NULL_NEIGHBOR == uNodeIndex)\r
- return;\r
-\r
- if (m_uNeighbor1[uNodeIndex] == uParentNodeIndex)\r
- ;\r
- else if (m_uNeighbor2[uNodeIndex] == uParentNodeIndex)\r
- {\r
- double dEdgeLength2 = m_dEdgeLength2[uNodeIndex];\r
- m_uNeighbor2[uNodeIndex] = m_uNeighbor1[uNodeIndex];\r
- m_dEdgeLength2[uNodeIndex] = m_dEdgeLength1[uNodeIndex];\r
- m_uNeighbor1[uNodeIndex] = uParentNodeIndex;\r
- m_dEdgeLength1[uNodeIndex] = dEdgeLength2;\r
- }\r
- else\r
- {\r
- assert(m_uNeighbor3[uNodeIndex] == uParentNodeIndex);\r
- double dEdgeLength3 = m_dEdgeLength3[uNodeIndex];\r
- m_uNeighbor3[uNodeIndex] = m_uNeighbor1[uNodeIndex];\r
- m_dEdgeLength3[uNodeIndex] = m_dEdgeLength1[uNodeIndex];\r
- m_uNeighbor1[uNodeIndex] = uParentNodeIndex;\r
- m_dEdgeLength1[uNodeIndex] = dEdgeLength3;\r
- }\r
-\r
- OrientParent(m_uNeighbor2[uNodeIndex], uNodeIndex);\r
- OrientParent(m_uNeighbor3[uNodeIndex], uNodeIndex);\r
- }\r
-\r
-unsigned Tree::FirstDepthFirstNode() const\r
- {\r
- assert(IsRooted());\r
-\r
-// Descend via left branches until we hit a leaf\r
- unsigned uNodeIndex = m_uRootNodeIndex;\r
- while (!IsLeaf(uNodeIndex))\r
- uNodeIndex = GetLeft(uNodeIndex);\r
- return uNodeIndex;\r
- }\r
-\r
-unsigned Tree::FirstDepthFirstNodeR() const\r
- {\r
- assert(IsRooted());\r
-\r
-// Descend via left branches until we hit a leaf\r
- unsigned uNodeIndex = m_uRootNodeIndex;\r
- while (!IsLeaf(uNodeIndex))\r
- uNodeIndex = GetRight(uNodeIndex);\r
- return uNodeIndex;\r
- }\r
-\r
-unsigned Tree::NextDepthFirstNode(unsigned uNodeIndex) const\r
- {\r
-#if TRACE\r
- Log("NextDepthFirstNode(%3u) ", uNodeIndex);\r
-#endif\r
-\r
- assert(IsRooted());\r
- assert(uNodeIndex < m_uNodeCount);\r
-\r
- if (IsRoot(uNodeIndex))\r
- {\r
-#if TRACE\r
- Log(">> Node %u is root, end of traversal\n", uNodeIndex);\r
-#endif\r
- return NULL_NEIGHBOR;\r
- }\r
-\r
- unsigned uParent = GetParent(uNodeIndex);\r
- if (GetRight(uParent) == uNodeIndex)\r
- {\r
-#if TRACE\r
- Log(">> Is right branch, return parent=%u\n", uParent);\r
-#endif\r
- return uParent;\r
- }\r
-\r
- uNodeIndex = GetRight(uParent);\r
-#if TRACE\r
- Log(">> Descend left from right sibling=%u ... ", uNodeIndex);\r
-#endif\r
- while (!IsLeaf(uNodeIndex))\r
- uNodeIndex = GetLeft(uNodeIndex);\r
-\r
-#if TRACE\r
- Log("bottom out at leaf=%u\n", uNodeIndex);\r
-#endif\r
- return uNodeIndex;\r
- }\r
-\r
-unsigned Tree::NextDepthFirstNodeR(unsigned uNodeIndex) const\r
- {\r
-#if TRACE\r
- Log("NextDepthFirstNode(%3u) ", uNodeIndex);\r
-#endif\r
-\r
- assert(IsRooted());\r
- assert(uNodeIndex < m_uNodeCount);\r
-\r
- if (IsRoot(uNodeIndex))\r
- {\r
-#if TRACE\r
- Log(">> Node %u is root, end of traversal\n", uNodeIndex);\r
-#endif\r
- return NULL_NEIGHBOR;\r
- }\r
-\r
- unsigned uParent = GetParent(uNodeIndex);\r
- if (GetLeft(uParent) == uNodeIndex)\r
- {\r
-#if TRACE\r
- Log(">> Is left branch, return parent=%u\n", uParent);\r
-#endif\r
- return uParent;\r
- }\r
-\r
- uNodeIndex = GetLeft(uParent);\r
-#if TRACE\r
- Log(">> Descend right from left sibling=%u ... ", uNodeIndex);\r
-#endif\r
- while (!IsLeaf(uNodeIndex))\r
- uNodeIndex = GetRight(uNodeIndex);\r
-\r
-#if TRACE\r
- Log("bottom out at leaf=%u\n", uNodeIndex);\r
-#endif\r
- return uNodeIndex;\r
- }\r
-\r
-void Tree::UnrootByDeletingRoot()\r
- {\r
- assert(IsRooted());\r
- assert(m_uNodeCount >= 3);\r
-\r
- const unsigned uLeft = GetLeft(m_uRootNodeIndex);\r
- const unsigned uRight = GetRight(m_uRootNodeIndex);\r
-\r
- m_uNeighbor1[uLeft] = uRight;\r
- m_uNeighbor1[uRight] = uLeft;\r
-\r
- bool bHasEdgeLength = HasEdgeLength(m_uRootNodeIndex, uLeft) &&\r
- HasEdgeLength(m_uRootNodeIndex, uRight);\r
- if (bHasEdgeLength)\r
- {\r
- double dEdgeLength = GetEdgeLength(m_uRootNodeIndex, uLeft) +\r
- GetEdgeLength(m_uRootNodeIndex, uRight);\r
- m_dEdgeLength1[uLeft] = dEdgeLength;\r
- m_dEdgeLength1[uRight] = dEdgeLength;\r
- }\r
-\r
-// Remove root node entry from arrays\r
- const unsigned uMoveCount = m_uNodeCount - m_uRootNodeIndex;\r
- const unsigned uUnsBytes = uMoveCount*sizeof(unsigned);\r
- memmove(m_uNeighbor1 + m_uRootNodeIndex, m_uNeighbor1 + m_uRootNodeIndex + 1,\r
- uUnsBytes);\r
- memmove(m_uNeighbor2 + m_uRootNodeIndex, m_uNeighbor2 + m_uRootNodeIndex + 1,\r
- uUnsBytes);\r
- memmove(m_uNeighbor3 + m_uRootNodeIndex, m_uNeighbor3 + m_uRootNodeIndex + 1,\r
- uUnsBytes);\r
-\r
- const unsigned uDoubleBytes = uMoveCount*sizeof(double);\r
- memmove(m_dEdgeLength1 + m_uRootNodeIndex, m_dEdgeLength1 + m_uRootNodeIndex + 1,\r
- uDoubleBytes);\r
- memmove(m_dEdgeLength2 + m_uRootNodeIndex, m_dEdgeLength2 + m_uRootNodeIndex + 1,\r
- uDoubleBytes);\r
- memmove(m_dEdgeLength3 + m_uRootNodeIndex, m_dEdgeLength3 + m_uRootNodeIndex + 1,\r
- uDoubleBytes);\r
-\r
- const unsigned uBoolBytes = uMoveCount*sizeof(bool);\r
- memmove(m_bHasEdgeLength1 + m_uRootNodeIndex, m_bHasEdgeLength1 + m_uRootNodeIndex + 1,\r
- uBoolBytes);\r
- memmove(m_bHasEdgeLength2 + m_uRootNodeIndex, m_bHasEdgeLength2 + m_uRootNodeIndex + 1,\r
- uBoolBytes);\r
- memmove(m_bHasEdgeLength3 + m_uRootNodeIndex, m_bHasEdgeLength3 + m_uRootNodeIndex + 1,\r
- uBoolBytes);\r
-\r
- const unsigned uPtrBytes = uMoveCount*sizeof(char *);\r
- memmove(m_ptrName + m_uRootNodeIndex, m_ptrName + m_uRootNodeIndex + 1, uPtrBytes);\r
-\r
- --m_uNodeCount;\r
- m_bRooted = false;\r
-\r
-// Fix up table entries\r
- for (unsigned uNodeIndex = 0; uNodeIndex < m_uNodeCount; ++uNodeIndex)\r
- {\r
-#define DEC(x) if (x != NULL_NEIGHBOR && x > m_uRootNodeIndex) --x;\r
- DEC(m_uNeighbor1[uNodeIndex])\r
- DEC(m_uNeighbor2[uNodeIndex])\r
- DEC(m_uNeighbor3[uNodeIndex])\r
-#undef DEC\r
- }\r
-\r
- Validate();\r
- }\r
-\r
-unsigned Tree::GetLeafParent(unsigned uNodeIndex) const\r
- {\r
- assert(IsLeaf(uNodeIndex));\r
-\r
- if (IsRooted())\r
- return GetParent(uNodeIndex);\r
-\r
- if (m_uNeighbor1[uNodeIndex] != NULL_NEIGHBOR)\r
- return m_uNeighbor1[uNodeIndex];\r
- if (m_uNeighbor2[uNodeIndex] != NULL_NEIGHBOR)\r
- return m_uNeighbor2[uNodeIndex];\r
- return m_uNeighbor3[uNodeIndex];\r
- }\r
-\r
-// TODO: This is not efficient for large trees, should cache.\r
-double Tree::GetNodeHeight(unsigned uNodeIndex) const\r
- {\r
- if (!IsRooted())\r
- Quit("Tree::GetNodeHeight: undefined unless rooted tree");\r
- \r
- if (IsLeaf(uNodeIndex))\r
- return 0.0;\r
-\r
- if (m_bHasHeight[uNodeIndex])\r
- return m_dHeight[uNodeIndex];\r
-\r
- const unsigned uLeft = GetLeft(uNodeIndex);\r
- const unsigned uRight = GetRight(uNodeIndex);\r
- double dLeftLength = GetEdgeLength(uNodeIndex, uLeft);\r
- double dRightLength = GetEdgeLength(uNodeIndex, uRight);\r
-\r
- if (dLeftLength < 0)\r
- dLeftLength = 0;\r
- if (dRightLength < 0)\r
- dRightLength = 0;\r
-\r
- const double dLeftHeight = dLeftLength + GetNodeHeight(uLeft);\r
- const double dRightHeight = dRightLength + GetNodeHeight(uRight);\r
- const double dHeight = (dLeftHeight + dRightHeight)/2;\r
- m_bHasHeight[uNodeIndex] = true;\r
- m_dHeight[uNodeIndex] = dHeight;\r
- return dHeight;\r
- }\r
-\r
-unsigned Tree::GetNeighborSubscript(unsigned uNodeIndex, unsigned uNeighborIndex) const\r
- {\r
- assert(uNodeIndex < m_uNodeCount);\r
- assert(uNeighborIndex < m_uNodeCount);\r
- if (uNeighborIndex == m_uNeighbor1[uNodeIndex])\r
- return 0;\r
- if (uNeighborIndex == m_uNeighbor2[uNodeIndex])\r
- return 1;\r
- if (uNeighborIndex == m_uNeighbor3[uNodeIndex])\r
- return 2;\r
- return NULL_NEIGHBOR;\r
- }\r
-\r
-unsigned Tree::GetNeighbor(unsigned uNodeIndex, unsigned uNeighborSubscript) const\r
- {\r
- switch (uNeighborSubscript)\r
- {\r
- case 0:\r
- return m_uNeighbor1[uNodeIndex];\r
- case 1:\r
- return m_uNeighbor2[uNodeIndex];\r
- case 2:\r
- return m_uNeighbor3[uNodeIndex];\r
- }\r
- Quit("Tree::GetNeighbor, sub=%u", uNeighborSubscript);\r
- return NULL_NEIGHBOR;\r
- }\r
-\r
-// TODO: check if this is a performance issue, could cache a lookup table\r
-unsigned Tree::LeafIndexToNodeIndex(unsigned uLeafIndex) const\r
- {\r
- const unsigned uNodeCount = GetNodeCount();\r
- unsigned uLeafCount = 0;\r
- for (unsigned uNodeIndex = 0; uNodeIndex < uNodeCount; ++uNodeIndex)\r
- {\r
- if (IsLeaf(uNodeIndex))\r
- {\r
- if (uLeafCount == uLeafIndex)\r
- return uNodeIndex;\r
- else\r
- ++uLeafCount;\r
- }\r
- }\r
- Quit("LeafIndexToNodeIndex: out of range");\r
- return 0;\r
- }\r
-\r
-unsigned Tree::GetLeafNodeIndex(const char *ptrName) const\r
- {\r
- const unsigned uNodeCount = GetNodeCount();\r
- for (unsigned uNodeIndex = 0; uNodeIndex < uNodeCount; ++uNodeIndex)\r
- {\r
- if (!IsLeaf(uNodeIndex))\r
- continue;\r
- const char *ptrLeafName = GetLeafName(uNodeIndex);\r
- if (0 == strcmp(ptrName, ptrLeafName))\r
- return uNodeIndex;\r
- }\r
- Quit("Tree::GetLeafNodeIndex, name not found");\r
- return 0;\r
- }\r
-\r
-void Tree::Copy(const Tree &tree)\r
- {\r
- const unsigned uNodeCount = tree.GetNodeCount();\r
- InitCache(uNodeCount);\r
-\r
- m_uNodeCount = uNodeCount;\r
-\r
- const size_t UnsignedBytes = uNodeCount*sizeof(unsigned);\r
- const size_t DoubleBytes = uNodeCount*sizeof(double);\r
- const size_t BoolBytes = uNodeCount*sizeof(bool);\r
-\r
- memcpy(m_uNeighbor1, tree.m_uNeighbor1, UnsignedBytes);\r
- memcpy(m_uNeighbor2, tree.m_uNeighbor2, UnsignedBytes);\r
- memcpy(m_uNeighbor3, tree.m_uNeighbor3, UnsignedBytes);\r
-\r
- memcpy(m_Ids, tree.m_Ids, UnsignedBytes);\r
-\r
- memcpy(m_dEdgeLength1, tree.m_dEdgeLength1, DoubleBytes);\r
- memcpy(m_dEdgeLength2, tree.m_dEdgeLength2, DoubleBytes);\r
- memcpy(m_dEdgeLength3, tree.m_dEdgeLength3, DoubleBytes);\r
-\r
- memcpy(m_dHeight, tree.m_dHeight, DoubleBytes);\r
-\r
- memcpy(m_bHasEdgeLength1, tree.m_bHasEdgeLength1, BoolBytes);\r
- memcpy(m_bHasEdgeLength2, tree.m_bHasEdgeLength2, BoolBytes);\r
- memcpy(m_bHasEdgeLength3, tree.m_bHasEdgeLength3, BoolBytes);\r
-\r
- memcpy(m_bHasHeight, tree.m_bHasHeight, BoolBytes);\r
-\r
- m_uRootNodeIndex = tree.m_uRootNodeIndex;\r
- m_bRooted = tree.m_bRooted;\r
-\r
- for (unsigned uNodeIndex = 0; uNodeIndex < m_uNodeCount; ++uNodeIndex)\r
- {\r
- if (tree.IsLeaf(uNodeIndex))\r
- {\r
- const char *ptrName = tree.GetLeafName(uNodeIndex);\r
- m_ptrName[uNodeIndex] = strsave(ptrName);\r
- }\r
- else\r
- m_ptrName[uNodeIndex] = 0;\r
- }\r
-\r
-#if DEBUG\r
- Validate();\r
-#endif\r
- }\r
-\r
-// Create rooted tree from a vector description.\r
-// Node indexes are 0..N-1 for leaves, N..2N-2 for\r
-// internal nodes.\r
-// Vector subscripts are i-N and have values for\r
-// internal nodes only, but those values are node\r
-// indexes 0..2N-2. So e.g. if N=6 and Left[2]=1,\r
-// this means that the third internal node (node index 8)\r
-// has the second leaf (node index 1) as its left child.\r
-// uRoot gives the vector subscript of the root, so add N\r
-// to get the node index.\r
-void Tree::Create(unsigned uLeafCount, unsigned uRoot, const unsigned Left[],\r
- const unsigned Right[], const float LeftLength[], const float RightLength[],\r
- const unsigned LeafIds[], char **LeafNames)\r
- {\r
- Clear();\r
-\r
- m_uNodeCount = 2*uLeafCount - 1;\r
- InitCache(m_uNodeCount);\r
-\r
- for (unsigned uNodeIndex = 0; uNodeIndex < uLeafCount; ++uNodeIndex)\r
- {\r
- m_Ids[uNodeIndex] = LeafIds[uNodeIndex];\r
- m_ptrName[uNodeIndex] = strsave(LeafNames[uNodeIndex]);\r
- }\r
-\r
- for (unsigned uNodeIndex = uLeafCount; uNodeIndex < m_uNodeCount; ++uNodeIndex)\r
- {\r
- unsigned v = uNodeIndex - uLeafCount;\r
- unsigned uLeft = Left[v];\r
- unsigned uRight = Right[v];\r
- float fLeft = LeftLength[v];\r
- float fRight = RightLength[v];\r
-\r
- m_uNeighbor2[uNodeIndex] = uLeft;\r
- m_uNeighbor3[uNodeIndex] = uRight;\r
-\r
- m_bHasEdgeLength2[uNodeIndex] = true;\r
- m_bHasEdgeLength3[uNodeIndex] = true;\r
-\r
- m_dEdgeLength2[uNodeIndex] = fLeft;\r
- m_dEdgeLength3[uNodeIndex] = fRight;\r
-\r
- m_uNeighbor1[uLeft] = uNodeIndex;\r
- m_uNeighbor1[uRight] = uNodeIndex;\r
-\r
- m_dEdgeLength1[uLeft] = fLeft;\r
- m_dEdgeLength1[uRight] = fRight;\r
-\r
- m_bHasEdgeLength1[uLeft] = true;\r
- m_bHasEdgeLength1[uRight] = true;\r
- }\r
-\r
- m_bRooted = true;\r
- m_uRootNodeIndex = uRoot + uLeafCount;\r
-\r
- Validate();\r
- }\r
git://source.jalview.org / jabaws.git / blobdiff