Merge pull request #169 from cdk/patch/sdg-refine

Looks useful. I could not merge it immediately, not realizing it's just push button via the website...
cdk · Oct 24, 2015 · f554bb9 · f554bb9
2 parents df1fb51 + b3ea9e1
commit f554bb9
Show file tree

Hide file tree

Showing 11 changed files with 1,386 additions and 66 deletions.
diff --git a/app/depict/src/main/java/org/openscience/cdk/depict/MolGridDepiction.java b/app/depict/src/main/java/org/openscience/cdk/depict/MolGridDepiction.java
@@ -220,6 +220,9 @@ String toVecStr(String fmt) {
 
         if (fmt.equals(SVG_FMT)) {
             svgPrevisit(fmt, scale * zoom * fitting, (SvgDrawVisitor) visitor, elements);
+        } else {
+            // pdf can handle fraction coords just fine
+            ((AWTDrawVisitor) visitor).setRounding(false);
         }
 
         visitor.setTransform(AffineTransform.getScaleInstance(1,-1));

diff --git a/app/depict/src/main/java/org/openscience/cdk/depict/ReactionDepiction.java b/app/depict/src/main/java/org/openscience/cdk/depict/ReactionDepiction.java
@@ -338,6 +338,9 @@ String toVecStr(String fmt) {
                                                          : AWTDrawVisitor.forVectorGraphics(wrapper.g2);
         if (fmt.equals(SVG_FMT)) {
             svgPrevisit(fmt, scale * zoom * fitting, (SvgDrawVisitor) visitor, mainComp);
+        } else {
+            // pdf can handle fraction coords just fine
+            ((AWTDrawVisitor) visitor).setRounding(false);
         }
 
         // background color

diff --git a/base/core/src/main/java/org/openscience/cdk/graph/Cycles.java b/base/core/src/main/java/org/openscience/cdk/graph/Cycles.java
@@ -410,6 +410,46 @@ public static CycleFinder allOrVertexShort() {
         return or(all(), vertexShort());
     }
 
+
+    /**
+     * Find and mark all cyclic atoms and bonds in the provided molecule.
+     *
+     * @param mol molecule
+     * @see IBond#isInRing()
+     * @see IAtom#isInRing()
+     */
+    public static void markRingAtomsAndBonds(IAtomContainer mol) {
+        EdgeToBondMap bonds = EdgeToBondMap.withSpaceFor(mol);
+        markRingAtomsAndBonds(mol, GraphUtil.toAdjList(mol, bonds), bonds);
+    }
+
+    /**
+     * Find and mark all cyclic atoms and bonds in the provided molecule. This optimised version
+     * allows the caller to optionally provided indexed fast access structure which would otherwise
+     * be created.
+     *
+     * @param mol molecule
+     * @see IBond#isInRing()
+     * @see IAtom#isInRing()
+     */
+    public static void markRingAtomsAndBonds(IAtomContainer mol, int[][] adjList, EdgeToBondMap bondMap) {
+        RingSearch ringSearch = new RingSearch(mol, adjList);
+        for (int v = 0; v < mol.getAtomCount(); v++) {
+            mol.getAtom(v).setIsInRing(false);
+            for (int w : adjList[v]) {
+                // note we only mark the bond on second visit (first v < w) and
+                // clear flag on first visit (or if non-cyclic)
+                if (v > w && ringSearch.cyclic(v, w)) {
+                    bondMap.get(v, w).setIsInRing(true);
+                    mol.getAtom(v).setIsInRing(true);
+                    mol.getAtom(w).setIsInRing(true);
+                } else {
+                    bondMap.get(v, w).setIsInRing(false);
+                }
+            }
+        }
+    }
+
     /**
      * Use an auxiliary cycle finder if the primary method was intractable.
      *

diff --git a/base/test-core/src/test/java/org/openscience/cdk/graph/CyclesTest.java b/base/test-core/src/test/java/org/openscience/cdk/graph/CyclesTest.java
@@ -2,7 +2,9 @@
 
 import org.junit.Test;
 import org.openscience.cdk.AtomContainer;
+import org.openscience.cdk.interfaces.IAtom;
 import org.openscience.cdk.interfaces.IAtomContainer;
+import org.openscience.cdk.interfaces.IBond;
 import org.openscience.cdk.interfaces.IRingSet;
 import org.openscience.cdk.io.MDLV2000Reader;
 import org.openscience.cdk.templates.TestMoleculeFactory;
@@ -218,6 +220,24 @@ public void toRingSet() throws Exception {
         assertThat(r2.getBond(5), is(biphenyl.getBond(12)));
     }
 
+    @Test
+    public void markAtomsAndBonds() throws Exception {
+        IAtomContainer biphenyl = makeBiphenyl();
+        Cycles.markRingAtomsAndBonds(biphenyl);
+        int cyclicAtoms = 0;
+        int cyclicBonds = 0;
+        for (IAtom atom : biphenyl.atoms()) {
+            if (atom.isInRing())
+                cyclicAtoms++;
+        }
+        for (IBond bond : biphenyl.bonds()) {
+            if (bond.isInRing())
+                cyclicBonds++;
+        }
+        assertThat(cyclicAtoms, is(biphenyl.getAtomCount()));
+        assertThat(cyclicBonds, is(biphenyl.getBondCount()-1));
+    }
+
     @Test
     public void or() throws Exception {
         CycleFinder cf = Cycles.or(Cycles.all(), Cycles.all(3));

diff --git a/display/renderawt/src/main/java/org/openscience/cdk/renderer/visitor/AWTDrawVisitor.java b/display/renderawt/src/main/java/org/openscience/cdk/renderer/visitor/AWTDrawVisitor.java
@@ -114,6 +114,11 @@ public Map<Integer, BasicStroke> getStrokeMap() {
 
     private final Graphics2D                 graphics;
 
+    /**
+     * Should we round coordinates to ints to circumvent graphical glitches from AWT.
+     */
+    private boolean roundCoords = true;
+
     /**
      * Returns the {@link Graphics2D} for for this visitor.
      *
@@ -162,6 +167,17 @@ public static AWTDrawVisitor forVectorGraphics(Graphics2D g2) {
         return new AWTDrawVisitor(g2, false, Float.NEGATIVE_INFINITY);
     }
 
+    /**
+     * Set whether we should we round coordinates to ints, this tries to circumvent
+     * graphical glitches from AWT where floating points are truncated (e.g. 1.6 -> 1)
+     * which causes notable defect such as parallel lines that aren't parallel.
+     *
+     * @param val rounding mode
+     */
+    public void setRounding(boolean val) {
+        this.roundCoords = val;
+    }
+
     private void visit(ElementGroup elementGroup) {
         elementGroup.visitChildren(this);
     }
@@ -187,7 +203,13 @@ private void visit(LineElement line) {
 
         graphics.setColor(line.color);
         transform.transform(coordinates, 0, coordinates, 0, 2);
-        graphics.draw(new Line2D.Double(coordinates[0], coordinates[1], coordinates[2], coordinates[3]));
+        if (roundCoords) {
+            graphics.drawLine((int) Math.round(coordinates[0]), (int) Math.round(coordinates[1]),
+                              (int) Math.round(coordinates[2]), (int) Math.round(coordinates[3]));
+        } else {
+            graphics.draw(new Line2D.Double(coordinates[0], coordinates[1],
+                                            coordinates[2], coordinates[3]));
+        }
         graphics.setStroke(savedStroke);
     }
 

diff --git a/doc/refs/cheminf.bibx b/doc/refs/cheminf.bibx
@@ -80,6 +80,18 @@
       <bibtex:pages>915-926</bibtex:pages>
     </bibtex:article>
   </bibtex:entry>
+
+  <bibtex:entry id="Clark06">
+    <bibtex:article>
+      <bibtex:author>Clark AM, Labute P, Santavy M</bibtex:author>
+      <bibtex:title>2D structure depiction</bibtex:title>
+      <bibtex:journal>J Chem Inf Model</bibtex:journal>
+      <bibtex:year>2006</bibtex:year>
+      <bibtex:volume>46</bibtex:volume>
+      <bibtex:number>3</bibtex:number>
+      <bibtex:pages>1107-23</bibtex:pages>
+    </bibtex:article>
+  </bibtex:entry>
 
    <bibtex:entry id="Clark13">
       <bibtex:article>
@@ -834,6 +846,17 @@ obtained by accurate mass spectrometry</bibtex:title>
     </bibtex:article>
   </bibtex:entry>
 
+  <bibtex:entry id="Shelley83">
+    <bibtex:article>
+      <bibtex:author>Shelley CA</bibtex:author>
+      <bibtex:title>Heuristic Approach for Displaying Chemical Structures</bibtex:title>
+      <bibtex:journal>J.Chem.Inf.Comput.Sci.</bibtex:journal>
+      <bibtex:year>1983</bibtex:year>
+      <bibtex:volume>23</bibtex:volume>
+      <bibtex:number>61</bibtex:number>
+    </bibtex:article>
+  </bibtex:entry>
+
   <bibtex:entry id="Grant06">
     <bibtex:article>
       <bibtex:author>J.A. Grant, J.A. Haigh, B.T. Pickup, A. Nicholls and R.A. Sayle</bibtex:author>

diff --git a/tool/sdg/src/main/java/org/openscience/cdk/layout/AtomPlacer.java b/tool/sdg/src/main/java/org/openscience/cdk/layout/AtomPlacer.java
@@ -23,18 +23,12 @@
  */
 package org.openscience.cdk.layout;
 
-import java.util.ArrayList;
-import java.util.Comparator;
-import java.util.List;
-
-import javax.vecmath.Point2d;
-import javax.vecmath.Vector2d;
-
 import org.openscience.cdk.CDKConstants;
 import org.openscience.cdk.config.Elements;
 import org.openscience.cdk.exception.CDKException;
 import org.openscience.cdk.geometry.BondTools;
 import org.openscience.cdk.geometry.GeometryUtil;
+import org.openscience.cdk.graph.GraphUtil;
 import org.openscience.cdk.graph.PathTools;
 import org.openscience.cdk.graph.matrix.ConnectionMatrix;
 import org.openscience.cdk.interfaces.IAtom;
@@ -44,6 +38,13 @@
 import org.openscience.cdk.tools.LoggingToolFactory;
 import org.openscience.cdk.tools.manipulator.AtomContainerManipulator;
 
+import javax.vecmath.Point2d;
+import javax.vecmath.Vector2d;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
 /**
  *  Methods for generating coordinates for atoms in various situations. They can
  *  be used for Automated Structure Diagram Generation or in the interactive
@@ -56,36 +57,14 @@
  */
 public class AtomPlacer {
 
-    public final static boolean debug      = true;
-    private static ILoggingTool logger     = LoggingToolFactory.createLoggingTool(AtomPlacer.class);
+    public final static boolean debug = true;
+    public static final String PRIORITY = "Weight";
+    private static ILoggingTool logger = LoggingToolFactory.createLoggingTool(AtomPlacer.class);
 
     /**
      *  The molecule to be laid out. To be assigned from outside
      */
-    IAtomContainer              molecule   = null;
-
-    final Comparator<IAtom>     ATOM_ORDER = new Comparator<IAtom>() {
-
-                                               @Override
-                                               public int compare(IAtom a, IAtom b) {
-                                                   return weight(a).compareTo(weight(b));
-                                               }
-
-                                               /**
-                                                * Access the weight property of the provided atom. If the weight is
-                                                * not set (i.e. <i>null</i>) then {@link Integer#MIN_VALUE} is
-                                                * returned. This allows atoms with no weight to sort lower then
-                                                * those with weight.
-                                                *
-                                                * @param atom an atom to obtain the weight property from
-                                                * @return the weight value or minimum integer value if null
-                                                */
-                                               private Integer weight(IAtom atom) {
-                                                   Integer weight = (Integer) atom.getProperty("Weight");
-                                                   return weight != null ? weight : Integer.MIN_VALUE;
-                                               }
-
-                                           };
+    IAtomContainer molecule = null;
 
     /**
      *  Constructor for the AtomPlacer object
@@ -814,48 +793,91 @@ static int getDegreeSum(IAtomContainer ac, IAtomContainer superAC) {
     }
 
     /**
-     *  Calculates weights for unplaced atoms.
+     * Calculates priority for atoms in a molecule.
      *
-     *@param  ac  The atomcontainer for which weights are to be calculated
+     * @param mol connected molecule
+     * @see #PRIORITY
      */
-    static void calculateWeights(IAtomContainer ac) {
-        int[] weights = getWeightNumbers(ac);
-        for (int f = 0; f < ac.getAtomCount(); f++) {
-            ac.getAtom(f).setProperty("Weight", Integer.valueOf(weights[f]));
+    static void prioritise(IAtomContainer mol) {
+        prioritise(mol, GraphUtil.toAdjList(mol));
+    }
+
+    /**
+     * Calculates priority for atoms in a molecule.
+     *
+     * @param mol connected molecule
+     * @param  adjList fast adjacency lookup
+     * @see #PRIORITY
+     */
+    static void prioritise(IAtomContainer mol, int[][] adjList) {
+        int[] weights = getPriority(mol, adjList);
+        for (int i = 0; i < mol.getAtomCount(); i++) {
+            mol.getAtom(i).setProperty(PRIORITY, weights[i]);
         }
     }
 
     /**
-     *  Makes an array containing morgan-number-like number for an atomContainer.
+     * Prioritise atoms of a molecule base on how 'buried' they are. The priority
+     * is cacheted with a morgan-like relaxation O(n^2 lg n). Priorities are assign
+     * from 1..|V| (usually less than |V| due to symmetry) where the lowest numbers
+     * have priority.
      *
-     *@param  atomContainer  The atomContainer to analyse.
-     *@return                The morgan numbers value.
+     * @param  mol     molecule
+     * @param  adjList fast adjacency lookup
+     * @return the priority
      */
-    static int[] getWeightNumbers(IAtomContainer atomContainer) {
-        int[] morganMatrix;
-        int[] tempMorganMatrix;
-        int N = atomContainer.getAtomCount();
-        morganMatrix = new int[N];
-        tempMorganMatrix = new int[N];
-        List atoms = null;
-        for (int f = 0; f < N; f++) {
-            morganMatrix[f] = atomContainer.getConnectedBondsCount(f);
-            tempMorganMatrix[f] = atomContainer.getConnectedBondsCount(f);
+    static int[] getPriority(IAtomContainer mol, int[][] adjList) {
+
+        final int n = mol.getAtomCount();
+        final Integer[] order = new Integer[n];
+        final int[] rank  = new int[n];
+        final int[] prev  = new int[n];
+
+        // init priorities, Helson 99 favours cyclic (init=2)
+        for (int f = 0; f < n; f++) {
+            rank[f]  = 1;
+            prev[f]  = 1;
+            order[f] = f;
         }
-        for (int e = 0; e < N; e++) {
-            for (int f = 0; f < N; f++) {
-                morganMatrix[f] = 0;
-                atoms = atomContainer.getConnectedAtomsList(atomContainer.getAtom(f));
-                for (int g = 0; g < atoms.size(); g++) {
-                    IAtom atom = (IAtom) atoms.get(g);
-                    if (!atom.getFlag(CDKConstants.ISPLACED)) {
-                        morganMatrix[f] += tempMorganMatrix[atomContainer.getAtomNumber(atom)];
-                    }
-                }
+
+        final Comparator<Integer> comparator = new Comparator<Integer>() {
+            @Override
+            public int compare(Integer a, Integer b) {
+                // highest (most buried) first
+                return Integer.compare(rank[a], rank[b]);
             }
-            System.arraycopy(morganMatrix, 0, tempMorganMatrix, 0, N);
+        };
+
+        int nDistinct = 1;
+
+        for (int rep = 0; rep < n; rep++) {
+            for (int i = 0; i < n; i++) {
+                rank[i] = 3 * prev[i];
+                for (int w : adjList[i])
+                    rank[i] += prev[w];
+            }
+
+            // assign new ranks
+            Arrays.sort(order, comparator);
+            int clsNum = 1;
+            prev[order[0]] = clsNum;
+            for (int i = 1; i < n; i++) {
+                if (rank[order[i]] != rank[order[i-1]])
+                    clsNum++;
+                prev[order[i]] = clsNum;
+            }
+
+            // no refinement over previous
+            if (clsNum == nDistinct)
+                break;
+            nDistinct = clsNum;
         }
-        return tempMorganMatrix;
+
+        // we want values 1 ≤ x < |V|
+        for (int i = 0; i < n; i++)
+            prev[i] = 1 + nDistinct - prev[i];
+
+        return prev;
     }
 
     static public boolean shouldBeLinear(IAtom atom, IAtomContainer molecule) {