pathtools.java

化学图形处理软件

/* $RCSfile$
 * $Author: egonw $    
 * $Date: 2007-10-23 16:20:20 +0200 (Tue, 23 Oct 2007) $    
 * $Revision: 9182 $
 *
 * Copyright (C) 2001-2007  The Chemistry Development Kit (CDK) project
 *
 * Contact: [e-mail]
 *
 * 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., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 */
package org.openscience.cdk.graph;

import org.openscience.cdk.CDKConstants;
import org.openscience.cdk.exception.NoSuchAtomException;
import org.openscience.cdk.graph.matrix.AdjacencyMatrix;
import org.openscience.cdk.interfaces.IAtom;
import org.openscience.cdk.interfaces.IAtomContainer;
import org.openscience.cdk.interfaces.IBond;
import org.openscience.cdk.interfaces.ILonePair;
import org.openscience.cdk.interfaces.IMolecule;
import org.openscience.cdk.interfaces.ISingleElectron;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Vector;

/**
 * Tools class with methods for handling molecular graphs.
 *
 * @author steinbeck
 * @cdk.module standard
 * @cdk.created 2001-06-17
 */
public class PathTools {

    public final static boolean debug = false;

    /**
     * Sums up the columns in a 2D int matrix
     *
     * @param apsp The 2D int matrix
     * @return A 1D matrix containing the column sum of the 2D matrix
     */
    public static int[] getInt2DColumnSum(int[][] apsp) {
        int[] colSum = new int[apsp.length];
        int sum;
        for (int i = 0; i < apsp.length; i++) {
            sum = 0;
            for (int j = 0; j < apsp.length; j++) {
                sum += apsp[i][j];
            }
            colSum[i] = sum;
        }
        return colSum;
    }


    /**
     * All-Pairs-Shortest-Path computation based on Floyds algorithm Takes an nxn
     * matrix C of edge costs and produces an nxn matrix A of lengths of shortest
     * paths.
     */
    public static int[][] computeFloydAPSP(int C[][]) {
        int i;
        int j;
        int k;
        int n = C.length;
        int[][] A = new int[n][n];
        //logger.debug("Matrix size: " + n);
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (C[i][j] == 0) {
                    A[i][j] = 999999999;
                } else {
                    A[i][j] = 1;
                }
            }
        }
        for (i = 0; i < n; i++) {
            A[i][i] = 0;
            // no self cycle
        }
        for (k = 0; k < n; k++) {
            for (i = 0; i < n; i++) {
                for (j = 0; j < n; j++) {
                    if (A[i][k] + A[k][j] < A[i][j]) {
                        A[i][j] = A[i][k] + A[k][j];
                        //P[i][j] = k;        // k is included in the shortest path
                    }
                }
            }
        }
        return A;
    }

    /**
     * All-Pairs-Shortest-Path computation based on Floyds algorithm Takes an nxn
     * matrix C of edge costs and produces an nxn matrix A of lengths of shortest
     * paths.
     */
    public static int[][] computeFloydAPSP(double C[][]) {
        int i;
        int j;
        int n = C.length;
        int[][] A = new int[n][n];
        //logger.debug("Matrix size: " + n);
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (C[i][j] == 0) {
                    A[i][j] = 0;
                } else {
                    A[i][j] = 1;
                }
            }
        }
        return computeFloydAPSP(A);
    }


    /**
     * Recursivly perfoms a depth first search in a molecular graphs contained in
     * the AtomContainer molecule, starting at the root atom and returning when it
     * hits the target atom.
     * CAUTION: This recursive method sets the VISITED flag of each atom
     * does not reset it after finishing the search. If you want to do the
     * operation on the same collection of atoms more than once, you have
     * to set all the VISITED flags to false before each operation
     * by looping of the atoms and doing a
     * "atom.setFlag((CDKConstants.VISITED, false));"
     *
     * @param molecule The
     *                 AtomContainer to be searched
     * @param root     The root atom
     *                 to start the search at
     * @param target   The target
     * @param path     An
     *                 AtomContainer to be filled with the path
     * @return true if the
     *         target atom was found during this function call
     */
    public static boolean depthFirstTargetSearch(IAtomContainer molecule, IAtom root, IAtom target, IAtomContainer path) throws NoSuchAtomException {
        java.util.List bonds = molecule.getConnectedBondsList(root);
        IAtom nextAtom;
        root.setFlag(CDKConstants.VISITED, true);
        for (int f = 0; f < bonds.size(); f++) {
        	IBond bond = (IBond)bonds.get(f);
            nextAtom = bond.getConnectedAtom(root);
            if (!nextAtom.getFlag(CDKConstants.VISITED)) {
                path.addAtom(nextAtom);
                path.addBond(bond);
                if (nextAtom == target) {
                    return true;
                } else {
                    if (!depthFirstTargetSearch(molecule, nextAtom, target, path)) {
                        // we did not find the target
                        path.removeAtom(nextAtom);
                        path.removeBond(bond);
                    } else {
                        return true;
                    }
                }
            }
        }
        return false;
    }


    /**
     * Performs a breadthFirstSearch in an AtomContainer starting with a
     * particular sphere, which usually consists of one start atom. While
     * searching the graph, the method marks each visited atom. It then puts all
     * the atoms connected to the atoms in the given sphere into a new vector
     * which forms the sphere to search for the next recursive method call. All
     * atoms that have been visited are put into a molecule container. This
     * breadthFirstSearch does thus find the connected graph for a given start
     * atom.
     *
     * @param ac       The AtomContainer to be searched
     * @param sphere   A sphere of atoms to start the search with
     * @param molecule A molecule into which all the atoms and bonds are stored
     *                 that are found during search
     */
    public static void breadthFirstSearch(IAtomContainer ac, Vector sphere, IMolecule molecule) {
        // logger.debug("Staring partitioning with this ac: " + ac);
        breadthFirstSearch(ac, sphere, molecule, -1);
    }


    /**
     * Returns the atoms which are closest to an atom in an AtomContainer by bonds.
     * If number of atoms in or below sphere x&lt;max andnumber of atoms in or below sphere x+1&gt;max then atoms in or below sphere x+1 are returned.
     *
     * @param ac  The AtomContainer to examine
     * @param a   the atom to start from
     * @param max the number of neighbours to return
     * @return the average bond length
     */
    public static IAtom[] findClosestByBond(IAtomContainer ac, IAtom a, int max) {
        IMolecule mol = ac.getBuilder().newMolecule();
        Vector v = new Vector();
        v.add(a);
        breadthFirstSearch(ac, v, mol, max);
        IAtom[] returnValue = new IAtom[mol.getAtomCount() - 1];
        int k = 0;
        for (int i = 0; i < mol.getAtomCount(); i++) {
            if (mol.getAtom(i) != a) {
                returnValue[k] = mol.getAtom(i);
                k++;
            }
        }
        return (returnValue);
    }


    /**
     * Performs a breadthFirstSearch in an AtomContainer starting with a
     * particular sphere, which usually consists of one start atom. While
     * searching the graph, the method marks each visited atom. It then puts all
     * the atoms connected to the atoms in the given sphere into a new vector
     * which forms the sphere to search for the next recursive method call. All
     * atoms that have been visited are put into a molecule container. This
     * breadthFirstSearch does thus find the connected graph for a given start
     * atom.
     *
     * @param ac       The AtomContainer to be searched
     * @param sphere   A sphere of atoms to start the search with
     * @param molecule A molecule into which all the atoms and bonds are stored
     *                 that are found during search
     */
    public static void breadthFirstSearch(IAtomContainer ac, Vector sphere, IMolecule molecule, int max) {
        IAtom atom;
        IAtom nextAtom;
        Vector newSphere = new Vector();
        for (int f = 0; f < sphere.size(); f++) {
            atom = (IAtom) sphere.elementAt(f);
            //logger.debug("atoms  "+ atom + f);
            //logger.debug("sphere size  "+ sphere.size());
            molecule.addAtom(atom);
            // first copy LonePair's and SingleElectron's of this Atom as they need
            // to be copied too
            java.util.List lonePairs = ac.getConnectedLonePairsList(atom);
            //logger.debug("found #ec's: " + lonePairs.length);
            for (int i = 0; i < lonePairs.size(); i++) molecule.addLonePair((ILonePair)lonePairs.get(i));
            java.util.List singleElectrons = ac.getConnectedSingleElectronsList(atom);
            for (int i = 0; i < singleElectrons.size(); i++) molecule.addSingleElectron((ISingleElectron)singleElectrons.get(i));
            // now look at bonds
            java.util.List bonds = ac.getConnectedBondsList(atom);
            for (int g = 0; g < bonds.size(); g++) {
            	IBond bond = (IBond)bonds.get(g);
                if (!bond.getFlag(CDKConstants.VISITED)) {
                    molecule.addBond(bond);
                    bond.setFlag(CDKConstants.VISITED, true);
                }
                nextAtom = bond.getConnectedAtom(atom);
                if (!nextAtom.getFlag(CDKConstants.VISITED)) {
//					logger.debug("wie oft???");
                    newSphere.addElement(nextAtom);
                    nextAtom.setFlag(CDKConstants.VISITED, true);
                }
            }
            if (max > -1 && molecule.getAtomCount() > max)
                return;
        }
        if (newSphere.size() > 0) {
            breadthFirstSearch(ac, newSphere, molecule, max);
        }
    }