+++ /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 dissimilar 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 defined to be a bachelor iff it is not\r
-married. If a node is a bachelor, then it has a\r
-dissimilar node in its subtree, and it follows\r
-immediately from the definition of marriage that its\r
-parent is also a bachelor. Hence all nodes on the path\r
-from a bachelor node to the root are bachelors.\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. Bachelor nodes\r
-are therefore always internal (i.e., non-leaf) nodes.\r
-\r
-A node is defined to be a diff iff (a) it is married\r
-and (b) its parent is a bachelor. The subtree under\r
-a diff is maximally similar to the other tree. (In\r
-other words, you cannot extend the subtree without\r
-adding a bachelor). \r
-\r
-The set of diffs is the subset of the two trees that\r
-we consider to be identical.\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
-Bachelors in the first tree are i and j, bachelors\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 bachelors). The diffs are C, D and k.\r
-\r
-The set of bachelor nodes can be viewed as the internal\r
-nodes of a tree, the leaves of which are diffs. (To see\r
-that there can't be disjoint subtrees, note that the path\r
-from a diff to a root is all bachelor nodes, so there is\r
-always a path between two diffs that goes through the root).\r
-We call this tree the "diffs tree".\r
-\r
-There is a simple O(N) algorithm to build the diffs tree.\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 a bachelor, we flag it as\r
-a bachelor.\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. Bachelor nodes do not get\r
-an id.\r
-***/\r
-\r
-static void BuildDiffs(const Tree &tree, unsigned uTreeNodeIndex,\r
- const bool bIsDiff[], Tree &Diffs, unsigned uDiffsNodeIndex,\r
- unsigned IdToDiffsLeafNodeIndex[])\r
- {\r
-#if TRACE\r
- Log("BuildDiffs(TreeNode=%u IsDiff=%d IsLeaf=%d)\n",\r
- uTreeNodeIndex, bIsDiff[uTreeNodeIndex], tree.IsLeaf(uTreeNodeIndex));\r
-#endif\r
- if (bIsDiff[uTreeNodeIndex])\r
- {\r
- unsigned uLeafCount = tree.GetLeafCount();\r
- unsigned *Leaves = new unsigned[uLeafCount];\r
- GetLeaves(tree, uTreeNodeIndex, Leaves, &uLeafCount);\r
- for (unsigned n = 0; n < uLeafCount; ++n)\r
- {\r
- const unsigned uLeafNodeIndex = Leaves[n];\r
- const unsigned uId = tree.GetLeafId(uLeafNodeIndex);\r
- if (uId >= tree.GetLeafCount())\r
- Quit("BuildDiffs, id out of range");\r
- IdToDiffsLeafNodeIndex[uId] = uDiffsNodeIndex;\r
-#if TRACE\r
- Log(" Leaf id=%u DiffsNode=%u\n", uId, uDiffsNodeIndex);\r
-#endif\r
- }\r
- delete[] Leaves;\r
- return;\r
- }\r
-\r
- if (tree.IsLeaf(uTreeNodeIndex))\r
- Quit("BuildDiffs: should never reach leaf");\r
-\r
- const unsigned uTreeLeft = tree.GetLeft(uTreeNodeIndex);\r
- const unsigned uTreeRight = tree.GetRight(uTreeNodeIndex);\r
-\r
- const unsigned uDiffsLeft = Diffs.AppendBranch(uDiffsNodeIndex);\r
- const unsigned uDiffsRight = uDiffsLeft + 1;\r
-\r
- BuildDiffs(tree, uTreeLeft, bIsDiff, Diffs, uDiffsLeft, IdToDiffsLeafNodeIndex);\r
- BuildDiffs(tree, uTreeRight, bIsDiff, Diffs, uDiffsRight, IdToDiffsLeafNodeIndex);\r
- }\r
-\r
-void DiffTrees(const Tree &Tree1, const Tree &Tree2, Tree &Diffs,\r
- unsigned IdToDiffsLeafNodeIndex[])\r
- {\r
-#if TRACE\r
- Log("Tree1:\n");\r
- Tree1.LogMe();\r
- Log("\n");\r
- Log("Tree2:\n");\r
- Tree2.LogMe();\r
-#endif\r
-\r
- if (!Tree1.IsRooted() || !Tree2.IsRooted())\r
- Quit("DiffTrees: requires rooted trees");\r
-\r
- const unsigned uNodeCount = Tree1.GetNodeCount();\r
- const unsigned uNodeCount2 = Tree2.GetNodeCount();\r
- \r
- const unsigned uLeafCount = Tree1.GetLeafCount();\r
- const unsigned uLeafCount2 = Tree2.GetLeafCount();\r
- assert(uLeafCount == uLeafCount2);\r
-\r
- if (uNodeCount != uNodeCount2)\r
- Quit("DiffTrees: different node counts");\r
-\r
-// Allocate tables so we can convert tree node index to\r
-// and from the unique id with a O(1) lookup.\r
- unsigned *NodeIndexToId1 = new unsigned[uNodeCount];\r
- unsigned *IdToNodeIndex2 = new unsigned[uNodeCount];\r
-\r
- bool *bIsBachelor1 = new bool[uNodeCount];\r
- bool *bIsDiff1 = new bool[uNodeCount];\r
-\r
- for (unsigned uNodeIndex = 0; uNodeIndex < uNodeCount; ++uNodeIndex)\r
- {\r
- NodeIndexToId1[uNodeIndex] = uNodeCount;\r
- bIsBachelor1[uNodeIndex] = false;\r
- bIsDiff1[uNodeIndex] = false;\r
-\r
- // Use uNodeCount as value meaning "not set".\r
- IdToNodeIndex2[uNodeIndex] = uNodeCount;\r
- }\r
-\r
-// Initialize node index <-> id lookup tables\r
- for (unsigned uNodeIndex = 0; uNodeIndex < uNodeCount; ++uNodeIndex)\r
- {\r
- if (Tree1.IsLeaf(uNodeIndex))\r
- {\r
- const unsigned uId = Tree1.GetLeafId(uNodeIndex);\r
- if (uId >= uNodeCount)\r
- Quit("Diff trees requires existing leaf ids in range 0 .. (N-1)");\r
- NodeIndexToId1[uNodeIndex] = uId;\r
- }\r
-\r
- if (Tree2.IsLeaf(uNodeIndex))\r
- {\r
- const unsigned uId = Tree2.GetLeafId(uNodeIndex);\r
- if (uId >= uNodeCount)\r
- Quit("Diff trees requires existing leaf ids in range 0 .. (N-1)");\r
- IdToNodeIndex2[uId] = uNodeIndex;\r
- }\r
- }\r
-\r
-// Validity check. This verifies that the ids\r
-// pre-assigned to the leaves in Tree1 are unique\r
-// (note that the id<N check above does not rule\r
-// out two leaves having duplicate ids).\r
- for (unsigned uId = 0; uId < uLeafCount; ++uId)\r
- {\r
- unsigned uNodeIndex2 = IdToNodeIndex2[uId];\r
- if (uNodeCount == uNodeIndex2)\r
- Quit("DiffTrees, check 2");\r
- }\r
-\r
-// Ids assigned to internal nodes are N, N+1 ...\r
-// An internal node id uniquely identifies a set\r
-// of two or more leaves.\r
- unsigned uInternalNodeId = uLeafCount;\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 uNodeIndex1 = Tree1.FirstDepthFirstNode();\r
- NULL_NEIGHBOR != uNodeIndex1;\r
- uNodeIndex1 = Tree1.NextDepthFirstNode(uNodeIndex1))\r
- {\r
-#if TRACE\r
- Log("Main loop: Node1=%u IsLeaf=%d IsBachelor=%d\n",\r
- uNodeIndex1,\r
- Tree1.IsLeaf(uNodeIndex1),\r
- bIsBachelor1[uNodeIndex1]);\r
-#endif\r
-\r
- // Leaves are trivial; nothing to do.\r
- if (Tree1.IsLeaf(uNodeIndex1) || bIsBachelor1[uNodeIndex1])\r
- continue;\r
-\r
- // If either child is a bachelor, flag\r
- // this node as a bachelor and continue.\r
- unsigned uLeft1 = Tree1.GetLeft(uNodeIndex1);\r
- if (bIsBachelor1[uLeft1])\r
- {\r
- bIsBachelor1[uNodeIndex1] = true;\r
- continue;\r
- }\r
-\r
- unsigned uRight1 = Tree1.GetRight(uNodeIndex1);\r
- if (bIsBachelor1[uRight1])\r
- {\r
- bIsBachelor1[uNodeIndex1] = true;\r
- continue;\r
- }\r
-\r
- // Both children are married.\r
- // Married nodes are guaranteed to have an id.\r
- unsigned uIdLeft = NodeIndexToId1[uLeft1];\r
- unsigned uIdRight = NodeIndexToId1[uRight1];\r
-\r
- if (uIdLeft == uNodeCount || uIdRight == uNodeCount)\r
- Quit("DiffTrees, check 5");\r
-\r
- // uLeft2 is the spouse of uLeft1, and similarly for uRight2.\r
- unsigned uLeft2 = IdToNodeIndex2[uIdLeft];\r
- unsigned uRight2 = IdToNodeIndex2[uIdRight];\r
-\r
- if (uLeft2 == uNodeCount || uRight2 == uNodeCount)\r
- Quit("DiffTrees, check 6");\r
-\r
- // If the spouses of uLeft1 and uRight1 have the same\r
- // parent, then this parent is the spouse of uNodeIndex1.\r
- // Otherwise, uNodeIndex1 is a diff.\r
- unsigned uParentLeft2 = Tree2.GetParent(uLeft2);\r
- unsigned uParentRight2 = Tree2.GetParent(uRight2);\r
-\r
-#if TRACE\r
- Log("L1=%u R1=%u L2=%u R2=%u PL2=%u PR2=%u\n",\r
- uLeft1,\r
- uRight1,\r
- uLeft2,\r
- uRight2,\r
- uParentLeft2,\r
- uParentRight2);\r
-#endif\r
-\r
- if (uParentLeft2 == uParentRight2)\r
- {\r
- NodeIndexToId1[uNodeIndex1] = uInternalNodeId;\r
- IdToNodeIndex2[uInternalNodeId] = uParentLeft2;\r
- ++uInternalNodeId;\r
- }\r
- else\r
- bIsBachelor1[uNodeIndex1] = true;\r
- }\r
-\r
- unsigned uDiffCount = 0;\r
- for (unsigned uNodeIndex = 0; uNodeIndex < uNodeCount; ++uNodeIndex)\r
- {\r
- if (bIsBachelor1[uNodeIndex])\r
- continue;\r
- if (Tree1.IsRoot(uNodeIndex))\r
- {\r
- // Special case: if no bachelors, consider the\r
- // root a diff.\r
- if (!bIsBachelor1[uNodeIndex])\r
- bIsDiff1[uNodeIndex] = true;\r
- continue;\r
- }\r
- const unsigned uParent = Tree1.GetParent(uNodeIndex);\r
- if (bIsBachelor1[uParent])\r
- {\r
- bIsDiff1[uNodeIndex] = true;\r
- ++uDiffCount;\r
- }\r
- }\r
-\r
-#if TRACE\r
- Log("Tree1:\n");\r
- Log("Node Id Bach Diff Name\n");\r
- Log("---- ---- ---- ---- ----\n");\r
- for (unsigned n = 0; n < uNodeCount; ++n)\r
- {\r
- Log("%4u %4u %d %d",\r
- n,\r
- NodeIndexToId1[n],\r
- bIsBachelor1[n],\r
- bIsDiff1[n]);\r
- if (Tree1.IsLeaf(n))\r
- Log(" %s", Tree1.GetLeafName(n));\r
- Log("\n");\r
- }\r
- Log("\n");\r
- Log("Tree2:\n");\r
- Log("Node Id Name\n");\r
- Log("---- ---- ----\n");\r
- for (unsigned n = 0; n < uNodeCount; ++n)\r
- {\r
- Log("%4u ", n);\r
- if (Tree2.IsLeaf(n))\r
- Log(" %s", Tree2.GetLeafName(n));\r
- Log("\n");\r
- }\r
-#endif\r
-\r
- Diffs.CreateRooted();\r
- const unsigned uDiffsRootIndex = Diffs.GetRootNodeIndex();\r
- const unsigned uRootIndex1 = Tree1.GetRootNodeIndex();\r
-\r
- for (unsigned n = 0; n < uLeafCount; ++n)\r
- IdToDiffsLeafNodeIndex[n] = uNodeCount;\r
-\r
- BuildDiffs(Tree1, uRootIndex1, bIsDiff1, Diffs, uDiffsRootIndex,\r
- IdToDiffsLeafNodeIndex);\r
-\r
-#if TRACE\r
- Log("\n");\r
- Log("Diffs:\n");\r
- Diffs.LogMe();\r
- Log("\n");\r
- Log("IdToDiffsLeafNodeIndex:");\r
- for (unsigned n = 0; n < uLeafCount; ++n)\r
- {\r
- if (n%16 == 0)\r
- Log("\n");\r
- else\r
- Log(" ");\r
- Log("%u=%u", n, IdToDiffsLeafNodeIndex[n]);\r
- }\r
- Log("\n");\r
-#endif\r
-\r
- for (unsigned n = 0; n < uLeafCount; ++n)\r
- if (IdToDiffsLeafNodeIndex[n] == uNodeCount)\r
- Quit("TreeDiffs check 7");\r
-\r
- delete[] NodeIndexToId1;\r
- delete[] IdToNodeIndex2;\r
-\r
- delete[] bIsBachelor1;\r
- delete[] bIsDiff1;\r
- }\r
git://source.jalview.org / jabaws.git / blobdiff