rgraph.java

化学图形处理软件

                    newTraversed = (BitSet) traversed.clone();
                    newTraversed.set(x);
                    forbidden.set(x);
                    
                    // parse recursively the RGraph
                    parseRec(newTraversed, newExtension, newForbidden);
                }
            }
        }
    }

    /**
     * Checks if a potantial solution is a real one 
     * (not included in a previous solution)
     *  and add this solution to the solution list
     * in case of success.
     *
     * @param  traversed  new potential solution
     */
    private void solution(BitSet traversed)
    {
        boolean included = false;
        BitSet projG1 = projectG1(traversed);
        BitSet projG2 = projectG2(traversed);

        // the solution must follows the search constrains
        // (must contain the mandatory elements in G1 an G2)
        if(isContainedIn(c1, projG1) && isContainedIn(c2, projG2))
        {
            // the solution should not be included in a previous solution
            // at the RGraph level. So we check against all prevous solution
            // On the other hand if a previous solution is included in the
            // new one, the previous solution is removed.
            for(ListIterator i = solutionList.listIterator(); i.hasNext() && !included; )
            {
                BitSet sol = (BitSet) i.next();

                if(!sol.equals(traversed))
                {
                    // if we asked to save all 'mappings' then keep this mapping
                    if(findAllMap && (projG1.equals(projectG1(sol)) || projG2.equals(projectG2(sol))))
                    {
                        // do nothing
                    }
                    // if the new solution is included mark it as included
                    else if(isContainedIn(projG1, projectG1(sol)) || isContainedIn(projG2, projectG2(sol)))
                    {
                        included = true;
                    }
                    // if the previous solution is contained in the new one, remove the previous solution
                    else if(isContainedIn(projectG1(sol), projG1) || isContainedIn(projectG2(sol), projG2))
                    {
                        i.remove();
                    }
                }
                else
                {
                    // solution already exists
                    included = true;
                }
            }

            if(included == false)
            {
                // if it is really a new solution add it to the 
                // list of current solution
                solutionList.add(traversed);
            }

            if(!findAllStructure)
            {
                // if we need only one solution
                // stop the search process
                // (e.g. substructure search)
                stop = true;
            }
        }
    }

    /**
     *  Determine if there are potential soltution remaining.
     * @param       potentialNode  set of remaining potential nodes
     * @return      true if it is worse to continue the search         
     */
    private boolean mustContinue(BitSet potentialNode)
    {
        boolean result = true;
        boolean cancel = false;
        BitSet projG1 = projectG1(potentialNode);
        BitSet projG2 = projectG2(potentialNode);

        // if we reached the maximum number of
        // serach iterations than do not continue
        if(maxIteration != -1 && nbIteration >= maxIteration)
        {
            return false;
        }
        
        // if constrains may no more be fullfilled than stop.
        if(!isContainedIn(c1, projG1) || !isContainedIn(c2, projG2))
        {
            return false;
        }
        
        // check if the solution potential is not included in an already
        // existing solution
        for(Iterator i = solutionList.iterator(); i.hasNext() && !cancel; )
        {
            BitSet sol = (BitSet) i.next();

            // if we want every 'mappings' do not stop
            if(findAllMap && (projG1.equals(projectG1(sol)) || projG2.equals(projectG2(sol))))
            {
                // do nothing
            }
            // if it is not possible to do better than an already existing solution than stop.
            else if(isContainedIn(projG1, projectG1(sol)) || isContainedIn(projG2, projectG2(sol)))
            {
                result = false;
                cancel = true;
            }
        }
        
        return result;
    }

    /**
     *  Builds the initial extension set. This is the
     *  set of node tha may be used as seed for the
     *  RGraph parsing. This set depends on the constrains
     *  defined by the user.
     * @param  c1  constraint in the graph G1
     * @param  c2  constraint in the graph G2
     * @return     
     */
    private BitSet buildB(BitSet c1, BitSet c2)
    {
        this.c1 = c1;
        this.c2 = c2;

        BitSet bs = new BitSet();

        // only nodes that fulfill the initial constrains
        // are allowed in the initial extension set : B
        for(Iterator i = graph.iterator(); i.hasNext(); )
        {
            RNode rn = (RNode) i.next();

            if((c1.get(rn.rMap.id1) || c1.isEmpty()) && (c2.get(rn.rMap.id2) || c2.isEmpty()))
            {
                bs.set(graph.indexOf(rn));
            }
        }
        return bs;
    }
    
    /**
     *  Returns the list of solutions.
     *
     * @return    The solution list 
     */
    public List getSolutions()
    {
        return solutionList;
    }

    /**
     *  Converts a RGraph bitset (set of RNode)
     * to a list of RMap that represents the 
     * mapping between to substructures in G1 and G2
     * (the projection of the RGraph bitset on G1
     * and G2).
     *
     * @param  set  the BitSet
     * @return      the RMap list
     */
    public List bitSetToRMap(BitSet set)
    {
        List rMapList = new ArrayList();

        for(int x = set.nextSetBit(0); x >= 0; x = set.nextSetBit(x + 1))
        {
            RNode xNode = (RNode) graph.get(x);
            rMapList.add(xNode.rMap);
        }
        return rMapList;
    }
    
    /**
     *  Sets the 'AllStructres' option. If true
     * all possible solutions will be generated. If false
     * the search will stop as soon as a solution is found.
     * (e.g. when we just want to know if a G2 is
     *  a substructure of G1 or not).
     *
     * @param  findAllStructure  
     */
    public void setAllStructure(boolean findAllStructure)
    {
        this.findAllStructure = findAllStructure;
    }

    /**
     *  Sets the 'finAllMap' option. If true
     * all possible 'mappings' will be generated. If false
     * the search will keep only one 'mapping' per structure
     * association.
     *
     * @param  findAllMap  
     */
    public void setAllMap(boolean findAllMap)
    {
        this.findAllMap = findAllMap;
    }

    /**
     * Sets the maxIteration for the RGraph parsing. If set to -1,
     * then no iteration maximum is taken into account.
     *
     * @param  it  The new maxIteration value
     */
    public void setMaxIteration(int it)
    {
        this.maxIteration = it;
    }
    
   /**
    *  Returns a string representation of the RGraph.
    * @return the string representation of the RGraph
    */
    public String toString()
    {
        String message = "";
        int j = 0;

        for(Iterator i = graph.iterator(); i.hasNext(); )
        {
            RNode rn = (RNode) i.next();
            message += "-------------\n" + "RNode " + j + "\n" + rn.toString() + "\n";
            j++;
        }
        return message;
    } 

    
    /////////////////////////////////
    // BitSet tools
    /**
     *  Projects a RGraph bitset on the source graph G1.
     * @param  set  RGraph BitSet to project
     * @return      The associate BitSet in G1 
     */
    public BitSet projectG1(BitSet set)
    {
        BitSet projection = new BitSet(firstGraphSize);
        RNode xNode = null;

        for(int x = set.nextSetBit(0); x >= 0; x = set.nextSetBit(x + 1))
        {
            xNode = (RNode) graph.get(x);
            projection.set(xNode.rMap.id1);
        }
        return projection;
    }

    /**
     *  Projects a RGraph bitset on the source graph G2.
     * @param  set  RGraph BitSet to project
     * @return      The associate BitSet in G2 
     */
    public BitSet projectG2(BitSet set)
    {
        BitSet projection = new BitSet(secondGraphSize);
        RNode xNode = null;

        for(int x = set.nextSetBit(0); x >= 0; x = set.nextSetBit(x + 1))
        {
            xNode = (RNode) graph.get(x);
            projection.set(xNode.rMap.id2);
        }
        return projection;
    }

    /**
     *  Test if set A is contained in  set B.
     * @param  A  a bitSet 
     * @param  B  a bitSet 
     * @return    true if  A is contained in  B 
     */
    private boolean isContainedIn(BitSet A, BitSet B)
    {
        boolean result = false;

        if(A.isEmpty())
        {
            return true;
        }

        BitSet setA = (BitSet) A.clone();
        setA.and(B);

        if(setA.equals(A))
        {
            result = true;
        }

        return result;
    }   
}