1 /*
2  * Copyright (c) 2013 European Bioinformatics Institute (EMBL-EBI)
3  *                    John May
4  *               2018 John Mayfield (ne May)
5  *
6  * Contact: cdk-devel@lists.sourceforge.net
7  *
8  * This program is free software; you can redistribute it and/or modify it
9  * under the terms of the GNU Lesser General Public License as published by
10  * the Free Software Foundation; either version 2.1 of the License, or (at
11  * your option) any later version. All we ask is that proper credit is given
12  * for our work, which includes - but is not limited to - adding the above
13  * copyright notice to the beginning of your source code files, and to any
14  * copyright notice that you may distribute with programs based on this work.
15  *
16  * This program is distributed in the hope that it will be useful, but WITHOUT
17  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
18  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
19  * License for more details.
20  *
21  * You should have received a copy of the GNU Lesser General Public License
22  * along with this program; if not, write to the Free Software
23  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
24  */
25 
26 package org.openscience.cdk.isomorphism;
27 
28 import com.google.common.base.Predicate;
29 import org.openscience.cdk.CDKConstants;
30 import org.openscience.cdk.graph.ConnectedComponents;
31 import org.openscience.cdk.graph.GraphUtil;
32 import org.openscience.cdk.interfaces.IAtomContainer;
33 
34 import java.util.Arrays;
35 
36 /**
37  * A predicate for verifying component level grouping in query/target structure
38  * matching. The grouping is used by SMARTS and is critical to querying
39  * reactions. The grouping specifies that substructures in the query should
40  * match to separate components in the target. The grouping specification is
41  * indicated by an {@code int[]} array of length (|V(query)| + 1). The final
42  * index indicates the maximum component group (in the query). A specification
43  * of '0' indicates there are no grouping restrictions.
44  *
45  * <blockquote><pre>
46  * // grouping is actually set by SMARTS parser but this shows how it's stored
47  * query.setProperty(ComponentGrouping.KEY, grouping);
48  *
49  * IAtomContainer query, target;
50  * Pattern        pattern = ...; // create pattern for query
51  *
52  * // filter for mappings which respect component grouping in the query
53  * Iterables.filter(pattern.matchAll(target),
54  *                  new ComponentGrouping(query, target));
55  * </pre></blockquote>
56  *
57  * @author John May
58  * @cdk.module isomorphism
59  * @see Pattern
60  */
61 final class ComponentFilter implements Predicate<int[]> {
62 
63     /**
64      * Key indicates where the grouping should be store in the query
65      * properties.
66      */
67     public static final String        KEY = "COMPONENT.GROUPING";
68 
69     /** The required  (query) and the targetComponents of the target. */
70     private final int[]               queryComponents, targetComponents;
71 
72     /**
73      * Create a predicate to match components for the provided query and target.
74      * The target is converted to an adjacency list ({@link
75      * GraphUtil#toAdjList(IAtomContainer)}) and the query components extracted
76      * from the property {@link #KEY} in the query.
77      *
78      * @param query  query structure
79      * @param target target structure
80      */
ComponentFilter(IAtomContainer query, IAtomContainer target)81     public ComponentFilter(IAtomContainer query, IAtomContainer target) {
82         this(query.getProperty(KEY) == null ? determineComponents(query, false) : query.getProperty(KEY, int[].class),
83              determineComponents(target, true));
84     }
85 
determineComponents(IAtomContainer target, boolean auto)86     private static int[] determineComponents(IAtomContainer target, boolean auto) {
87         int[] components = null;
88         // no atoms -> no components
89         if (target.isEmpty())
90             components = new int[0];
91         // defined by reaction grouping
92         if (components == null && target.getAtom(0).getProperty(CDKConstants.REACTION_GROUP) != null) {
93             int max = 0;
94             components = new int[target.getAtomCount()+1];
95             for (int i = 0; i < target.getAtomCount(); i++) {
96                 Integer grp = target.getAtom(i).getProperty(CDKConstants.REACTION_GROUP);
97                 if (grp == null)
98                     grp = 0;
99                 components[i] = grp;
100                 if (grp > max)
101                     max = grp;
102             }
103             components[target.getAtomCount()] = max;
104         }
105         // calculate from connection table
106         if (components == null && auto) {
107             components = new ConnectedComponents(GraphUtil.toAdjList(target)).components();
108             components = Arrays.copyOf(components, components.length+1);
109             int max = 0;
110             for (int grp : components)
111                 if (grp > max)
112                     max = grp;
113             components[target.getAtomCount()] = max;
114         }
115         return components;
116     }
117 
118     /**
119      * Create a predicate to match components for the provided query (grouping)
120      * and target (connected components).
121      *
122      * @param grouping  query grouping
123      * @param targetComponents connected component of the target
124      */
ComponentFilter(int[] grouping, int[] targetComponents)125     public ComponentFilter(int[] grouping, int[] targetComponents) {
126         this.queryComponents  = grouping;
127         this.targetComponents = targetComponents;
128     }
129 
130     /**
131      * Does the mapping respected the component grouping specified by the
132      * query.
133      *
134      * @param mapping a permutation of the query vertices
135      * @return the mapping preserves the specified grouping
136      */
137     @Override
apply(final int[] mapping)138     public boolean apply(final int[] mapping) {
139 
140         // no grouping required
141         if (queryComponents == null) return true;
142 
143         // bidirectional map of query/target components, last index
144         // of query components holds the count
145         int[] usedBy = new int[targetComponents[targetComponents.length-1]+1];
146         int[] usedIn = new int[queryComponents[queryComponents.length-1] + 1];
147 
148         // verify we don't have any collisions
149         for (int v = 0; v < mapping.length; v++) {
150             if (queryComponents[v] == 0) continue;
151 
152             int w = mapping[v];
153 
154             int queryComponent = queryComponents[v];
155             int targetComponent = targetComponents[w];
156 
157             // is the target component already used by a query component?
158             if (usedBy[targetComponent] == 0)
159                 usedBy[targetComponent] = queryComponent;
160             else if (usedBy[targetComponent] != queryComponent) return false;
161 
162             // is the query component already used in a target component?
163             if (usedIn[queryComponent] == 0)
164                 usedIn[queryComponent] = targetComponent;
165             else if (usedIn[queryComponent] != targetComponent) return false;
166 
167         }
168 
169         return true;
170     }
171 }
172