rgraph.java

化学图形处理软件

/* $Revision: 7986 $ $Author: egonw $ $Date: 2007-02-21 12:49:33 +0100 (Wed, 21 Feb 2007) $
 *
 * Copyright (C) 2002-2007  Stephane Werner <[e-mail]>
 *  
 * This code has been kindly provided by Stephane Werner 
 * and Thierry Hanser from IXELIS [e-mail].
 *  
 * IXELIS sarl - Semantic Information Systems
 *               17 rue des C?dres 67200 Strasbourg, France
 *               Tel/Fax : [phone] Email: [e-mail]
 *
 * CDK Contact: [e-mail]
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either version 2.1
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 */
package org.openscience.cdk.isomorphism.mcss;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
  * This class implements the Resolution Graph (RGraph).
  * The RGraph is a graph based representation of the search problem.
  * An RGraph is constructred from the two compared graphs (G1 and G2).
  * Each vertex (node) in the RGraph represents a possible association
  * from an edge in G1 with an edge in G2. Thus two compatible bonds
  * in two molecular graphs are represented by a vertex in the RGraph.
  * Each edge in the RGraph corresponds to a common adjacency relationship
  * between the 2 couple of compatible edges associated to the 2 RGraph nodes
  * forming this edge.
  * 
  * <p>Example:
  * <pre>
  *    G1 : C-C=O  and G2 : C-C-C=0
  *         1 2 3           1 2 3 4
  * </pre>
  *
  *  <p>The resulting RGraph(G1,G2) will contain 3 nodes:
  *  <ul>
  *    <li>Node A : association between bond C-C :  1-2 in G1 and 1-2 in G2
  *    <li>Node B : association between bond C-C :  1-2 in G1 and 2-3 in G2
  *    <li>Node C : association between bond C=0 :  2-3 in G1 and 3-4 in G2
  *  </ul>
  *  The RGraph will also contain one edge representing the 
  *  adjacency between node B and C  that is : bonds 1-2 and 2-3 in G1 
  *  and bonds 2-3 and 3-4 in G2.
  *
  *  <p>Once the RGraph has been built from the two compared graphs
  *  it becomes a very interesting tool to perform all kinds of 
  *  structural search (isomorphism, substructure search, maximal common
  *  substructure,....).
  *
  *  <p>The  search may be constrained by mandatory elements (e.g. bonds that
  *  have to be present in the mapped common substructures).
  *
  *  <p>Performing a query on an RGraph requires simply to set the constrains
  *  (if any) and to invoke the parsing method (parse())
  * 
  *  <p>The RGraph has been designed to be a generic tool. It may be constructed
  *  from any kind of source graphs, thus it is not restricted to a chemical
  *  context.
  *
  *  <p>The RGraph model is indendant from the CDK model and the link between
  *  both model is performed by the RTools class. In this way the RGraph 
  *  class may be reused in other graph context (conceptual graphs,....)
  *
  *  <p><b>Important note</b>: This implementation of the algorithm has not been
  *                      optimized for speed at this stage. It has been
  *                      written with the goal to clearly retrace the 
  *                      principle of the underlined search method. There is
  *                      room for optimization in many ways including the
  *                      the algorithm itself. 
  *
  *  <p>This algorithm derives from the algorithm described in
  *  {@cdk.cite HAN90} and modified in the thesis of T. Hanser {@cdk.cite HAN93}.
  *
  * @author      Stephane Werner from IXELIS [e-mail]
  * @cdk.created 2002-07-17
  * @cdk.require java1.4+
  * @cdk.module  standard
  */
public class RGraph
{
    // an RGraph is a list of RGraph nodes
    // each node keeping track of its
    // neighbours.
    List graph = null;

    // maximal number of iterations before
    // search break
    int maxIteration = -1;
    
    // dimensions of the compared graphs
    int firstGraphSize = 0;
    int secondGraphSize = 0;

    // constrains 
    BitSet c1 = null;
    BitSet c2 = null;
    
    // current solution list
    List solutionList = null;

    // flag to define if we want to get all possible 'mappings'    
    boolean findAllMap = false;
    
    // flag to define if we want to get all possible 'structures'
    boolean findAllStructure = true;
    
    // working variables
    boolean stop = false;
    int nbIteration = 0;
    BitSet graphBitSet = null;
    
    /**
     * Constructor for the RGraph object and creates an empty RGraph.
     */
    public RGraph()
    {
        graph = new ArrayList();
        solutionList = new ArrayList();
        graphBitSet = new BitSet();
    }

    /**
     *  Returns the size of the first of the two
     *  compared graphs.
     * @return The size of the first of the two compared graphs         
     */
    public int getFirstGraphSize()
    {
	    return firstGraphSize;
    }
    
    /**
     *  Returns the size of the second of the two
     *  compared graphs.
     * @return The size of the second of the two compared graphs         
     */
    public int getSecondGraphSize()
    {
	    return secondGraphSize;
    }

    
    /**
     *  Sets the size of the first of the two
     *  compared graphs.
     * @param n1 The size of the second of the two compared graphs         
     */
    public void setFirstGraphSize(int n1)
    {
	    firstGraphSize = n1;
    }
    
    /**
     *  Returns the size of the second of the two
     *  compared graphs.
     * @param n2 The size of the second of the two compared graphs         
     */
    public void setSecondGraphSize(int n2)
    {
	    secondGraphSize = n2;
    }

    /**
     *  Reinitialisation of the TGraph.
     */
    public void clear()
    {
        graph.clear();
        graphBitSet.clear();
    }

    /**
     *  Returns the graph object of this RGraph.
     * @return      The graph object, a list         
     */
    public List getGraph()
    {
	    return this.graph;
    }
    
    /**
     *  Adds a new node to the RGraph.
     * @param  newNode  The node to add to the graph
     */
    public void addNode(RNode newNode)
    {
        graph.add(newNode);
        graphBitSet.set(graph.size() - 1);
    }

    /**
     *  Parsing of the RGraph. This is the main method
     *  to perform a query. Given the constrains c1 and c2
     *  defining mandatory elements in G1 and G2 and given
     *  the search options, this m?thod builds an initial set
     *  of starting nodes (B) and parses recursively the
     *  RGraph to find a list of solution according to 
     *  these parameters.
     *
     * @param  c1  constrain on the graph G1
     * @param  c2  constrain on the graph G2
     * @param  findAllStructure true if we want all results to be generated   
     * @param  findAllMap true is we want all possible 'mappings'
     */
    public void parse(BitSet c1, BitSet c2, boolean findAllStructure, boolean findAllMap)
    {
        // initialize the list of solution
        solutionList.clear();
        
        // builds the set of starting nodes
        // according to the constrains
        BitSet b = buildB(c1, c2);
        
        // setup options
        setAllStructure(findAllStructure);
        setAllMap(findAllMap);
        
        // parse recursively the RGraph
        parseRec(new BitSet(b.size()), b, new BitSet(b.size()));
    }
    
    /**
     *  Parsing of the RGraph. This is the recursive method
     *  to perform a query. The method will recursively
     *  parse the RGraph thru connected nodes and visiting the
     *  RGraph using allowed adjacency relationship.
     *
     * @param  traversed  node already parsed
     * @param  extension  possible extension node (allowed neighbours)
     * @param  forbiden   node forbiden (set of node incompatible with the current solution)
     */
    private void parseRec(BitSet traversed, BitSet extension, BitSet forbidden)
    {
        BitSet newTraversed = null;
        BitSet newExtension = null;
        BitSet newForbidden = null;
        BitSet potentialNode = null;

        // if there is no more extension possible we
        // have reached a potential new solution
        if(extension.isEmpty())
        {
            solution(traversed);
        }
        // carry on with each possible extension
        else
        {
            // calculates the set of nodes that may still
            // be reached at this stage (not forbiden)
            potentialNode = ((BitSet) graphBitSet.clone());
            potentialNode.andNot(forbidden);
            potentialNode.or(traversed);

            // checks if we must continue the search
            // according to the potential node set
            if(mustContinue(potentialNode))
            {
                // carry on research and update iteration count
                nbIteration++;

                // for each node in the set of possible extension (neighbours of 
                // the current partial solution, include the node to the solution
                // and perse recursively the RGraph with the new context.
                for(int x = extension.nextSetBit(0); x >= 0 && !stop; x = extension.nextSetBit(x + 1))
                {
                    // evaluates the new set of forbidden nodes
                    // by including the nodes not compatible with the
                    // newly accepted node.
                    newForbidden = (BitSet) forbidden.clone();
                    newForbidden.or(((RNode) graph.get(x)).forbidden);

                    // if it is the first time we are here then
                    // traversed is empty and we initialize the set of
                    // possible extensions to the extension of the first
                    // accepted node in the solution.
                    if(traversed.isEmpty())
                    {
                        newExtension = (BitSet) (((RNode) graph.get(x)).extension.clone());
                    }
                    // else we simply update the set of solution by
                    // including the neighbours of the newly accepted node
                    else
                    {
                        newExtension = (BitSet) extension.clone();
                        newExtension.or(((RNode) graph.get(x)).extension);
                    }
                    
                    // extension my not contain forbidden nodes
                    newExtension.andNot(newForbidden);
                    
                    // create the new set of traversed node
                    // (update current partial solution)
                    // and add x to the set of forbidden node
                    // (a node may only appear once in a solution)