Package org.openscience.cdk.graph
Class ShortestPaths
java.lang.Object
org.openscience.cdk.graph.ShortestPaths
Find and reconstruct the shortest paths from a given start atom to any other
connected atom. The number of shortest paths (
nPathsTo(int)
) and the
distance (distanceTo(int)
) can be accessed before reconstructing all
the paths. When no path is found (i.e. notconnected) an empty path is always
returned.
If shortest paths from multiple start atoms are requiredIAtomContainer benzene = MoleculeFactory.makeBenzene(); IAtom c1 = benzene.getAtom(0); IAtom c4 = benzene.getAtom(3); // shortest paths from C1 ShortestPaths sp = new ShortestPaths(benzene, c1); // number of paths from C1 to C4 int nPaths = sp.nPathsTo(c4); // distance between C1 to C4 int distance = sp.distanceTo(c4); // reconstruct a path to the C4  determined by storage order int[] path = sp.pathTo(c4); // reconstruct all paths int[][] paths = sp.pathsTo(c4); int[] org = paths[0]; // paths[0] == path int[] alt = paths[1];
AllPairsShortestPaths
will have a small performance advantage. Please use
TopologicalMatrix
if only the
shortest distances between atoms is required. Author:
 John May
 See Also:
 Source code:
 main
 Belongs to CDK module:
 core

Constructor Summary
ConstructorDescriptionShortestPaths
(IAtomContainer container, IAtom start) Create a new shortest paths tool for a single start atom. 
Method Summary
Modifier and TypeMethodDescriptionIAtom[]
atomsTo
(int end) Reconstruct a shortest path to the provided end vertex.IAtom[]
Reconstruct a shortest path to the provided end atom.int
distanceTo
(int end) Access the distance to the provided end vertex.int
distanceTo
(IAtom end) Access the distance to the provided end atom.boolean
isPrecedingPathTo
(int end) Returns whether the first shortest path from the start to a given end vertex which only passed through vertices smaller then start.int
nPathsTo
(int end) Access the number of possible paths to the end vertex.int
Access the number of possible paths to the end atom.int[][]
pathsTo
(int end) Reconstruct all shortest paths to the provided end vertex.int[][]
Reconstruct all shortest paths to the provided end vertex.int[]
pathTo
(int end) Reconstruct a shortest path to the provided end vertex.int[]
Reconstruct a shortest path to the provided end atom.

Constructor Details

ShortestPaths
Create a new shortest paths tool for a single start atom. If shortest paths from multiple start atoms are requiredAllPairsShortestPaths
will have a small performance advantage. Parameters:
container
 an atom container to find the paths ofstart
 the start atom to which all shortest paths will be computed See Also:


Method Details

pathTo
public int[] pathTo(int end) Reconstruct a shortest path to the provided end vertex. The path is an inclusive fixed size array of vertex indices. If there are multiple shortest paths the first shortest path is determined by vertex storage order. When there is no path an empty array is returned. It is considered there to be no path if the end vertex belongs to the same container but is a member of a different fragment, or the vertex is not present in the container at all.ShortestPaths sp = ...; // reconstruct first path int[] path = sp.pathTo(5); // check there is only one path if(sp.nPathsTo(5) == 1){ int[] path = sp.pathTo(5); // reconstruct the path }
 Parameters:
end
 the end vertex to find a path to Returns:
 path from the start to the end vertex
 See Also:

pathTo
Reconstruct a shortest path to the provided end atom. The path is an inclusive fixed size array of vertex indices. If there are multiple shortest paths the first shortest path is determined by vertex storage order. When there is no path an empty array is returned. It is considered there to be no path if the end atom belongs to the same container but is a member of a different fragment, or the atom is not present in the container at all.ShortestPaths sp = ...; IAtom end = ...; // reconstruct first path int[] path = sp.pathTo(end); // check there is only one path if(sp.nPathsTo(end) == 1){ int[] path = sp.pathTo(end); // reconstruct the path }
 Parameters:
end
 the end vertex to find a path to Returns:
 path from the start to the end vertex
 See Also:

isPrecedingPathTo
public boolean isPrecedingPathTo(int end) Returns whether the first shortest path from the start to a given end vertex which only passed through vertices smaller then start. This is useful for reducing the search space, the idea is used by [Vismara, Philippe. Combinatorics. 1997. 4] in the computation of cycle prototypes. Parameters:
end
 the end vertex Returns:
 whether the path to the end only passed through vertices preceding the start

pathsTo
public int[][] pathsTo(int end) Reconstruct all shortest paths to the provided end vertex. The paths are n (where n isnPathsTo(int)
) inclusive fixed size arrays of vertex indices. When there is no path an empty array is returned. It is considered there to be no path if the end vertex belongs to the same container but is a member of a different fragment, or the vertex is not present in the container at all. Important: for every possible branch the number of possible paths doubles and could be in the order of tens of thousands. Although the chance of finding such a molecule is highly unlikely (C720 fullerene has at maximum 1024 paths). It is safer to check the number of paths (nPathsTo(int)
) before attempting to reconstruct all shortest paths.int threshold = 20; ShortestPaths sp = ...; // reconstruct shortest paths int[][] paths = sp.pathsTo(5); // only reconstruct shortest paths below a threshold if(sp.nPathsTo(5) < threshold){ int[][] path = sp.pathsTo(5); // reconstruct shortest paths }
 Parameters:
end
 the end vertex Returns:
 all shortest paths from the start to the end vertex

pathsTo
Reconstruct all shortest paths to the provided end vertex. The paths are n (where n isnPathsTo(int)
) inclusive fixed size arrays of vertex indices. When there is no path an empty array is returned. It is considered there to be no path if the end vertex belongs to the same container but is a member of a different fragment, or the vertex is not present in the container at all. Important: for every possible branch the number of possible paths doubles and could be in the order of tens of thousands. Although the chance of finding such a molecule is highly unlikely (C720 fullerene has at maximum 1024 paths). It is safer to check the number of paths (nPathsTo(int)
) before attempting to reconstruct all shortest paths.int threshold = 20; ShortestPaths sp = ...; IAtom end = ...; // reconstruct all shortest paths int[][] paths = sp.pathsTo(end); // only reconstruct shortest paths below a threshold if(sp.nPathsTo(end) < threshold){ int[][] path = sp.pathsTo(end); // reconstruct shortest paths }
 Parameters:
end
 the end atom Returns:
 all shortest paths from the start to the end vertex

atomsTo
Reconstruct a shortest path to the provided end vertex. The path is an inclusive fixed size arrayIAtom
s. If there are multiple shortest paths the first shortest path is determined by vertex storage order. When there is no path an empty array is returned. It is considered there to be no path if the end vertex belongs to the same container but is a member of a different fragment, or the vertex is not present in the container at all.ShortestPaths sp = ...; // reconstruct a shortest path IAtom[] path = sp.atomsTo(5); // ensure single shortest path if(sp.nPathsTo(5) == 1){ IAtom[] path = sp.atomsTo(5); // reconstruct shortest path }
 Parameters:
end
 the end vertex to find a path to Returns:
 path from the start to the end atoms as fixed size
array of
IAtom
s  See Also:

atomsTo
Reconstruct a shortest path to the provided end atom. The path is an inclusive fixed size arrayIAtom
s. If there are multiple shortest paths the first shortest path is determined by vertex storage order. When there is no path an empty array is returned. It is considered there to be no path if the end atom belongs to the same container but is a member of a different fragment, or the atom is not present in the container at all.ShortestPaths sp = ...; IAtom end = ...; // reconstruct a shortest path IAtom[] path = sp.atomsTo(end); // ensure single shortest path if(sp.nPathsTo(end) == 1){ IAtom[] path = sp.atomsTo(end); // reconstruct shortest path }
 Parameters:
end
 the end atom to find a path to Returns:
 path from the start to the end atoms as fixed size
array of
IAtom
s.  See Also:

nPathsTo
public int nPathsTo(int end) Access the number of possible paths to the end vertex. When there is no path 0 is returned. It is considered there to be no path if the end vertex belongs to the same container but is a member of a different fragment, or the vertex is not present in the container at all.ShortestPaths sp = ...; sp.nPathsTo(5); // number of paths sp.nPathsTo(1); // returns 0  there are no paths
 Parameters:
end
 the end vertex to which the number of paths will be returned Returns:
 the number of paths to the end vertex

nPathsTo
Access the number of possible paths to the end atom. When there is no path 0 is returned. It is considered there to be no path if the end atom belongs to the same container but is a member of a different fragment, or the atom is not present in the container at all.ShortestPaths sp = ...; IAtom end = ...l sp.nPathsTo(end); // number of paths sp.nPathsTo(null); // returns 0  there are no paths sp.nPathsTo(new Atom("C")); // returns 0  there are no paths
 Parameters:
end
 the end vertex to which the number of paths will be returned Returns:
 the number of paths to the end vertex

distanceTo
public int distanceTo(int end) Access the distance to the provided end vertex. If the two are not connected the distance is returned asInteger.MAX_VALUE
. Formally, there is a path if the distance is less then the number of vertices.
Conveniently the distance is also the index of the last vertex in the path.IAtomContainer container = ...; ShortestPaths sp = ...; // start = 0 int n = container.getAtomCount(); if(sp.distanceTo(5) < n) { // these is a path from 0 to 5 }
IAtomContainer container = ...; ShortestPaths sp = ...; // start = 0 int path = sp.pathTo(5); int start = path[0]; int end = path[sp.distanceTo(5)];
 Parameters:
end
 vertex to measure the distance to Returns:
 distance to this vertex
 See Also:

distanceTo
Access the distance to the provided end atom. If the two are not connected the distance is returned asInteger.MAX_VALUE
. Formally, there is a path if the distance is less then the number of atoms.
Conveniently the distance is also the index of the last vertex in the path.IAtomContainer container = ...; ShortestPaths sp = ...; // start atom IAtom end = ...; int n = container.getAtomCount(); if( sp.distanceTo(end) < n ) { // these is a path from start to end }
IAtomContainer container = ...; ShortestPaths sp = ...; // start atom IAtom end = ...; int atoms = sp.atomsTo(end); // end == atoms[sp.distanceTo(end)];
 Parameters:
end
 atom to measure the distance to Returns:
 distance to the given atom
 See Also:
