+++ /dev/null
-#include "muscle.h"\r
-#include "tree.h"\r
-\r
-#define TRACE 0\r
-\r
-/***\r
-Algorithm to compare two trees, X and Y.\r
-\r
-A node x in X and node y in Y are defined to be\r
-similar iff the set of leaves in the subtree under\r
-x is identical to the set of leaves under y.\r
-\r
-A node is defined to be changed iff it is not\r
-similar to any node in the other tree.\r
-\r
-Nodes x and y are defined to be married iff every\r
-node in the subtree under x is similar to a node\r
-in the subtree under y. Married nodes are considered\r
-to be equal. The subtrees under two married nodes can\r
-at most differ by exchanges of left and right branches,\r
-which we do not consider to be significant here.\r
-\r
-A node is changed iff it is not married. If a node is\r
-changed, then it has a dissimilar node in its subtree,\r
-and it follows immediately from the definition of marriage\r
-that its parent is also a bachelor. Hence all nodes on the\r
-path from a changed node to the root are changed.\r
-\r
-We assume the trees have the same set of leaves, so\r
-every leaf is trivially both similar and married to\r
-the same leaf in the opposite tree. Changed nodes\r
-are therefore always internal (i.e., non-leaf) nodes.\r
-\r
-Example:\r
-\r
- -----A\r
- -----k\r
- ----j -----B\r
---i -----C\r
- ------D\r
-\r
-\r
- -----A\r
- -----p\r
- ----n -----B\r
---m -----D\r
- ------C\r
-\r
-\r
-The following pairs of internal nodes are similar.\r
-\r
- Nodes Set of leaves\r
- ----- -------------\r
- k,p A,B\r
- i,m A,B,C,D\r
-\r
-Changed nodes in the first tree are i and j, changed nodes\r
-in the second tree are m and n.\r
-\r
-Node k and p are married, but i and m are not (because j\r
-and n are changed). The diffs are C, D and k.\r
-\r
-To achieve O(N) we avoid traversing a given subtree multiple\r
-times and also avoid comparing lists of leaves. \r
-\r
-We visit nodes in depth-first order (i.e., a node is visited\r
-before its parent).\r
-\r
-If either child of a node is changed, we flag it as changed.\r
-\r
-If both children of the node we are visiting are married,\r
-we check whether the spouses of those children have the\r
-same parent in the other tree. If the parents are different,\r
-the current node is a bachelor. If they have the same parent,\r
-then the node we are visiting is the spouse of that parent.\r
-We assign this newly identified married couple a unique integer\r
-id. The id of a node is in one-to-one correspondence with the\r
-set of leaves in its subtree. Two nodes have the same set of\r
-leaves iff they have the same id. Changed nodes do not get\r
-an id.\r
-***/\r
-\r
-void DiffTreesE(const Tree &NewTree, const Tree &OldTree,\r
- unsigned NewNodeIndexToOldNodeIndex[])\r
- {\r
-#if TRACE\r
- Log("DiffTreesE NewTree:\n");\r
- NewTree.LogMe();\r
- Log("\n");\r
- Log("OldTree:\n");\r
- OldTree.LogMe();\r
-#endif\r
-\r
- if (!NewTree.IsRooted() || !OldTree.IsRooted())\r
- Quit("DiffTrees: requires rooted trees");\r
-\r
- const unsigned uNodeCount = NewTree.GetNodeCount();\r
- const unsigned uOldNodeCount = OldTree.GetNodeCount();\r
- const unsigned uLeafCount = NewTree.GetLeafCount();\r
- const unsigned uOldLeafCount = OldTree.GetLeafCount();\r
- if (uNodeCount != uOldNodeCount || uLeafCount != uOldLeafCount)\r
- Quit("DiffTreesE: different node counts");\r
-\r
- {\r
- unsigned *IdToOldNodeIndex = new unsigned[uNodeCount];\r
- for (unsigned uOldNodeIndex = 0; uOldNodeIndex < uNodeCount; ++uOldNodeIndex)\r
- {\r
- if (OldTree.IsLeaf(uOldNodeIndex))\r
- {\r
- unsigned Id = OldTree.GetLeafId(uOldNodeIndex);\r
- IdToOldNodeIndex[Id] = uOldNodeIndex;\r
- }\r
- }\r
-\r
-// Initialize NewNodeIndexToOldNodeIndex[]\r
-// All internal nodes are marked as changed, but may be updated later.\r
- for (unsigned uNewNodeIndex = 0; uNewNodeIndex < uNodeCount; ++uNewNodeIndex)\r
- {\r
- if (NewTree.IsLeaf(uNewNodeIndex))\r
- {\r
- unsigned uId = NewTree.GetLeafId(uNewNodeIndex);\r
- assert(uId < uLeafCount);\r
-\r
- unsigned uOldNodeIndex = IdToOldNodeIndex[uId];\r
- assert(uOldNodeIndex < uNodeCount);\r
-\r
- NewNodeIndexToOldNodeIndex[uNewNodeIndex] = uOldNodeIndex;\r
- }\r
- else\r
- NewNodeIndexToOldNodeIndex[uNewNodeIndex] = NODE_CHANGED;\r
- }\r
- delete[] IdToOldNodeIndex;\r
- }\r
-\r
-// Depth-first traversal of tree.\r
-// The order guarantees that a node is visited before\r
-// its parent is visited.\r
- for (unsigned uNewNodeIndex = NewTree.FirstDepthFirstNode();\r
- NULL_NEIGHBOR != uNewNodeIndex;\r
- uNewNodeIndex = NewTree.NextDepthFirstNode(uNewNodeIndex))\r
- {\r
- if (NewTree.IsLeaf(uNewNodeIndex))\r
- continue;\r
-\r
- // If either child is changed, flag this node as changed and continue.\r
- unsigned uNewLeft = NewTree.GetLeft(uNewNodeIndex);\r
- unsigned uOldLeft = NewNodeIndexToOldNodeIndex[uNewLeft];\r
- if (NODE_CHANGED == uOldLeft)\r
- {\r
- NewNodeIndexToOldNodeIndex[uNewLeft] = NODE_CHANGED;\r
- continue;\r
- }\r
-\r
- unsigned uNewRight = NewTree.GetRight(uNewNodeIndex);\r
- unsigned uOldRight = NewNodeIndexToOldNodeIndex[uNewRight];\r
- if (NODE_CHANGED == NewNodeIndexToOldNodeIndex[uNewRight])\r
- {\r
- NewNodeIndexToOldNodeIndex[uNewRight] = NODE_CHANGED;\r
- continue;\r
- }\r
-\r
- unsigned uOldParentLeft = OldTree.GetParent(uOldLeft);\r
- unsigned uOldParentRight = OldTree.GetParent(uOldRight);\r
- if (uOldParentLeft == uOldParentRight)\r
- NewNodeIndexToOldNodeIndex[uNewNodeIndex] = uOldParentLeft;\r
- else\r
- NewNodeIndexToOldNodeIndex[uNewNodeIndex] = NODE_CHANGED;\r
- }\r
-\r
-#if TRACE\r
- {\r
- Log("NewToOld ");\r
- for (unsigned uNewNodeIndex = 0; uNewNodeIndex < uNodeCount; ++uNewNodeIndex)\r
- {\r
- Log(" [%3u]=", uNewNodeIndex);\r
- if (NODE_CHANGED == NewNodeIndexToOldNodeIndex[uNewNodeIndex])\r
- Log(" X");\r
- else\r
- Log("%3u", NewNodeIndexToOldNodeIndex[uNewNodeIndex]);\r
- if ((uNewNodeIndex+1)%8 == 0)\r
- Log("\n ");\r
- }\r
- Log("\n");\r
- }\r
-#endif\r
-\r
-#if DEBUG\r
- {\r
- for (unsigned uNewNodeIndex = 0; uNewNodeIndex < uNodeCount; ++uNewNodeIndex)\r
- {\r
- unsigned uOld = NewNodeIndexToOldNodeIndex[uNewNodeIndex];\r
- if (NewTree.IsLeaf(uNewNodeIndex))\r
- {\r
- if (uOld >= uNodeCount)\r
- {\r
- Log("NewNode=%u uOld=%u > uNodeCount=%u\n",\r
- uNewNodeIndex, uOld, uNodeCount);\r
- Quit("Diff check failed");\r
- }\r
- unsigned uIdNew = NewTree.GetLeafId(uNewNodeIndex);\r
- unsigned uIdOld = OldTree.GetLeafId(uOld);\r
- if (uIdNew != uIdOld)\r
- {\r
- Log("NewNode=%u uOld=%u IdNew=%u IdOld=%u\n",\r
- uNewNodeIndex, uOld, uIdNew, uIdOld);\r
- Quit("Diff check failed");\r
- }\r
- continue;\r
- }\r
-\r
- if (NODE_CHANGED == uOld)\r
- continue;\r
-\r
- unsigned uNewLeft = NewTree.GetLeft(uNewNodeIndex);\r
- unsigned uNewRight = NewTree.GetRight(uNewNodeIndex);\r
-\r
- unsigned uOldLeft = OldTree.GetLeft(uOld);\r
- unsigned uOldRight = OldTree.GetRight(uOld);\r
-\r
- unsigned uNewLeftPartner = NewNodeIndexToOldNodeIndex[uNewLeft];\r
- unsigned uNewRightPartner = NewNodeIndexToOldNodeIndex[uNewRight];\r
-\r
- bool bSameNotRotated = (uNewLeftPartner == uOldLeft && uNewRightPartner == uOldRight);\r
- bool bSameRotated = (uNewLeftPartner == uOldRight && uNewRightPartner == uOldLeft);\r
- if (!bSameNotRotated && !bSameRotated)\r
- {\r
- Log("NewNode=%u NewL=%u NewR=%u\n", uNewNodeIndex, uNewLeft, uNewRight);\r
- Log("OldNode=%u OldL=%u OldR=%u\n", uOld, uOldLeft, uOldRight);\r
- Log("NewLPartner=%u NewRPartner=%u\n", uNewLeftPartner, uNewRightPartner);\r
- Quit("Diff check failed");\r
- }\r
- }\r
- }\r
-#endif\r
- }\r
git://source.jalview.org / jabaws.git / blobdiff