fragment.java

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

      }                         /* is a bridge in all embeddings */
      this.flgs |= PERFECT; return true;
    }                           /* if it is, extension is perfect */
    emb = this.list;            /* get the first embedding */
    bas = emb.base; n = 0;      /* note base and init. ext. counter */
    do {                        /* count the number of extensions */
      n++;                      /* of the first base embedding */
      if (tonew && !emb.bonds[this.idx].isBridge())
        return false;           /* check whether the new bond */
      emb = emb.succ;           /* is a bridge in all embeddings */
    } while (emb.base == bas);  /* while at first base embedding */
    /* Note that emb cannot become null with the above loop, since */
    /* there are at least two molecules and thus two embeddings.   */
    bas = emb.base;             /* note the next base embedding */
    bel = nxt = null;           /* and clear the auxiliary lists */
    while (true) {              /* traverse the remaining embeddings */
      if (bas == null) {        /* if there is no base embedding */
        bas = bel = emb.mol.embed(this.base.getAsMolecule());
        nxt = emb.succ;         /* create a list of base embeddings */
      }                         /* for the embedding's molecule */
      /* If an embedding is packed (that is, if only the molecule */
      /* reference is kept), the embeddings must be recreated by  */
      /* extending base embeddings. Otherwise it is not known     */
      /* which embeddings resulted from the same base embedding.  */
      if (bel != null) {        /* if to process base embeddings */
        k   = (this.dst < this.base.mol.atomcnt) ? this.dst : -1;
        b   = this.mol.bonds[this.idx].type;
        a   = this.mol.atoms[this.dst].type;
        emb = bas.extend(this.src, k, b, a);
      }                         /* create a list of extensions */
      if (emb != null) {        /* if there are extensions to check */
        /* If extensions are created by actually extending a base   */
        /* embedding, it may be that for a specific base embedding  */
        /* there are no extensions leading to the current fragment. */
        /* However, this can only happen if there is more than one  */
        /* embedding of the base fragment into this molecule.       */
        k = 0;                  /* init. the extension counter */
        do {                    /* count the number of extensions */
          if (++k > n)          /* of the current base embedding */
            return false;       /* (must be the same as for first) */
          if (tonew && !emb.bonds[this.idx].isBridge())
            return false;       /* check whether the new bond */
          emb = emb.succ;       /* is a bridge in all embeddings */
        } while ((emb != null) && (emb.base == bas));
        if (k != n) return false;
      }                         /* compare the number of extensions */
      if (bel != null) {        /* if to process base embeddings, */
        bel = bel.succ;         /* go to the next base embedding */
        if (bel != null) { bas = bel; continue; }
        emb = nxt;              /* if there is none, continue with */
      }                         /* the next embedding from the list */
      if (emb == null) break;   /* if all embeddings processed, abort */
      bas = emb.base;           /* get the next base embedding */
    }
    this.flgs |= PERFECT;       /* set the perfect extension flag */
    return true;                /* return 'extension is perfect' */
  }  /* isPerfect() */

  /*--------------------------------------------------------------------
  The above function checks whether an extension is perfect, that is,
  whether it can be applied in exactly the same way to all embeddings.
  If this is the case, only the branch of the perfect extension needs
  to be followed. In order to avoid certain problems, such pruning must
  be restricted to extension bonds that are bridges in all molecules.
  --------------------------------------------------------------------*/

  protected void revert ()
  {                             /* --- revert extension information */
    if ((this.flgs & PERFECT) == 0)
      return;                   /* do nothing for non-perfect ext. */
    this.idx = this.base.idx;   /* reset the bond index and the */
    this.src = this.base.src;   /* indices of its source and dest. */
    this.dst = this.base.dst;   /* to those of the base fragment */
  }  /* revert() */

  /*--------------------------------------------------------------------
  If a perfect extension is followed as the only branch, the extension
  information must be reset to that of the base fragment, so that no
  possible fragments are lost. The above function does this.
  --------------------------------------------------------------------*/

  protected boolean isEquivTo (Fragment frag)
  {                             /* --- check for equivalence */
    int       i, k;             /* loop variables */
    Embedding emb, ref;         /* to traverse the embeddings */

    ref = frag.list;            /* get the embeddings of */
    emb = this.first();         /* the fragments to compare */
    if ((ref.mol != emb.mol)    /* if basic properties differ */
    ||  (ref.atoms.length != emb.atoms.length)
    ||  (ref.bonds.length != emb.bonds.length))
      return false;             /* fragments cannot be equivalent */
    for (i = ref.bonds.length; --i >= 0; )
      ref.bonds[i].mark = 0;    /* mark the embedding in the molecule */
    do {                        /* embedding comparison loop */
      for (k = emb.bonds.length; --k >= 0; )
        if (emb.bonds[k].mark < 0) /* if a bond marker is not set, */
          break;                   /* the embeddings differ */
      if (k < 0) break;         /* if an equiv. embed. found, abort, */
      emb = this.next();        /* otherwise go to the next fragment */
    } while ((emb != null)      /* until all embeddings are processed */
    &&       (emb.mol == ref.mol));
    for (i = ref.bonds.length; --i >= 0; )
      ref.bonds[i].mark = -1;   /* unmark the embedding in molecule */
    return (k < 0);             /* return comparison result */
  }  /* isEquivTo() */

  /*--------------------------------------------------------------------
  The above function checks whether two fragments are equivalent, i.e.,
  whether they refer to the same atoms and bonds, although maybe in a
  different way. To check this, it is tried to find an equivalent
  embedding of the two fragments for one molecule.
  --------------------------------------------------------------------*/

  protected void map (Extension ext)
  {                             /* --- map fragment after makeCanonic */
    int       i, na, nb;        /* loop variable, buffers */
    Embedding emb;              /* to traverse the embeddings */

    na = this.mol.atomcnt;      /* get number of atoms and */
    nb = this.mol.bondcnt;      /* the number of bonds */
    if (this.idx >= 0) {        /* if this fragment is the result */
      this.idx = ext.word[    this.idx];       /* of an extension */
      this.src = ext.word[nb +this.src];
      this.dst = ext.word[nb +this.dst];
    }                           /* map the extension information */
    for (emb = this.list; emb != null; emb = emb.succ) {
      if (emb.bonds == null)    /* if this is a packed embedding, */
        continue;               /* it can be skipped (no adaptation) */
      System.arraycopy(emb.bonds, 0, ext.bonds, 0, nb);
      if (emb.bonds == emb.base.bonds)
        emb.bonds = new Bond[nb];
      for (i = nb; --i >= 0; )  /* reorder the bond references */
        emb.bonds[ext.word[   i]] = ext.bonds[i];
      System.arraycopy(emb.atoms, 0, ext.atoms, 0, na);
      if (emb.atoms == emb.base.atoms)
        emb.atoms = new Atom[na];
      for (i = na; --i >= 0; )  /* reorder the atom references */
        emb.atoms[ext.word[nb+i]] = ext.atoms[i];
    }                           /* (reorganize the embeddings) */
  }  /* map() */

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

  protected boolean makeCanonic (Extension ext)
  { return this.makeCanonic(ext, -1); }

  protected boolean makeCanonic (Extension ext, int keep)
  {                             /* --- construct canonical form */
    if (this.list.bonds.length <= ((keep < 0) ? 0 : keep))
      return false;             /* check the number of movable bonds */
    if (this.mol == null)       /* create a molecule if necessary */
      this.mol = new Molecule(this);
    if (!this.mol.makeCanonic(ext, keep))
      return false;             /* make the molecule canonic and */
    this.map(ext);              /* map the embeddings accordingly */
    return true;                /* return 'fragment is changed' */
  }  /* makeCanonic() */

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

  protected boolean isCanonic (Extension ext)
  { return this.isCanonic(ext, false) > 0; }

  protected int isCanonic (Extension ext, boolean part)
  {                             /* --- check for canonical form */
    int n = this.list.bonds.length;
    if (n <= 0) return 1;       /* check whether there are bonds */
    if (this.mol == null)       /* create a molecule if necessary */
      this.mol = new Molecule(this);
    if (part) n = this.idx+1;   /* check whether molecule is canonic */
    return this.mol.isCanonic(ext, n);
  }  /* isCanonic() */

  /*--------------------------------------------------------------------
  The above function checks whether a fragment is in canonical form.
  In this function the search is initialized and the root node of the
  spanning tree is checked. The recursive check of the bonds is carried
  out in a function of the Extension class, because this check depends
  on the Extension strategy used (maximum bond source or rightmost).
  --------------------------------------------------------------------*/

  private ExtLE rings (Extension ext, Atom s, Bond b, Atom d, int mna)
  {                             /* --- create ring extensions */
    int   i, k, n;              /* loop variables */
    long  all, cur;             /* all ring flags and current one */
    Atom  a;                    /* to traverse the atoms of the ring */
    Bond  r, x = null;          /* to traverse the bonds of the ring */
    ExtLE e, l = null;          /* list of ring extensions */

    all = b.flags; cur = 1;     /* note start atom and ring flags */
    while (all != 0) {          /* while there is another ring flag */
      while ((all & cur) == 0) cur <<= 1;
      all &= ~cur;              /* find and remove the next ring flag */
      r = b; a = d; n = k = 0;  /* get initial bond and dest. atom */
      do {                      /* traverse the ring */
        if (a.mark < 0) k++;    /* count new atoms */
        for (i = a.bondcnt; --i >= 0; ) {
          x = a.bonds[i];       /* traverse the bonds of the atom */
          if (((x.flags & cur) != 0) && (x != r))
            break;              /* find the next bond */
        }                       /* of the ring to be added */
        if (i < 0) break;       /* if the ring is incomplete, abort */
        r = x;                  /* go to the next bond and atom */
        a = (r.src != a) ? r.src : r.dst;
        ext.word[n++] = r.type; /* store the bond type, */
        ext.word[n++] = a.type; /* the dest. atom type, */
        ext.word[n++] = a.mark; /* and the dest. atom index */
      } while (a != s);         /* while the ring is not closed */
      if ((a != s) || (k > mna))/* check whether the ring was closed */
        continue;               /* and whether it is small enough */
      e = new ExtLE(s.mark, d.mark, b.type, d.type, ext.word, n);
      e.succ = l; l = e;        /* create a new ring extension and */
    }                           /* add it at the head of the list */
    return l;                   /* return the created extensions */
  }  /* rings() */

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

  private boolean match (ExtLE e, Atom s, Bond b, Atom d)
  {                             /* --- match ring extensions */
    int   i, n;                 /* loop variables */
    long  all, cur;             /* all ring flags and current one */
    Atom  a;                    /* to traverse the atoms of the ring */
    Bond  r, x = null;          /* to traverse the bonds of the ring */

    all = b.flags; cur = 1;     /* note start atom and ring flags */
    while (all != 0) {          /* while there is another ring flag */
      while ((all & cur) == 0) cur <<= 1;
      all &= ~cur;              /* find and remove the next ring flag */
      r = b; a = d; n = 0;      /* get initial bond and dest. atom */
      do {                      /* traverse the ring */
        if (n >= e.ring.length) {
          n = -1; break; }      /* check the size of the ring */
        for (i = a.bondcnt; --i >= 0; ) {
          x = a.bonds[i];       /* traverse the bonds of the atom */
          if (((x.flags & cur) != 0) && (x != r))
            break;              /* find the next bond */
        }                       /* of the ring to be added */
        if (i < 0) break;       /* if the ring is incomplete, abort */
        r = x;                  /* go to the next bond and atom */
        a = (r.src != a) ? r.src : r.dst;
        if ((e.ring[n++] != r.type)
        ||  (e.ring[n++] != a.type)
        ||  (e.ring[n++] != a.mark)) {
          n = -1; break; }      /* check the bond properties */
      } while (a != s);         /* while the ring is not closed */
      if (n >= e.ring.length)   /* check whether all bonds */
        return true;            /* of the ring were matched */
    }
    return false;               /* no matching ring found */
  }  /* match() */

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

  protected void setClosed (boolean closed)
  { if (closed) this.flgs |= CLOSED; else this.flgs &= ~CLOSED; }

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

  protected boolean isClosed (Extension ext)
  {                             /* --- check for a closed fragment */
    int       i, k;             /* loop variables */
    int       mna;              /* maximal number of new atoms */
    Embedding emb;              /* to traverse the embeddings */
    Molecule  cur;              /* to traverse the molecules */
    Atom      a, d;             /* to traverse the atoms */
    Bond      b;                /* bond of previous extension */
    ExtLE     l1, l2, l3, e;    /* list of extensions */

    if ((this.flgs & CLOSED) == 0)
      return false;             /* check the non-closed flag */

    /* --- collect extensions in first molecule --- */
    mna = ext.max -this.size(); /* get max. number of new atoms */
    emb = this.first();         /* and the first embedding */
    cur = emb.mol; l1 = null;   /* note molecule and init. list */
    do {                        /* extension generation loop */