org.openscience.cdk.graph

Class PathTools

java.lang.Object

org.openscience.cdk.graph.PathTools

public class PathTools
extends Object

Tools class with methods for handling molecular graphs.

Author:

steinbeck

Source code:

master

Belongs to CDK module:

core

Created on:

2001-06-17

Field Summary

Fields

Modifier and Type	Field and Description
static boolean	DEBUG Boolean with which debugging can be turned on.

Constructor Summary

Constructors

Constructor and Description
PathTools()

Method Summary

Methods

Modifier and Type	Method and Description
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.
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.
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.
static int[][]	computeFloydAPSP(double[][] costMatrix) All-Pairs-Shortest-Path computation based on Floyd's algorithm [Floyd, R.W., Algorithm 97: Shortest path, Commun. ACM, 1962, 5:345, doi:10.1145/367766.368168].
static int[][]	computeFloydAPSP(int[][] costMatrix) All-Pairs-Shortest-Path computation based on Floyd's algorithm [Floyd, R.W., Algorithm 97: Shortest path, Commun. ACM, 1962, 5:345, doi:10.1145/367766.368168].
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.
static IAtom[]	findClosestByBond(IAtomContainer atomContainer, IAtom atom, int max) Returns the atoms which are closest to an atom in an AtomContainer by bonds.
static List<List<IAtom>>	getAllPaths(IAtomContainer atomContainer, IAtom start, IAtom end) Get a list of all the paths between two atoms.
static int[]	getInt2DColumnSum(int[][] apsp) Sums up the columns in a 2D int matrix.
static List<List<IAtom>>	getLimitedPathsOfLengthUpto(IAtomContainer atomContainer, IAtom start, int length, int limit) Get all the paths starting from an atom of length 0 up to the specified length.
static int	getMolecularGraphDiameter(IAtomContainer atomContainer) Returns the diameter of the molecular graph.
static int	getMolecularGraphRadius(IAtomContainer atomContainer) Returns the radius of the molecular graph.
static List<List<IAtom>>	getPathsOfLength(IAtomContainer atomContainer, IAtom start, int length) Get the paths starting from an atom of specified length.
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.
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)
static int	getVertexCountAtDistance(IAtomContainer atomContainer, int distance) Returns the number of vertices that are a distance 'd' apart.
protected static void	resetFlags(IAtomContainer atomContainer)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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., Algorithm 97: Shortest path, Commun. ACM, 1962, 5:345, doi:10.1145/367766.368168]. 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., Algorithm 97: Shortest path, Commun. ACM, 1962, 5:345, doi:10.1145/367766.368168]. 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.