1 /* 2 * Copyright (c) 2015 John May <jwmay@users.sf.net> 3 * 4 * Contact: cdk-devel@lists.sourceforge.net 5 * 6 * This program is free software; you can redistribute it and/or modify it 7 * under the terms of the GNU Lesser General Public License as published by 8 * the Free Software Foundation; either version 2.1 of the License, or (at 9 * your option) any later version. All we ask is that proper credit is given 10 * for our work, which includes - but is not limited to - adding the above 11 * copyright notice to the beginning of your source code files, and to any 12 * copyright notice that you may distribute with programs based on this work. 13 * 14 * This program is distributed in the hope that it will be useful, but WITHOUT 15 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 16 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 17 * License for more details. 18 * 19 * You should have received a copy of the GNU Lesser General Public License 20 * along with this program; if not, write to the Free Software 21 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 U 22 */ 23 24 package org.openscience.cdk.layout; 25 26 import org.openscience.cdk.interfaces.IAtom; 27 import org.openscience.cdk.interfaces.IAtomContainer; 28 import org.openscience.cdk.tools.manipulator.AtomContainerManipulator; 29 30 import javax.vecmath.Point2d; 31 32 /** 33 * Measure and update a score of congestion in a molecule layout 34 * {@cdk.cite HEL99}, {@cdk.cite Clark06}. This can be tuned in 35 * several ways but currently uses a basic '1/(dist^2)'. 36 */ 37 final class Congestion { 38 39 // lower bound on scores 40 private static final double MIN_SCORE = 0.00001; 41 42 double[][] contribution; 43 double score; 44 IAtom[] atoms; 45 Congestion(IAtomContainer mol, int[][] adjList)46 Congestion(IAtomContainer mol, int[][] adjList) { 47 final int numAtoms = mol.getAtomCount(); 48 this.contribution = new double[numAtoms][numAtoms]; 49 this.atoms = AtomContainerManipulator.getAtomArray(mol); 50 for (int v = 0; v < numAtoms; v++) 51 for (int w : adjList[v]) 52 contribution[v][v] = contribution[v][w] = -1; 53 this.score = initScore(); 54 } 55 56 /** 57 * Calculate the initial score. 58 * 59 * @return congestion score 60 */ initScore()61 private double initScore() { 62 double score = 0; 63 final int n = atoms.length; 64 for (int i = 0; i < n; i++) { 65 final Point2d p1 = atoms[i].getPoint2d(); 66 for (int j = i + 1; j < n; j++) { 67 if (contribution[i][j] < 0) continue; 68 final Point2d p2 = atoms[j].getPoint2d(); 69 final double x = p1.x - p2.x; 70 final double y = p1.y - p2.y; 71 final double len2 = x * x + y * y; 72 score += contribution[j][i] = contribution[i][j] = 1 / Math.max(len2, MIN_SCORE); 73 } 74 } 75 return score; 76 } 77 78 /** 79 * Update the score considering that some atoms have moved. We only 80 * need to update the score of atom that have moved vs those that haven't 81 * since all those that moved did so together. 82 * 83 * @param visit visit flags 84 * @param vs visit list 85 * @param n number of visited in visit list 86 */ update(boolean[] visit, int[] vs, int n)87 void update(boolean[] visit, int[] vs, int n) { 88 int len = atoms.length; 89 double subtract = 0; 90 for (int i = 0; i < n; i++) { 91 final int v = vs[i]; 92 final Point2d p1 = atoms[v].getPoint2d(); 93 for (int w = 0; w < len; w++) { 94 if (visit[w] || contribution[v][w] < 0) continue; 95 subtract += contribution[v][w]; 96 final Point2d p2 = atoms[w].getPoint2d(); 97 final double x = p1.x - p2.x; 98 final double y = p1.y - p2.y; 99 final double len2 = x * x + y * y; 100 score += contribution[w][v] = contribution[v][w] = 1 / Math.max(len2, MIN_SCORE); 101 } 102 } 103 score -= subtract; 104 } 105 106 /** 107 * Update the score considering the atoms have moved (provided). 108 * 109 * @param vs visit list 110 * @param n number of visited in visit list 111 */ update(int[] vs, int n)112 void update(int[] vs, int n) { 113 int len = atoms.length; 114 double subtract = 0; 115 for (int i = 0; i < n; i++) { 116 final int v = vs[i]; 117 final Point2d p1 = atoms[v].getPoint2d(); 118 for (int w = 0; w < len; w++) { 119 if (contribution[v][w] < 0) continue; 120 subtract += contribution[v][w]; 121 final Point2d p2 = atoms[w].getPoint2d(); 122 final double x = p1.x - p2.x; 123 final double y = p1.y - p2.y; 124 final double len2 = x * x + y * y; 125 score += contribution[w][v] = contribution[v][w] = 1 / Math.max(len2, MIN_SCORE); 126 } 127 } 128 score -= subtract; 129 } 130 131 /** 132 * The congestion score. 133 * 134 * @return the current score 135 */ score()136 double score() { 137 return score; 138 } 139 140 /** 141 * Access the contribution of an atom pair to the congestion. 142 * 143 * @param i atom idx 144 * @param j atom idx 145 * @return score 146 */ contribution(int i, int j)147 double contribution(int i, int j) { 148 return contribution[i][j]; 149 } 150 } 151