Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
Convenience, return number of rings (circuit rank) when ring flags ar…
…e assigned.
  • Loading branch information
johnmay committed Mar 29, 2017
1 parent fd684bd commit f36a9f4
Show file tree
Hide file tree
Showing 6 changed files with 43 additions and 3 deletions.
11 changes: 8 additions & 3 deletions base/core/src/main/java/org/openscience/cdk/graph/Cycles.java
Expand Up @@ -417,10 +417,12 @@ public static CycleFinder allOrVertexShort() {
* @param mol molecule
* @see IBond#isInRing()
* @see IAtom#isInRing()
* @return Number of rings found (circuit rank)
* @see <a href="https://en.wikipedia.org/wiki/Circuit_rank">Circuit Rank</a>
*/
public static void markRingAtomsAndBonds(IAtomContainer mol) {
public static int markRingAtomsAndBonds(IAtomContainer mol) {
EdgeToBondMap bonds = EdgeToBondMap.withSpaceFor(mol);
markRingAtomsAndBonds(mol, GraphUtil.toAdjList(mol, bonds), bonds);
return markRingAtomsAndBonds(mol, GraphUtil.toAdjList(mol, bonds), bonds);
}

/**
Expand All @@ -431,8 +433,10 @@ public static void markRingAtomsAndBonds(IAtomContainer mol) {
* @param mol molecule
* @see IBond#isInRing()
* @see IAtom#isInRing()
* @return Number of rings found (circuit rank)
* @see <a href="https://en.wikipedia.org/wiki/Circuit_rank">Circuit Rank</a>
*/
public static void markRingAtomsAndBonds(IAtomContainer mol, int[][] adjList, EdgeToBondMap bondMap) {
public static int 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);
Expand All @@ -448,6 +452,7 @@ public static void markRingAtomsAndBonds(IAtomContainer mol, int[][] adjList, Ed
}
}
}
return ringSearch.numRings();
}

/**
Expand Down
Expand Up @@ -34,6 +34,13 @@
*/
public interface CyclicVertexSearch {

/**
* Returns the number of cycles (circuit rank, frère jacques number, num SSSR).
*
* @return number of cycles
*/
int numCycles();

/**
* Returns true if the vertex <i>v</i> is in a cycle.
*
Expand Down
Expand Up @@ -56,6 +56,8 @@ class JumboCyclicVertexSearch implements CyclicVertexSearch {
/** vertex colored by each component. */
private int[] colors;

private int numCycles = 0;

/**
* Create a new cyclic vertex search for the provided graph.
*
Expand Down Expand Up @@ -116,6 +118,7 @@ private void search(int v, BitSet prev, BitSet curr) {
// we don't check out current state as this will always
// include w - they are adjacent
if (prev.get(w)) {
numCycles++;
// we have a cycle, xor the state when we last visited 'w'
// with our current state. this set is all the vertices
// we visited since then
Expand All @@ -135,6 +138,11 @@ else if (!visited.get(w)) {
/** Synchronisation lock. */
private final Object lock = new Object();

@Override
public int numCycles() {
return numCycles;
}

/**
* Lazily build an indexed lookup of vertex color. The vertex color
* indicates which cycle a given vertex belongs. If a vertex belongs to more
Expand Down
Expand Up @@ -56,6 +56,8 @@ class RegularCyclicVertexSearch implements CyclicVertexSearch {
/** Vertex colors - which component does each vertex belong. */
private volatile int[] colors;

private int numCycles = 0;

/**
* Create a new cyclic vertex search for the provided graph.
*
Expand Down Expand Up @@ -113,6 +115,7 @@ private void search(int v, long prev, long curr) {
// we don't check out current state as this will always
// include w - they are adjacent
if (isBitSet(prev, w)) {
numCycles++;

// xor the state when we last visited 'w' with our current
// state. this set is all the vertices we visited since then
Expand All @@ -126,6 +129,11 @@ private void search(int v, long prev, long curr) {
}
}

@Override
public int numCycles() {
return numCycles;
}

/**
* Returns whether the vertex 'v' has been visited.
*
Expand Down
Expand Up @@ -179,6 +179,16 @@ private static CyclicVertexSearch makeSearcher(int[][] graph) {
}
}

/**
* Access the number of rings found (aka. circuit rank, SSSR size).
*
* @return number of rings
* @see <a href="https://en.wikipedia.org/wiki/Circuit_rank">Circuit Rank</a>
*/
public int numRings() {
return searcher.numCycles();
}

/**
* Determine whether the edge between the vertices <i>u</i> and <i>v</i> is
* cyclic.
Expand Down
Expand Up @@ -364,6 +364,7 @@ public void connectingEdge1() {
IAtomContainer mol = diSpiroPentane();
RingSearch rs = new RingSearch(mol);
IAtomContainer frag = rs.ringFragments();
assertThat(rs.numRings(), is(4));
assertThat(mol.getBondCount(), is(frag.getBondCount() + 1));
}

Expand All @@ -372,6 +373,7 @@ public void connectingEdge2() {
IAtomContainer mol = triSpiroPentane();
RingSearch rs = new RingSearch(mol);
IAtomContainer frag = rs.ringFragments();
assertThat(rs.numRings(), is(5));
assertThat(mol.getBondCount(), is(frag.getBondCount()));
}

Expand Down

0 comments on commit f36a9f4

Please sign in to comment.