org.openscience.cdk.isomorphism

Class Ullmann

java.lang.Object

org.openscience.cdk.isomorphism.Pattern

org.openscience.cdk.isomorphism.Ullmann

public final class Ullmann
extends Pattern

A structure pattern which utilises the Ullmann algorithm [Ullmann J R, An Algorithm for Subgraph Isomorphism, Journal of the Association for Computing Machinery, 1976, 23:?-?, doi:10.1145/321921.321925]. Find and count the number molecules which contain the query substructure.

 IAtomContainer query   = ...;
 Pattern        pattern = Ullmann.findSubstructure(query);

 int hits = 0;
 for (IAtomContainer m : ms)
     if (pattern.matches(m))
         hits++;
 

Finding the matching to molecules which contain the query substructure. It is more efficient to obtain the match(org.openscience.cdk.interfaces.IAtomContainer) and check it's size rather than test if it Pattern.matches(org.openscience.cdk.interfaces.IAtomContainer) first. These methods automatically verify stereochemistry.

IAtomContainer query   = ...;
 Pattern        pattern = Ullmann.findSubstructure(query);

 int hits = 0;
 for (IAtomContainer m : ms) {
     int[] match = pattern.match(m);
     if (match.length > 0)
         hits++;
 }
 

Author:

John May

Belongs to CDK module:

isomorphism

Method Summary

Methods

Modifier and Type	Method and Description
static Pattern	findSubstructure(IAtomContainer query) Create a pattern which can be used to find molecules which contain the query structure.
int[]	match(IAtomContainer target) Find a matching of this pattern in the target.
Mappings	matchAll(IAtomContainer target) Find all mappings of this pattern in the target.

Methods inherited from class org.openscience.cdk.isomorphism.Pattern

findIdentical, matchAll, matches, matches

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

match

public int[] match(IAtomContainer target)

Description copied from class: Pattern

Find a matching of this pattern in the target. If no such order exist an empty mapping is returned. Depending on the implementation stereochemistry may be checked (recommended).

Pattern        pattern = ...; // create pattern
 for (IAtomContainer m : ms) {
     int[] mapping = pattern.match(m);
     if (mapping.length > 0) {
         // found mapping!
     }
 }
 

Specified by:

match in class Pattern

Parameters:

target - the container to search for the pattern in

Returns:

the mapping from the pattern to the target or an empty array

matchAll

public Mappings matchAll(IAtomContainer target)

Description copied from class: Pattern

Find all mappings of this pattern in the target. Stereochemistry should not be checked to allow filtering with Mappings.stereochemistry().

 Pattern pattern = Pattern.findSubstructure(query);
 for (IAtomContainer m : ms) {
     for (int[] mapping : pattern.matchAll(m)) {
         // found mapping
     }
 }
 

Using the fluent interface (see Mappings) we can search and manipulate the mappings. Here's an example of finding the first 5 mappings and creating an array. If the mapper is lazy other states are simply not explored.

 // find only the first 5 mappings and store them in an array
 Pattern pattern  = Pattern.findSubstructure(query);
 int[][] mappings = pattern.matchAll(target)
                           .limit(5)
                           .toArray();
 

Specified by:

matchAll in class Pattern

Parameters:

target - the container to search for the pattern in

Returns:

the mapping from the pattern to the target

See Also:

Mappings

findSubstructure

public static Pattern findSubstructure(IAtomContainer query)

Create a pattern which can be used to find molecules which contain the query structure.

Parameters:

query - the substructure to find

Returns:

a pattern for finding the query