Package org.openscience.cdk.graph
Class PathTools
 java.lang.Object

 org.openscience.cdk.graph.PathTools


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

Constructor Summary
Constructors Constructor Description PathTools()

Method Summary
All Methods Static Methods Concrete Methods Deprecated Methods Modifier and Type Method 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)
AllPairsShortestPath computation based on Floyd's algorithm [Floyd, R.W.. Commun. ACM. 1962. 5].static int[][]
computeFloydAPSP(int[][] costMatrix)
AllPairsShortestPath computation based on Floyd's algorithm [Floyd, R.W.. Commun. ACM. 1962. 5].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.static int
getVertexCountAtDistance(IAtomContainer atomContainer, int distance)
Returns the number of vertices that are a distance 'd' apart.protected static void
resetFlags(IAtomContainer atomContainer)



Field Detail

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


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)
AllPairsShortestPath 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)
AllPairsShortestPath 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 searchedroot
 The root atom to start the search attarget
 The targetpath
 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 searchedsphere
 A sphere of atoms to start the search withmolecule
 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 examineatom
 the atom to start frommax
 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 searchedsphere
 A sphere of atoms to start the search withmolecule
 A molecule into which all the atoms and bonds are stored that are found during searchmax


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 atomtarget
 The target atom to be searchedpathLength
 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 considerdistance
 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 byShortestPaths.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 instart
 The starting atomend
 The ending atom Returns:
 A
List
containing the atoms in the shortest path betweenstart
andend
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 NPhard and so can take a long time for large graphs. Parameters:
atomContainer
 The molecule to considerstart
 The starting Atom of the pathend
 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 aList
of atoms that make up the path (ie they are sequentially connected). Parameters:
atomContainer
 The molecule to considerstart
 The starting atomlength
 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 aList
of atoms that make up the path (ie they are sequentially connected). Parameters:
atomContainer
 The molecule to considerstart
 The starting atomlength
 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 setlimit
then an exception is thrown. This method returns a set of paths. Each path is aList
of atoms that make up the path (ie they are sequentially connected). Parameters:
atomContainer
 The molecule to considerstart
 The starting atomlength
 The maximum length of paths to look forlimit
 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.

