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