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