Source code: org/openscience/compchem/IsomorphismTester.java
1 /* IsomorphismTester.java
2 *
3 * Copyright (C) 1997, 1998 Dr. Christoph Steinbeck
4 *
5 * Contact: steinbeck@ice.mpg.de
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License as
9 * published by the Free Software Foundation; either version 2 of the
10 * License, or (at your option) any later version. All I ask is that
11 * proper credit is given for my work, which includes - but is not
12 * limited to - adding the above copyright notice to the beginning of
13 * your source code files, and to any copyright notice that you may
14 * distribute with programs based on this work.
15 *
16 * This program is distributed in the hope that it will be useful, but
17 * WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 * General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public License
22 * along with this program; if not, write to the Free Software
23 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
24 * 02111-1307, USA.
25 *
26 */
27
28 package org.openscience.compchem;
29
30 import java.util.Vector;
31
32
33 public class IsomorphismTester {
34
35 int[] baseTable;
36 Node[] baseNodes;
37
38 public IsomorphismTester() {}
39
40
41 public IsomorphismTester(Node[] atomSet) {
42 this.baseNodes = atomSet;
43 this.baseTable = computeMorganMatrix(baseNodes);
44 }
45
46 public int[] computeMorganMatrix(Node[] atomSet) {
47 int [] morganMatrix, tempMorganMatrix;
48 int N = atomSet.length;
49 morganMatrix = new int[N];
50 tempMorganMatrix = new int[N];
51 for (int f = 0; f < N; f++) {
52 morganMatrix[f] = atomSet[f].getBondCount();
53 tempMorganMatrix[f] = atomSet[f].getBondCount();
54 }
55 for (int i = 0; i < N; i++) {
56 for (int f = 0; f < N; f++) {
57 for (int g = 0; g < atomSet[f].degree; g ++) {
58 morganMatrix[f] += tempMorganMatrix[atomSet[f].nodeTable[g]];
59 }
60 }
61 System.arraycopy(morganMatrix, 0, tempMorganMatrix, 0, N);
62 }
63 return morganMatrix;
64 }
65
66 public boolean isIsomorph(Node[] atomSet1, Node[] atomSet2) {
67 boolean found;
68 int[] morganMatrix1 = computeMorganMatrix(atomSet1);
69 int[] morganMatrix2 = computeMorganMatrix(atomSet2);
70 for (int f = 0; f < morganMatrix1.length; f++) {
71 found = false;
72 for (int g = 0; g < morganMatrix2.length; g++) {
73 if (morganMatrix1[f] == morganMatrix2[g]) {
74 if(!(atomSet1[f].symbol.equals(atomSet2[g].symbol) && atomSet1[f].HCount == atomSet2[g].HCount))
75 return false;
76 found = true;
77 }
78 }
79 if (!found)
80 return false;
81 }
82 return true;
83 }
84
85 public boolean isIsomorph(Node[] atomSet2) {
86 boolean found;
87 int[] morganMatrix2 = computeMorganMatrix(atomSet2);
88 for (int f = 0; f < baseTable.length; f++) {
89 found = false;
90 for (int g = 0; g < morganMatrix2.length; g++) {
91 if (baseTable[f] == morganMatrix2[g]) {
92 if(!(baseNodes[f].symbol.equals(atomSet2[g].symbol) && baseNodes[f].HCount == atomSet2[g].HCount))
93 return false;
94 found = true;
95 }
96 }
97 if (!found)
98 return false;
99 }
100 return true;
101 }
102
103
104 }