Class AllPairsShortestPaths

java.lang.Object
org.openscience.cdk.graph.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:
Source code:
main
Belongs to CDK module:
core
  • Constructor Details

    • 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 Details

    • 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:
    • 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: