java.lang.Object
org.openscience.cdk.smsd.algorithm.rgraph.CDKRGraph

@Deprecated public class CDKRGraph extends Object
Deprecated.
This class is part of SMSD and either duplicates functionality elsewhere in the CDK or provides public access to internal implementation details. SMSD has been deprecated from the CDK with a newer, more recent version of SMSD is available at http://github.com/asad/smsd.
This class implements the Resolution Graph (CDKRGraph). The CDKRGraph is a graph based representation of the search problem. An CDKRGraph is constructed from the two compared graphs (G1 and G2). Each vertex (node) in the CDKRGraph 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 CDKRGraph. Each edge in the CDKRGraph corresponds to a common adjacency relationship between the 2 couple of compatible edges associated to the 2 CDKRGraph nodes forming this edge.

Example:

    G1 : C-C=O  and G2 : C-C-C=0
         1 2 3           1 2 3 4
 

The resulting CDKRGraph(G1,G2) will contain 3 nodes:

  • Node sourceBitSet : association between bond C-C : 1-2 in G1 and 1-2 in G2
  • Node targetBitSet : association between bond C-C : 1-2 in G1 and 2-3 in G2
  • Node C : association between bond C=0 : 2-3 in G1 and 3-4 in G2
The CDKRGraph will also contain one edge representing the adjacency between node targetBitSet and C that is : bonds 1-2 and 2-3 in G1 and bonds 2-3 and 3-4 in G2.

Once the CDKRGraph has been built from the two compared graphs maxIterator becomes a very interesting tool to perform all kinds of structural search (isomorphism, substructure search, maximal common substructure,....).

The search may be constrained by mandatory elements (e.g. bonds that have to be present in the mapped common substructures).

Performing a query on an CDKRGraph requires simply to set the constrains (if any) and to invoke the parsing method (parse())

The CDKRGraph has been designed to be a generic tool. It may be constructed from any kind of source graphs, thus maxIterator is not restricted to a chemical context.

The CDKRGraph model is indendant from the CDK model and the link between both model is performed by the RTools class. In this way the CDKRGraph class may be reused in other graph context (conceptual graphs,....)

Important note: 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.

This algorithm derives from the algorithm described in [Tonnelier, C. et. al.. Tetrahedron Comput. Methodol.. 1990. 3] and modified in the thesis of T. Hanser [Hanser, Th., Apprentissage automatique de méthodes de synthèse à partir d'exemples, 1993, ?Institute?].

Author:
Stephane Werner from IXELIS mail@ixelis.net, Syed Asad Rahman >asad@ebi.ac.uk< (modified the orignal code)
Source code:
main
Belongs to CDK module:
smsd
Created on:
2002-07-17
Requires:
java1.4+
  • Constructor Summary

    Constructors
    Constructor
    Description
    Deprecated.
    Constructor for the CDKRGraph object and creates an empty CDKRGraph.
  • Method Summary

    Modifier and Type
    Method
    Description
    void
    addNode(CDKRNode newNode)
    Deprecated.
    Adds a new node to the CDKRGraph.
    Deprecated.
    Converts a CDKRGraph bitset (set of CDKRNode) to a list of CDKRMap that represents the mapping between to substructures in G1 and G2 (the projection of the CDKRGraph bitset on G1 and G2).
    void
    Deprecated.
    Reinitialisation of the TGraph.
    int
    Deprecated.
    Returns the size of the first of the two compared graphs.
    Deprecated.
    Returns the graph object of this CDKRGraph.
    int
    Deprecated.
    Returns the size of the second of the two compared graphs.
    Deprecated.
    Returns the list of solutions.
    void
    parse(BitSet sourceBitSet, BitSet targetBitSet, boolean findAllStructure, boolean findAllMap, TimeManager timeManager)
    Deprecated.
    Parsing of the CDKRGraph.
    Deprecated.
    Projects a CDKRGraph bitset on the source graph G1.
    Deprecated.
    Projects a CDKRGraph bitset on the source graph G2.
    void
    setAllMap(boolean findAllMap)
    Deprecated.
    Sets the 'finAllMap' option.
    void
    setAllStructure(boolean findAllStructure)
    Deprecated.
    Sets the 'AllStructres' option.
    void
    setFirstGraphSize(int graphSize)
    Deprecated.
    Sets the size of the first of the two compared graphs.
    void
    setMaxIteration(int maxIterator)
    Deprecated.
    Sets the maxIteration for the CDKRGraph parsing.
    void
    setSecondGraphSize(int graphSize)
    Deprecated.
    Returns the size of the second of the two compared graphs.
    Deprecated.
    Returns a string representation of the CDKRGraph.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
  • Constructor Details

    • CDKRGraph

      public CDKRGraph()
      Deprecated.
      Constructor for the CDKRGraph object and creates an empty CDKRGraph.
  • Method Details

    • getFirstGraphSize

      public int getFirstGraphSize()
      Deprecated.
      Returns the size of the first of the two compared graphs.
      Returns:
      The size of the first of the two compared graphs
    • getSecondGraphSize

      public int getSecondGraphSize()
      Deprecated.
      Returns the size of the second of the two compared graphs.
      Returns:
      The size of the second of the two compared graphs
    • setFirstGraphSize

      public void setFirstGraphSize(int graphSize)
      Deprecated.
      Sets the size of the first of the two compared graphs.
      Parameters:
      graphSize - The size of the second of the two compared graphs
    • setSecondGraphSize

      public void setSecondGraphSize(int graphSize)
      Deprecated.
      Returns the size of the second of the two compared graphs.
      Parameters:
      graphSize - The size of the second of the two compared graphs
    • clear

      public void clear()
      Deprecated.
      Reinitialisation of the TGraph.
    • getGraph

      public List<CDKRNode> getGraph()
      Deprecated.
      Returns the graph object of this CDKRGraph.
      Returns:
      The graph object, a list
    • addNode

      public void addNode(CDKRNode newNode)
      Deprecated.
      Adds a new node to the CDKRGraph.
      Parameters:
      newNode - The node to add to the graph
    • parse

      public void parse(BitSet sourceBitSet, BitSet targetBitSet, boolean findAllStructure, boolean findAllMap, TimeManager timeManager) throws CDKException
      Deprecated.
      Parsing of the CDKRGraph. This is the main method to perform a query. Given the constrains sourceBitSet and targetBitSet defining mandatory elements in G1 and G2 and given the search options, this method builds an initial set of starting nodes (targetBitSet) and parses recursively the CDKRGraph to find a list of solution according to these parameters.
      Parameters:
      sourceBitSet - constrain on the graph G1
      targetBitSet - constrain on the graph G2
      findAllStructure - true if we want all results to be generated
      findAllMap - true is we want all possible 'mappings'
      timeManager -
      Throws:
      CDKException
    • getSolutions

      public List<BitSet> getSolutions()
      Deprecated.
      Returns the list of solutions.
      Returns:
      The solution list
    • bitSetToRMap

      public List<CDKRMap> bitSetToRMap(BitSet set)
      Deprecated.
      Converts a CDKRGraph bitset (set of CDKRNode) to a list of CDKRMap that represents the mapping between to substructures in G1 and G2 (the projection of the CDKRGraph bitset on G1 and G2).
      Parameters:
      set - the BitSet
      Returns:
      the CDKRMap list
    • setAllStructure

      public void setAllStructure(boolean findAllStructure)
      Deprecated.
      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).
      Parameters:
      findAllStructure -
    • setAllMap

      public void setAllMap(boolean findAllMap)
      Deprecated.
      Sets the 'finAllMap' option. If true all possible 'mappings' will be generated. If false the search will keep only one 'mapping' per structure association.
      Parameters:
      findAllMap -
    • setMaxIteration

      public void setMaxIteration(int maxIterator)
      Deprecated.
      Sets the maxIteration for the CDKRGraph parsing. If set to -1, then no iteration maximum is taken into account.
      Parameters:
      maxIterator - The new maxIteration value
    • toString

      public String toString()
      Deprecated.
      Returns a string representation of the CDKRGraph.
      Overrides:
      toString in class Object
      Returns:
      the string representation of the CDKRGraph
    • projectG1

      public BitSet projectG1(BitSet set)
      Deprecated.
      Projects a CDKRGraph bitset on the source graph G1.
      Parameters:
      set - CDKRGraph BitSet to project
      Returns:
      The associate BitSet in G1
    • projectG2

      public BitSet projectG2(BitSet set)
      Deprecated.
      Projects a CDKRGraph bitset on the source graph G2.
      Parameters:
      set - CDKRGraph BitSet to project
      Returns:
      The associate BitSet in G2