← Back to branch summary

~ubuntu-branches/ubuntu/maverick/cdk/maverick

« back to all changes in this revision

Viewing changes to src/org/openscience/cdk/structgen/stochastic/operator/ChemGraph.java

  • Committer: Bazaar Package Importer
  • Author(s): Paul Cager
  • Date: 2008-04-09 21:17:53 UTC
  • Revision ID: james.westby@ubuntu.com-20080409211753-46lmjw5z8mx5pd8d
Tags: upstream-1.0.2
Import upstream version 1.0.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/org/openscience/cdk/structgen/stochastic/operator/ChemGraph.java
 
1
/*  $Revision: 7691 $ $Author: egonw $ $Date: 2007-01-11 12:47:48 +0100 (Thu, 11 Jan 2007) $    
 
2
 *
 
3
 *  Copyright (C) 1997-2007  The CDK project
 
4
 *
 
5
 *  Contact: cdk-devel@lists.sourceforge.net
 
6
 *
 
7
 *  This program is free software; you can redistribute it and/or
 
8
 *  modify it under the terms of the GNU Lesser General Public License
 
9
 *  as published by the Free Software Foundation; either version 2.1
 
10
 *  of the License, or (at your option) any later version.
 
11
 *  All we ask is that proper credit is given for our work, which includes
 
12
 *  - but is not limited to - adding the above copyright notice to the beginning
 
13
 *  of your source code files, and to any copyright notice that you may distribute
 
14
 *  with programs based on this work.
 
15
 *
 
16
 *  This program is distributed in the hope that it will be useful,
 
17
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
18
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
19
 *  GNU Lesser General Public License for more details.
 
20
 *
 
21
 *  You should have received a copy of the GNU Lesser General Public License
 
22
 *  along with this program; if not, write to the Free Software
 
23
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 
24
 */
 
25
package org.openscience.cdk.structgen.stochastic.operator;
 
26
 
 
27
import java.util.ArrayList;
 
28
import java.util.List;
 
29
 
 
30
import org.openscience.cdk.graph.matrix.ConnectionMatrix;
 
31
import org.openscience.cdk.interfaces.IAtomContainer;
 
32
import org.openscience.cdk.math.RandomNumbersTool;
 
33
 
 
34
/**
 
35
 * @cdk.module     structgen
 
36
 */
 
37
public class ChemGraph
 
38
{
 
39
        /*Number of atoms in this structure*/
 
40
        protected int dim;
 
41
        /*Number of atoms needed to form subgraph*/
 
42
        protected int numAtoms;
 
43
        protected double[][] contab;
 
44
        /*Number of atoms that have been traversed */
 
45
        protected int travIndex;
 
46
        /*Flag: true if atom visited during a traversal*/
 
47
        protected boolean[] visited;
 
48
        /*Depth first traversal of the graph*/
 
49
        protected List subGraph;
 
50
                
 
51
        public ChemGraph(IAtomContainer chrom)
 
52
        {
 
53
                dim = chrom.getAtomCount();
 
54
                numAtoms = (int)(dim/2);
 
55
                contab = new double[dim][dim];
 
56
                contab = ConnectionMatrix.getMatrix(chrom);
 
57
        }
 
58
        
 
59
        public List pickDFgraph()
 
60
        {
 
61
                //depth first search from a randomly selected atom
 
62
                
 
63
                travIndex = 0;
 
64
                subGraph = new ArrayList();             
 
65
                visited = new boolean[dim];                                     
 
66
                for (int atom = 0; atom < dim; atom++)  visited[atom] = false;
 
67
        int seedAtom = RandomNumbersTool.randomInt(0,dim-1);
 
68
                recursiveDFT(seedAtom);
 
69
        
 
70
                return subGraph;
 
71
        }
 
72
 
 
73
        private void recursiveDFT(int atom)
 
74
        {
 
75
                if ((travIndex < numAtoms)&&(!visited[atom]))
 
76
                {
 
77
                        subGraph.add(new Integer(atom));
 
78
                        travIndex++;
 
79
                        visited[atom] = true;
 
80
                        
 
81
//                      for (int nextAtom = 0; nextAtom < dim; nextAtom++) //not generalized
 
82
//                              if (contab[atom][nextAtom] != 0) recursiveDFT(nextAtom);
 
83
            List adjSet = new ArrayList();
 
84
            for (int nextAtom = 0; nextAtom < dim; nextAtom++)
 
85
            {
 
86
                                if ((int)contab[atom][nextAtom] != 0)
 
87
                                {
 
88
                                        adjSet.add(new Integer(nextAtom));
 
89
                                }
 
90
            }
 
91
                        while (adjSet.size() > 0)
 
92
                        {
 
93
                                int adjIndex = RandomNumbersTool.randomInt(0,adjSet.size()-1);
 
94
                                recursiveDFT(((Integer)adjSet.get(adjIndex)).intValue());
 
95
                                adjSet.remove(adjIndex);
 
96
                        }
 
97
                        
 
98
                }
 
99
        }
 
100
        
 
101
        public List pickBFgraph()
 
102
        {
 
103
                //breadth first search from a randomly selected atom
 
104
                
 
105
                travIndex = 0;
 
106
                subGraph = new ArrayList();             
 
107
                visited = new boolean[dim];                                     
 
108
                for (int atom = 0; atom < dim; atom++)  visited[atom] = false;
 
109
        int seedAtom = RandomNumbersTool.randomInt(0,dim-1);
 
110
                
 
111
                List atomQueue = new ArrayList();
 
112
                atomQueue.add(new Integer(seedAtom));
 
113
                visited[seedAtom] = true;               
 
114
                
 
115
                while (!atomQueue.isEmpty()&&(subGraph.size()<numAtoms))
 
116
                {
 
117
                        int foreAtom = ((Integer)atomQueue.get(0)).intValue();
 
118
                        subGraph.add(new Integer(foreAtom));
 
119
                        atomQueue.remove(0);
 
120
                        travIndex++;
 
121
                        
 
122
                        List adjSet = new ArrayList();
 
123
            for (int nextAtom = 0; nextAtom < dim; nextAtom++)
 
124
            {
 
125
                                if (((int)contab[foreAtom][nextAtom] != 0)&&(!visited[nextAtom]))
 
126
                                {
 
127
                                        adjSet.add(new Integer(nextAtom));
 
128
                                }
 
129
            }
 
130
                        while (adjSet.size() > 0)
 
131
                        {
 
132
                                int adjIndex = RandomNumbersTool.randomInt(0,adjSet.size()-1);
 
133
                                atomQueue.add((Integer)adjSet.get(adjIndex));
 
134
                                visited[((Integer)adjSet.get(adjIndex)).intValue()] = true;
 
135
                                adjSet.remove(adjIndex);
 
136
                        }
 
137
 
 
138
                }
 
139
                return subGraph;        
 
140
        }
 
141
        
 
142
        public List getSubgraph()
 
143
        {
 
144
                return subGraph;
 
145
        }
 
146
        
 
147
        public void setSubgraph(List subgraph)
 
148
        {
 
149
                subGraph = subgraph;
 
150
        }
 
151
        
 
152
        public int getNumAtoms()
 
153
        {
 
154
                return numAtoms;
 
155
        }
 
156
        
 
157
        public void setNumAtoms(int numatoms)
 
158
        {
 
159
                numAtoms = numatoms;
 
160
        }
 
161
}