maxsrcext.java

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

/*----------------------------------------------------------------------
  File    : MaxSrcExt.java
  Contents: Molecular fragment extension management
            (breadth first search/maximum bond source extension)
  Author  : Christian Borgelt
  History : 11.03.2002 file created as file submol.java
            02.04.2002 function compareTo added
            07.08.2003 complete rewrite of extension functions
            08.06.2005 elimination of forward bonds added
            19.07.2005 forward bounds allowed, backward bonds eliminated
            21.07.2005 element manager added, excluded check removed
            23.07.2005 order of the extensions inverted
            11.08.2005 class Extension made abstract
            10.04.2006 compareTo for rings simplified
            11.04.2006 function compareBond added (for comparing bonds)
            02.05.2006 functions makeCanonic and makeWord added
            03.05.2006 function makeCanonic completed and debugged
            10.05.2006 function makeString added
            12.05.2006 extension-specific ring filtering moved here
            16.05.2006 bug in function ring fixed (ring direction)
            18.05.2006 adapted to new field Extension.dst
            31.05.2006 function isCanonic extended, result changed
            06.06.2006 adapted to changed type of bond flags
            07.06.2006 function compareWord added
            01.07.2006 adaptation of ring extensions moved here
            03.07.2006 bond splicing for ring extension adaptation
            04.07.2006 second functions makeWord/compareWord added
            06.07.2006 function adaptRing redesigned completely
            10.07.2006 marking of non-ring bonds added to adaptRing
            10.08.2006 adapted to new class TypeMap
----------------------------------------------------------------------*/
package moss;

/*--------------------------------------------------------------------*/
public class MaxSrcExt extends Extension {
/*--------------------------------------------------------------------*/

  private static final int FIXED   = Integer.MIN_VALUE;
  private static final int MAXCODE = Integer.MAX_VALUE;

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

  public MaxSrcExt (int mode, int max, TypeMap map)
  { super(mode, max, map); }

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

  public void init (Fragment frag, Embedding base)
  {                             /* --- initialize an extension */
    Atom a, d, dd;              /* to traverse the atoms */
    Bond b, bb;                 /* to traverse the bonds */

    base.markId();              /* mark the embedding in the molecule */
    this.frag = frag;           /* note the (possibly new) fragment*/
    this.base = base;           /* and the embedding to extend */
    this.src  = frag.src;       /* start with the first bond */
    this.idx  = -1;             /* of the previous source atom */
    this.size = -1;             /* clear the ring size and flags */
    this.all  =  0;             /* (also extension type indicator) */
    this.pos1 = this.pmin = -1; /* clear ring variant variables */
    if (frag.idx < 0) return;   /* if no previous bond, abort */
    a = base.atoms[frag.src];   /* get the current atom and */
    b = base.bonds[frag.idx];   /* find the previous bond's index */
    while (a.bonds[++this.idx] != b);
    d = (b.src != a) ? b.src : b.dst;
    while (--this.idx >= 0) {   /* check for equivalent bonds */
      bb = a.bonds[this.idx];   /* among the preceding ones */
      if (bb.type != b.type) break;
      dd = (bb.src != a) ? bb.src : bb.dst;
      if (dd.type != d.type) break;
    }                           /* (equivalent processed bonds */
  }  /* init() */               /*  must be considered again) */

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

  public boolean next ()
  {                             /* --- create the next extension */
    Atom a, d, p[];             /* to traverse/access the atoms */
    Bond b;                     /* to traverse/access the bonds */
    
    /* --- continue an old extension --- */
    if (((this.mode & EQVARS) != 0)
    &&  (this.pos1 >= 0)        /* if there is another equivalent */
    &&   this.variant())        /* variant of the previous ring, */
      return true;              /* return "extension successful" */
    if (((this.mode & RING)   != 0)
    &&  (this.all != 0)         /* if there is another ring flag */
    &&   this.ring())           /* and some ring is admissible, */
      return true;              /* return "extension successful" */
    if (((this.mode & CHAIN)  != 0)
    &&  (this.size == 0)        /* if last extension was a bond and */
    &&   this.chain())          /* it can be extended into a chain, */
      return true;              /* return "extension successful" */

    /* --- find a new extension --- */
    p = this.base.atoms;        /* get the atoms of the base embed. */
    a = p[this.src];            /* and the current anchor atom */
    while (true) {              /* find the next unprocessed bond */
      while (++this.idx >= a.bondcnt) {
        if (++this.src >= p.length) {
          this.base.unmark();   /* if atom's last bond is processed, */
          return false;         /* go to the next extendable atom */
        }                       /* and if there is none, abort */
        a = p[this.src];        /* get the new anchor atom and */
        this.idx = -1;          /* start with the first bond */
      }
      b = a.bonds[this.idx];    /* get the next bond of this atom */
      if (b.mark != -1)         /* if the bond is in the embedding */
        continue;               /* or excluded, it is cannot be added */
      d = (a != b.src) ? b.src : b.dst;
      this.dst = (d.mark >= 0) ? d.mark : this.base.atoms.length;
      if (this.dst <= this.src) /* skip bonds closing a ring that */
        continue;               /* lead "backward" in the fragment */
      if ((d.mark < 0)          /* if atom is not in the embedding */
      &&  (p.length +this.frag.chns >= this.max))
        continue;               /* check whether a new atom is ok */
      this.atoms[0] = a;        /* note the anchor atom and the */
      this.bonds[0] = b;        /* (first) bond of the extension */
      this.atoms[1] = d;        /* note the destination atom */
      if (b.isInRing()          /* if ring extension */
      &&  ((this.mode & RING) != 0)) {
        this.all  = b.getRings();   /* note the ring flags and */
        this.curr = 1;          /* initialize the current flag */
        if (this.ring()) return true;
        continue;               /* if some ring is admissible, */
      }                         /* return "extension successful" */
      if ((this.mode & BOND) == 0)
        continue;               /* check for bond extensions */
      this.atnew = (d.mark < 0) ? 1 : 0;
      this.bdnew = 1;           /* zero/one new atom, one new bond */
      this.size  = 0;           /* clear the extension size */
      this.chns  = this.frag.chns;
      return true;              /* copy the chain counter and */
    }                           /* return "extension successful" */
  }  /* next() */

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

  protected boolean checkRing ()
  {                             /* --- check a ring extension */
    int  i;                     /* loop variable */
    Atom s, a, d;               /* to traverse the ring atoms */
    Bond b, r;                  /* to access first and last bond */

    s = this.atoms[0];          /* get the anchor atom (source) */
    for (i = this.size; --i > 0; ) {
      a = this.atoms[i];        /* traverse the ring atoms and */
      if ( (a.mark >= 0)        /* check whether the ring is */
      &&   (a.mark <  s.mark)   /* admissible for this anchor */
      &&  ((this.bonds[i  ].mark < 0)
      ||   (this.bonds[i-1].mark < 0)))
        break;                  /* (no ring atom that is incident to */
    }                           /* a new bond (mark < 0) must have */
    if (i > 0) return false;    /* a smaller index than the anchor) */
    this.pos2 = -1;             /* default: locally asymmetric */
    b = this.bonds[0];          /* check first and last ring bond */
    r = this.bonds[this.size-1];
    if (r.mark >= 0)      return true;
    if (r.type >  b.type) return true;
    if (r.type <  b.type) return false;
    d = this.atoms[1];          /* check the destination atoms */
    a = (r.src != s) ? r.src : r.dst;
    if (a.type >  d.type) return true;
    if (a.type <  d.type) return false;
    this.pos2 = 0;              /* note the local symmetry */
    return ((a.mark <  0)       /* check for correct direction */
         || (a.mark >= this.dst));
  }  /* checkRing() */

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

  protected void initVars ()
  {                             /* --- init. ring extension variants */
    int  i;                     /* loop variable */
    Bond b, r;                  /* to access/traverse the bonds */
    Atom a, s, d;               /* to access/traverse the atoms */

    this.pmin = this.base.bonds.length;
    this.pmax = -1;             /* init. the insertion position range */
    r = this.bonds[0];          /* get the first bond of the ring */
    s = this.atoms[0];          /* and its source and */
    d = this.atoms[1];          /* destination atom */
    for (i = s.bondcnt; --i >= 0; ) {
      b = s.bonds[i];           /* traverse the bonds of the source */
      if (b.mark <  0)      continue;  /* skip bonds that are */
      if (b.type != r.type) continue;  /* not in the fragment */
      a = (b.src != s) ? b.src : b.dst;
      if (a.mark <  s.mark) continue;  /* skip backward bonds */
      if (a.type != d.type) continue;  /* (to preceding atom) */
      if (b.mark < this.pmin) this.pmin = b.mark;
      if (b.mark > this.pmax) this.pmax = b.mark;
    }                           /* find range of equivalent bonds */
    if (this.pmax < 0) {        /* if there are no equivalent bonds, */
      this.pos1 = -1; return; } /* abort with unknown positions */
    if (this.pmin <= this.frag.idx)   /* do not allow to shift */
      this.pmin = this.frag.idx +1;   /* bonds into the fixed part */
    this.pos1 = ++this.pmax;    /* compute the initial position(s) */
    if (this.pos2 >= 0) this.pos2 = ++this.pmax;
  }  /* initVars() */

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

  protected boolean variant ()
  {                             /* --- create ring extension variant */
    if  (--this.pos1 >= this.pmin) /* shift first bond to the left */
      return true;                 /* if shift is possible, abort */
    if ((  this.pos2 < 0)      /* check if second bond can be moved */