RGraph (cdk 1.5.15 API)

java.lang.Object
- org.openscience.cdk.isomorphism.mcss.RGraph

```
public class RGraph
extends Object
```
This class implements the Resolution Graph (RGraph). The RGraph is a graph based representation of the search problem. An RGraph is constructed 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.
Example:
```
    G1 : C-C=O  and G2 : C-C-C=0
         1 2 3           1 2 3 4
 
```
The resulting RGraph(G1,G2) will contain 3 nodes:
- Node A : association between bond C-C : 1-2 in G1 and 1-2 in G2
- Node B : 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 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.
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,....).
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 RGraph requires simply to set the constrains (if any) and to invoke the parsing method (parse())
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.
The RGraph model is independent 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,....)
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. and Jauffret, Ph. and Hanser, Th. and Jauffret, Ph. and Kaufmann, G., Machine Learning of generic reactions: 3. An efficient algorithm for maximal common substructure determination, Tetrahedron Comput. Methodol., 1990, 3:351-358] 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

Source code:
master

Belongs to CDK module:
standard

Created on:

2002-07-17

Requires:

java1.4+

Constructor Summary

Constructors
Constructor and Description

RGraph()
Constructor for the RGraph object and creates an empty RGraph.

Constructors
Constructor and Description
`RGraph()` Constructor for the RGraph object and creates an empty RGraph.

Method Summary

Methods
Modifier and Type	Method and Description
`void`	`addNode(RNode newNode)` Adds a new node to the RGraph.
`List<RMap>`	`bitSetToRMap(BitSet set)` 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).
`void`	`clear()` Reinitialisation of the TGraph.
`int`	`getFirstGraphSize()` Returns the size of the first of the two compared graphs.
`List<RNode>`	`getGraph()` Returns the graph object of this RGraph.
`int`	`getSecondGraphSize()` Returns the size of the second of the two compared graphs.
`List<BitSet>`	`getSolutions()` Returns the list of solutions.
`void`	`parse(BitSet c1, BitSet c2, boolean findAllStructure, boolean findAllMap)` Parsing of the RGraph.
`BitSet`	`projectG1(BitSet set)` Projects a RGraph bitset on the source graph G1.
`BitSet`	`projectG2(BitSet set)` Projects a RGraph bitset on the source graph G2.
`void`	`setAllMap(boolean findAllMap)` Sets the 'finAllMap' option.
`void`	`setAllStructure(boolean findAllStructure)` Sets the 'AllStructres' option.
`void`	`setFirstGraphSize(int n1)` Sets the size of the first of the two compared graphs.
`void`	`setMaxIteration(int it)` Sets the maxIteration for the RGraph parsing.
`void`	`setSecondGraphSize(int n2)` Returns the size of the second of the two compared graphs.
`void`	`setStart(long start)`
`void`	`setTimeout(long timeout)` Sets the time in milliseconds until the substructure search will be breaked.
`String`	`toString()` Returns a string representation of the RGraph.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

- Constructor Detail
  - RGraph
```
public RGraph()
```
    Constructor for the RGraph object and creates an empty RGraph.
- Method Detail
  - getFirstGraphSize
```
public int getFirstGraphSize()
```
    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()
```
    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 n1)
```
    Sets the size of the first of the two compared graphs.
    
    Parameters:
    n1 - The size of the second of the two compared graphs
  - setSecondGraphSize
```
public void setSecondGraphSize(int n2)
```
    Returns the size of the second of the two compared graphs.
    
    Parameters:
    n2 - The size of the second of the two compared graphs
  - clear
```
public void clear()
```
    Reinitialisation of the TGraph.
  - getGraph
```
public List<RNode> getGraph()
```
    Returns the graph object of this RGraph.
    
    Returns:
    The graph object, a list
  - addNode
```
public void addNode(RNode newNode)
```
    Adds a new node to the RGraph.
    
    Parameters:
    newNode - The node to add to the graph
  - parse
```
public void parse(BitSet c1,
         BitSet c2,
         boolean findAllStructure,
         boolean findAllMap)
```
    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 method builds an initial set of starting nodes (B) and parses recursively the RGraph to find a list of solution according to these parameters.
    
    Parameters:
    c1 - constrain on the graph G1
    c2 - constrain on the graph G2
    findAllStructure - true if we want all results to be generated
    findAllMap - true is we want all possible 'mappings'
  - getSolutions
```
public List<BitSet> getSolutions()
```
    Returns the list of solutions.
    
    Returns:
    The solution list
  - bitSetToRMap
```
public List<RMap> bitSetToRMap(BitSet set)
```
    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).
    
    Parameters:
    set - the BitSet
    
    Returns:
    the RMap list
  - setAllStructure
```
public void setAllStructure(boolean findAllStructure)
```
    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)
```
    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 it)
```
    Sets the maxIteration for the RGraph parsing. If set to -1, then no iteration maximum is taken into account.
    
    Parameters:
    it - The new maxIteration value
  - toString
```
public String toString()
```
    Returns a string representation of the RGraph.
    
    Overrides:
    
    toString in class Object
    
    Returns:
    the string representation of the RGraph
  - projectG1
```
public BitSet projectG1(BitSet set)
```
    Projects a RGraph bitset on the source graph G1.
    
    Parameters:
    set - RGraph BitSet to project
    
    Returns:
    The associate BitSet in G1
  - projectG2
```
public BitSet projectG2(BitSet set)
```
    Projects a RGraph bitset on the source graph G2.
    
    Parameters:
    set - RGraph BitSet to project
    
    Returns:
    The associate BitSet in G2
  - setTimeout
```
public void setTimeout(long timeout)
```
    Sets the time in milliseconds until the substructure search will be breaked.
    
    Parameters:
    timeout - Time in milliseconds. -1 to ignore the timeout.
  - setStart
```
public void setStart(long start)
```
    Parameters:
    start - The start time in milliseconds.

Class RGraph

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

RGraph

Method Detail

getFirstGraphSize

getSecondGraphSize

setFirstGraphSize

setSecondGraphSize

clear

getGraph

addNode

parse

getSolutions

bitSetToRMap

setAllStructure

setAllMap

setMaxIteration

toString

projectG1

projectG2

setTimeout

setStart