--- /dev/null
+package fr.orsay.lri.varna.models.treealign;
+
+import java.util.*;
+
+
+/**
+ * Tree alignment algorithm.
+ * This class implements the tree alignment algorithm
+ * for ordered trees explained in article:
+ * T. Jiang, L. Wang, K. Zhang,
+ * Alignment of trees - an alternative to tree edit,
+ * Theoret. Comput. Sci. 143 (1995).
+ * Other references:
+ * - Claire Herrbach, Alain Denise and Serge Dulucq.
+ * Average complexity of the Jiang-Wang-Zhang pairwise tree alignment
+ * algorithm and of a RNA secondary structure alignment algorithm.
+ * Theoretical Computer Science 411 (2010) 2423-2432.
+ *
+ * Our implementation supposes that the trees will never have more
+ * than 32000 nodes and that the total distance will never require more
+ * significant digits that a float (single precision) has.
+ *
+ * @author Raphael Champeimont
+ * @param <ValueType1> The type of values on nodes in the first tree.
+ * @param <ValueType2> The type of values on nodes in the second tree.
+ */
+public class TreeAlign<ValueType1, ValueType2> {
+
+ private class TreeData<ValueType> {
+ /**
+ * The tree.
+ */
+ public Tree<ValueType> tree;
+
+ /**
+ * The tree size (number of nodes).
+ */
+ public int size = -1;
+
+ /**
+ * The number of children of a node is called the node degree.
+ * This variable is the maximum node degree in the tree.
+ */
+ public int degree = -1;
+
+ /**
+ * The number of children of a node is called the node degree.
+ * degree[i] is the degree of node i, with i being an index in nodes.
+ */
+ public int[] degrees;
+
+ /**
+ * The trees as an array of its nodes (subtrees rooted at each node
+ * in fact), in postorder.
+ */
+ public Tree<ValueType>[] nodes;
+
+ /**
+ * children[i] is the array of children (as indexes in nodes)
+ * of i (an index in nodes)
+ */
+ public int[][] children;
+
+ /**
+ * Values of nodes.
+ */
+ public ValueType[] values;
+ }
+
+
+ /**
+ * The distance function between labels.
+ */
+ private TreeAlignLabelDistanceAsymmetric<ValueType1,ValueType2> labelDist;
+
+
+ /**
+ * Create a TreeAlignSymmetric object, which can align trees.
+ * The distance function will be called only once on every pair
+ * of nodes. The result is then kept in a matrix, so you need not manage
+ * yourself a cache of f(value1, value2).
+ * Note that it is permitted to have null values on nodes,
+ * so comparing a node with a non-null value with a node with a null
+ * value will give the same cost as to insert the first node.
+ * This can be useful if you tree has "fake" nodes.
+ * @param labelDist The label distance.
+ */
+ public TreeAlign(TreeAlignLabelDistanceAsymmetric<ValueType1,ValueType2> labelDist) {
+ this.labelDist = labelDist;
+ }
+
+
+
+ private class ConvertTreeToArray<ValueType> {
+ private int nextNodeIndex = 0;
+ private TreeData<ValueType> treeData;
+
+ public ConvertTreeToArray(TreeData<ValueType> treeData) {
+ this.treeData = treeData;
+ }
+
+ private void convertTreeToArrayAux(
+ Tree<ValueType> subtree,
+ int[] siblingIndexes,
+ int siblingNumber) throws TreeAlignException {
+ // We want it in postorder, so first we put the children
+ List<Tree<ValueType>> children = subtree.getChildren();
+ int numberOfChildren = children.size();
+ int[] childrenIndexes = new int[numberOfChildren];
+ int myIndex = -1;
+ {
+ int i = 0;
+ for (Tree<ValueType> child: children) {
+ convertTreeToArrayAux(child, childrenIndexes, i);
+ i++;
+ }
+ }
+ // Compute the maximum degree
+ if (numberOfChildren > treeData.degree) {
+ treeData.degree = numberOfChildren;
+ }
+ // Now we add the node (root of the given subtree).
+ myIndex = nextNodeIndex;
+ nextNodeIndex++;
+ treeData.nodes[myIndex] = subtree;
+ // Record how many children I have
+ treeData.degrees[myIndex] = numberOfChildren;
+ // Store my value in an array
+ ValueType v = subtree.getValue();
+ treeData.values[myIndex] = v;
+ // Tell the caller my index
+ siblingIndexes[siblingNumber] = myIndex;
+ // Record my children indexes
+ treeData.children[myIndex] = childrenIndexes;
+ }
+
+ /**
+ * Reads: treeData.tree
+ * Computes: treeData.nodes, treeData.degree, treeData.degrees
+ * treeData.fathers, treeData.children, treeData.size,
+ * treeData.values
+ * Converts a tree to an array of nodes, in postorder.
+ * We also compute the maximum node degree in the tree.
+ * @throws TreeAlignException
+ */
+ @SuppressWarnings("unchecked")
+ public void convert() throws TreeAlignException {
+ treeData.degree = 0;
+ treeData.size = treeData.tree.countNodes();
+ // we didn't write new Tree<ValueType>[treeData.size] because
+ // java does not support generics with arrays
+ treeData.nodes = new Tree[treeData.size];
+ treeData.children = new int[treeData.size][];
+ treeData.degrees = new int[treeData.size];
+ treeData.values = (ValueType[]) new Object[treeData.size];
+ int rootIndex[] = new int[1];
+ convertTreeToArrayAux(treeData.tree, rootIndex, 0);
+ }
+ }
+
+
+ /**
+ * For arrays that take at least O(|T1|*|T2|) we take care
+ * not to use too big data types.
+ */
+ private class Aligner {
+ /**
+ * The first tree.
+ */
+ private TreeData<ValueType1> treeData1;
+
+ /**
+ * The second tree.
+ */
+ private TreeData<ValueType2> treeData2;
+
+ /**
+ * DF1[i][j_t] is DFL for (i,j,s,t) with s=0.
+ * See description of DFL in Aligner.computeAlignmentP1().
+ * DF1 and DF2 are the "big" arrays, ie. those that may the space
+ * complexity what it is.
+ */
+ private float[][][][] DF1;
+
+ /**
+ * DF2[j][i_s] is DFL for (i,j,s,t) with t=0.
+ * See description of DFL in Aligner.computeAlignmentP1().
+ */
+ private float[][][][] DF2;
+
+ /**
+ * This arrays have the same shape as respectively DF1.
+ * They are used to remember which term in the minimum won, so that
+ * we can compute the alignment.
+ * Decision1 is a case number (< 10)
+ * and Decision2 is a child index, hence the types.
+ */
+ private byte[][][][] DF1Decisions1;
+ private short[][][][] DF1Decisions2;
+
+ /**
+ * This arrays have the same shape as respectively DF2.
+ * They are used to remember which term in the minimum won, so that
+ * we can compute the alignment.
+ */
+ private byte[][][][] DF2Decisions1;
+ private short[][][][] DF2Decisions2;
+
+ /**
+ * Distances between subtrees.
+ * DT[i][j] is the distance between the subtree rooted at i in the first tree
+ * and the subtree rooted at j in the second tree.
+ */
+ private float[][] DT;
+
+ /**
+ * This array has the same shape as DT, but is used to remember which
+ * case gave the minimum, so that we can later compute the alignment.
+ */
+ private byte[][] DTDecisions1;
+ private short[][] DTDecisions2;
+
+ /**
+ * Distances between labels.
+ * DL[i][j] is the distance labelDist.f(value(T1[i]), value(T2[i])).
+ * By convention, we say that value(T1[|T1|]) = null
+ * and value(T2[|T2|]) = null
+ */
+ private float[][] DL;
+
+ /**
+ * DET1[i] is the distance between the empty tree and T1[i]
+ * (the subtree rooted at node i in the first tree).
+ */
+ private float[] DET1;
+
+ /**
+ * Same as DET1, but for second tree.
+ */
+ private float[] DET2;
+
+ /**
+ * DEF1[i] is the distance between the empty forest and F1[i]
+ * (the forest of children of node i in the first tree).
+ */
+ private float[] DEF1;
+
+ /**
+ * Same as DEF1, but for second tree.
+ */
+ private float[] DEF2;
+
+
+ /**
+ * @param i node in T1
+ * @param s number of first child of i to consider
+ * @param m_i degree of i
+ * @param j node in T2
+ * @param t number of first child of j to consider
+ * @param n_j degree of j
+ * @param DFx which array to fill (DF1 or DF2)
+ */
+ private void computeAlignmentP1(int i, int s, int m_i, int j, int t, int n_j, int DFx) {
+ /**
+ * DFL[pr][qr] is D(F1[i_s, i_p], F2[j_t, j_q])
+ * where p=s+pr-1 and q=t+qr-1 (ie. pr=p-s+1 and qr=q-t+1)
+ * By convention, F1[i_s, i_{s-1}] and F2[j_t, j_{t-1}] are the
+ * empty forests.
+ * Said differently, DFL[pr][qr] is the distance between the forest
+ * of the pr first children of i, starting with child s
+ * (first child is s = 0), and the forest of the qr first children
+ * of j, starting with child t (first child is t = 0).
+ * This array is allocated for a fixed value of (i,j,s,t).
+ */
+ float[][] DFL;
+
+ /**
+ * Same shape as DFL, but to remember which term gave the min,
+ * so that we can later compute the alignment.
+ */
+ byte[][] DFLDecisions1;
+ short[][] DFLDecisions2;
+
+ DFL = new float[m_i-s+2][n_j-t+2];
+ DFL[0][0] = 0; // D(empty forest, empty forest) = 0
+
+ DFLDecisions1 = new byte[m_i-s+2][n_j-t+2];
+ DFLDecisions2 = new short[m_i-s+2][n_j-t+2];
+
+ // Compute indexes of i_s and j_t because we will need them
+ int i_s = m_i != 0 ? treeData1.children[i][s] : -1;
+ int j_t = n_j != 0 ? treeData2.children[j][t] : -1;
+
+ for (int p=s; p<m_i; p++) {
+ DFL[p-s+1][0] = DFL[p-s][0] + DET1[treeData1.children[i][p]];
+ }
+
+ for (int q=t; q<n_j; q++) {
+ DFL[0][q-t+1] = DFL[0][q-t] + DET2[treeData2.children[j][q]];
+ }
+
+ for (int p=s; p<m_i; p++) {
+ int i_p = treeData1.children[i][p];
+ for (int q=t; q<n_j; q++) {
+ int j_q = treeData2.children[j][q];
+
+ float min = Float.POSITIVE_INFINITY;
+ int decision1 = -1;
+ int decision2 = -1;
+
+ // Lemma 3 - Case: We delete the rightmost tree of T1
+ {
+ float minCandidate = DFL[p-s][q-t+1] + DET1[i_p];
+ if (minCandidate < min) {
+ min = minCandidate;
+ decision1 = 1;
+ }
+ }
+
+ // Lemma 3 - Case: We insert the rightmost tree of T2 (symmetric of previous case)
+ {
+ float minCandidate = DFL[p-s+1][q-t] + DET2[j_q];
+ if (minCandidate < min) {
+ min = minCandidate;
+ decision1 = 2;
+ }
+ }
+
+ // Lemma 3 - Case: Align rightmost trees with each other
+ {
+ float minCandidate =
+ DFL[p-s][q-t] + DT [i_p] [j_q];
+ if (minCandidate < min) {
+ min = minCandidate;
+ decision1 = 3;
+ }
+ }
+
+ // Lemma 3 - Case: We cut the T1 forest and match the first part
+ // with the T2 forest except the rightmost tree, and we match the second
+ // part with the T2 rightmost tree's forest of children
+ {
+ float minCandidate = Float.POSITIVE_INFINITY;
+ int best_k = -1;
+ for (int k=s; k<p; k++) {
+ float d = DFL[k-s][q-t]
+ + DF2 [j_q] [treeData1.children[i][k]] [p-k+1] [treeData2.degrees[j_q]];
+ if (d < minCandidate) {
+ minCandidate = d;
+ best_k = k;
+ }
+ }
+ minCandidate += DL[treeData1.size][j_q];
+ if (minCandidate < min) {
+ min = minCandidate;
+ decision1 = 4;
+ decision2 = best_k;
+ }
+ }
+
+ // Lemma 3 - Case: Syemmetric of preivous case
+ {
+ float minCandidate = Float.POSITIVE_INFINITY;
+ int best_k = -1;
+ for (int k=t; k<q; k++) {
+ float d = DFL[p-s][k-t]
+ + DF1 [i_p] [treeData2.children[j][k]] [treeData1.degrees[i_p]] [q-k+1];
+ if (d < minCandidate) {
+ minCandidate = d;
+ best_k = k;
+ }
+ }
+ minCandidate += DL[i_p][treeData2.size];
+ if (minCandidate < min) {
+ min = minCandidate;
+ decision1 = 5;
+ decision2 = best_k;
+ }
+ }
+
+ DFL[p-s+1][q-t+1] = min;
+ DFLDecisions1[p-s+1][q-t+1] = (byte) decision1;
+ DFLDecisions2[p-s+1][q-t+1] = (short) decision2;
+ }
+ }
+
+ // Copy references to DFL to persistent arrays
+ if (DFx == 2) {
+ DF2[j][i_s] = DFL;
+ DF2Decisions1[j][i_s] = DFLDecisions1;
+ DF2Decisions2[j][i_s] = DFLDecisions2;
+ } else {
+ DF1[i][j_t] = DFL;
+ DF1Decisions1[i][j_t] = DFLDecisions1;
+ DF1Decisions2[i][j_t] = DFLDecisions2;
+ }
+
+ }
+
+ public float align() throws TreeAlignException {
+ (new ConvertTreeToArray<ValueType1>(treeData1)).convert();
+ (new ConvertTreeToArray<ValueType2>(treeData2)).convert();
+
+ // Allocate necessary arrays
+ DT = new float[treeData1.size][treeData2.size];
+ DTDecisions1 = new byte[treeData1.size][treeData2.size];
+ DTDecisions2 = new short[treeData1.size][treeData2.size];
+ DL = new float[treeData1.size+1][treeData2.size+1];
+ DET1 = new float[treeData1.size];
+ DET2 = new float[treeData2.size];
+ DEF1 = new float[treeData1.size];
+ DEF2 = new float[treeData2.size];
+ DF1 = new float[treeData1.size][treeData2.size][][];
+ DF1Decisions1 = new byte[treeData1.size][treeData2.size][][];
+ DF1Decisions2 = new short[treeData1.size][treeData2.size][][];
+ DF2 = new float[treeData2.size][treeData1.size][][];
+ DF2Decisions1 = new byte[treeData2.size][treeData1.size][][];
+ DF2Decisions2 = new short[treeData2.size][treeData1.size][][];
+
+ DL[treeData1.size][treeData2.size] = (float) labelDist.f(null, null);
+
+ for (int i=0; i<treeData1.size; i++) {
+ int m_i = treeData1.degrees[i];
+ DEF1[i] = 0;
+ for (int k=0; k<m_i; k++) {
+ DEF1[i] += DET1[treeData1.children[i][k]];
+ }
+ DL[i][treeData2.size] = (float) labelDist.f((ValueType1) treeData1.values[i], null);
+ DET1[i] = DEF1[i] + DL[i][treeData2.size];
+ }
+
+ for (int j=0; j<treeData2.size; j++) {
+ int n_j = treeData2.degrees[j];
+ DEF2[j] = 0;
+ for (int k=0; k<n_j; k++) {
+ DEF2[j] += DET2[treeData2.children[j][k]];
+ }
+ DL[treeData1.size][j] = (float) labelDist.f(null, (ValueType2) treeData2.values[j]);
+ DET2[j] = DEF2[j] + DL[treeData1.size][j];
+ }
+
+
+ for (int i=0; i<treeData1.size; i++) {
+ int m_i = treeData1.degrees[i];
+ for (int j=0; j<treeData2.size; j++) {
+ int n_j = treeData2.degrees[j];
+
+ // Precompute f(value(i), value(j)) and keep the result
+ // to avoid calling f on the same values several times.
+ // This is important in case the computation of f takes
+ // long.
+ DL[i][j] = (float) labelDist.f((ValueType1) treeData1.values[i], (ValueType2) treeData2.values[j]);
+
+ for (int s=0; s<m_i; s++) {
+ computeAlignmentP1(i, s, m_i, j, 0, n_j, 2);
+ }
+
+ for (int t=0; t<n_j; t++) {
+ computeAlignmentP1(i, 0, m_i, j, t, n_j, 1);
+ }
+
+ DT[i][j] = Float.POSITIVE_INFINITY;
+ // Lemma 2 - Case: Root is (blank, j)
+ {
+ float minCandidate = Float.POSITIVE_INFINITY;
+ int best_r = -1;
+ for (int r=0; r<n_j; r++) {
+ float d = DT[i][treeData2.children[j][r]] - DET2[treeData2.children[j][r]];
+ if (d < minCandidate) {
+ minCandidate = d;
+ best_r = r;
+ }
+ }
+ minCandidate += DET2[j];
+ if (minCandidate < DT[i][j]) {
+ DT[i][j] = minCandidate;
+ DTDecisions1[i][j] = 1;
+ DTDecisions2[i][j] = (short) best_r;
+ }
+ }
+ // Lemma 2 - Case: Root is (i, blank)
+ {
+ float minCandidate = Float.POSITIVE_INFINITY;
+ int best_r = -1;
+ for (int r=0; r<m_i; r++) {
+ float d = DT[treeData1.children[i][r]][j] - DET1[treeData1.children[i][r]];
+ if (d < minCandidate) {
+ minCandidate = d;
+ best_r = r;
+ }
+ }
+ minCandidate += DET1[i];
+ if (minCandidate < DT[i][j]) {
+ DT[i][j] = minCandidate;
+ DTDecisions1[i][j] = 2;
+ DTDecisions2[i][j] = (short) best_r;
+ }
+ }
+ // Lemma 2 - Case: Root is (i,j)
+ {
+ float minCandidate;
+ if (n_j != 0) {
+ minCandidate = DF1 [i] [treeData2.children[j][0]] [m_i] [n_j];
+ } else {
+ if (m_i != 0) {
+ minCandidate = DF2 [j] [treeData1.children[i][0]] [m_i] [n_j];
+ } else {
+ minCandidate = 0; // D(empty forest, empty forest) = 0
+ }
+ }
+ minCandidate += DL[i][j];
+ if (minCandidate < DT[i][j]) {
+ DT[i][j] = minCandidate;
+ DTDecisions1[i][j] = 3;
+ }
+ }
+
+
+ }
+ }
+
+
+ // We return the distance beetween T1[root] and T2[root].
+ return DT[treeData1.size-1][treeData2.size-1];
+ }
+
+ public Aligner(Tree<ValueType1> T1, Tree<ValueType2> T2) {
+ treeData1 = new TreeData<ValueType1>();
+ treeData1.tree = T1;
+ treeData2 = new TreeData<ValueType2>();
+ treeData2.tree = T2;
+ }
+
+ /** Align F1[i_s,i_p] with F2[j_t,j_q].
+ * If p = s-1, by convention it means F1[i_s,i_p] = empty forest.
+ * Idem for q=t-1.
+ */
+ private List<Tree<AlignedNode<ValueType1,ValueType2>>> computeForestAlignment(int i, int s, int p, int j, int t, int q) {
+ if (p == s-1) { // left forest is the empty forest
+ List<Tree<AlignedNode<ValueType1,ValueType2>>> result = new ArrayList<Tree<AlignedNode<ValueType1,ValueType2>>>();
+ for (int k=t; k<=q; k++) {
+ result.add(treeInserted(treeData2.children[j][k]));
+ }
+ return result;
+ } else {
+ if (q == t-1) { // right forest is the empty forest
+ List<Tree<AlignedNode<ValueType1,ValueType2>>> result = new ArrayList<Tree<AlignedNode<ValueType1,ValueType2>>>();
+ for (int k=s; k<=p; k++) {
+ result.add(treeDeleted(treeData1.children[i][k]));
+ }
+ return result;
+ } else { // both forests are non-empty
+ int decision1, k;
+ if (s == 0) {
+ decision1 =
+ DF1Decisions1 [i] [treeData2.children[j][t]] [p-s+1] [q-t+1];
+ k =
+ DF1Decisions2 [i] [treeData2.children[j][t]] [p-s+1] [q-t+1];
+ } else if (t == 0) {
+ decision1 =
+ DF2Decisions1 [j] [treeData1.children[i][s]] [p-s+1] [q-t+1];
+ k =
+ DF2Decisions2 [j] [treeData1.children[i][s]] [p-s+1] [q-t+1];
+ } else {
+ throw (new Error("TreeAlignSymmetric bug: both s and t are non-zero"));
+ }
+ switch (decision1) {
+ case 1:
+ {
+ List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
+ result = computeForestAlignment(i, s, p-1, j, t, q);
+ result.add(treeDeleted(treeData1.children[i][p]));
+ return result;
+ }
+ case 2:
+ {
+ List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
+ result = computeForestAlignment(i, s, p, j, t, q-1);
+ result.add(treeInserted(treeData2.children[j][q]));
+ return result;
+ }
+ case 3:
+ {
+ List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
+ result = computeForestAlignment(i, s, p-1, j, t, q-1);
+ result.add(computeTreeAlignment(treeData1.children[i][p], treeData2.children[j][q]));
+ return result;
+ }
+ case 4:
+ {
+ List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
+ result = computeForestAlignment(i, s, k-1, j, t, q-1);
+
+ int j_q = treeData2.children[j][q];
+ Tree<AlignedNode<ValueType1,ValueType2>> insertedNode = new Tree<AlignedNode<ValueType1,ValueType2>>();
+ AlignedNode<ValueType1,ValueType2> insertedNodeValue = new AlignedNode<ValueType1,ValueType2>();
+ insertedNodeValue.setLeftNode(null);
+ insertedNodeValue.setRightNode((Tree<ValueType2>) treeData2.nodes[j_q]);
+ insertedNode.setValue(insertedNodeValue);
+
+ insertedNode.replaceChildrenListBy(computeForestAlignment(i, k, p, j_q, 0, treeData2.degrees[j_q]-1));
+
+ result.add(insertedNode);
+
+ return result;
+ }
+ case 5:
+ {
+ List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
+ result = computeForestAlignment(i, s, p-1, j, t, k-1);
+
+ int i_p = treeData1.children[i][p];
+ Tree<AlignedNode<ValueType1,ValueType2>> deletedNode = new Tree<AlignedNode<ValueType1,ValueType2>>();
+ AlignedNode<ValueType1,ValueType2> deletedNodeValue = new AlignedNode<ValueType1,ValueType2>();
+ deletedNodeValue.setLeftNode((Tree<ValueType1>) treeData1.nodes[i_p]);
+ deletedNodeValue.setRightNode(null);
+ deletedNode.setValue(deletedNodeValue);
+
+ deletedNode.replaceChildrenListBy(computeForestAlignment(i_p, 0, treeData1.degrees[i_p]-1, j, k, q));
+
+ result.add(deletedNode);
+
+ return result;
+ }
+ default:
+ throw (new Error("TreeAlign: decision1 = " + decision1));
+ }
+ }
+ }
+ }
+
+ /**
+ * Align T1[i] with the empty tree.
+ * @return the alignment
+ */
+ private Tree<AlignedNode<ValueType1,ValueType2>> treeDeleted(int i) {
+ Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
+ AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
+ alignedNode.setLeftNode(treeData1.nodes[i]);
+ alignedNode.setRightNode(null);
+ root.setValue(alignedNode);
+ for (int r = 0; r<treeData1.degrees[i]; r++) {
+ root.getChildren().add(treeDeleted(treeData1.children[i][r]));
+ }
+ return root;
+ }
+
+ /**
+ * Align the empty tree with T2[j].
+ * @return the alignment
+ */
+ private Tree<AlignedNode<ValueType1,ValueType2>> treeInserted(int j) {
+ Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
+ AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
+ alignedNode.setLeftNode(null);
+ alignedNode.setRightNode(treeData2.nodes[j]);
+ root.setValue(alignedNode);
+ for (int r = 0; r<treeData2.degrees[j]; r++) {
+ root.getChildren().add(treeInserted(treeData2.children[j][r]));
+ }
+ return root;
+ }
+
+ private Tree<AlignedNode<ValueType1,ValueType2>> computeTreeAlignment(int i, int j) {
+ switch (DTDecisions1[i][j]) {
+ case 1:
+ {
+ Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
+
+ // Compute the value of the node
+ AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
+ alignedNode.setLeftNode(null);
+ alignedNode.setRightNode(treeData2.nodes[j]);
+ root.setValue(alignedNode);
+
+ // Compute the children
+ for (int r = 0; r<treeData2.degrees[j]; r++) {
+ if (r == DTDecisions2[i][j]) {
+ root.getChildren().add(computeTreeAlignment(i, treeData2.children[j][r]));
+ } else {
+ root.getChildren().add(treeInserted(treeData2.children[j][r]));
+ }
+ }
+ return root;
+ }
+ case 2:
+ {
+ Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
+
+ // Compute the value of the node
+ AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
+ alignedNode.setLeftNode(treeData1.nodes[i]);
+ alignedNode.setRightNode(null);
+ root.setValue(alignedNode);
+
+ // Compute the children
+ for (int r = 0; r<treeData1.degrees[i]; r++) {
+ if (r == DTDecisions2[i][j]) {
+ root.getChildren().add(computeTreeAlignment(treeData1.children[i][r], j));
+ } else {
+ root.getChildren().add(treeDeleted(treeData1.children[i][r]));
+ }
+ }
+ return root;
+ }
+ case 3:
+ {
+ Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
+
+ // Compute the value of the node
+ AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
+ alignedNode.setLeftNode(treeData1.nodes[i]);
+ alignedNode.setRightNode(treeData2.nodes[j]);
+ root.setValue(alignedNode);
+
+ // Compute the children
+ List<Tree<AlignedNode<ValueType1,ValueType2>>> children =
+ computeForestAlignment(i, 0, treeData1.degrees[i]-1, j, 0, treeData2.degrees[j]-1);
+ root.replaceChildrenListBy(children);
+
+ return root;
+ }
+ default:
+ throw (new Error("TreeAlign: DTDecisions1[i][j] = " + DTDecisions1[i][j]));
+ }
+ }
+
+ public Tree<AlignedNode<ValueType1,ValueType2>> computeAlignment() {
+ return computeTreeAlignment(treeData1.size-1, treeData2.size-1);
+ }
+
+ }
+
+
+ /**
+ * Align T1 with T2, computing both the distance and the alignment.
+ * Time: O(|T1|*|T2|*(deg(T1)+deg(T2))^2)
+ * Space: O(|T1|*|T2|*(deg(T1)+deg(T2)))
+ * Average (over possible trees) time: O(|T1|*|T2|)
+ * @param T1 The first tree.
+ * @param T2 The second tree.
+ * @return The distance and the alignment.
+ * @throws TreeAlignException
+ */
+ public TreeAlignResult<ValueType1, ValueType2> align(Tree<ValueType1> T1, Tree<ValueType2> T2) throws TreeAlignException {
+ TreeAlignResult<ValueType1, ValueType2> result = new TreeAlignResult<ValueType1, ValueType2>();
+ Aligner aligner = new Aligner(T1, T2);
+ result.setDistance(aligner.align());
+ result.setAlignment(aligner.computeAlignment());
+ return result;
+ }
+
+
+ /**
+ * Takes a alignment, and compute the distance between the two
+ * original trees. If you have called align(), the result object already
+ * contains the distance D and the alignment A. If you call
+ * distanceFromAlignment on the alignment A it will compute the distance D.
+ */
+ public float distanceFromAlignment(Tree<AlignedNode<ValueType1,ValueType2>> alignment) {
+ Tree<ValueType1> originalT1Node;
+ Tree<ValueType2> originalT2Node;
+ originalT1Node = alignment.getValue().getLeftNode();
+ originalT2Node = alignment.getValue().getRightNode();
+ float d = (float) labelDist.f(
+ originalT1Node != null ? originalT1Node.getValue() : null,
+ originalT2Node != null ? originalT2Node.getValue() : null);
+ for (Tree<AlignedNode<ValueType1,ValueType2>> child: alignment.getChildren()) {
+ d += distanceFromAlignment(child);
+ }
+ return d;
+ }
+
+
+}
git://source.jalview.org / jalview.git / blobdiff