Menu
▾
▴
[Cdk-commits] CVS: cdk/src/org/openscience/cdk/ringsearch/cyclebasis Cycle.java,1.1,1.2 CycleBasis.java,1.1,1.2 SimpleCycleBasis.java,1.1,1.2
|
From: Ulrich B. <zzz...@us...> - 2004-07-24 18:43:34
|
Update of /cvsroot/cdk/cdk/src/org/openscience/cdk/ringsearch/cyclebasis In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv6454/src/org/openscience/cdk/ringsearch/cyclebasis Modified Files: Cycle.java CycleBasis.java SimpleCycleBasis.java Log Message: added JavaDoc & copyright to SSSRFinder related classes fixed the getConnectionMatrix() and addBonds() problems Index: Cycle.java =================================================================== RCS file: /cvsroot/cdk/cdk/src/org/openscience/cdk/ringsearch/cyclebasis/Cycle.java,v retrieving revision 1.1 retrieving revision 1.2 diff -u -r1.1 -r1.2 --- Cycle.java 23 Jul 2004 14:23:53 -0000 1.1 +++ Cycle.java 24 Jul 2004 18:42:54 -0000 1.2 @@ -1,3 +1,32 @@ +/* $RCSfile$ + * $Author$ + * $Date$ + * $Revision$ + * + * Copyright (C) 2004 The Chemistry Development Kit (CDK) project + * + * Contact: cdk...@li... + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * as published by the Free Software Foundation; either version 2.1 + * of the License, or (at your option) any later version. + * All we ask is that proper credit is given for our work, which includes + * - but is not limited to - adding the above copyright notice to the beginning + * of your source code files, and to any copyright notice that you may distribute + * with programs based on this work. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + */ + package org.openscience.cdk.ringsearch.cyclebasis; import java.util.ArrayList; import java.util.Collection; @@ -11,21 +40,40 @@ import org._3pq.jgrapht.UndirectedGraph; import org._3pq.jgrapht.graph.UndirectedSubgraph; -/* - * Created on Apr 18, 2004 - * - */ - /** - * @author uli + * A cycle in a graph. + * A cycle in a graph G is a subgraph in which every vertex has even degree. + * + * @author Ulrich Bauer <ba...@cs...> + * * + * @cdk.module standard + * + * @cdk.keyword smallest-set-of-rings + * @cdk.keyword ring search + * + * @cdk.builddepends jgrapht-0.5.3.jar + * @cdk.depends jgrapht-0.5.3.jar */ + public class Cycle extends UndirectedSubgraph { + /** + * Constructs a cycle in a graph consisting of the specified edges. + * + * @param g the graph in which the cycle is contained + * @param edges the edges of the cycle + */ public Cycle (UndirectedGraph g, Collection edges) { this(g, new HashSet(edges)); } + /** + * Constructs a cycle in a graph consisting of the specified edges. + * + * @param g the graph in which the cycle is contained + * @param edges the edges of the cycle + */ public Cycle (UndirectedGraph g, Set edges) { super(g, inducedVertices(g, edges), edges); } @@ -40,10 +88,11 @@ return inducedVertices; } - public boolean hasEdge(Edge edge) { - return containsEdge(edge); - } - + /** + * Returns the sum of the weights of all edges in this cycle. + * + * @returns the sum of the weights of all edges in this cycle + */ public double weight() { double result = 0; Iterator edgeIterator = edgeSet().iterator(); @@ -53,11 +102,13 @@ return result; } - public Collection edges() { - return edgeSet(); - } - - public List vertices() { + /** + * Returns a list of the vertices contained in this cycle. + * The vertices are in the order of a traversal of the cycle. + * + * @returns a list of the vertices contained in this cycle + */ + public List vertexList() { List vertices = new ArrayList(edgeSet().size()); Object startVertex = vertexSet().iterator().next(); @@ -91,7 +142,7 @@ } public String toString() { - return vertices().toString(); + return vertexList().toString(); } public int hashCode() { Index: CycleBasis.java =================================================================== RCS file: /cvsroot/cdk/cdk/src/org/openscience/cdk/ringsearch/cyclebasis/CycleBasis.java,v retrieving revision 1.1 retrieving revision 1.2 diff -u -r1.1 -r1.2 --- CycleBasis.java 23 Jul 2004 14:23:53 -0000 1.1 +++ CycleBasis.java 24 Jul 2004 18:42:54 -0000 1.2 @@ -1,3 +1,32 @@ +/* $RCSfile$ + * $Author$ + * $Date$ + * $Revision$ + * + * Copyright (C) 2004 The Chemistry Development Kit (CDK) project + * + * Contact: cdk...@li... + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * as published by the Free Software Foundation; either version 2.1 + * of the License, or (at your option) any later version. + * All we ask is that proper credit is given for our work, which includes + * - but is not limited to - adding the above copyright notice to the beginning + * of your source code files, and to any copyright notice that you may distribute + * with programs based on this work. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + */ + package org.openscience.cdk.ringsearch.cyclebasis; import java.util.ArrayList; import java.util.Arrays; @@ -16,19 +45,22 @@ import org._3pq.jgrapht.graph.UndirectedSubgraph; import org.openscience.cdk.graph.BiconnectivityInspector; -/* - * Created on Apr 18, 2004 - * - * To change the template for this generated file go to - * Window - Preferences - Java - Code Generation - Code and Comments - */ - /** - * @author uli + * A minimum basis of all cycles in a graph. + * All cycles in a graph G can be constructed from the basis cycles by binary + * addition of their invidence vectors. + * + * A minimum cycle basis is a Matroid. + * + * @author Ulrich Bauer <ba...@cs...> + * + * + * @cdk.module standard * - * To change the template for this generated type comment go to - * Window - Preferences - Java - Code Generation - Code and Comments + * @cdk.builddepends jgrapht-0.5.3.jar + * @cdk.depends jgrapht-0.5.3.jar */ + public class CycleBasis { //private List cycles = new Vector(); @@ -43,9 +75,14 @@ private boolean isMinimized = false; private List subgraphBases = new Vector(); - public CycleBasis (UndirectedGraph aGraph) { + /** + * Constructs a minimum cycle basis of a graph. + * + * @param g the graph for the cycle basis + */ + public CycleBasis (UndirectedGraph g) { - baseGraph = aGraph; + baseGraph = g; // We construct a simple graph out of the input (multi-)graph // as a subgraph with no multiedges. @@ -53,10 +90,10 @@ // Moreover, shortest cycles through these edges are constructed and // collected in mulitEdgeCycles - UndirectedGraph simpleGraph = new UndirectedSubgraph(aGraph, null, null); + UndirectedGraph simpleGraph = new UndirectedSubgraph(g, null, null); // Iterate over the edges and discard all edges with the same source and target - for (Iterator it = aGraph.edgeSet().iterator(); it.hasNext();) { + for (Iterator it = g.edgeSet().iterator(); it.hasNext();) { Edge edge = (Edge) it.next(); Object u = edge.getSource(); Object v = edge.getTarget(); @@ -140,6 +177,9 @@ */ + /** + * Prints the cycle-edge incidence matrix of the cycle basis. + */ public void printIncidenceMatrix() { SimpleCycleBasis basis = simpleBasis(); List edgeList = basis.edgeList; @@ -168,21 +208,21 @@ } } - public double[] weightVector() { + public int[] weightVector() { SimpleCycleBasis basis = simpleBasis(); List cycles = basis.cycles; - double[] result = new double[cycles.size()]; + int[] result = new int[cycles.size()]; for (int i=0; i<cycles.size(); i++) { Cycle cycle = (Cycle) cycles.get(i); - result[i] = cycle.weight(); + result[i] = (int) cycle.weight(); } Arrays.sort(result); return result; } - public SimpleCycleBasis simpleBasis() { + private SimpleCycleBasis simpleBasis() { if (cachedCycleBasis == null) { List cycles = new ArrayList(); List edgeList = new ArrayList(); @@ -206,10 +246,23 @@ } + /** + * Returns the cycles that form the cycle basis. + * + * @returns a <Code>Collection</code> of the basis cycles + */ + public Collection cycles() { return simpleBasis().cycles; } + /** + * Returns the essential cycles of this cycle basis. + * A essential cycle is contained in every minimum cycle basis of a graph. + * + * @returns a <Code>Collection</code> of the essential cycles + */ + public Collection essentialCycles() { Collection result = new HashSet(); //minimize(); @@ -222,6 +275,14 @@ return result; } + /** + * Returns the essential cycles of this cycle basis. + * A relevant cycle is contained in some minimum cycle basis of a graph. + * + * @returns a <Code>Map</code> mapping each relevant cycles to the corresponding + * basis cycle in this basis + */ + public Map relevantCycles() { Map result = new HashMap(); //minimize(); @@ -234,6 +295,15 @@ return result; } + /** + * Returns the connected components of this cycle basis, in regard to matroid theory. + * Two cycles belong to the same commected component if there is a circuit (a minimal + * dependent set) containing both cycles. + * + * @returns a <Code>List</code> of <Code>Set</code>s consisting of the cycles in a + * equivalence class. + */ + public List equivalenceClasses() { List result = new ArrayList(); //minimize(); Index: SimpleCycleBasis.java =================================================================== RCS file: /cvsroot/cdk/cdk/src/org/openscience/cdk/ringsearch/cyclebasis/SimpleCycleBasis.java,v retrieving revision 1.1 retrieving revision 1.2 diff -u -r1.1 -r1.2 --- SimpleCycleBasis.java 23 Jul 2004 14:23:53 -0000 1.1 +++ SimpleCycleBasis.java 24 Jul 2004 18:42:54 -0000 1.2 @@ -1,3 +1,32 @@ +/* $RCSfile$ + * $Author$ + * $Date$ + * $Revision$ + * + * Copyright (C) 2004 The Chemistry Development Kit (CDK) project + * + * Contact: cdk...@li... + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * as published by the Free Software Foundation; either version 2.1 + * of the License, or (at your option) any later version. + * All we ask is that proper credit is given for our work, which includes + * - but is not limited to - adding the above copyright notice to the beginning + * of your source code files, and to any copyright notice that you may distribute + * with programs based on this work. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + */ + package org.openscience.cdk.ringsearch.cyclebasis; import java.util.ArrayList; import java.util.Arrays; @@ -23,19 +52,18 @@ import org._3pq.jgrapht.graph.Subgraph; import org.openscience.cdk.graph.MinimalPathIterator; -/* - * Created on Apr 18, 2004 - * - * To change the template for this generated file go to - * Window - Preferences - Java - Code Generation - Code and Comments - */ - /** - * @author uli + * Auxiliary class for <code>CycleBasis</code>. + * + * @author Ulrich Bauer <ba...@cs...> + * + * + * @cdk.module standard * - * To change the template for this generated type comment go to - * Window - Preferences - Java - Code Generation - Code and Comments + * @cdk.builddepends jgrapht-0.5.3.jar + * @cdk.depends jgrapht-0.5.3.jar */ + public class SimpleCycleBasis { List edgeList; @@ -353,7 +381,7 @@ Cycle cycle = (Cycle) cycleArray[i]; for (int j=0; j<edgeList.size(); j++) { Edge edge = (Edge)edgeList.get(j); - result[i][j] = cycle.hasEdge(edge); + result[i][j] = cycle.containsEdge(edge); } } @@ -494,7 +522,7 @@ // insert the new cycle into the matrix for (int j=1; j<edgeList.size(); j++) { - a[i][j] = shortestCycle.hasEdge((Edge) edgeList.get(j)); + a[i][j] = shortestCycle.containsEdge((Edge) edgeList.get(j)); } // perform gaussian elimination on the inserted row @@ -556,12 +584,12 @@ } } - public double[] weightVector() { + public int[] weightVector() { - double[] result = new double[cycles.size()]; + int[] result = new int[cycles.size()]; for (int i=0; i<cycles.size(); i++) { Cycle cycle = (Cycle) cycles.get(i); - result[i] = cycle.weight(); + result[i] = (int) cycle.weight(); } Arrays.sort(result); @@ -753,7 +781,7 @@ } public List equivalenceClasses() { - double[] weight = weightVector(); + int[] weight = weightVector(); Object[] cyclesArray = (Object[]) cycles.toArray(); Arrays.sort(cyclesArray, new Comparator() { |