Package org.openscience.cdk.graph

Class AllPairsShortestPaths

  • public final class AllPairsShortestPaths
extends Object
    Utility to determine the shortest paths between all pairs of atoms in a molecule. 
     IAtomContainer        benzene = MoleculeFactory.makeBenzene();
 AllPairsShortestPaths apsp    = new AllPairsShortestPaths(benzene);

 for (int i = 0; i < benzene.getAtomCount(); i++) {

     // only to half the comparisons, we can reverse the
     // path[] to get all j to i
     for (int j = i + 1; j < benzene.getAtomCount(); j++) {

         // reconstruct shortest path from i to j
         int[] path = apsp.from(i).pathTo(j);

         // reconstruct all shortest paths from i to j
         int[][] paths = apsp.from(i).pathsTo(j);

         // reconstruct the atoms in the path from i to j
         IAtom[] atoms = apsp.from(i).atomsTo(j);

         // access the number of paths from i to j
         int nPaths = apsp.from(i).nPathsTo(j);

         // access the distance from i to j
         int distance = apsp.from(i).nPathsTo(j);

     }
 }
    Author:
    John May
    See Also:
    ShortestPaths
    Source code:
    main
    Belongs to CDK module:
    core

    • Constructor Detail

      • AllPairsShortestPaths

        public AllPairsShortestPaths​(IAtomContainer container)
        Create a new all shortest paths utility for an IAtomContainer.
        Parameters:
        container - the molecule of which to find the shortest paths

    • Method Detail

      • from

        public ShortestPaths from​(int start)
        Access the shortest paths object for provided start vertex. 
         AllPairsShortestPaths apsp = ...;

 // access explicitly
 ShortestPaths sp = asp.from(0);

 // or chain method calls
 int[] path = asp.from(0).pathTo(5);
        Parameters:
        start - the start vertex of the path
        Returns:
        The shortest paths from the given state vertex
        See Also:
        ShortestPaths

      • from

        public ShortestPaths from​(IAtom start)
        Access the shortest paths object for provided start atom. 
         AllPairsShortestPaths apsp = ...;
 IAtom start, end = ...;

 // access explicitly
 ShortestPaths sp = asp.from(start);

 // or chain the method calls together

 // first path from start to end atom
 int[] path = asp.from(start).pathTo(end);

 // first atom path from start to end atom
 IAtom[] atoms = asp.from(start).atomTo(end);
        Parameters:
        start - the start atom of the path
        Returns:
        The shortest paths from the given state vertex
        See Also:
        ShortestPaths