maxsrcext.java

A program to find frequent molecular substructures and discriminative fragments in a database of mol

      changed = (k1 != frag.idx);
      for (i = 0; i < k1; i++)  /* copy up to first insertion point */
        this.bonds[i] = mol.bonds[i];
      this.bonds[k1++] = x;     /* store the first ring bond */
      k2 = frag.ris[frag.ris.length-2];
      while (k1 < k2)           /* copy up to second insertion point */
        this.bonds[k1++] = mol.bonds[i++];
      if (k2 > 0) {             /* store the second/last ring bond */
        this.bonds[k1++] = mol.bonds[n-1];
        if (k2 != n-1) changed = true;
      }                         /* update whether fragment is changed */
      k2 = frag.ris[frag.ris.length-1];
      while (k1 <= k2)          /* copy remaining equivalent bonds */
        this.bonds[k1++] = mol.bonds[i++];
      for (k1 = n = 0; k1 <= k2; k1++) {
        b = this.bonds[k1];     /* traverse bonds in the fixed part */
        b.mark = k1;            /* mark each bond as processed */
        if      (b.src.mark < 0) this.atoms[b.src.mark = ++n] = b.src;
        else if (b.dst.mark < 0) this.atoms[b.dst.mark = ++n] = b.dst;
      } }                       /* number and collect the atoms */
    else {                      /* if insertion position is unknown */
      for (n = i = 0; i < frag.idx; i++) {
        b = mol.bonds[i];       /* traverse the bonds ascendingly */
        if (((x.src.mark >= 0)  /* if incident to the marked part */
        ||   (x.dst.mark >= 0)) /* and no greater than the next bond */
        &&  (this.compareBond(x, b, n+1) < 0))
          break;                /* insertion position is found */
        this.bonds[i] = b;      /* copy the bond to the buffer */
        b.mark = i;             /* mark the bond as processed */
        if      (b.src.mark < 0) this.atoms[b.src.mark = ++n] = b.src;
        else if (b.dst.mark < 0) this.atoms[b.dst.mark = ++n] = b.dst;
      }                         /* mark and collect fixed atoms */
      this.bonds[x.mark = i] = x;
      changed = (i != frag.idx);/* store the first ring bond */
      k2 = i; k1 = i+1;         /* and mark it as processed */
      if      (x.src.mark < 0) this.atoms[x.src.mark = ++n] = x.src;
      else if (x.dst.mark < 0) this.atoms[x.dst.mark = ++n] = x.dst;
    }                           /* mark and collect fixed atoms */
    while (k1 < mol.bondcnt) {  /* copy the remaining bonds */
      if (i == frag.idx) i++;   /* except the first ring bond */
      this.bonds[k1++] = mol.bonds[i++];
    }                           /* (complete the bond vector) */
    this.src = n;               /* note the highest atom index */
    this.makeWord(this.bonds, k2+1);
    this.word[k2*4+5] = MAXCODE;/* build the initial code word */
    if (this.makeCanonic(k2+1, 0, n+1))
      changed = true;           /* make the fragment canonic */
    k1 = frag.ris[frag.ris.length-3];
    if (k1 <= frag.base.idx)    /* determine the index */
      k1 = frag.base.idx +1;    /* of the last fixed bond */
    n = mol.bondcnt;            /* mark the fixed and the new bonds */
    for (i = n; --i > k1; )        this.bonds[i].mark = 0;
    for (++i;   --i >= 0; )        this.bonds[i].mark = FIXED;
    for (i = n; --i >= frag.idx; ) mol.bonds[i].mark  = FIXED;
    for (i = n; --i >= 0; ) {   /* traverse all bonds and */
      b   = this.bonds[i];      /* get their ring flags */
      rgs = b.flags & Bond.RINGS;
      if (rgs == 0)             /* mark non-ring bonds as fixed, */
        b.mark = FIXED;         /* since they can never be removed */
      for (cur = 1; rgs != 0; cur <<= 1)
        if ((rgs & cur) != 0) { rgs &= ~cur; b.mark++; }
      this.word[i] = b.mark;    /* count the number of ring flags */
    }                           /* and buffer the bond markers */
    while (++k1 < n) {          /* traverse the non-fixed bonds */
      if ((this.bonds[k1].mark & FIXED) != 0) continue;
      for (i = n; --i >= 0; )   /* restore the bond markers */
        this.bonds[i].mark = this.word[i];
      if (this.removable(this.bonds[k1]))
        return false;           /* if a bond can be removed, then */
    }                           /* rings were added in a wrong order */
    if (!changed) return true;  /* if fragment is unchanged, abort */
    mol.map(this);              /* map the fragment (copy changes) */
    frag.map(this);             /* and map the embeddings accordingly */
    return true;                /* return 'adaptation successful' */
  }  /* adaptRing() */

  /*------------------------------------------------------------------*/

  private void makeWord (Bond[] bvec, int bondcnt)
  {                             /* --- construct (part of) code word */
    int  i, k;                  /* loop variables, buffers */
    Bond b;                     /* to traverse the bonds */

    b = bvec[0];                /* get first bond and root atom */
    this.word[0] = (b.src.mark < b.dst.mark) ? b.src.type : b.dst.type;
    for (i = k = 0; i < bondcnt; i++) {
      b = bvec[i];              /* traverse the molecule's bonds */
      if (b.src.mark < b.dst.mark) {
        this.word[++k] = b.src.mark; /* if "forward" bond */
        this.word[++k] = b.type;     /* start with source atom */
        this.word[++k] = b.dst.type;
        this.word[++k] = b.dst.mark; }
      else {                         /* if "backward" bond */
        this.word[++k] = b.dst.mark; /* start with destination atom */
        this.word[++k] = b.type;
        this.word[++k] = b.src.type;
        this.word[++k] = b.src.mark;
      }                         /* describe a bond of the molecule */
    }                           /* (four characters per bond) */
  }  /* makeWord() */

  /*------------------------------------------------------------------*/

  protected int makeWord (Molecule mol, int bondcnt)
  {                             /* --- construct (part of) code word */
    int n = (bondcnt << 2) +1;  /* compute number of characters */ 
    if (n > this.word.length)   /* if the word gets too long, */
      this.word = new int[n];   /* create a new buffer */
    for (int i = mol.atomcnt; --i >= 0; )
      mol.atoms[i].mark = i;    /* number the atoms of the molecule */
    if (bondcnt <= 0) {         /* if there are no bonds, abort */
      this.word[0] = mol.atoms[0].type; return 1; }
    this.makeWord(mol.bonds, bondcnt);
    return n;                   /* return the number of characters */
  }  /* makeWord() */

  /*------------------------------------------------------------------*/

  private int compareWord (Bond[] bvec, int bondcnt)
  {                             /* --- compare bonds to code word */
    int  i, k;                  /* loop variables */
    Bond b;                     /* to traverse the bonds */
    Atom s, d;                  /* to traverse the atoms */

    b = bvec[0];                /* compare the type of the root atom */
    s = (b.src.mark < b.dst.mark) ? b.src : b.dst;
    if (s.type < this.word[0]) return -1;
    if (s.type > this.word[0]) return +1;
    for (i = k = 0; i < bondcnt; i++) {
      b = bvec[i];              /* traverse the molecule's bonds */
      s = b.src; d = b.dst;     /* get the source and dest. atoms */
      if (s.mark > d.mark) { s = d; d = b.src; }
      if (s.mark < this.word[++k]) return -1;
      if (s.mark > this.word[  k]) return +1;
      if (b.type < this.word[++k]) return -1;
      if (b.type > this.word[  k]) return +1;
      if (d.type < this.word[++k]) return -1;
      if (d.type > this.word[  k]) return +1;
      if (d.mark < this.word[++k]) return -1;
      if (d.mark > this.word[  k]) return +1;
    }                           /* return sign of difference */
    return 0;                   /* otherwise return 'equal' */
  }  /* compareWord() */

  /*------------------------------------------------------------------*/

  protected int compareWord (Molecule mol, int bondcnt)
  {                             /* --- compare molecule to code word */
    for (int i = mol.atomcnt; --i >= 0; )
      mol.atoms[i].mark = i;    /* number the atoms of the molecule */
    return this.compareWord(mol.bonds, bondcnt);
  }  /* compareWord() */        /* compare the bonds of the molecule */

  /*------------------------------------------------------------------*/

  protected String makeString (Molecule mol, boolean create)
  {                             /* --- print a molecule's code word */
    int          i, k, n;       /* loop variable, buffers */
    StringBuffer s;             /* created description */

    if (create)                 /* construct molecule's code word */
      this.makeWord(mol, mol.bondcnt);
    k = this.word[0];           /* get and decode type of root atom */
    if (mol.map != null) k = mol.map.decode(k);
    s = new StringBuffer(Atom.names[k & Atom.TYPEMASK]);
    n = mol.bondcnt << 2;       /* get the number of characters */
    for (i = 0; i < n; ) {      /* traverse the characters */
      s.append("|" +this.word[++i]);   /* source atom index */
      s.append(Bond.names[this.word[++i] & Bond.TYPEMASK]);
      k = this.word[++i];       /* bond and atom type */
      if (mol.map != null) k = mol.map.decode(k);
      s.append(Atom.names[k & Atom.TYPEMASK]);
      s.append(" " +this.word[++i]);   /* destination atom index */
    }                           /* store the edge descriptions */
    return s.toString();        /* return created string description */
  }  /* makeString() */

  /*------------------------------------------------------------------*/

  protected int compareBond (Bond b1, Bond b2, int next)
  {                             /* --- compare two bonds */
    Atom s1, d1, s2, d2;        /* source and destination atoms */
    int  i1, i2;                /* indices of the destination atoms */

    s1 = b1.src; d1 = b1.dst;   /* get atoms of first bond */
    if ((d1.mark >= 0) && (d1.mark < s1.mark)) {
      s1 = d1; d1 = b1.src; }   /* exchange atoms if necessary */
    s2 = b2.src; d2 = b2.dst;   /* get atoms of second bond */
    if ((d2.mark >= 0) && (d2.mark < s2.mark)) {
      s2 = d2; d2 = b2.src; }   /* exchange atoms if necessary */
    if (s1.mark < s2.mark) return -1;  /* compare the indices */
    if (s1.mark > s2.mark) return +1;  /* of the source atoms */
    if (b1.type < b2.type) return -1;  /* compare the types */
    if (b1.type > b2.type) return +1;  /* of the two bonds */
    if (d1.type < d2.type) return -1;  /* compare the types */ 
    if (d1.type > d2.type) return +1;  /* of the destination atoms */
    i1 = (d1.mark >= 0) ? d1.mark : next;
    i2 = (d2.mark >= 0) ? d2.mark : next;
    if (i1      < i2)      return -1;  /* compare the indices */
    if (i1      > i2)      return +1;  /* of the destination atoms */
    return 0;                   /* otherwise the bonds are equal */
  }  /* compareBond() */

}  /* class MaxSrcExt */