src2/fr/orsay/lri/varna/models/treealign/TreeAlign.java

   1 package fr.orsay.lri.varna.models.treealign;
   2
   3 import java.util.*;
   4
   5
   6 /**
   7  * Tree alignment algorithm.
   8  * This class implements the tree alignment algorithm
   9  * for ordered trees explained in article:
  10  *   T. Jiang, L. Wang, K. Zhang,
  11  *   Alignment of trees - an alternative to tree edit,
  12  *   Theoret. Comput. Sci. 143 (1995).
  13  * Other references:
  14  * - Claire Herrbach, Alain Denise and Serge Dulucq.
  15  *   Average complexity of the Jiang-Wang-Zhang pairwise tree alignment
  16  *   algorithm and of a RNA secondary structure alignment algorithm.
  17  *   Theoretical Computer Science 411 (2010) 2423-2432.
  18  *
  19  * Our implementation supposes that the trees will never have more
  20  * than 32000 nodes and that the total distance will never require more
  21  * significant digits that a float (single precision) has.
  22  *
  23  * @author Raphael Champeimont
  24  * @param <ValueType1> The type of values on nodes in the first tree.
  25  * @param <ValueType2> The type of values on nodes in the second tree.
  26  */
  27 public class TreeAlign<ValueType1, ValueType2> {
  28
  29         private class TreeData<ValueType> {
  30                 /**
  31                  * The tree.
  32                  */
  33                 public Tree<ValueType> tree;
  34
  35                 /**
  36                  * The tree size (number of nodes).
  37                  */
  38                 public int size = -1;
  39
  40                 /**
  41                  * The number of children of a node is called the node degree.
  42                  * This variable is the maximum node degree in the tree.
  43                  */
  44                 public int degree = -1;
  45
  46                 /**
  47                  * The number of children of a node is called the node degree.
  48                  * degree[i] is the degree of node i, with i being an index in nodes.
  49                  */
  50                 public int[] degrees;
  51
  52                 /**
  53                  * The trees as an array of its nodes (subtrees rooted at each node
  54                  * in fact), in postorder.
  55                  */
  56                 public Tree<ValueType>[] nodes;
  57
  58                 /**
  59                  * children[i] is the array of children (as indexes in nodes)
  60                  * of i (an index in nodes)
  61                  */
  62                 public int[][] children;
  63
  64                 /**
  65                  * Values of nodes.
  66                  */
  67                 public ValueType[] values;
  68         }
  69
  70
  71         /**
  72          * The distance function between labels.
  73          */
  74         private TreeAlignLabelDistanceAsymmetric<ValueType1,ValueType2> labelDist;
  75
  76
  77         /**
  78          * Create a TreeAlignSymmetric object, which can align trees.
  79          * The distance function will be called only once on every pair
  80          * of nodes. The result is then kept in a matrix, so you need not manage
  81          * yourself a cache of f(value1, value2).
  82          * Note that it is permitted to have null values on nodes,
  83          * so comparing a node with a non-null value with a node with a null
  84          * value will give the same cost as to insert the first node.
  85          * This can be useful if you tree has "fake" nodes.
  86          * @param labelDist The label distance.
  87          */
  88         public TreeAlign(TreeAlignLabelDistanceAsymmetric<ValueType1,ValueType2> labelDist) {
  89                 this.labelDist = labelDist;
  90         }
  91
  92
  93
  94         private class ConvertTreeToArray<ValueType> {
  95                 private int nextNodeIndex = 0;
  96                 private TreeData<ValueType> treeData;
  97
  98                 public ConvertTreeToArray(TreeData<ValueType> treeData) {
  99                         this.treeData = treeData;
 100                 }
 101
 102                 private void convertTreeToArrayAux(
 103                                 Tree<ValueType> subtree,
 104                                 int[] siblingIndexes,
 105                                 int siblingNumber) throws TreeAlignException {
 106                         // We want it in postorder, so first we put the children
 107                         List<Tree<ValueType>> children = subtree.getChildren();
 108                         int numberOfChildren = children.size();
 109                         int[] childrenIndexes = new int[numberOfChildren];
 110                         int myIndex = -1;
 111                         {
 112                                 int i = 0;
 113                                 for (Tree<ValueType> child: children) {
 114                                         convertTreeToArrayAux(child, childrenIndexes, i);
 115                                         i++;
 116                                 }
 117                         }
 118                         // Compute the maximum degree
 119                         if (numberOfChildren > treeData.degree) {
 120                                 treeData.degree = numberOfChildren;
 121                         }
 122                         // Now we add the node (root of the given subtree).
 123                         myIndex = nextNodeIndex;
 124                         nextNodeIndex++;
 125                         treeData.nodes[myIndex] = subtree;
 126                         // Record how many children I have
 127                         treeData.degrees[myIndex] = numberOfChildren;
 128                         // Store my value in an array
 129                         ValueType v = subtree.getValue();
 130                         treeData.values[myIndex] = v;
 131                         // Tell the caller my index
 132                         siblingIndexes[siblingNumber] = myIndex;
 133                         // Record my children indexes
 134                         treeData.children[myIndex] = childrenIndexes;
 135                 }
 136
 137                 /**
 138                  * Reads: treeData.tree
 139                  * Computes: treeData.nodes, treeData.degree, treeData.degrees
 140                  *           treeData.fathers, treeData.children, treeData.size,
 141                  *           treeData.values
 142                  * Converts a tree to an array of nodes, in postorder.
 143                  * We also compute the maximum node degree in the tree.
 144                  * @throws TreeAlignException
 145                  */
 146                 @SuppressWarnings("unchecked")
 147                 public void convert() throws TreeAlignException {
 148                         treeData.degree = 0;
 149                         treeData.size = treeData.tree.countNodes();
 150                         // we didn't write new Tree<ValueType>[treeData.size] because
 151                         // java does not support generics with arrays
 152                         treeData.nodes = new Tree[treeData.size];
 153                         treeData.children = new int[treeData.size][];
 154                         treeData.degrees = new int[treeData.size];
 155                         treeData.values = (ValueType[]) new Object[treeData.size];
 156                         int rootIndex[] = new int[1];
 157                         convertTreeToArrayAux(treeData.tree, rootIndex, 0);
 158                 }
 159         }
 160
 161
 162         /**
 163          * For arrays that take at least O(|T1|*|T2|) we take care
 164          * not to use too big data types.
 165          */
 166         private class Aligner {
 167                 /**
 168                  * The first tree.
 169                  */
 170                 private TreeData<ValueType1> treeData1;
 171
 172                 /**
 173                  * The second tree.
 174                  */
 175                 private TreeData<ValueType2> treeData2;
 176
 177                 /**
 178                  * DF1[i][j_t] is DFL for (i,j,s,t) with s=0.
 179                  * See description of DFL in Aligner.computeAlignmentP1().
 180                  * DF1 and DF2 are the "big" arrays, ie. those that may the space
 181                  * complexity what it is.
 182                  */
 183                 private float[][][][] DF1;
 184
 185                 /**
 186                  * DF2[j][i_s] is DFL for (i,j,s,t) with t=0.
 187                  * See description of DFL in Aligner.computeAlignmentP1().
 188                  */
 189                 private float[][][][] DF2;
 190
 191                 /**
 192                  * This arrays have the same shape as respectively DF1.
 193                  * They are used to remember which term in the minimum won, so that
 194                  * we can compute the alignment.
 195                  * Decision1 is a case number (< 10)
 196                  * and Decision2 is a child index, hence the types.
 197                  */
 198                 private byte[][][][] DF1Decisions1;
 199                 private short[][][][] DF1Decisions2;
 200
 201                 /**
 202                  * This arrays have the same shape as respectively DF2.
 203                  * They are used to remember which term in the minimum won, so that
 204                  * we can compute the alignment.
 205                  */
 206                 private byte[][][][] DF2Decisions1;
 207                 private short[][][][] DF2Decisions2;
 208
 209                 /**
 210                  * Distances between subtrees.
 211                  * DT[i][j] is the distance between the subtree rooted at i in the first tree
 212                  * and the subtree rooted at j in the second tree.
 213                  */
 214                 private float[][] DT;
 215
 216                 /**
 217                  * This array has the same shape as DT, but is used to remember which
 218                  * case gave the minimum, so that we can later compute the alignment.
 219                  */
 220                 private byte[][] DTDecisions1;
 221                 private short[][] DTDecisions2;
 222
 223                 /**
 224                  * Distances between labels.
 225                  * DL[i][j] is the distance labelDist.f(value(T1[i]), value(T2[i])).
 226                  * By convention, we say that value(T1[|T1|]) = null
 227                  * and value(T2[|T2|]) = null
 228                  */
 229                 private float[][] DL;
 230
 231                 /**
 232                  * DET1[i] is the distance between the empty tree and T1[i]
 233                  * (the subtree rooted at node i in the first tree).
 234                  */
 235                 private float[] DET1;
 236
 237                 /**
 238                  * Same as DET1, but for second tree.
 239                  */
 240                 private float[] DET2;
 241
 242                 /**
 243                  * DEF1[i] is the distance between the empty forest and F1[i]
 244                  * (the forest of children of node i in the first tree).
 245                  */
 246                 private float[] DEF1;
 247
 248                 /**
 249                  * Same as DEF1, but for second tree.
 250                  */
 251                 private float[] DEF2;
 252
 253
 254                 /**
 255                  * @param i node in T1
 256                  * @param s number of first child of i to consider
 257                  * @param m_i degree of i
 258                  * @param j node in T2
 259                  * @param t number of first child of j to consider
 260                  * @param n_j degree of j
 261                  * @param DFx which array to fill (DF1 or DF2)
 262                  */
 263                 private void computeAlignmentP1(int i, int s, int m_i, int j, int t, int n_j, int DFx) {
 264                         /**
 265                          * DFL[pr][qr] is D(F1[i_s, i_p], F2[j_t, j_q])
 266                          * where p=s+pr-1 and q=t+qr-1 (ie. pr=p-s+1 and qr=q-t+1)
 267                          * By convention, F1[i_s, i_{s-1}] and F2[j_t, j_{t-1}] are the
 268                          * empty forests.
 269                          * Said differently, DFL[pr][qr] is the distance between the forest
 270                          * of the pr first children of i, starting with child s
 271                          * (first child is s = 0), and the forest of the qr first children
 272                          * of j, starting with child t (first child is t = 0).
 273                          * This array is allocated for a fixed value of (i,j,s,t).
 274                          */
 275                         float[][] DFL;
 276
 277                         /**
 278                          * Same shape as DFL, but to remember which term gave the min,
 279                          * so that we can later compute the alignment.
 280                          */
 281                         byte[][] DFLDecisions1;
 282                         short[][] DFLDecisions2;
 283
 284                         DFL = new float[m_i-s+2][n_j-t+2];
 285                         DFL[0][0] = 0; // D(empty forest, empty forest) = 0
 286
 287                         DFLDecisions1 = new byte[m_i-s+2][n_j-t+2];
 288                         DFLDecisions2 = new short[m_i-s+2][n_j-t+2];
 289
 290                         // Compute indexes of i_s and j_t because we will need them
 291                         int i_s = m_i != 0 ? treeData1.children[i][s] : -1;
 292                         int j_t = n_j != 0 ? treeData2.children[j][t] : -1;
 293
 294                         for (int p=s; p<m_i; p++) {
 295                                 DFL[p-s+1][0] = DFL[p-s][0] + DET1[treeData1.children[i][p]];
 296                         }
 297
 298                         for (int q=t; q<n_j; q++) {
 299                                 DFL[0][q-t+1] = DFL[0][q-t] + DET2[treeData2.children[j][q]];
 300                         }
 301
 302                         for (int p=s; p<m_i; p++) {
 303                                 int i_p = treeData1.children[i][p];
 304                                 for (int q=t; q<n_j; q++) {
 305                                         int j_q = treeData2.children[j][q];
 306
 307                                         float min = Float.POSITIVE_INFINITY;
 308                                         int decision1 = -1;
 309                                         int decision2 = -1;
 310
 311                                         // Lemma 3 - Case: We delete the rightmost tree of T1
 312                                         {
 313                                                 float minCandidate = DFL[p-s][q-t+1] + DET1[i_p];
 314                                                 if (minCandidate < min) {
 315                                                         min = minCandidate;
 316                                                         decision1 = 1;
 317                                                 }
 318                                         }
 319
 320                                         // Lemma 3 - Case: We insert the rightmost tree of T2 (symmetric of previous case)
 321                                         {
 322                                                 float minCandidate = DFL[p-s+1][q-t] + DET2[j_q];
 323                                                 if (minCandidate < min) {
 324                                                         min = minCandidate;
 325                                                         decision1 = 2;
 326                                                 }
 327                                         }
 328
 329                                         // Lemma 3 - Case: Align rightmost trees with each other
 330                                         {
 331                                                 float minCandidate =
 332                                                         DFL[p-s][q-t] + DT [i_p] [j_q];
 333                                                 if (minCandidate < min) {
 334                                                         min = minCandidate;
 335                                                         decision1 = 3;
 336                                                 }
 337                                         }
 338
 339                                         // Lemma 3 - Case: We cut the T1 forest and match the first part
 340                                         // with the T2 forest except the rightmost tree, and we match the second
 341                                         // part with the T2 rightmost tree's forest of children
 342                                         {
 343                                                 float minCandidate = Float.POSITIVE_INFINITY;
 344                                                 int best_k = -1;
 345                                                 for (int k=s; k<p; k++) {
 346                                                         float d = DFL[k-s][q-t]
 347                                                                  + DF2 [j_q] [treeData1.children[i][k]] [p-k+1] [treeData2.degrees[j_q]];
 348                                                         if (d < minCandidate) {
 349                                                                 minCandidate = d;
 350                                                                 best_k = k;
 351                                                         }
 352                                                 }
 353                                                 minCandidate += DL[treeData1.size][j_q];
 354                                                 if (minCandidate < min) {
 355                                                         min = minCandidate;
 356                                                         decision1 = 4;
 357                                                         decision2 = best_k;
 358                                                 }
 359                                         }
 360
 361                                         // Lemma 3 - Case: Syemmetric of preivous case
 362                                         {
 363                                                 float minCandidate = Float.POSITIVE_INFINITY;
 364                                                 int best_k = -1;
 365                                                 for (int k=t; k<q; k++) {
 366                                                         float d = DFL[p-s][k-t]
 367                                                                  + DF1 [i_p] [treeData2.children[j][k]] [treeData1.degrees[i_p]] [q-k+1];
 368                                                         if (d < minCandidate) {
 369                                                                 minCandidate = d;
 370                                                                 best_k = k;
 371                                                         }
 372                                                 }
 373                                                 minCandidate += DL[i_p][treeData2.size];
 374                                                 if (minCandidate < min) {
 375                                                         min = minCandidate;
 376                                                         decision1 = 5;
 377                                                         decision2 = best_k;
 378                                                 }
 379                                         }
 380
 381                                         DFL[p-s+1][q-t+1] = min;
 382                                         DFLDecisions1[p-s+1][q-t+1] = (byte) decision1;
 383                                         DFLDecisions2[p-s+1][q-t+1] = (short) decision2;
 384                                 }
 385                         }
 386
 387                         // Copy references to DFL to persistent arrays
 388                         if (DFx == 2) {
 389                                 DF2[j][i_s] = DFL;
 390                                 DF2Decisions1[j][i_s] = DFLDecisions1;
 391                                 DF2Decisions2[j][i_s] = DFLDecisions2;
 392                         } else {
 393                                 DF1[i][j_t] = DFL;
 394                                 DF1Decisions1[i][j_t] = DFLDecisions1;
 395                                 DF1Decisions2[i][j_t] = DFLDecisions2;
 396                         }
 397
 398                 }
 399
 400                 public float align() throws TreeAlignException {
 401                         (new ConvertTreeToArray<ValueType1>(treeData1)).convert();
 402                         (new ConvertTreeToArray<ValueType2>(treeData2)).convert();
 403
 404                         // Allocate necessary arrays
 405                         DT = new float[treeData1.size][treeData2.size];
 406                         DTDecisions1 = new byte[treeData1.size][treeData2.size];
 407                         DTDecisions2 = new short[treeData1.size][treeData2.size];
 408                         DL = new float[treeData1.size+1][treeData2.size+1];
 409                         DET1 = new float[treeData1.size];
 410                         DET2 = new float[treeData2.size];
 411                         DEF1 = new float[treeData1.size];
 412                         DEF2 = new float[treeData2.size];
 413                         DF1 = new float[treeData1.size][treeData2.size][][];
 414                         DF1Decisions1 = new byte[treeData1.size][treeData2.size][][];
 415                         DF1Decisions2 = new short[treeData1.size][treeData2.size][][];
 416                         DF2 = new float[treeData2.size][treeData1.size][][];
 417                         DF2Decisions1 = new byte[treeData2.size][treeData1.size][][];
 418                         DF2Decisions2 = new short[treeData2.size][treeData1.size][][];
 419
 420                         DL[treeData1.size][treeData2.size] = (float) labelDist.f(null, null);
 421
 422                         for (int i=0; i<treeData1.size; i++) {
 423                                 int m_i = treeData1.degrees[i];
 424                                 DEF1[i] = 0;
 425                                 for (int k=0; k<m_i; k++) {
 426                                         DEF1[i] += DET1[treeData1.children[i][k]];
 427                                 }
 428                                 DL[i][treeData2.size] = (float) labelDist.f((ValueType1) treeData1.values[i], null);
 429                                 DET1[i] = DEF1[i] + DL[i][treeData2.size];
 430                         }
 431
 432                         for (int j=0; j<treeData2.size; j++) {
 433                                 int n_j = treeData2.degrees[j];
 434                                 DEF2[j] = 0;
 435                                 for (int k=0; k<n_j; k++) {
 436                                         DEF2[j] += DET2[treeData2.children[j][k]];
 437                                 }
 438                                 DL[treeData1.size][j] = (float) labelDist.f(null, (ValueType2) treeData2.values[j]);
 439                                 DET2[j] = DEF2[j] + DL[treeData1.size][j];
 440                         }
 441
 442
 443                         for (int i=0; i<treeData1.size; i++) {
 444                                 int m_i = treeData1.degrees[i];
 445                                 for (int j=0; j<treeData2.size; j++) {
 446                                         int n_j = treeData2.degrees[j];
 447
 448                                         // Precompute f(value(i), value(j)) and keep the result
 449                                         // to avoid calling f on the same values several times.
 450                                         // This is important in case the computation of f takes
 451                                         // long.
 452                                         DL[i][j] = (float) labelDist.f((ValueType1) treeData1.values[i], (ValueType2) treeData2.values[j]);
 453
 454                                         for (int s=0; s<m_i; s++) {
 455                                                 computeAlignmentP1(i, s, m_i, j, 0, n_j, 2);
 456                                         }
 457
 458                                         for (int t=0; t<n_j; t++) {
 459                                                 computeAlignmentP1(i, 0, m_i, j, t, n_j, 1);
 460                                         }
 461
 462                                         DT[i][j] = Float.POSITIVE_INFINITY;
 463                                         // Lemma 2 - Case: Root is (blank, j)
 464                                         {
 465                                                 float minCandidate = Float.POSITIVE_INFINITY;
 466                                                 int best_r = -1;
 467                                                 for (int r=0; r<n_j; r++) {
 468                                                         float d = DT[i][treeData2.children[j][r]] - DET2[treeData2.children[j][r]];
 469                                                         if (d < minCandidate) {
 470                                                                 minCandidate = d;
 471                                                                 best_r = r;
 472                                                         }
 473                                                 }
 474                                                 minCandidate += DET2[j];
 475                                                 if (minCandidate < DT[i][j]) {
 476                                                         DT[i][j] = minCandidate;
 477                                                         DTDecisions1[i][j] = 1;
 478                                                         DTDecisions2[i][j] = (short) best_r;
 479                                                 }
 480                                         }
 481                                         // Lemma 2 - Case: Root is (i, blank)
 482                                         {
 483                                                 float minCandidate = Float.POSITIVE_INFINITY;
 484                                                 int best_r = -1;
 485                                                 for (int r=0; r<m_i; r++) {
 486                                                         float d = DT[treeData1.children[i][r]][j] - DET1[treeData1.children[i][r]];
 487                                                         if (d < minCandidate) {
 488                                                                 minCandidate = d;
 489                                                                 best_r = r;
 490                                                         }
 491                                                 }
 492                                                 minCandidate += DET1[i];
 493                                                 if (minCandidate < DT[i][j]) {
 494                                                         DT[i][j] = minCandidate;
 495                                                         DTDecisions1[i][j] = 2;
 496                                                         DTDecisions2[i][j] = (short) best_r;
 497                                                 }
 498                                         }
 499                                         // Lemma 2 - Case: Root is (i,j)
 500                                         {
 501                                                 float minCandidate;
 502                                                 if (n_j != 0) {
 503                                                         minCandidate = DF1 [i] [treeData2.children[j][0]] [m_i] [n_j];
 504                                                 } else {
 505                                                         if (m_i != 0) {
 506                                                                 minCandidate = DF2 [j] [treeData1.children[i][0]] [m_i] [n_j];
 507                                                         } else {
 508                                                                 minCandidate = 0; // D(empty forest, empty forest) = 0
 509                                                         }
 510                                                 }
 511                                                 minCandidate += DL[i][j];
 512                                                 if (minCandidate < DT[i][j]) {
 513                                                         DT[i][j] = minCandidate;
 514                                                         DTDecisions1[i][j] = 3;
 515                                                 }
 516                                         }
 517
 518
 519                                 }
 520                         }
 521
 522
 523                         // We return the distance beetween T1[root] and T2[root].
 524                         return DT[treeData1.size-1][treeData2.size-1];
 525                 }
 526
 527                 public Aligner(Tree<ValueType1> T1, Tree<ValueType2> T2) {
 528                         treeData1 = new TreeData<ValueType1>();
 529                         treeData1.tree = T1;
 530                         treeData2 = new TreeData<ValueType2>();
 531                         treeData2.tree = T2;
 532                 }
 533
 534                 /** Align F1[i_s,i_p] with F2[j_t,j_q].
 535                  * If p = s-1, by convention it means F1[i_s,i_p] = empty forest.
 536                  * Idem for q=t-1.
 537                  */
 538                 private List<Tree<AlignedNode<ValueType1,ValueType2>>> computeForestAlignment(int i, int s, int p, int j, int t, int q) {
 539                         if (p == s-1) { // left forest is the empty forest
 540                                 List<Tree<AlignedNode<ValueType1,ValueType2>>> result = new ArrayList<Tree<AlignedNode<ValueType1,ValueType2>>>();
 541                                 for (int k=t; k<=q; k++) {
 542                                         result.add(treeInserted(treeData2.children[j][k]));
 543                                 }
 544                                 return result;
 545                         } else {
 546                                 if (q == t-1) { // right forest is the empty forest
 547                                         List<Tree<AlignedNode<ValueType1,ValueType2>>> result = new ArrayList<Tree<AlignedNode<ValueType1,ValueType2>>>();
 548                                         for (int k=s; k<=p; k++) {
 549                                                 result.add(treeDeleted(treeData1.children[i][k]));
 550                                         }
 551                                         return result;
 552                                 } else { // both forests are non-empty
 553                                         int decision1, k;
 554                                         if (s == 0) {
 555                                                 decision1 =
 556                                                         DF1Decisions1 [i] [treeData2.children[j][t]] [p-s+1] [q-t+1];
 557                                                 k =
 558                                                         DF1Decisions2 [i] [treeData2.children[j][t]] [p-s+1] [q-t+1];
 559                                         } else if (t == 0) {
 560                                                 decision1 =
 561                                                         DF2Decisions1 [j] [treeData1.children[i][s]] [p-s+1] [q-t+1];
 562                                                 k =
 563                                                         DF2Decisions2 [j] [treeData1.children[i][s]] [p-s+1] [q-t+1];
 564                                         } else {
 565                                                 throw (new Error("TreeAlignSymmetric bug: both s and t are non-zero"));
 566                                         }
 567                                         switch (decision1) {
 568                                         case 1:
 569                                         {
 570                                                 List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
 571                                                 result = computeForestAlignment(i, s, p-1, j, t, q);
 572                                                 result.add(treeDeleted(treeData1.children[i][p]));
 573                                                 return result;
 574                                         }
 575                                         case 2:
 576                                         {
 577                                                 List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
 578                                                 result = computeForestAlignment(i, s, p, j, t, q-1);
 579                                                 result.add(treeInserted(treeData2.children[j][q]));
 580                                                 return result;
 581                                         }
 582                                         case 3:
 583                                         {
 584                                                 List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
 585                                                 result = computeForestAlignment(i, s, p-1, j, t, q-1);
 586                                                 result.add(computeTreeAlignment(treeData1.children[i][p], treeData2.children[j][q]));
 587                                                 return result;
 588                                         }
 589                                         case 4:
 590                                         {
 591                                                 List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
 592                                                 result = computeForestAlignment(i, s, k-1, j, t, q-1);
 593
 594                                                 int j_q = treeData2.children[j][q];
 595                                                 Tree<AlignedNode<ValueType1,ValueType2>> insertedNode = new Tree<AlignedNode<ValueType1,ValueType2>>();
 596                                                 AlignedNode<ValueType1,ValueType2> insertedNodeValue = new AlignedNode<ValueType1,ValueType2>();
 597                                                 insertedNodeValue.setLeftNode(null);
 598                                                 insertedNodeValue.setRightNode((Tree<ValueType2>) treeData2.nodes[j_q]);
 599                                                 insertedNode.setValue(insertedNodeValue);
 600
 601                                                 insertedNode.replaceChildrenListBy(computeForestAlignment(i, k, p, j_q, 0, treeData2.degrees[j_q]-1));
 602
 603                                                 result.add(insertedNode);
 604
 605                                                 return result;
 606                                         }
 607                                         case 5:
 608                                         {
 609                                                 List<Tree<AlignedNode<ValueType1,ValueType2>>> result;
 610                                                 result = computeForestAlignment(i, s, p-1, j, t, k-1);
 611
 612                                                 int i_p = treeData1.children[i][p];
 613                                                 Tree<AlignedNode<ValueType1,ValueType2>> deletedNode = new Tree<AlignedNode<ValueType1,ValueType2>>();
 614                                                 AlignedNode<ValueType1,ValueType2> deletedNodeValue = new AlignedNode<ValueType1,ValueType2>();
 615                                                 deletedNodeValue.setLeftNode((Tree<ValueType1>) treeData1.nodes[i_p]);
 616                                                 deletedNodeValue.setRightNode(null);
 617                                                 deletedNode.setValue(deletedNodeValue);
 618
 619                                                 deletedNode.replaceChildrenListBy(computeForestAlignment(i_p, 0, treeData1.degrees[i_p]-1, j, k, q));
 620
 621                                                 result.add(deletedNode);
 622
 623                                                 return result;
 624                                         }
 625                                         default:
 626                                                 throw (new Error("TreeAlign: decision1 = " + decision1));
 627                                         }
 628                                 }
 629                         }
 630                 }
 631
 632                 /**
 633                  * Align T1[i] with the empty tree.
 634                  * @return the alignment
 635                  */
 636                 private Tree<AlignedNode<ValueType1,ValueType2>> treeDeleted(int i) {
 637                         Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
 638                         AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
 639                         alignedNode.setLeftNode(treeData1.nodes[i]);
 640                         alignedNode.setRightNode(null);
 641                         root.setValue(alignedNode);
 642                         for (int r = 0; r<treeData1.degrees[i]; r++) {
 643                                 root.getChildren().add(treeDeleted(treeData1.children[i][r]));
 644                         }
 645                         return root;
 646                 }
 647
 648                 /**
 649                  * Align the empty tree with T2[j].
 650                  * @return the alignment
 651                  */
 652                 private Tree<AlignedNode<ValueType1,ValueType2>> treeInserted(int j) {
 653                         Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
 654                         AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
 655                         alignedNode.setLeftNode(null);
 656                         alignedNode.setRightNode(treeData2.nodes[j]);
 657                         root.setValue(alignedNode);
 658                         for (int r = 0; r<treeData2.degrees[j]; r++) {
 659                                 root.getChildren().add(treeInserted(treeData2.children[j][r]));
 660                         }
 661                         return root;
 662                 }
 663
 664                 private Tree<AlignedNode<ValueType1,ValueType2>> computeTreeAlignment(int i, int j) {
 665                         switch (DTDecisions1[i][j]) {
 666                         case 1:
 667                         {
 668                                 Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
 669
 670                                 // Compute the value of the node
 671                                 AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
 672                                 alignedNode.setLeftNode(null);
 673                                 alignedNode.setRightNode(treeData2.nodes[j]);
 674                                 root.setValue(alignedNode);
 675
 676                                 // Compute the children
 677                                 for (int r = 0; r<treeData2.degrees[j]; r++) {
 678                                         if (r == DTDecisions2[i][j]) {
 679                                                 root.getChildren().add(computeTreeAlignment(i, treeData2.children[j][r]));
 680                                         } else {
 681                                                 root.getChildren().add(treeInserted(treeData2.children[j][r]));
 682                                         }
 683                                 }
 684                                 return root;
 685                         }
 686                         case 2:
 687                         {
 688                                 Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
 689
 690                                 // Compute the value of the node
 691                                 AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
 692                                 alignedNode.setLeftNode(treeData1.nodes[i]);
 693                                 alignedNode.setRightNode(null);
 694                                 root.setValue(alignedNode);
 695
 696                                 // Compute the children
 697                                 for (int r = 0; r<treeData1.degrees[i]; r++) {
 698                                         if (r == DTDecisions2[i][j]) {
 699                                                 root.getChildren().add(computeTreeAlignment(treeData1.children[i][r], j));
 700                                         } else {
 701                                                 root.getChildren().add(treeDeleted(treeData1.children[i][r]));
 702                                         }
 703                                 }
 704                                 return root;
 705                         }
 706                         case 3:
 707                         {
 708                                 Tree<AlignedNode<ValueType1,ValueType2>> root = new Tree<AlignedNode<ValueType1,ValueType2>>();
 709
 710                                 // Compute the value of the node
 711                                 AlignedNode<ValueType1,ValueType2> alignedNode = new AlignedNode<ValueType1,ValueType2>();
 712                                 alignedNode.setLeftNode(treeData1.nodes[i]);
 713                                 alignedNode.setRightNode(treeData2.nodes[j]);
 714                                 root.setValue(alignedNode);
 715
 716                                 // Compute the children
 717                                 List<Tree<AlignedNode<ValueType1,ValueType2>>> children =
 718                                         computeForestAlignment(i, 0, treeData1.degrees[i]-1, j, 0, treeData2.degrees[j]-1);
 719                                 root.replaceChildrenListBy(children);
 720
 721                                 return root;
 722                         }
 723                         default:
 724                                 throw (new Error("TreeAlign: DTDecisions1[i][j] = " + DTDecisions1[i][j]));
 725                         }
 726                 }
 727
 728                 public Tree<AlignedNode<ValueType1,ValueType2>> computeAlignment() {
 729                         return computeTreeAlignment(treeData1.size-1, treeData2.size-1);
 730                 }
 731
 732         }
 733
 734
 735         /**
 736          * Align T1 with T2, computing both the distance and the alignment.
 737          * Time:  O(|T1|*|T2|*(deg(T1)+deg(T2))^2)
 738          * Space: O(|T1|*|T2|*(deg(T1)+deg(T2)))
 739          * Average (over possible trees) time: O(|T1|*|T2|)
 740          * @param T1 The first tree.
 741          * @param T2 The second tree.
 742          * @return The distance and the alignment.
 743          * @throws TreeAlignException
 744          */
 745         public TreeAlignResult<ValueType1, ValueType2> align(Tree<ValueType1> T1, Tree<ValueType2> T2) throws TreeAlignException {
 746                 TreeAlignResult<ValueType1, ValueType2> result = new TreeAlignResult<ValueType1, ValueType2>();
 747                 Aligner aligner = new Aligner(T1, T2);
 748                 result.setDistance(aligner.align());
 749                 result.setAlignment(aligner.computeAlignment());
 750                 return result;
 751         }
 752
 753
 754         /**
 755          * Takes a alignment, and compute the distance between the two
 756          * original trees. If you have called align(), the result object already
 757          * contains the distance D and the alignment A. If you call
 758          * distanceFromAlignment on the alignment A it will compute the distance D.
 759          */
 760         public float distanceFromAlignment(Tree<AlignedNode<ValueType1,ValueType2>> alignment) {
 761                 Tree<ValueType1> originalT1Node;
 762                 Tree<ValueType2> originalT2Node;
 763                 originalT1Node = alignment.getValue().getLeftNode();
 764                 originalT2Node = alignment.getValue().getRightNode();
 765                 float d = (float) labelDist.f(
 766                                 originalT1Node != null ? originalT1Node.getValue() : null,
 767                                 originalT2Node != null ? originalT2Node.getValue() : null);
 768                 for (Tree<AlignedNode<ValueType1,ValueType2>> child: alignment.getChildren()) {
 769                         d += distanceFromAlignment(child);
 770                 }
 771                 return d;
 772         }
 773
 774
 775 }