universalisomorphismtester.java

化学图形处理软件

	  
    // resets the target graph.
    gr.clear();

      // compares each bond of G1 to each bond of G2
    for (int i = 0; i < ac1.getBondCount(); i++) {
      for (int j = 0; j < ac2.getBondCount(); j++) {
          if(timeout>-1 && (System.currentTimeMillis()-start)>timeout)
        	  throw new CDKException("Timeout exceeded in getOverlaps");
          IBond bondA2 = ac2.getBond(j);
          if (bondA2 instanceof IQueryBond) {
              IQueryBond queryBond = (IQueryBond)bondA2;
              IQueryAtom atom1 = (IQueryAtom)(bondA2.getAtom(0));
              IQueryAtom atom2 = (IQueryAtom)(bondA2.getAtom(1));
              IBond bond = ac1.getBond(i);
              if (queryBond.matches(bond)) {
                  // ok, bonds match
            	    if (atom1.matches(bond.getAtom(0)) && atom2.matches(bond.getAtom(1)) ||
                      atom1.matches(bond.getAtom(1)) && atom2.matches(bond.getAtom(0))) {
                      // ok, atoms match in either order
                      gr.addNode(new RNode(i,j));
                  }
              }
          } else {
              // if both bonds are compatible then create an association node
              // in the resolution graph
              if (
                ( // bond type conditions
                  ( // same bond order and same aromaticity flag (either both on or off)
                    ac1.getBond(i).getOrder() == ac2.getBond(j).getOrder() &&
                	ac1.getBond(i).getFlag(CDKConstants.ISAROMATIC) ==
                    ac2.getBond(j).getFlag(CDKConstants.ISAROMATIC)
                  )
                  ||
                  ( // both bond are aromatic
                	ac1.getBond(i).getFlag(CDKConstants.ISAROMATIC) &&
                    ac2.getBond(j).getFlag(CDKConstants.ISAROMATIC)
                  )
                )
                &&
                ( // atome type conditions
                  ( // a1 = a2 && b1 = b2
                	  ac1.getBond(i).getAtom(0).getSymbol().equals(ac2.getBond(j).getAtom(0).getSymbol()) &&
                	  ac1.getBond(i).getAtom(1).getSymbol().equals(ac2.getBond(j).getAtom(1).getSymbol())
                  )
                  ||
                  ( // a1 = b2 && b1 = a2
                	  ac1.getBond(i).getAtom(0).getSymbol().equals(ac2.getBond(j).getAtom(1).getSymbol()) &&
                	  ac1.getBond(i).getAtom(1).getSymbol().equals(ac2.getBond(j).getAtom(0).getSymbol())
                  )
                )
              ) {
                  gr.addNode(new RNode(i, j));
              }
          }
      }
    }
  }


  /**
   *  Build edges of the RGraphs
   *  This method create the edge of the RGraph and
   *  calculates the incompatibility and neighbourhood
   *  relationships between RGraph nodes.
   *
   * @param  gr   the rGraph
   * @param  g1   first molecule. Must not be an IQueryAtomContainer.
   * @param  g2   second molecule. May be an IQueryAtomContainer.
   */
  private static void arcConstructor(RGraph gr, IAtomContainer ac1, IAtomContainer ac2) throws CDKException{
    // each node is incompatible with himself
    for (int i = 0; i < gr.getGraph().size(); i++) {
      RNode x = (RNode) gr.getGraph().get(i);
      x.getForbidden().set(i);
    }

    IBond a1;
    IBond a2;
    IBond b1;
    IBond b2;

    gr.setFirstGraphSize(ac1.getBondCount());
    gr.setSecondGraphSize(ac2.getBondCount());

    for (int i = 0; i < gr.getGraph().size(); i++) {
      RNode x = (RNode) gr.getGraph().get(i);

      // two nodes are neighbours if their adjacency
      // relationship in are equivalent in G1 and G2
      // else they are incompatible.
      for (int j = i + 1; j < gr.getGraph().size(); j++) {
        if(timeout>-1 && (System.currentTimeMillis()-start)>timeout)
          throw new CDKException("Timeout exceeded in getOverlaps");
        RNode y = (RNode) gr.getGraph().get(j);

        a1 = ac1.getBond(((RNode) gr.getGraph().get(i)).getRMap().getId1());
        a2 = ac2.getBond(((RNode) gr.getGraph().get(i)).getRMap().getId2());
        b1 = ac1.getBond(((RNode) gr.getGraph().get(j)).getRMap().getId1());
        b2 = ac2.getBond(((RNode) gr.getGraph().get(j)).getRMap().getId2());

        if (a2 instanceof IQueryBond) {
            if (a1.equals(b1) || a2.equals(b2) ||
                !queryAdjacencyAndOrder(a1, b1, a2, b2)) {
                x.getForbidden().set(j);
                y.getForbidden().set(i);
            } else if (hasCommonAtom(a1, b1)) {
                x.getExtension().set(j);
                y.getExtension().set(i);
            }
        } else {
            if (a1.equals(b1) || a2.equals(b2) ||
                (!getCommonSymbol(a1, b1).equals(getCommonSymbol(a2, b2)))) {
              x.getForbidden().set(j);
              y.getForbidden().set(i);
            } else if (hasCommonAtom(a1, b1)) {
              x.getExtension().set(j);
              y.getExtension().set(i);
            }
        }
      }
    }
  }


  /**
   * Determines if two bonds have at least one atom in common.
   *
   * @param  a  first bond
   * @param  b  second bond
   * @return    the symbol of the common atom or "" if
   *            the 2 bonds have no common atom
   */
  private static boolean hasCommonAtom(IBond a, IBond b) {
    return a.contains(b.getAtom(0)) || a.contains(b.getAtom(1));
  }

  /**
   *  Determines if 2 bond have 1 atom in common and returns the common symbol
   *
   * @param  a  first bond
   * @param  b  second bond
   * @return    the symbol of the common atom or "" if
   *            the 2 bonds have no common atom
   */
  private static String getCommonSymbol(IBond a, IBond b) {
    String symbol = "";

    if (a.contains(b.getAtom(0))) {
      symbol = b.getAtom(0).getSymbol();
    } else if (a.contains(b.getAtom(1))) {
      symbol = b.getAtom(1).getSymbol();
    }

    return symbol;
  }

    /**
   *  Determines if 2 bond have 1 atom in common if second is a query AtomContainer
   *
   * @param  a1  first bond
   * @param  b1  second bond
   * @return    the symbol of the common atom or "" if
   *            the 2 bonds have no common atom
   */
  private static boolean queryAdjacency(IBond a1, IBond b1, IBond a2, IBond b2) {

	  IAtom atom1 = null;
	  IAtom atom2 = null;

      if (a1.contains(b1.getAtom(0))) {
          atom1 = b1.getAtom(0);
      } else if (a1.contains(b1.getAtom(1))) {
          atom1 = b1.getAtom(1);
      }

      if (a2.contains(b2.getAtom(0))) {
          atom2 = b2.getAtom(0);
      } else if (a2.contains(b2.getAtom(1))) {
          atom2 = b2.getAtom(1);
      }

      if (atom1 != null && atom2 != null){
    	  // well, this looks fishy: the atom2 is not always a IQueryAtom !
          return ((IQueryAtom)atom2).matches(atom1);
      } else return atom1 == null && atom2 == null;

  }
  
  /**
   *  Determines if 2 bond have 1 atom in common if second is a query AtomContainer
   *  and wheter the order of the atoms is correct (atoms match).
   *
   * @param  a1  first bond
   * @param  b1  second bond
   * @return    the symbol of the common atom or "" if
   *            the 2 bonds have no common atom
   */
  private static boolean queryAdjacencyAndOrder(IBond bond1, IBond bond2, IBond queryBond1, IBond queryBond2) {

	  IAtom centralAtom = null;
	  IAtom centralQueryAtom = null;

      if (bond1.contains(bond2.getAtom(0))) {
    	  centralAtom = bond2.getAtom(0);
      } else if (bond1.contains(bond2.getAtom(1))) {
    	  centralAtom = bond2.getAtom(1);
      }

      if (queryBond1.contains(queryBond2.getAtom(0))) {
    	  centralQueryAtom = queryBond2.getAtom(0);
      } else if (queryBond1.contains(queryBond2.getAtom(1))) {
    	  centralQueryAtom = queryBond2.getAtom(1);
      }

      if (centralAtom != null && centralQueryAtom != null
          && ((IQueryAtom)centralQueryAtom).matches(centralAtom)) {
    	  IQueryAtom queryAtom1 = (IQueryAtom)queryBond1.getConnectedAtom(centralQueryAtom);
    	  IQueryAtom queryAtom2 = (IQueryAtom)queryBond2.getConnectedAtom(centralQueryAtom);
    	  IAtom atom1 = bond1.getConnectedAtom(centralAtom);
    	  IAtom atom2 = bond2.getConnectedAtom(centralAtom);
    	  if (queryAtom1.matches(atom1) && queryAtom2.matches(atom2) ||
        	  queryAtom1.matches(atom2) && queryAtom2.matches(atom1)) {
    		  return true;
    	  } else return false;
      } else return centralAtom == null && centralQueryAtom == null;

  }

  /**
   *  Checks some simple heuristics for whether the subgraph query can
   *  realistically be a subgraph of the supergraph. If, for example, the
   *  number of nitrogen atoms in the query is larger than that of the supergraph
   *  it cannot be part of it.
   *
   * @param  ac1  the supergraph to be checked. Must not be an IQueryAtomContainer.
   * @param  ac2  the subgraph to be tested for. May be an IQueryAtomContainer.
   * @return    true if the subgraph ac2 has a chance to be a subgraph of ac1
   */
  private static boolean testSubgraphHeuristics(IAtomContainer ac1, IAtomContainer ac2)
  	throws CDKException {
	  if (ac1 instanceof IQueryAtomContainer)
		  throw new CDKException(
		      "The first IAtomContainer must not be an IQueryAtomContainer"
		  );
	  
	  int ac1SingleBondCount = 0;
	  int ac1DoubleBondCount = 0;
	  int ac1TripleBondCount = 0;
	  int ac1AromaticBondCount = 0;
	  int ac2SingleBondCount = 0;
	  int ac2DoubleBondCount = 0;
	  int ac2TripleBondCount = 0;
	  int ac2AromaticBondCount = 0;
	  int ac1SCount = 0;
	  int ac1OCount = 0;
	  int ac1NCount = 0;
	  int ac1FCount = 0;
	  int ac1ClCount = 0;
	  int ac1BrCount = 0;
	  int ac1ICount = 0;
	  int ac1CCount = 0;

	  int ac2SCount = 0;
	  int ac2OCount = 0;
	  int ac2NCount = 0;
	  int ac2FCount = 0;
	  int ac2ClCount = 0;
	  int ac2BrCount = 0;
	  int ac2ICount = 0;
	  int ac2CCount = 0;

	  IBond bond;
	  IAtom atom;
	  for (int i = 0; i < ac1.getBondCount(); i++)
	  {
		  bond = ac1.getBond(i);
		  if (bond.getFlag(CDKConstants.ISAROMATIC)) ac1AromaticBondCount ++;
		  else if (bond.getOrder() == 1) ac1SingleBondCount ++;
		  else if (bond.getOrder() == 2) ac1DoubleBondCount ++;
		  else if (bond.getOrder() == 3) ac1TripleBondCount ++;
	  }
	  for (int i = 0; i < ac2.getBondCount(); i++)
	  {
		  bond = ac2.getBond(i);
          if (bond instanceof IQueryBond) continue;
		  if (bond.getFlag(CDKConstants.ISAROMATIC)) ac2AromaticBondCount ++;
		  else if (bond.getOrder() == 1) ac2SingleBondCount ++;
		  else if (bond.getOrder() == 2) ac2DoubleBondCount ++;
		  else if (bond.getOrder() == 3) ac2TripleBondCount ++;
	  }

	  if (ac2SingleBondCount > ac1SingleBondCount) return false;
	  if (ac2AromaticBondCount > ac1AromaticBondCount) return false;
	  if (ac2DoubleBondCount > ac1DoubleBondCount) return false;
	  if (ac2TripleBondCount > ac1TripleBondCount) return false;

	  for (int i = 0; i < ac1.getAtomCount(); i++)
	  {
		  atom = ac1.getAtom(i);
		  if (atom.getSymbol().equals("S")) ac1SCount ++;
		  else if (atom.getSymbol().equals("N")) ac1NCount ++;
		  else if (atom.getSymbol().equals("O")) ac1OCount ++;
		  else if (atom.getSymbol().equals("F")) ac1FCount ++;
		  else if (atom.getSymbol().equals("Cl")) ac1ClCount ++;
		  else if (atom.getSymbol().equals("Br")) ac1BrCount ++;
		  else if (atom.getSymbol().equals("I")) ac1ICount ++;
		  else if (atom.getSymbol().equals("C")) ac1CCount ++;
	  }
	  for (int i = 0; i < ac2.getAtomCount(); i++)
	  {
		  atom = ac2.getAtom(i);
          if (atom instanceof IQueryAtom) continue;
		  if (atom.getSymbol().equals("S")) ac2SCount ++;
		  else if (atom.getSymbol().equals("N")) ac2NCount ++;
		  else if (atom.getSymbol().equals("O")) ac2OCount ++;
		  else if (atom.getSymbol().equals("F")) ac2FCount ++;
		  else if (atom.getSymbol().equals("Cl")) ac2ClCount ++;
		  else if (atom.getSymbol().equals("Br")) ac2BrCount ++;
		  else if (atom.getSymbol().equals("I")) ac2ICount ++;
		  else if (atom.getSymbol().equals("C")) ac2CCount ++;
	  }

	  if (ac1SCount < ac2SCount) return false;
	  if (ac1NCount < ac2NCount) return false;
	  if (ac1OCount < ac2OCount) return false;
	  if (ac1FCount < ac2FCount) return false;
	  if (ac1ClCount < ac2ClCount) return false;
	  if (ac1BrCount < ac2BrCount) return false;
	  if (ac1ICount < ac2ICount) return false;
	  if (ac1CCount < ac2CCount) return false;


	  return true;
  }
  
}