public final class ShortestPaths extends Object
nPathsTo(int)
) and the
distance (distanceTo(int)
) can be accessed before reconstructing all
the paths. When no path is found (i.e. not-connected) 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.AllPairsShortestPaths
,
TopologicalMatrix
Constructor and Description |
---|
ShortestPaths(IAtomContainer container,
IAtom start)
Create a new shortest paths tool for a single start atom.
|
Modifier and Type | Method and Description |
---|---|
IAtom[] |
atomsTo(IAtom end)
Reconstruct a shortest path to the provided end atom.
|
IAtom[] |
atomsTo(int end)
Reconstruct a shortest path to the provided end vertex.
|
int |
distanceTo(IAtom end)
Access the distance to the provided end atom.
|
int |
distanceTo(int end)
Access the distance to the provided end vertex.
|
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(IAtom end)
Access the number of possible paths to the end atom.
|
int |
nPathsTo(int end)
Access the number of possible paths to the end vertex.
|
int[][] |
pathsTo(IAtom end)
Reconstruct all shortest paths to the provided end vertex.
|
int[][] |
pathsTo(int end)
Reconstruct all shortest paths to the provided end vertex.
|
int[] |
pathTo(IAtom end)
Reconstruct a shortest path to the provided end atom.
|
int[] |
pathTo(int end)
Reconstruct a shortest path to the provided end vertex.
|
public ShortestPaths(IAtomContainer container, IAtom start)
AllPairsShortestPaths
will have a small performance advantage.container
- an atom container to find the paths ofstart
- the start atom to which all shortest paths will be
computedAllPairsShortestPaths
public int[] pathTo(int end)
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
}
end
- the end vertex to find a path topathTo(org.openscience.cdk.interfaces.IAtom)
,
atomsTo(int)
,
atomsTo(org.openscience.cdk.interfaces.IAtom)
public int[] pathTo(IAtom end)
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
}
end
- the end vertex to find a path toatomsTo(org.openscience.cdk.interfaces.IAtom)
,
atomsTo(int)
,
pathTo(int)
public boolean isPrecedingPathTo(int end)
end
- the end vertexpublic int[][] pathsTo(int end)
nPathsTo(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
}
end
- the end vertexpublic int[][] pathsTo(IAtom end)
nPathsTo(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
}
end
- the end atompublic IAtom[] atomsTo(int end)
IAtom
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
}
end
- the end vertex to find a path toIAtom
satomsTo(int)
,
pathTo(int)
,
pathTo(org.openscience.cdk.interfaces.IAtom)
public IAtom[] atomsTo(IAtom end)
IAtom
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
}
end
- the end atom to find a path toIAtom
s.atomsTo(int)
,
pathTo(int)
,
pathTo(org.openscience.cdk.interfaces.IAtom)
public int nPathsTo(int end)
ShortestPaths sp = ...;
sp.nPathsTo(5); // number of paths
sp.nPathsTo(-1); // returns 0 - there are no paths
end
- the end vertex to which the number of paths will be
returnedpublic int nPathsTo(IAtom end)
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
end
- the end vertex to which the number of paths will be
returnedpublic int distanceTo(int end)
Integer.MAX_VALUE
.
Formally, there is a path if the distance is less then the number of
vertices.
IAtomContainer container = ...;
ShortestPaths sp = ...; // start = 0
int n = container.getAtomCount();
if(sp.distanceTo(5) < n) {
// these is a path from 0 to 5
}
Conveniently the distance is also the index of the last vertex in the
path.
IAtomContainer container = ...; ShortestPaths sp = ...; // start = 0 int path = sp.pathTo(5); int start = path[0]; int end = path[sp.distanceTo(5)];
end
- vertex to measure the distance todistanceTo(org.openscience.cdk.interfaces.IAtom)
public int distanceTo(IAtom end)
Integer.MAX_VALUE
.
Formally, there is a path if the distance is less then the number of
atoms.
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
}
Conveniently the distance is also the index of the last vertex in the
path.
IAtomContainer container = ...;
ShortestPaths sp = ...; // start atom
IAtom end = ...;
int atoms = sp.atomsTo(end);
// end == atoms[sp.distanceTo(end)];
end
- atom to measure the distance todistanceTo(int)
Copyright © 2021. All rights reserved.