1 /* 2 * Copyright (c) 2013 European Bioinformatics Institute (EMBL-EBI) 3 * John May <jwmay@users.sf.net> 4 * 5 * Contact: cdk-devel@lists.sourceforge.net 6 * 7 * This program is free software; you can redistribute it and/or modify it 8 * under the terms of the GNU Lesser General Public License as published by 9 * the Free Software Foundation; either version 2.1 of the License, or (at 10 * your option) any later version. All we ask is that proper credit is given 11 * for our work, which includes - but is not limited to - adding the above 12 * copyright notice to the beginning of your source code files, and to any 13 * copyright notice that you may distribute with programs based on this work. 14 * 15 * This program is distributed in the hope that it will be useful, but WITHOUT 16 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 17 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 18 * License for more details. 19 * 20 * You should have received a copy of the GNU Lesser General Public License 21 * along with this program; if not, write to the Free Software 22 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 U 23 */ 24 25 package org.openscience.cdk.isomorphism; 26 27 /** 28 * Defines a state for matching (subgraph-)isomorphism from a query graph 29 * (<i>G1</i>) to a target graph (<i>G2</i>). The mutable state allows 30 * generation and adding and removal of mappings. A mapping {n, m} indicates a 31 * query vertex (from <i>G1</i>), n, is paired (mapped) with the target vertex, 32 * m (from <i>G2</i>). Candidate pairs are generated using {@link #nextN(int)} 33 * and {@link #nextM(int)}. Each candidate pair {n, m} is then {@link #add}ed if 34 * the mapping was feasible. 35 * 36 * @author John May 37 * @cdk.module isomorphism 38 */ 39 abstract class State { 40 41 /** 42 * Given the previous candidate generate the next query candidate. The first 43 * candidate passed is always -1. 44 * 45 * @param n the previous candidate 46 * @return next candidate 47 */ nextN(int n)48 abstract int nextN(int n); 49 50 /** 51 * Given the previous candidate generate the next target candidate. The 52 * first candidate passed is always -1. 53 * 54 * @param n the current n vertex 55 * @param m the previous candidate 56 * @return next candidate 57 */ nextM(int n, int m)58 abstract int nextM(int n, int m); 59 60 /** 61 * The max query candidate (number of vertices in the query). 62 * 63 * @return <i>|V| ∈ G1</i> 64 */ nMax()65 abstract int nMax(); 66 67 /** 68 * The max target candidate (number of vertices in the target). 69 * 70 * @return <i>|V| ∈ G2</i> 71 */ mMax()72 abstract int mMax(); 73 74 /** 75 * Add a mapping between n (a vertex G1) and m (a vertex in G2). If the 76 * mapping was not feasible the mapping is not added. 77 * 78 * @param n a vertex in G1 79 * @param m a vertex in G2 80 * @return the mapping was added 81 */ add(int n, int m)82 abstract boolean add(int n, int m); 83 84 /** 85 * Remove a mapping (backtrack) between n (a vertex G1) and m (a vertex in 86 * G2). 87 * 88 * @param n a vertex in G1 89 * @param m a vertex in G2 90 */ remove(int n, int m)91 abstract void remove(int n, int m); 92 93 /** 94 * Access a copy of the current mapping. 95 * 96 * @return mapping of vertices from <i>G1</i> to <i>G2</i> 97 */ mapping()98 abstract int[] mapping(); 99 100 /** 101 * Current size of the state. If <i>size</i> is the current number of mapped 102 * candidates. 103 * 104 * @return the size of the state 105 */ size()106 abstract int size(); 107 } 108