Package org.openscience.cdk.graph

Class ShortestPaths

  • public final class ShortestPaths
extends Object
    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. not-connected) an empty path is always returned. 
    
 IAtomContainer 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];
    If shortest paths from multiple start atoms are required AllPairsShortestPaths will have a small performance advantage. Please use TopologicalMatrix if only the shortest distances between atoms is required.
    Author:
    John May
    See Also:
    AllPairsShortestPaths, TopologicalMatrix
    Source code:
    main
    Belongs to CDK module:
    core

    • Constructor Summary

      Constructors 
      Constructor Description
      ShortestPaths​(IAtomContainer container, IAtom start)
      Create a new shortest paths tool for a single start atom.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      IAtom[] atomsTo​(int end)
      Reconstruct a shortest path to the provided end vertex.
      IAtom[] atomsTo​(IAtom end)
      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 nPathsTo​(IAtom end)
      Access the number of possible paths to the end atom.
      int[][] pathsTo​(int end)
      Reconstruct all shortest paths to the provided end vertex.
      int[][] pathsTo​(IAtom end)
      Reconstruct all shortest paths to the provided end vertex.
      int[] pathTo​(int end)
      Reconstruct a shortest path to the provided end vertex.
      int[] pathTo​(IAtom end)
      Reconstruct a shortest path to the provided end atom.

    • Constructor Detail

      • ShortestPaths

        public ShortestPaths​(IAtomContainer container,
                     IAtom start)
        Create a new shortest paths tool for a single start atom. If shortest paths from multiple start atoms are required AllPairsShortestPaths will have a small performance advantage.
        Parameters:
        container - an atom container to find the paths of
        start - the start atom to which all shortest paths will be computed
        See Also:
        AllPairsShortestPaths

    • Method Detail

      • 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(org.openscience.cdk.interfaces.IAtom), atomsTo(int), atomsTo(org.openscience.cdk.interfaces.IAtom)

      • pathTo

        public int[] pathTo​(IAtom end)
        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:
        atomsTo(org.openscience.cdk.interfaces.IAtom), atomsTo(int), pathTo(int)

      • 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 is 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
 }
        Parameters:
        end - the end vertex
        Returns:
        all shortest paths from the start to the end vertex

      • pathsTo

        public int[][] pathsTo​(IAtom end)
        Reconstruct all shortest paths to the provided end vertex. The paths are n (where n is 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
 }
        Parameters:
        end - the end atom
        Returns:
        all shortest paths from the start to the end vertex

      • atomsTo

        public IAtom[] atomsTo​(int end)
        Reconstruct a shortest path to the provided end vertex. The path is an inclusive fixed size array IAtoms. 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 IAtoms
        See Also:
        atomsTo(int), pathTo(int), pathTo(org.openscience.cdk.interfaces.IAtom)

      • atomsTo

        public IAtom[] atomsTo​(IAtom end)
        Reconstruct a shortest path to the provided end atom. The path is an inclusive fixed size array IAtoms. 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 IAtoms.
        See Also:
        atomsTo(int), pathTo(int), pathTo(org.openscience.cdk.interfaces.IAtom)

      • 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

        public int nPathsTo​(IAtom end)
        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 as 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)];
        Parameters:
        end - vertex to measure the distance to
        Returns:
        distance to this vertex
        See Also:
        distanceTo(org.openscience.cdk.interfaces.IAtom)

      • distanceTo

        public int distanceTo​(IAtom end)
        Access the distance to the provided end atom. If the two are not connected the distance is returned as 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)];
        Parameters:
        end - atom to measure the distance to
        Returns:
        distance to the given atom
        See Also:
        distanceTo(int)