fragment.java

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

      emb.markId(); l2 = null;  /* mark embedding in the molecule */
      for (i = emb.atoms.length; --i >= 0; ) {
        a = emb.atoms[i];       /* traverse the embedding's atoms */
        for (k = a.bondcnt; --k >= 0; ) {
          b = a.bonds[k];       /* traverse the unmarked bonds */
          if (b.mark >= 0) continue;
          d = (b.src != a) ? b.src : b.dst;
          if ((mna <= 0) && (d.mark < 0))
            continue;           /* if a new atom is not allowed */
          if (((b.type & Bond.RINGBOND) == 0)
          ||  ((ext.mode & (Extension.RING|Miner.CLOSERINGS)) == 0))
            l3 = e = new ExtLE(a.mark, d.mark, b.type, d.type);
          else {                /* create single bond extension */
            l3 = e = this.rings(ext, a, b, d, mna);
            if (e == null) continue;
            while (e.succ != null) e = e.succ;
          }                     /* create ring extension(s) */
          e.succ = l2; l2 = l3; /* add the new list element(s) */
        }                       /* at the head of the extension list */
      }
      emb.unmark();             /* unmark the embedding again */
      if ((ext.mode & (Extension.RING|Miner.CLOSERINGS)) != 0)
        l2 = ExtLE.sort(l2);    /* sort new extensions if necessary */
      l1 = ExtLE.merge(l1, l2); /* merge the extension lists */
      emb = this.next();        /* (and remove duplicates) */
    } while ((emb != null) && (emb.mol == cur));

    /* --- check extensions in remaining molecules --- */
    while ((emb != null)        /* traverse remaining embeddings */
    &&     (l1  != null)) {     /* while there are extensions left */
      cur = emb.mol; l2 = null; /* note the next molecule */
      do {                      /* extension match loop */
        emb.markId();           /* mark embedding in the molecule */
        for (l3 = null; l1 != null; ) {
          e = l1; l1 = e.succ;  /* traverse unmatched extensions */
          a = emb.atoms[e.src]; /* get the extension's source atom */
          for (i = a.bondcnt; --i >= 0; ) {
            b = a.bonds[i];     /* traverse the unmarked bonds */
            if ((b.mark >= 0) || (b.type != e.bond))
              continue;         /* check the bond type */
            d = (b.src != a) ? b.src : b.dst;
            if ((d.type != e.atom)
            ||  (d.mark != e.dst))
              continue;         /* check dest. atom type and index */
            if ((e.ring == null)
            ||  this.match(e, a, b, d))
              break;            /* if there is a matching extension, */
          }                     /* abort the search loop */
          if (i >= 0) { e.succ = l2; l2 = e; }
          else        { e.succ = l3; l3 = e; }
        }                       /* distribute according to match */
        l1 = l3;                /* get unmatched extensions */
        emb.unmark();           /* unmark the embedding again */
        emb = this.next();      /* and go to the next embedding */
      } while ((emb != null) && (emb.mol == cur));
      l1 = l2;                  /* get list of potential extensions */
    }                           /* (may still match all molecules) */
    if (l1 != null)             /* if there are extensions left, */
      this.flgs &= ~CLOSED;     /* the fragment is not closed */
    return (l1 == null);        /* return whether fragment is closed */
  }  /* isClosed() */

  /*--------------------------------------------------------------------
  The above functions check whether a fragment is closed by checking
  all extensions not considered as children and determining whether
  any of them is possible in all molecules that contain the fragment.
  This is usually faster than doing substructure tests with the
  recorded closed fragments.
  --------------------------------------------------------------------*/

  protected boolean hasOpenRings (int min, int max)
  { return this.getAsMolecule().hasOpenRings(min, max); }

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

  protected boolean isUnclosable (Extension ext)
  { return ext.unclosable(this); }

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

  protected int mergeExts (Fragment[] exts, int cnt)
  {                             /* --- merge ring extensions */
    int       i, j, k, n, frst; /* loop variables, buffer */
    int       b, s, d, bt, dt;  /* bond and atom indices and types */
    Fragment  res, x;           /* to traverse the extensions */
    Embedding emb, e, c;        /* to traverse the embeddings */
    boolean   found;            /* whether compat. embwdding found */
    Bond[]    bvec;             /* buffer for reallocation */
    Atom[]    avec;             /* ditto */

    i = n = 0;                  /* init. the extension indices */
    while (i < cnt) {           /* section finding and merge loop */
      while ((i < cnt) && (exts[i].size <= 0))
        exts[n++] = exts[i++];  /* skip non-ring extensions */
      if (i >= cnt) break;      /* if all extensions processed, abort */
      x  = exts[frst = i++];    /* note the first ring extension */
      s  = x.src;               /* and its defining parameters */
      bt = x.list.bonds[b = x.idx].type;
      dt = x.list.atoms[d = x.dst].type;
      while ((i < cnt) && (exts[i].size >  0)
      &&     (exts[i].src                == s)
      &&     (exts[i].dst                == d)
      &&     (exts[i].list.bonds[b].type == bt)
      &&     (exts[i].list.atoms[d].type == dt))
        i++;                    /* find corresp. ring extensions */

      /* -- single element section -- */
      if (i -frst <= 1) {       /* if only one extension in section, */
        exts[n++] = x;          /* it can simply be kept and adapted */
        x.size    = 0;          /* set extension type to single bond */
        j         = b+1;        /* compute the new number of bonds */
        if (j >= x.list.bonds.length) /* if only one bond is added, */
          continue;             /* no fragment adaptation is needed */
        x.mol = null;           /* delete the molecule (invalid now) */
        x.ris = null;           /* and the ring atoms index vector */
        k = this.list.atoms.length;
        if (d >= k) k++;        /* compute the new number of atoms */
        if (k >= x.list.atoms.length) k = -1;               
        for (emb = x.list; emb != null; emb = emb.succ) {
          if (emb.bonds == null)/* traverse the unpacked embeddings */
            continue;           /* (packed ones need not be adapted) */
          System.arraycopy(emb.bonds, 0, bvec = new Bond[j], 0, j);
          emb.bonds = bvec;     /* shrink the bond vector */
          if (k >= 0) {         /* if there are additional atoms */
            System.arraycopy(emb.atoms, 0, avec = new Atom[k], 0, k);
            emb.atoms = avec;   /* shrink the atom vector */
          }                     /* (length must fit contents) */
          while ((emb.succ     != null)
          &&     (emb.base     == emb.succ.base)
          &&     (emb.bonds[b] == emb.succ.bonds[b]))
            emb.succ = emb.succ.succ;
        }                       /* remove equivalent embeddings */
        continue;               /* the extension has been adapted, */
      }                         /* so continue with the next */

      /* -- multiple element section -- */
      res = new Fragment(this, b, s, d);   /* create result fragment */
      if (d >= this.list.atoms.length)
        d = -1;                 /* adapt the destination atom marker */
      for (emb = this.first(); emb != null; emb = this.next()) {
        for (k = frst; k < i; k++) {
          e = exts[k].list;     /* traverse the extensions */
          if ((e != null) && (e.mol == emb.mol)
          &&  ((e.base == null) || (e.base == emb)))
            break;              /* if a compatible embedding */
        }                       /* can be found, abort the loop, */
        if (k >= i) continue;   /* otherwise skip the embedding */
        c = emb.extend(s, d, bt, dt);
        while (c != null) {     /* traverse candidate embeddings */
          found = false;        /* default: no corresp. embedding */
          for (k = frst; k < i; k++) {
            e = exts[k].list;   /* traverse the extensions */
            if ((e == null) || (e.mol != emb.mol)
            ||  ((e.base != null) && (e.base != emb)))
              continue;         /* skip incompatible embeddings */
            if (e.bonds[b] != c.bonds[b])
              continue;         /* skip incompatible embeddings */
            if (e.base == null){/* if the base embedding is unknown */
              for (j = b; --j >= 0; )  /* the base must be compared */
                if (e.bonds[j] != c.bonds[j])
                  break;        /* check for a different bond */
              if (j >= 0) continue;
            }                   /* if base differs, skip embedding */
            exts[k--].list = e.succ;
            found = true;       /* remove compatible embeddings */
          }                     /* from the ring extensions */
          e = c; c = c.succ; e.succ = null;
          if (found) res.add(e);
        }                       /* add compatible single bond */
      }                         /* extension to the result list */
      exts[n++] = res;          /* store the created fragment */
    }                           /* which is the merging result */
    for (i = n; i < cnt; i++)   /* "delete" all other extensions */
      exts[i] = null;           /* from the extension vector */
    return n;                   /* return new number of fragments */
  }  /* mergeExts() */

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

  protected boolean adapt (Extension ext)
  {                             /* --- adapt a fragment */
    int       i, k, na, nb;     /* loop variables, buffers */
    Atom[]    atoms;            /* atom vector of the fragment */
    Bond[]    bonds;            /* bond vector of the fragment */
    Bond      b, x;             /* to traverse the bonds */
    Embedding emb;              /* to traverse the embeddings */
    Atom      a;                /* buffer for atom to shift */

    if ((this.flgs & ADAPTED) != 0)
      return true;              /* if already adapted, simply abort */
    this.flgs |= ADAPTED;       /* set flag for an adapted fragment */
    if (this.size > 0)          /* check for a ring extension */
      return ext.adaptRing(this);
    if (this.idx -this.base.idx <= 1)
      return true;              /* if no movable bonds, abort */
    if (this.mol == null)       /* create a molecule if necessary */
      this.mol = new Molecule(this);
    atoms = this.mol.atoms;     /* traverse the fragment's atoms */
    for (i = this.mol.atomcnt; --i > 0; )
      atoms[i].mark = -1;       /* unmark all atoms and */
    atoms[0].mark = 0;          /* then mark the root atom */
    bonds = this.mol.bonds;     /* traverse the fragment's bonds */
    for (k = 1, i = 0; i <= this.base.idx; i++) {
      b = bonds[i];             /* traverse the fixed bonds */
      if      (b.src.mark < 0) b.src.mark = k++;
      else if (b.dst.mark < 0) b.dst.mark = k++;
    }                           /* mark atoms in fixed part */
    x = bonds[this.idx];        /* get the newly added bond */
    for (; i < this.idx; i++) { /* and find its proper position */
      b = bonds[i];             /* traverse the movable bonds */
      if (((x.src.mark >= 0)    /* if incident to the marked part */
      ||   (x.dst.mark >= 0))   /* and smaller than the next bond */
      &&  (ext.compareBond(x, b, k) < 0))
        break;                  /* abort the position search loop */
      if      (b.src.mark < 0) b.src.mark = k++;
      else if (b.dst.mark < 0) b.dst.mark = k++;
    }                           /* mark atoms in (now) fixed part */
    if (i >= this.idx)          /* if no shift is necessary, */
      return true;              /* abort the function */
    System.arraycopy(bonds, i, bonds, i+1, nb = this.idx -i);
    bonds[i] = x;               /* shift the movable bonds */
    if      (x.src.mark < 0) this.src = x.dst.mark;
    else if (x.dst.mark < 0) this.src = x.src.mark;
    else if (x.src.mark < x.dst.mark)
         { this.src = x.src.mark; this.dst = x.dst.mark; k = -1; }
    else { this.src = x.dst.mark; this.dst = x.src.mark; k = -1; }
    na = this.dst -k;           /* adapt the atom indices */
    if ((k < 0) || (na <= 0)) { /* if only to adapt the bonds */
      for (emb = this.list; emb != null; emb = emb.succ) {
        if (emb.bonds == null)  /* if this is a packed embedding, */
          continue;             /* it can be skipped */
        b = emb.bonds[this.idx];/* get the bond added last */
        System.arraycopy(emb.bonds, i, emb.bonds, i+1, nb);
        emb.bonds[i] = b;       /* shift the added bond */
      } }                       /* to its proper position */
    else {                      /* if to adapt bonds and atoms */
      a = atoms[this.dst];      /* get the atom added last */
      System.arraycopy(atoms, k, atoms, k+1, na);
      atoms[k] = a;             /* shift the added atom */
      for (emb = this.list; emb != null; emb = emb.succ) {
        if (emb.bonds == null)  /* if this is a packed embedding, */
          continue;             /* it can be skipped */
        b = emb.bonds[this.idx];/* get the bond added last */
        System.arraycopy(emb.bonds, i, emb.bonds, i+1, nb);
        emb.bonds[i] = b;       /* shift the added bond */
        a = emb.atoms[this.dst];/* get the atom added last */
        System.arraycopy(emb.atoms, k, emb.atoms, k+1, na);
        emb.atoms[k] = a;       /* shift the added atom */
      }                         /* to its proper position */
      this.dst = k;             /* and set the new index */
    }                           /* of the destination atom */
    k = this.idx; this.idx = i; /* note old bond index and set new */
    return true;                /* return 'adaptation successful' */
  }  /* adapt() */

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

  public String toString (Notation ntn)
  {                             /* --- produce a string description */
    Molecule m = new Molecule(this);
    m.sort(false);              /* turn fragment into a molecule, */
    return ntn.format(m);       /* then format this molecule */
  }  /* toString() */

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

  public String toString (Extension ext)
  { return ext.makeString(this.getAsMolecule(), true); }

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

  public String toString ()     /* --- produce a string description */
  { return this.toString(new SMILES()); }

}  /* class Fragment */