embedding.java

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

/*----------------------------------------------------------------------
  File    : Embedding.java
  Contents: Management of embeddings of molecular fragments
  Author  : Christian Borgelt
  History : 11.03.2002 file created as file submol.java
            04.08.2003 embedding duplication function added (for debug)
            07.08.2003 file split, this part renamed to Embedding.java
            09.08.2003 position of new bonds changed to end of vector
            10.08.2003 extension of an embedding by an atom added
            22.07.2005 marking functions/marking strategy modified
            01.08.2005 output functions removed (did not work anyway)
            02.08.2005 constructor from molecule markers added
            03.08.2005 special functions for seed embedding removed
            17.08.2005 unnecessary functions removed, reembedding added
            03.05.2006 bug in constructor Embedding(Extension) fixed
----------------------------------------------------------------------*/
package moss;

/*----------------------------------------------------------------------
An embedding of a fragment is represented by referring to a molecule.
It lists the atoms and bonds of the molecule that form the fragment.
An embedding must contain at least one atom, i.e., it cannot be empty.
----------------------------------------------------------------------*/

/*--------------------------------------------------------------------*/
public class Embedding {
/*--------------------------------------------------------------------*/

  /* --- instance variables --- */
  protected Embedding succ;     /* next embedding in list */
  protected Embedding base;     /* base from which it was created */
  protected Molecule  mol;      /* molecule referred to */
  protected Atom[]    atoms;    /* vector of atoms (of the molecule) */
  protected Bond[]    bonds;    /* vector of bonds (of the molecule) */

  /*--------------------------------------------------------------------
  If the bonds vector has a positive length, then bonds[bonds.length-1]
  contains the bond added last. The atoms in the atom vector are sorted
  in the order in which they have been added in the extension process.
  --------------------------------------------------------------------*/

  protected Embedding () { }    /* dummy constructor */

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

  protected Embedding (Molecule mol, int index)
  {                             /* --- create a single atom embedding */
    this.mol   = mol;           /* note the molecule referred to */
    this.base  = null;          /* and clear the base structure */
    this.succ  = null;          /* and the successor pointer */
    this.bonds = new Bond[0];   /* there are no bonds */
    this.atoms = new Atom[1];   /* store a reference to the atom */
    this.atoms[0] = mol.atoms[index];
  }  /* Embedding() */

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

  protected Embedding (Molecule mol, Atom[] atoms, int bondcnt)
  {                             /* --- create embedding from markers */
    int  i, k;                  /* loop variables */
    Atom a, d;                  /* to traverse the atoms */
    Bond b;                     /* to traverse the bonds */

    this.mol   = mol;           /* note the molecule referred to */
    this.base  = null;          /* and clear the base structure */
    this.succ  = null;          /* and the successor pointer */
    this.atoms = new Atom[atoms.length];
    this.bonds = new Bond[bondcnt];
    for (i = 0; i < atoms.length; i++) {
      this.atoms[i] = a = atoms[i]; /* copy the given atoms */
      for (k = 0; k < a.bondcnt; k++) {
        b = a.bonds[k];         /* traverse each atom's bonds */
        if (b.mark < 0) continue;
        d = (b.src != a) ? b.src : b.dst;
        if (d.mark > a.mark) this.bonds[b.mark] = b;
      }                         /* collect the corresponding bonds */
    }                           /* (must lead in top. direction) */
  }  /* Embedding() */

  /*--------------------------------------------------------------------
  The above function creates an embedding for a seed. The atoms of the
  seed are given directly, both atoms and bonds are also marked in the
  molecule referred to. In this way the bonds can be collected.
  --------------------------------------------------------------------*/

  protected Embedding (Extension ext)
  {                             /* --- create an embedding */
    int  i, k, na, nb;          /* loop variables, buffers */
    Atom a;                     /* to traverse the atoms */
    Bond b;                     /* to traverse the bonds */

    this.mol  = ext.base.mol;   /* note the molecule referred to */
    this.base = ext.base;       /* and the base that was extended */
    this.succ = null;           /* clear the successor pointer */
    na = ext.base.atoms.length; /* get the old number of atoms */
    if (ext.atnew <= 0)         /* if there are no new atoms */
      this.atoms = ext.base.atoms;
    else {                      /* if there are new atoms */
      this.atoms = new Atom[na +ext.atnew];
      System.arraycopy(ext.base.atoms, 0, this.atoms, 0, na);
    }                           /* copy the atoms of the base */
    nb = ext.base.bonds.length; /* get the old number of bonds */
    if (ext.bdnew <= 0)         /* if there are no new bonds */
      this.bonds = ext.base.bonds;
    else {                      /* if there are new bonds */
      this.bonds = new Bond[nb +ext.bdnew];
      System.arraycopy(ext.base.bonds, 0, this.bonds, 0, nb);
    }                           /* copy the bonds of the base */
    if (ext.size <= 0) {        /* if single bond or chain extension */
      if (ext.atnew > 0) this.atoms[na]   = ext.atoms[1];
      if (ext.bdnew > 0) this.bonds[nb]   = ext.bonds[0];
      if (ext.bdnew > 1) this.bonds[nb+1] = ext.bonds[1]; }
    else {                      /* if ring extension */
      for (k = ext.atnew, i = ext.size; --i >= 0; ) {
        a = ext.atoms[i];       /* traverse the extension atoms */
        if (a.mark < 0) this.atoms[--k +na] = a;
      }                         /* copy the new atoms */
      for (k = ext.bdnew, i = ext.size; --i >= 0; ) {
        b = ext.bonds[i];       /* traverse the extension bonds */
        if (b.mark < 0) this.bonds[--k +nb] = b;
      }                         /* copy the new bonds */
    }                           /* (skip old atoms and bonds) */
  }  /* Embedding() */

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

  protected Embedding (Embedding emb, Bond bond)
  {                             /* --- create an extended embedding */
    int n;                      /* numbers of atoms and bonds */

    this.mol  = emb.mol;        /* note the molecule referred to */
    this.base = emb;            /* and the base that is extended */
    this.succ = null;           /* clear the successor pointer */
    n = emb.bonds.length;       /* get the (old) number of bonds */
    this.bonds = new Bond[n+1]; /* and create the bond vector */
    System.arraycopy(emb.bonds, 0, this.bonds, 0, n);
    this.bonds[n] = bond;       /* store the new bond */
    if ((bond.src.mark >= 0)    /* if neither the source atom */
    &&  (bond.dst.mark >= 0))   /* nor the destination atom are new */
      this.atoms = emb.atoms;   /* set the vector of the base */
    else {                      /* if a new atom is added */
      n = emb.atoms.length;     /* get the (0ld) number of atoms */
      this.atoms = new Atom[n+1];    /* create a new atom vector */
      System.arraycopy(emb.atoms, 0, this.atoms, 0, n);
      this.atoms[n] = (bond.src.mark < 0) ? bond.src : bond.dst;
    }                           /* store the new atom */
  }  /* Embedding() */

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

  protected void mark ()
  {                             /* --- mark embedding in molecule */
    for (int i = this.atoms.length; --i >= 0; )
      this.atoms[i].mark = 0;   /* mark the atoms of the embedding */
    for (int i = this.bonds.length; --i >= 0; )
      this.bonds[i].mark = 0;   /* mark the bonds of the embedding */
  }  /* mark() */

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

  protected void markId ()
  {                             /* --- mark embedding in molecule */
    for (int i = this.atoms.length; --i >= 0; )
      this.atoms[i].mark = i;   /* number the atoms of the embedding */
    for (int i = this.bonds.length; --i >= 0; )
      this.bonds[i].mark = i;   /* number the bonds of the embedding */
  }  /* markId() */

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

  protected void unmark ()
  {                             /* --- unmark embedding in molecule */
    for (int i = this.atoms.length; --i >= 0; )
      this.atoms[i].mark = -1;  /* unmark the atoms of the embedding */
    for (int i = this.bonds.length; --i >= 0; )
      this.bonds[i].mark = -1;  /* unmark the bonds of the embedding */
  }  /* unmark() */

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

  protected Embedding extend (int src, int dst, int bond, int atom)
  {                             /* --- create extensions of an embed. */
    int       i;                /* loop variable */
    Atom      a, d;             /* to traverse/access the atoms */
    Bond      b;                /* to traverse/access the bonds */
    Embedding emb, list = null; /* list of extended embeddings */

    this.markId();              /* traverse and mark the base embeds. */
    a = this.atoms[src];        /* get the source atom of the ext. */
    for (i = a.bondcnt; --i >= 0; ) {
      b = a.bonds[i];           /* traverse the unmarked bonds */
      if (b.mark >= 0)   continue;
      if (b.type < bond) break;     /* compare the */
      if (b.type > bond) continue;  /* bond type */
      d = (b.src != a) ? b.src : b.dst;
      if (d.type < atom) break;     /* compare destination */
      if (d.type > atom) continue;  /* atom type */
      if (d.mark != dst) continue;  /* and index */
      emb = new Embedding(this, b);
      emb.succ = list; list = emb;
    }                           /* add reextension to the list */
    this.unmark();              /* unmark the base embedding again */
    return list;                /* return the list of embeddings */
  }  /* extend() */

}  /* class Embedding */