binaries/src/ViennaRNA/RNAforester/src/unpairs.c

   1 #include "wmatch.h"
   2
   3 /* Expands a blossom.  Fixes up LINK and MATE. */
   4
   5 void UNPAIR (int oldbase, int oldmate)
   6 {   int e, newbase, u;
   7
   8 #ifdef DEBUG
   9     printf("Unpair oldbase, oldmate=%d %d\n",oldbase, oldmate);
  10 #endif
  11
  12     UNLINK (oldbase);
  13     newbase = BMATE (oldmate);
  14     if (newbase != oldbase) {
  15         LINK [oldbase] = -DUMMYEDGE;
  16         REMATCH (newbase, MATE[oldbase]);
  17         if (f == LASTEDGE[1])
  18             LINK[secondmate] = -LASTEDGE[2];
  19         else LINK[secondmate] = -LASTEDGE[1];
  20         }
  21     e = LINK[oldmate];
  22     u = BEND (OPPEDGE (e));
  23     if (u == newbase) {
  24         POINTER (newbase, oldmate, e);
  25         return;
  26         }
  27     LINK[BMATE (u)] = -e;
  28     do {
  29         e = -LINK[u];
  30         v = BMATE (u);
  31         POINTER (u, v, -LINK[v]);
  32         u = BEND (e);
  33     } while (u != newbase);
  34     e = OPPEDGE (e);
  35     POINTER (newbase, oldmate, e);
  36 }
  37
  38
  39 /* changes the matching along an alternating path */
  40 /* firstmate is the first base vertex on the path */
  41 /* edge e is the new matched edge for firstmate   */
  42
  43 void REMATCH (int firstmate, int e)
  44 {
  45 #ifdef DEBUG
  46      printf("Rematch firstmate=%d e=%d-%d\n",firstmate, END[OPPEDGE(e)], END[e]);
  47 #endif
  48
  49     MATE[firstmate] = e;
  50     nexte = -LINK[firstmate];
  51     while (nexte != DUMMYEDGE) {
  52         e = nexte;
  53         f = OPPEDGE (e);
  54         firstmate = BEND (e);
  55         secondmate = BEND (f);
  56         nexte = -LINK[firstmate];
  57         LINK[firstmate] = -MATE[secondmate];
  58         LINK[secondmate] = -MATE[firstmate];
  59         MATE[firstmate] = f;
  60         MATE[secondmate] = e;
  61         }
  62 }
  63
  64
  65 /* unlinks subblossoms in a blossom.  oldbase is the base of the blossom to */
  66 /* be unlinked. */
  67
  68 void UNLINK (int oldbase)
  69 {   int k, j=1;
  70
  71 #ifdef DEBUG
  72     printf("Unlink oldbase=%d\n",oldbase);
  73 #endif
  74
  75     i = NEXTVTX[oldbase];
  76     newbase = NEXTVTX[oldbase];
  77     nextbase = NEXTVTX[LASTVTX[newbase]];
  78     e = LINK[nextbase];
  79 UL2:
  80     do {
  81         nextedge = OPPEDGE (LINK[newbase]);
  82         for (k=1; k <= 2; ++k) {
  83             LINK[newbase] = -LINK[newbase];
  84             BASE[i] = newbase;
  85             i = NEXTVTX[i];
  86             while (i != nextbase) {
  87                 BASE[i] = newbase;
  88                 i = NEXTVTX[i];
  89                 }
  90             newbase = nextbase;
  91             nextbase = NEXTVTX[LASTVTX[newbase]];
  92             }
  93         } while (LINK[nextbase] == nextedge);
  94     if (j==1) {
  95         LASTEDGE[1] = nextedge;
  96         j++;
  97         nextedge = OPPEDGE (e);
  98         if (LINK[nextbase] == nextedge) {
  99             goto UL2;
 100             }
 101         }
 102     LASTEDGE[2] = nextedge;
 103
 104     if (BASE[LASTVTX[oldbase]] == oldbase)
 105         NEXTVTX[oldbase] = newbase;
 106     else {
 107         NEXTVTX[oldbase] = DUMMYVERTEX;
 108         LASTVTX[oldbase] = oldbase;
 109         }
 110 }
 111
 112