Package org.openscience.cdk.graph

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:

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