3
* $Date: 2007-10-23 16:20:20 +0200 (Tue, 23 Oct 2007) $
6
* Copyright (C) 2001-2007 The Chemistry Development Kit (CDK) project
8
* Contact: cdk-devel@lists.sourceforge.net
10
* This program is free software; you can redistribute it and/or
11
* modify it under the terms of the GNU Lesser General Public License
12
* as published by the Free Software Foundation; either version 2.1
13
* of the License, or (at your option) any later version.
14
* All we ask is that proper credit is given for our work, which includes
15
* - but is not limited to - adding the above copyright notice to the beginning
16
* of your source code files, and to any copyright notice that you may distribute
17
* with programs based on this work.
19
* This program is distributed in the hope that it will be useful,
20
* but WITHOUT ANY WARRANTY; without even the implied warranty of
21
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22
* GNU Lesser General Public License for more details.
24
* You should have received a copy of the GNU Lesser General Public License
25
* along with this program; if not, write to the Free Software
26
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
29
package org.openscience.cdk.graph;
31
import org.openscience.cdk.CDKConstants;
32
import org.openscience.cdk.exception.NoSuchAtomException;
33
import org.openscience.cdk.graph.matrix.AdjacencyMatrix;
34
import org.openscience.cdk.interfaces.IAtom;
35
import org.openscience.cdk.interfaces.IAtomContainer;
36
import org.openscience.cdk.interfaces.IBond;
37
import org.openscience.cdk.interfaces.ILonePair;
38
import org.openscience.cdk.interfaces.IMolecule;
39
import org.openscience.cdk.interfaces.ISingleElectron;
41
import java.util.ArrayList;
42
import java.util.Iterator;
43
import java.util.List;
44
import java.util.Vector;
47
* Tools class with methods for handling molecular graphs.
50
* @cdk.module standard
51
* @cdk.created 2001-06-17
53
public class PathTools {
55
public final static boolean debug = false;
58
* Sums up the columns in a 2D int matrix
60
* @param apsp The 2D int matrix
61
* @return A 1D matrix containing the column sum of the 2D matrix
63
public static int[] getInt2DColumnSum(int[][] apsp) {
64
int[] colSum = new int[apsp.length];
66
for (int i = 0; i < apsp.length; i++) {
68
for (int j = 0; j < apsp.length; j++) {
78
* All-Pairs-Shortest-Path computation based on Floyds algorithm Takes an nxn
79
* matrix C of edge costs and produces an nxn matrix A of lengths of shortest
82
public static int[][] computeFloydAPSP(int C[][]) {
87
int[][] A = new int[n][n];
88
//logger.debug("Matrix size: " + n);
89
for (i = 0; i < n; i++) {
90
for (j = 0; j < n; j++) {
98
for (i = 0; i < n; i++) {
102
for (k = 0; k < n; k++) {
103
for (i = 0; i < n; i++) {
104
for (j = 0; j < n; j++) {
105
if (A[i][k] + A[k][j] < A[i][j]) {
106
A[i][j] = A[i][k] + A[k][j];
107
//P[i][j] = k; // k is included in the shortest path
116
* All-Pairs-Shortest-Path computation based on Floyds algorithm Takes an nxn
117
* matrix C of edge costs and produces an nxn matrix A of lengths of shortest
120
public static int[][] computeFloydAPSP(double C[][]) {
124
int[][] A = new int[n][n];
125
//logger.debug("Matrix size: " + n);
126
for (i = 0; i < n; i++) {
127
for (j = 0; j < n; j++) {
135
return computeFloydAPSP(A);
140
* Recursivly perfoms a depth first search in a molecular graphs contained in
141
* the AtomContainer molecule, starting at the root atom and returning when it
142
* hits the target atom.
143
* CAUTION: This recursive method sets the VISITED flag of each atom
144
* does not reset it after finishing the search. If you want to do the
145
* operation on the same collection of atoms more than once, you have
146
* to set all the VISITED flags to false before each operation
147
* by looping of the atoms and doing a
148
* "atom.setFlag((CDKConstants.VISITED, false));"
150
* @param molecule The
151
* AtomContainer to be searched
152
* @param root The root atom
153
* to start the search at
154
* @param target The target
156
* AtomContainer to be filled with the path
157
* @return true if the
158
* target atom was found during this function call
160
public static boolean depthFirstTargetSearch(IAtomContainer molecule, IAtom root, IAtom target, IAtomContainer path) throws NoSuchAtomException {
161
java.util.List bonds = molecule.getConnectedBondsList(root);
163
root.setFlag(CDKConstants.VISITED, true);
164
for (int f = 0; f < bonds.size(); f++) {
165
IBond bond = (IBond)bonds.get(f);
166
nextAtom = bond.getConnectedAtom(root);
167
if (!nextAtom.getFlag(CDKConstants.VISITED)) {
168
path.addAtom(nextAtom);
170
if (nextAtom == target) {
173
if (!depthFirstTargetSearch(molecule, nextAtom, target, path)) {
174
// we did not find the target
175
path.removeAtom(nextAtom);
176
path.removeBond(bond);
188
* Performs a breadthFirstSearch in an AtomContainer starting with a
189
* particular sphere, which usually consists of one start atom. While
190
* searching the graph, the method marks each visited atom. It then puts all
191
* the atoms connected to the atoms in the given sphere into a new vector
192
* which forms the sphere to search for the next recursive method call. All
193
* atoms that have been visited are put into a molecule container. This
194
* breadthFirstSearch does thus find the connected graph for a given start
197
* @param ac The AtomContainer to be searched
198
* @param sphere A sphere of atoms to start the search with
199
* @param molecule A molecule into which all the atoms and bonds are stored
200
* that are found during search
202
public static void breadthFirstSearch(IAtomContainer ac, Vector sphere, IMolecule molecule) {
203
// logger.debug("Staring partitioning with this ac: " + ac);
204
breadthFirstSearch(ac, sphere, molecule, -1);
209
* Returns the atoms which are closest to an atom in an AtomContainer by bonds.
210
* If number of atoms in or below sphere x<max andnumber of atoms in or below sphere x+1>max then atoms in or below sphere x+1 are returned.
212
* @param ac The AtomContainer to examine
213
* @param a the atom to start from
214
* @param max the number of neighbours to return
215
* @return the average bond length
217
public static IAtom[] findClosestByBond(IAtomContainer ac, IAtom a, int max) {
218
IMolecule mol = ac.getBuilder().newMolecule();
219
Vector v = new Vector();
221
breadthFirstSearch(ac, v, mol, max);
222
IAtom[] returnValue = new IAtom[mol.getAtomCount() - 1];
224
for (int i = 0; i < mol.getAtomCount(); i++) {
225
if (mol.getAtom(i) != a) {
226
returnValue[k] = mol.getAtom(i);
230
return (returnValue);
235
* Performs a breadthFirstSearch in an AtomContainer starting with a
236
* particular sphere, which usually consists of one start atom. While
237
* searching the graph, the method marks each visited atom. It then puts all
238
* the atoms connected to the atoms in the given sphere into a new vector
239
* which forms the sphere to search for the next recursive method call. All
240
* atoms that have been visited are put into a molecule container. This
241
* breadthFirstSearch does thus find the connected graph for a given start
244
* @param ac The AtomContainer to be searched
245
* @param sphere A sphere of atoms to start the search with
246
* @param molecule A molecule into which all the atoms and bonds are stored
247
* that are found during search
249
public static void breadthFirstSearch(IAtomContainer ac, Vector sphere, IMolecule molecule, int max) {
252
Vector newSphere = new Vector();
253
for (int f = 0; f < sphere.size(); f++) {
254
atom = (IAtom) sphere.elementAt(f);
255
//logger.debug("atoms "+ atom + f);
256
//logger.debug("sphere size "+ sphere.size());
257
molecule.addAtom(atom);
258
// first copy LonePair's and SingleElectron's of this Atom as they need
260
java.util.List lonePairs = ac.getConnectedLonePairsList(atom);
261
//logger.debug("found #ec's: " + lonePairs.length);
262
for (int i = 0; i < lonePairs.size(); i++) molecule.addLonePair((ILonePair)lonePairs.get(i));
263
java.util.List singleElectrons = ac.getConnectedSingleElectronsList(atom);
264
for (int i = 0; i < singleElectrons.size(); i++) molecule.addSingleElectron((ISingleElectron)singleElectrons.get(i));
266
java.util.List bonds = ac.getConnectedBondsList(atom);
267
for (int g = 0; g < bonds.size(); g++) {
268
IBond bond = (IBond)bonds.get(g);
269
if (!bond.getFlag(CDKConstants.VISITED)) {
270
molecule.addBond(bond);
271
bond.setFlag(CDKConstants.VISITED, true);
273
nextAtom = bond.getConnectedAtom(atom);
274
if (!nextAtom.getFlag(CDKConstants.VISITED)) {
275
// logger.debug("wie oft???");
276
newSphere.addElement(nextAtom);
277
nextAtom.setFlag(CDKConstants.VISITED, true);
280
if (max > -1 && molecule.getAtomCount() > max)
283
if (newSphere.size() > 0) {
284
breadthFirstSearch(ac, newSphere, molecule, max);
290
* Performs a breadthFirstTargetSearch in an AtomContainer starting with a
291
* particular sphere, which usually consists of one start atom. While
292
* searching the graph, the method marks each visited atom. It then puts all
293
* the atoms connected to the atoms in the given sphere into a new vector
294
* which forms the sphere to search for the next recursive method call.
295
* The method keeps track of the sphere count and returns it as soon
296
* as the target atom is encountered.
298
* @param ac The AtomContainer in which the path search is to be performed.
299
* @param sphere The sphere of atoms to start with. Usually just the starting atom
300
* @param target The target atom to be searched
301
* @param pathLength The current path length, incremented and passed in recursive calls. Call this method with "zero".
302
* @param cutOff Stop the path search when this cutOff sphere count has been reached
303
* @return The shortest path between the starting sphere and the target atom
305
public static int breadthFirstTargetSearch(IAtomContainer ac, Vector sphere, IAtom target, int pathLength, int cutOff) {
306
if (pathLength == 0) resetFlags(ac);
308
if (pathLength > cutOff) {
314
Vector newSphere = new Vector();
315
for (int f = 0; f < sphere.size(); f++) {
316
atom = (IAtom) sphere.elementAt(f);
317
java.util.List bonds = ac.getConnectedBondsList(atom);
318
for (int g = 0; g < bonds.size(); g++) {
319
IBond bond = (IBond)bonds.get(g);
320
if (!bond.getFlag(CDKConstants.VISITED)) {
321
bond.setFlag(CDKConstants.VISITED, true);
323
nextAtom = bond.getConnectedAtom(atom);
324
if (!nextAtom.getFlag(CDKConstants.VISITED)) {
325
if (nextAtom == target) {
328
newSphere.addElement(nextAtom);
329
nextAtom.setFlag(CDKConstants.VISITED, true);
333
if (newSphere.size() > 0) {
334
return breadthFirstTargetSearch(ac, newSphere, target, pathLength, cutOff);
339
public static void resetFlags(IAtomContainer ac) {
340
for (int f = 0; f < ac.getAtomCount(); f++) {
341
ac.getAtom(f).setFlag(CDKConstants.VISITED, false);
343
for (int f = 0; f < ac.getBondCount(); f++) {
344
ac.getBond(f).setFlag(CDKConstants.VISITED, false);
350
* Returns the radius of the molecular graph.
352
* @param atomContainer The molecule to consider
353
* @return The topological radius
355
public static int getMolecularGraphRadius(IAtomContainer atomContainer) {
356
int natom = atomContainer.getAtomCount();
358
int[][] admat = AdjacencyMatrix.getMatrix(atomContainer);
359
int[][] distanceMatrix = computeFloydAPSP(admat);
361
int[] eta = new int[natom];
362
for (int i = 0; i < natom; i++) {
364
for (int j = 0; j < natom; j++) {
365
if (distanceMatrix[i][j] > max) max = distanceMatrix[i][j];
370
for (int i = 0; i < eta.length; i++) {
371
if (eta[i] < min) min = eta[i];
377
* Returns the diameter of the molecular graph.
379
* @param atomContainer The molecule to consider
380
* @return The topological diameter
382
public static int getMolecularGraphDiameter(IAtomContainer atomContainer) {
383
int natom = atomContainer.getAtomCount();
385
int[][] admat = AdjacencyMatrix.getMatrix(atomContainer);
386
int[][] distanceMatrix = computeFloydAPSP(admat);
388
int[] eta = new int[natom];
389
for (int i = 0; i < natom; i++) {
391
for (int j = 0; j < natom; j++) {
392
if (distanceMatrix[i][j] > max) max = distanceMatrix[i][j];
397
for (int i = 0; i < eta.length; i++) {
398
if (eta[i] > max) max = eta[i];
404
* Returns the number of vertices that are a distance 'd' apart.
406
* In this method, d is the topological distance (ie edge count).
408
* @param atomContainer The molecule to consider
409
* @param distance The distance to consider
410
* @return The number of vertices
412
public static int getVertexCountAtDistance(IAtomContainer atomContainer, int distance) {
413
int natom = atomContainer.getAtomCount();
415
int[][] admat = AdjacencyMatrix.getMatrix(atomContainer);
416
int[][] distanceMatrix = computeFloydAPSP(admat);
420
for (int i = 0; i < natom; i++) {
421
for (int j = 0; j < natom; j++) {
422
if (distanceMatrix[i][j] == distance) n++;
429
* Returns a list of atoms in the shortest path between two atoms.
431
* This method uses the Djikstra algorithm to find all the atoms in the shortest
432
* path between the two specified atoms. The start and end atoms are also included
433
* in the path returned
435
* @param atomContainer The molecule to search in
436
* @param start The starting atom
437
* @param end The ending atom
438
* @return A <code>List</code> containing the atoms in the shortest path between <code>start</code> and
439
* <code>end</code> inclusive
441
public static List getShortestPath(IAtomContainer atomContainer, IAtom start, IAtom end) {
442
int natom = atomContainer.getAtomCount();
443
int endNumber = atomContainer.getAtomNumber(end);
444
int startNumber = atomContainer.getAtomNumber(start);
445
int[] dist = new int[natom];
446
int[] previous = new int[natom];
447
for (int i = 0; i < natom; i++) {
451
dist[atomContainer.getAtomNumber(start)] = 0;
453
ArrayList S = new ArrayList();
454
ArrayList Q = new ArrayList();
455
for (int i = 0; i < natom; i++) Q.add(new Integer(i));
458
if (Q.size() == 0) break;
463
for (int i = 0; i < Q.size(); i++) {
464
int tmp = ((Integer)Q.get(i)).intValue();
470
Q.remove(Q.indexOf(new Integer(index)));
471
S.add(atomContainer.getAtom(index));
472
if (index == endNumber) break;
475
java.util.List connected = atomContainer.getConnectedAtomsList( atomContainer.getAtom(index) );
476
for (int i = 0; i < connected.size(); i++) {
477
int anum = atomContainer.getAtomNumber((IAtom)connected.get(i));
478
if (dist[anum] > dist[index] + 1) { // all edges have equals weights
479
dist[anum] = dist[index] + 1;
480
previous[anum] = index;
485
ArrayList tmp = new ArrayList();
488
tmp.add(0, atomContainer.getAtom(u));
490
if (u == startNumber){
491
tmp.add(0, atomContainer.getAtom(u));
498
private static List allPaths;
501
* Get a list of all the paths between two atoms.
503
* If the two atoms are the same an empty list is returned. Note that this problem
504
* is NP-hard and so can take a long time for large graphs.
506
* @param atomContainer The molecule to consider
507
* @param start The starting Atom of the path
508
* @param end The ending Atom of the path
509
* @return A <code>List</code> containing all the paths between the specified atoms
511
public static List getAllPaths(IAtomContainer atomContainer, IAtom start, IAtom end) {
512
allPaths = new ArrayList();
513
if (start.equals(end)) return allPaths;
514
findPathBetween(atomContainer, start, end, new ArrayList());
518
private static void findPathBetween(IAtomContainer atomContainer, IAtom start, IAtom end, List path) {
521
allPaths.add(new ArrayList(path));
522
path.remove(path.size() - 1);
525
if (path.contains(start))
528
List nbrs = atomContainer.getConnectedAtomsList(start);
529
for (Iterator i = nbrs.iterator(); i.hasNext();)
530
findPathBetween(atomContainer, (IAtom) i.next(), end, path);
531
path.remove(path.size() - 1);
535
* Get the paths starting from an atom of specified length.
537
* This method returns a set of paths. Each path is a <code>List</code> of atoms that
538
* make up the path (ie they are sequentially connected).
540
* @param atomContainer The molecule to consider
541
* @param start The starting atom
542
* @param length The length of paths to look for
543
* @return A <code>List</code> containing the paths found
545
public static List getPathsOfLength(IAtomContainer atomContainer, IAtom start, int length) {
546
ArrayList curPath = new ArrayList();
547
ArrayList paths = new ArrayList();
550
for (int i = 0; i < length; i++) {
551
ArrayList tmpList = new ArrayList();
552
for (int j = 0; j < paths.size(); j++) {
553
curPath = (ArrayList) paths.get(j);
554
IAtom lastVertex = (IAtom) curPath.get(curPath.size() - 1);
555
List neighbors = atomContainer.getConnectedAtomsList(lastVertex);
556
for (int k = 0; k < neighbors.size(); k++) {
557
ArrayList newPath = new ArrayList(curPath);
558
if (newPath.contains(neighbors.get(k))) continue;
559
newPath.add(neighbors.get(k));
560
tmpList.add(newPath);
564
paths.addAll(tmpList);
added
removed
src/org/openscience/cdk/graph/PathTools.java
