Package org.openscience.cdk.graph

Class PathTools

  • public class PathTools
extends Object
    Tools class with methods for handling molecular graphs.
    Author:
    steinbeck
    Source code:
    main
    Belongs to CDK module:
    core
    Created on:
    2001-06-17

    • Field Detail

      • DEBUG

        public static final boolean DEBUG
        Boolean with which debugging can be turned on.
        See Also:
        Constant Field Values

    • Constructor Detail

      • PathTools

        public PathTools()

    • Method Detail

      • getInt2DColumnSum

        public static int[] getInt2DColumnSum​(int[][] apsp)
        Sums up the columns in a 2D int matrix.
        Parameters:
        apsp - The 2D int matrix
        Returns:
        A 1D matrix containing the column sum of the 2D matrix

      • computeFloydAPSP

        public static int[][] computeFloydAPSP​(int[][] costMatrix)
        All-Pairs-Shortest-Path computation based on Floyd's algorithm [Floyd, R.W.. Commun. ACM. 1962. 5]. It takes an nxn matrix C of edge costs and produces an nxn matrix A of lengths of shortest paths.
        Parameters:
        costMatrix - edge cost matrix
        Returns:
        the topological distance matrix

      • computeFloydAPSP

        public static int[][] computeFloydAPSP​(double[][] costMatrix)
        All-Pairs-Shortest-Path computation based on Floyd's algorithm [Floyd, R.W.. Commun. ACM. 1962. 5]. It takes an nxn matrix C of edge costs and produces an nxn matrix A of lengths of shortest paths.
        Parameters:
        costMatrix - edge cost matrix
        Returns:
        the topological distance matrix

      • depthFirstTargetSearch

        public static boolean depthFirstTargetSearch​(IAtomContainer molecule,
                                             IAtom root,
                                             IAtom target,
                                             IAtomContainer path)
        Recursively performs 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));"

        Note that the path generated by the search will not contain the root atom, but will contain the target atom

        Parameters:
        molecule - The AtomContainer to be searched
        root - The root atom to start the search at
        target - The target
        path - An AtomContainer to be filled with the path
        Returns:
        true if the target atom was found during this function call

      • breadthFirstSearch

        public static void breadthFirstSearch​(IAtomContainer atomContainer,
                                      List<IAtom> sphere,
                                      IAtomContainer molecule)
        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.
        Parameters:
        atomContainer - The AtomContainer to be searched
        sphere - A sphere of atoms to start the search with
        molecule - A molecule into which all the atoms and bonds are stored that are found during search

      • findClosestByBond

        public static IAtom[] findClosestByBond​(IAtomContainer atomContainer,
                                        IAtom atom,
                                        int max)
        Returns the atoms which are closest to an atom in an AtomContainer by bonds. If number of atoms in or below sphere x<max and number of atoms in or below sphere x+1>max then atoms in or below sphere x+1 are returned.
        Parameters:
        atomContainer - The AtomContainer to examine
        atom - the atom to start from
        max - the number of neighbours to return
        Returns:
        the average bond length

      • breadthFirstSearch

        public static void breadthFirstSearch​(IAtomContainer atomContainer,
                                      List<IAtom> sphere,
                                      IAtomContainer molecule,
                                      int max)
        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.

        IMPORTANT: this method does not reset the VISITED flags, which must be done if calling this method twice!

        Parameters:
        atomContainer - The AtomContainer to be searched
        sphere - A sphere of atoms to start the search with
        molecule - A molecule into which all the atoms and bonds are stored that are found during search
        max -

      • breadthFirstTargetSearch

        public static int breadthFirstTargetSearch​(IAtomContainer atomContainer,
                                           List<IAtom> sphere,
                                           IAtom target,
                                           int pathLength,
                                           int cutOff)
        Performs a breadthFirstTargetSearch 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. The method keeps track of the sphere count and returns it as soon as the target atom is encountered.
        Parameters:
        atomContainer - The AtomContainer in which the path search is to be performed.
        sphere - The sphere of atoms to start with. Usually just the starting atom
        target - The target atom to be searched
        pathLength - The current path length, incremented and passed in recursive calls. Call this method with "zero".
        cutOff - Stop the path search when this cutOff sphere count has been reatomContainerhed
        Returns:
        The shortest path between the starting sphere and the target atom

      • resetFlags

        protected static void resetFlags​(IAtomContainer atomContainer)

      • getMolecularGraphRadius

        public static int getMolecularGraphRadius​(IAtomContainer atomContainer)
        Returns the radius of the molecular graph.
        Parameters:
        atomContainer - The molecule to consider
        Returns:
        The topological radius

      • getMolecularGraphDiameter

        public static int getMolecularGraphDiameter​(IAtomContainer atomContainer)
        Returns the diameter of the molecular graph.
        Parameters:
        atomContainer - The molecule to consider
        Returns:
        The topological diameter

      • getVertexCountAtDistance

        public static int getVertexCountAtDistance​(IAtomContainer atomContainer,
                                           int distance)
        Returns the number of vertices that are a distance 'd' apart. In this method, d is the topological distance (ie edge count).
        Parameters:
        atomContainer - The molecule to consider
        distance - The distance to consider
        Returns:
        The number of vertices

      • getShortestPath

        @Deprecated
public static List<IAtom> getShortestPath​(IAtomContainer atomContainer,
                                          IAtom start,
                                          IAtom end)
        Deprecated.
        This implementation recalculates all shortest paths from the start atom for each method call and does not indicate if there are equally short paths from the start to the end. Replaced by ShortestPaths.atomsTo(IAtom)
        Returns a list of atoms in the shortest path between two atoms. This method uses the Djikstra algorithm to find all the atoms in the shortest path between the two specified atoms. The start and end atoms are also included in the path returned
        Parameters:
        atomContainer - The molecule to search in
        start - The starting atom
        end - The ending atom
        Returns:
        A List containing the atoms in the shortest path between start and end inclusive
        See Also:
        ShortestPaths, ShortestPaths.atomsTo(IAtom), AllPairsShortestPaths

      • getAllPaths

        public static List<List<IAtom>> getAllPaths​(IAtomContainer atomContainer,
                                            IAtom start,
                                            IAtom end)
        Get a list of all the paths between two atoms. If the two atoms are the same an empty list is returned. Note that this problem is NP-hard and so can take a long time for large graphs.
        Parameters:
        atomContainer - The molecule to consider
        start - The starting Atom of the path
        end - The ending Atom of the path
        Returns:
        A List containing all the paths between the specified atoms

      • getPathsOfLength

        public static List<List<IAtom>> getPathsOfLength​(IAtomContainer atomContainer,
                                                 IAtom start,
                                                 int length)
        Get the paths starting from an atom of specified length. This method returns a set of paths. Each path is a List of atoms that make up the path (ie they are sequentially connected).
        Parameters:
        atomContainer - The molecule to consider
        start - The starting atom
        length - The length of paths to look for
        Returns:
        A List containing the paths found

      • getPathsOfLengthUpto

        public static List<List<IAtom>> getPathsOfLengthUpto​(IAtomContainer atomContainer,
                                                     IAtom start,
                                                     int length)
        Get all the paths starting from an atom of length 0 upto the specified length. This method returns a set of paths. Each path is a List of atoms that make up the path (ie they are sequentially connected).
        Parameters:
        atomContainer - The molecule to consider
        start - The starting atom
        length - The maximum length of paths to look for
        Returns:
        A List containing the paths found

      • getLimitedPathsOfLengthUpto

        public static List<List<IAtom>> getLimitedPathsOfLengthUpto​(IAtomContainer atomContainer,
                                                            IAtom start,
                                                            int length,
                                                            int limit)
                                                     throws CDKException
        Get all the paths starting from an atom of length 0 up to the specified length. If the number of paths exceeds the the set limit then an exception is thrown. This method returns a set of paths. Each path is a List of atoms that make up the path (ie they are sequentially connected).
        Parameters:
        atomContainer - The molecule to consider
        start - The starting atom
        length - The maximum length of paths to look for
        limit - Limit the number of paths - thrown an exception if exceeded
        Returns:
        A List containing the paths found
        Throws:
        CDKException - throw if the number of paths generated was larger than the limit.