universalisomorphismtester.java

化学图形处理软件

      // reduction of set of solution (isomorphism and substructure
      // with different 'mappings'

      return getMaximum(graphList);
  }


  /**
   * Transforms an AtomContainer into a BitSet (which's size = number of bond
   * in the atomContainer, all the bit are set to true).
   *
   * @param  ac  AtomContainer to transform
   * @return     The bitSet
   */
  public static BitSet getBitSet(IAtomContainer ac) {
    BitSet bs;
    int n = ac.getBondCount();

    if (n != 0) {
      bs = new BitSet(n);
      for (int i = 0; i < n; i++) { bs.set(i); }
    } else {
      bs = new BitSet();
    }

    return bs;
  }


  //////////////////////////////////////////////////
  //          Internal methods

  /**
   * Builds the RGraph ( resolution graph ), from two atomContainer
   * (description of the two molecules to compare)
   * This is the interface point between the CDK model and
   * the generic MCSS algorithm based on the RGRaph.
   *
   * @param  g1  Description of the first molecule
   * @param  g2  Description of the second molecule
   * @return     the rGraph
   */
  public static RGraph buildRGraph(IAtomContainer g1, IAtomContainer g2)  throws CDKException{
    RGraph rGraph = new RGraph();
    nodeConstructor(rGraph, g1, g2);
    arcConstructor(rGraph, g1, g2);
    return rGraph;
  }


  /**
   * General Rgraph parsing method (usually not used directly)
   * This method is the entry point for the recursive search
   * adapted to the atom container input.
   *
   * @param  g1                first molecule. Must not be an IQueryAtomContainer.
   * @param  g2                second molecule. May be an IQueryAtomContainer.
   * @param  c1                initial condition ( bonds from g1 that
   *                           must be contains in the solution )
   * @param  c2                initial condition ( bonds from g2 that
   *                           must be contains in the solution )
   * @param  findAllStructure  if false stop at the first structure found
   * @param  findAllMap        if true search all the 'mappings' for one same
   *                           structure
   * @return                   a List of Lists of RMap objects that represent the search solutions
   */
  public static List search(IAtomContainer g1, IAtomContainer g2, BitSet c1,
		  BitSet c2, boolean findAllStructure, boolean findAllMap)  throws CDKException{

	  // reset result
	  ArrayList rMapsList = new ArrayList();

	  // build the RGraph corresponding to this problem
	  RGraph rGraph = buildRGraph(g1, g2);
	  // parse the RGraph with the given constrains and options
	  rGraph.parse(c1, c2, findAllStructure, findAllMap);
	  List solutionList = rGraph.getSolutions();

	  // convertions of RGraph's internal solutions to G1/G2 mappings
	  for (Iterator i = solutionList.iterator(); i.hasNext(); ) {
		  BitSet set = (BitSet) i.next();
		  rMapsList.add(rGraph.bitSetToRMap(set));
	  }

	  return rMapsList;
  }

  //////////////////////////////////////
  //    Manipulation tools

  /**
   * Projects a list of RMap on a molecule.
   *
   * @param  rMapList  the list to project
   * @param  g         the molecule on which project
   * @param  id        the id in the RMap of the molecule g
   * @return           an AtomContainer
   */
  public static IAtomContainer project(List rMapList, IAtomContainer g, int id) {
    IAtomContainer ac = g.getBuilder().newAtomContainer();

    Map table = new HashMap();
    IAtom a1;
    IAtom a2;
    IAtom a;
    IBond bond;

    for (Iterator i = rMapList.iterator(); i.hasNext(); ) {
      RMap rMap = (RMap) i.next();
      if (id == UniversalIsomorphismTester.ID1) {
        bond = g.getBond(rMap.getId1());
      } else {
        bond = g.getBond(rMap.getId2());
      }

      a = bond.getAtom(0);
      a1 = (IAtom) table.get(a);

      if (a1 == null) {
        try {
			a1 = (IAtom)a.clone();
		} catch (CloneNotSupportedException e) {
			e.printStackTrace();
		}
        ac.addAtom(a1);
        table.put(a, a1);
      }

      a = bond.getAtom(1);
      a2 = (IAtom) table.get(a);

      if (a2 == null) {
        try {
			a2 = (IAtom)a.clone();
		} catch (CloneNotSupportedException e) {
			e.printStackTrace();
		}
        ac.addAtom(a2);
        table.put(a, a2);
      }
      IBond newBond = g.getBuilder().newBond(a1, a2, bond.getOrder());
      newBond.setFlag(
        CDKConstants.ISAROMATIC,
        bond.getFlag(CDKConstants.ISAROMATIC)
      );
      ac.addBond(newBond);
    }
    return ac;
  }


  /**
   * Projects a list of RMapsList on a molecule.
   *
   * @param  rMapsList  list of RMapsList to project
   * @param  g          the molecule on which project
   * @param  id         the id in the RMap of the molecule g
   * @return            a list of AtomContainer
   */
  public static ArrayList projectList(List rMapsList, IAtomContainer g, int id) {
    ArrayList graphList = new ArrayList();

    for (Iterator i = rMapsList.iterator(); i.hasNext(); ) {
      List rMapList = (List) i.next();
      IAtomContainer ac = project(rMapList, g, id);
      graphList.add(ac);
    }
    return graphList;
  }

  /**
   * Removes all redundant solution.
   *
   * @param  graphList  the list of structure to clean
   * @return            the list cleaned
   */
  private static ArrayList getMaximum(ArrayList graphList)  throws CDKException{
    ArrayList reducedGraphList = (ArrayList) graphList.clone();

    for (int i = 0; i < graphList.size(); i++) {
      IAtomContainer gi = (IAtomContainer) graphList.get(i);

      for (int j = i + 1; j < graphList.size(); j++) {
        IAtomContainer gj = (IAtomContainer) graphList.get(j);

        // Gi included in Gj or Gj included in Gi then
        // reduce the irrelevant solution
        if (isSubgraph(gj, gi)) {
            reducedGraphList.remove(gi);
        } else if (isSubgraph(gi, gj)) {
            reducedGraphList.remove(gj);
        }
      }
    }
    return reducedGraphList;
  }

  /**
   *  Checks for single atom cases before doing subgraph/isomorphism search
   *
   * @param  g1  AtomContainer to match on. Must not be an IQueryAtomContainer.
   * @param  g2  AtomContainer as query. May be an IQueryAtomContainer.
   * @return     List of List of RMap objects for the Atoms (not Bonds!), null if no single atom case
  */
  public static ArrayList checkSingleAtomCases(IAtomContainer g1, IAtomContainer g2) throws CDKException {
	  if (g1 instanceof IQueryAtomContainer)
		  throw new CDKException(
		      "The first IAtomContainer must not be an IQueryAtomContainer"
		  );
	  
	  if (g2.getAtomCount() == 1) {
		  ArrayList arrayList = new ArrayList();
		  IAtom atom = g2.getAtom(0);
		  if (atom instanceof IQueryAtom) {
			  IQueryAtom qAtom = (IQueryAtom)atom;
			  for (int i=0; i<g1.getAtomCount(); i++){
				  if(qAtom.matches(g1.getAtom(i)))
					  arrayList.add(new RMap(i,0));
			  }
		  } else {
			  String atomSymbol = atom.getSymbol();
			  for(int i=0; i<g1.getAtomCount(); i++){
				  if(g1.getAtom(i).getSymbol().equals(atomSymbol))
					  arrayList.add(new RMap(i,0));
			  }
		  }
		  return arrayList;
	  } else if (g1.getAtomCount() == 1) {
		  ArrayList arrayList = new ArrayList();
		  IAtom atom = g1.getAtom(0);
		  for (int i=0; i<g2.getAtomCount(); i++) {
		      IAtom atom2 = g2.getAtom(i);
		      if (atom2 instanceof IQueryAtom) {
		    	  IQueryAtom qAtom = (IQueryAtom)atom2;
		    	  if (qAtom.matches(atom))
		    		  arrayList.add(new RMap(0,i));
		      } else {
		    	  if(atom2.getSymbol().equals(atom.getSymbol()))
					  arrayList.add(new RMap(0,i));
		      }
		  }
		  return arrayList;
	  } else {
          return null;
      }
  }

  /**
   *  This makes maps of matching atoms out of a maps of matching bonds as produced by the get(Subgraph|Ismorphism)Maps methods.
   *
   * @param  l   The list produced by the getMap method.
   * @param  g1  The first atom container. Must not be a IQueryAtomContainer.
   * @param  g2  The second one (first and second as in getMap). May be an QueryAtomContaienr.
   * @return     A Vector of Vectors of RMap objects of matching Atoms.
   */
   public static List makeAtomsMapsOfBondsMaps(List l, IAtomContainer g1, IAtomContainer g2) {
	   if(l==null) {
		   return l;
	   }
	   List result = new ArrayList();
	   for (int i = 0; i < l.size(); i++) {
		   ArrayList l2 = (ArrayList)l.get(i);
           result.add(makeAtomsMapOfBondsMap(l2, g1, g2));
       }
	   return result;
   }

  /**
   *  This makes a map of matching atoms out of a map of matching bonds as produced by the get(Subgraph|Ismorphism)Map methods.
   *
   * @param  l   The list produced by the getMap method.
   * @param  g1  first molecule. Must not be an IQueryAtomContainer.
   * @param  g2  second molecule. May be an IQueryAtomContainer.
   * @return     The mapping found projected on g1. This is a List of RMap objects containing Ids of matching atoms.
   */
  public static List makeAtomsMapOfBondsMap(List l, IAtomContainer g1, IAtomContainer g2) {
    if(l==null)
      return(l);
    List result = new ArrayList();
    for (int i = 0; i < l.size(); i++) {
    	IBond bond1 = g1.getBond(((RMap) l.get(i)).getId1());
    	IBond bond2 = g2.getBond(((RMap) l.get(i)).getId2());
      IAtom[] atom1 = BondManipulator.getAtomArray(bond1);
      IAtom[] atom2 = BondManipulator.getAtomArray(bond2);
      for (int j = 0; j < 2; j++) {
    	  List bondsConnectedToAtom1j = g1.getConnectedBondsList(atom1[j]);
        for (int k = 0; k < bondsConnectedToAtom1j.size(); k++) {
          if (bondsConnectedToAtom1j.get(k) != bond1) {
        	  IBond testBond = (IBond)bondsConnectedToAtom1j.get(k);
            for (int m = 0; m < l.size(); m++) {
            	IBond testBond2;
              if (((RMap) l.get(m)).getId1() == g1.getBondNumber(testBond)) {
                testBond2 = g2.getBond(((RMap) l.get(m)).getId2());
                for (int n = 0; n < 2; n++) {
                  List bondsToTest = g2.getConnectedBondsList(atom2[n]);
                  if (bondsToTest.contains(testBond2)) {
                    RMap map;
                    if (j == n) {
                      map = new RMap(g1.getAtomNumber(atom1[0]), g2.getAtomNumber(atom2[0]));
                    } else {
                      map = new RMap(g1.getAtomNumber(atom1[1]), g2.getAtomNumber(atom2[0]));
                    }
                    if (!result.contains(map)) {
                      result.add(map);
                    }
                    RMap map2;
                    if (j == n) {
                      map2 = new RMap(g1.getAtomNumber(atom1[1]), g2.getAtomNumber(atom2[1]));
                    } else {
                      map2 = new RMap(g1.getAtomNumber(atom1[0]), g2.getAtomNumber(atom2[1]));
                    }
                    if (!result.contains(map2)) {
                      result.add(map2);
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
    return (result);
  }


  /**
   *  Builds  the nodes of the RGraph ( resolution graph ), from
   *  two atom containers (description of the two molecules to compare)
   *
   * @param  gr   the target RGraph
   * @param  g1   first molecule. Must not be an IQueryAtomContainer.
   * @param  g2   second molecule. May be an IQueryAtomContainer.
   */
  private static void nodeConstructor(RGraph gr, IAtomContainer ac1, IAtomContainer ac2) throws CDKException {
	  if (ac1 instanceof IQueryAtomContainer)
		  throw new CDKException(
		      "The first IAtomContainer must not be an IQueryAtomContainer"
		  );